Cost-Optimal and Net-Benefit Planning - A Parameterised Complexity View

1 Introduction

It is very common in planning and search to assign costs to actions (or operators) and ask for a solution which minimises the sum of these. Considering the prevalence and importance of this problem in the literature, surprisingly little attention is paid to motivate and discuss the choice of numeric domain for these costs. The following are only some examples to illustrate the diversity in the literature: Katz and Domshlak [2008] and Helmert et al. [2014] use non-negative reals; B¨ackstr¨om and Jonsson [2013] and Yang et al. [2008] use non-negative integers; Cooper et al. [2011] use positive integers; Coles et al. [2008] specify non-negative costs, but no type; while Thayer et al. [2012] do not specify the costs at all, not even whether negative costs are allowed. Furthermore, only two of these publications give a motivation for the choice: accounting for only a subset of the transitions in the state space [Helmert et al., 2014] and simulating several goal states by zero-cost edges to a single goal state [Yang et al., 2008]. While the choice may be dictated by models of applications in many cases, the publications listed above focus primarily on theoretical investigations or empirical studies of benchmark examples. It may seem as if the choice of domain is often either not considered very important or is so little understood that an arbitrary choice is made.

∗Aghighi is partially supported by the National Graduate School in Computer Science (CUGS), Sweden. B¨ackstr¨om is partially supported by the Swedish Research Council (VR) under grant 6212014-4086.

Real values can be motivated in theoretical studies, since it makes the results general and there is a powerful collection of mathematical results to use. However, specific results for reals are seldom, if ever, used. In implementations and in complexity theory we are restricted to finite representations, so the initial costs are necessarily rational numbers. Furthermore, the mathematical operations used are normally such that irrational numbers cannot arise, even in theory. Hence, we study rational numbers instead of reals.

From a perspective of classical complexity analysis, one might argue that the choice of domain is not important; costoptimal planning is PSPACE-complete regardless of whether we use integers or rational numbers or whether we allow zero cost or only positive values. However, this does not correlate well with practical experience, which often indicates that cost-optimisation does not perform very well. One problem is that zero-cost actions can result in very long plans with very low cost [Richter and Westphal, 2010]. Also big differences in action costs can cause similar problems [Cushing et al., 2010]. Contrasting these findings with the observations on domain choice above indicates that we still have a considerable gap of knowledge regarding cost-optimal planning and search. In order to get a more refined picture of this issue, we apply the tool of parameterised complexity analysis.

Parameterised complexity [Downey and Fellows, 1999] has been previously applied to plan-length optimisation [B¨ackstr¨om et al., 2012; Kronegger et al., 2013], but almost no such results exist for cost-optimal planning. We analyse three different cases that differ in the type of action costs: positive integers, non-negative integers and positive rationals. The first case is W[2]-complete, which means it is of the same complexity as finding a plan of minimum length, while both the other cases are para-NP-hard, a very strong evidence that they are significantly harder than the first one. That is, the choice of numeric domain is very important from an efficiency point of view. Our results correlate well with practical experience and they can, thus, help to explain the problems encountered and to find ways around them. In addition, we analyse a number of restricted cases based on the PUBS restrictions [B¨ackstr¨om and Nebel, 1995] and on restricting the number of preconditions and effects, (cf. Bylander [1994]).

We further consider the related problem of net-benefit planning [van den Briel et al., 2004]. We show that this problem is para-NP-hard even if the action costs and utilities are positive integers, which suggests that it is harder than cost-optimal planning, although both problems are PSPACE-complete under classical analysis. Aghighi and Jonsson [2014] analysed a number of restricted cases of this problem, using classical complexity analysis. We complement their picture by providing corresponding parameterised analyses.

The content of the paper is as follows. Parameterised complexity and planning are introduced in Sections 2 and 3. Section 4 is devoted to parameterised complexity analysis of cost-optimal planning, for different assumptions about the costs as well as for a number of restricted cases. Section 5 similarily analyses the net-benefit planning problem. The paper ends with a discussion of connections with related work and directions for future research.

2 Parameterised Complexity

Parameterised complexity theory allows for more finegrained complexity analyses than traditional complexity theory, and it was invented with the purpose of delivering complexity results that conform better with practical experience.

A parameterised problem is a language L ⊆ Σ∗ × Z0, where Σ is a finite alphabet and Z0 is the non-negative integers. The instances of the problem are pairs on the form 〈I, k〉, where I is a string over Σ∗ and k is the parameter. A parameterised problem is fixed-parameter tractable (fpt) if there exists an algorithm that solves every instance 〈I, k〉 of size n = |I| in time f(k) · nc where f is an arbitrary computable function and c is a constant independent of both n and k. FPT is the class of all fixed-parameter tractable decision problems. In contrast to classical tractability, some exponentiality is allowed, but confined to the parameter only, thus better reflecting reality.

Parameterised complexity offers a completeness theory, similar to the theory of NP-completeness. This theory is based on a hierarchy of parameterised complexity classes

known as the W hierarchy. The W[i] classes are defined by the WEIGHTED SATISFIABILITY PROBLEM for restricted circuits, where W[P] is the case of arbitrary circuits. Hardness for parameterised classes is proven in the usual way, but using fpt reductions instead of ordinary polynomial-time reductions. An fpt reduction from a parameterised language L ⊆ Σ∗ × Z0 to another parameterised language L′ ⊆ Π∗ × Z0 is a mapping R : Σ∗ × Z0 → Π∗ × Z0 such that: (1) 〈I, k〉 ∈ L if and only if 〈I′ , k′ 〉 = R(I, k) ∈ L′ ; (2) there is a computable function f and a constant c such that R can be computed in time f(k) · nc , where n = |I|; and (3) there is a computable function g such that k′ ≤ g(k).

Not much is known about the relationship between the parameterised complexity classes and the standard ones, except that P ⊆ FPT. There is otherwise no simple relationship between classes; for instance, there are NP-complete problems that are W[P]-complete and there are PSPACEcomplete problems that are in FPT. There are also parameterised classes outside the W hierarchy. Of particular interest to us is the class para-NP, which consists of all parameterised problems that can be solved in non-deterministic time f(k) · nc , where f is an arbitrary computable function and c is a constant independent of both n and k. It is known that W[P] ⊆ para-NP, but not whether this inclusion is strict.

The ith slice of a parameterised problem L is defined as Li = {〈I, k〉 ∈ L | k = i}, which is not parameterised.

We will need the following generalisation of Corollary 2.16 in Flum and Grohe [2006] 1 .

Corollary 1. (to Theorem 2.14 in Flum and Grohe [2006]). Any non-trivial 2 parameterised problem L with at least one NP-hard slice is para-NP-hard.

For a detailed account of parameterised complexity, see Downey and Fellows [1999] or Flum and Grohe [2006].

We will not formally define different problems for classical and parameterised analysis. Given an instance 〈I, k〉, a classical analysis measures time as a function t(n) where n = |〈I, k〉| = |I| + log k, while a parameterised analysis uses a multi-variable function t(n, k) where n = |I|.

3 Planning

We use the SAS+ planning framework [B¨ackstr¨om and Nebel, 1995]. Let V = {v1, . . . , vn} be a finite set of variables, with an implicit order v1, . . . , vn, each with a finite domain D(vi). This defines the state space S(V ) = D(v1) × . . . ×D(vn). A member s ∈ S(V ) is called a (total) state and can be viewed as a total function that specifies a value in D(vi) for each vi ∈ V . A partial state may leave the value undefined for some (or all) variables, and is thus a partial function. The value of a defined variable vi in a (total or partial) state s is denoted s[vi]. If s is a partial state, then vars(s) is the set of variables with a defined value in s.

A planning instance P = 〈V,A, I,G〉 has a set of variables V , a set of actions A, a total initial state I and a partial goal state G. Each action a ∈ A has a precondition pre(a) and an effect eff(a), both partial states. Let a ∈ A and s ∈ S(V ). Then a is valid in s if pre(a)[v] = s[v] for all v ∈ vars(pre(a)), and the result of a in s is a state t ∈ S(V ) such that for all v ∈ V , t[v] = eff(a)[v] if v ∈ vars(eff(a)) and t[v] = s[v] otherwise. Let s0, sℓ ∈ S(V ) and let ω = a1, . . . , aℓ be a sequence of actions. Then ω is a plan from s0 to sℓ if either (1) ω = 〈〉 and ℓ = 0 or (2) there are states s1, . . . , sℓ-1 ∈ S(V ) such that for all i (1 ≤ i ≤ ℓ), ai is valid in si-1 and si is the result of ai in si-1. Furthermore,

1 Corollary 2.16 is derived from Theorem 2.14, which has membership restrictions that are not used in the relevant part of the proof. The same generalisation is tacitly used by Kronegger et al. [2013].

2L ⊆ Σ∗ × Z0 is non-trivial if ∅ ̸= {I | 〈I, k〉 ∈ L} ̸= Σ∗ .

ω is a plan (i.e. a solution) for P if it is a plan from I to some state t such that t[v] = G[v] for all v ∈ vars(G).

We will consider combinations of the following four restrictions on instances [B¨ackstr¨om and Nebel, 1995].

P (post-unique): For all v ∈ V and x ∈ D(v), eff(a)[v] = x for at most one a ∈ A. U (unary): For each a ∈ A, |vars(eff(a))| = 1. B (binary): |D(v)| = 2 for all v ∈ V . S (single-valued): For all a, b ∈ A and v ∈ V , if v ∈ vars(pre(a)) ∩ vars(pre(b)) and v ̸∈ vars(eff(a)) ∪ vars(eff(b)) then pre(a)[v] = pre(b)[v].

The class SAS+-B corresponds to STRIPS with negative preconditions. We assume binary domains {0, 1}, where 1 is positive. We use the notation of Bylander [1994], e.g. B21+ denotes the restriction to actions a where pre(a) defines at most 2 variables and eff(a) defines at most one variable that must also be positive. A ∗ denotes an unbounded value.

Finding the minimum length of a plan is a well-studied problem in the literature, and our primary interest in it is to transfer complexity results to other problems. In order to discuss restrictions concisely, we instantiate the problem with some subclass C ⊆ SAS+ of planning instances, e.g. C = SAS+-UB is both unary and binary.

LENGTH-OPTIMAL PLANNING (LOP(C))

Instance: A SAS+ instance P = 〈V, A, I, G〉 in C.

Parameter: A non-negative integer k.

Question: Does P have a plan ω of length |ω| ≤ k?

In cost-optimal planning we additionaly specify a cost c(a) for each action a and ask for the minimum cost for a plan. The cost of a plan ω = a1, . . . , an is c(ω) = ∑ni=1 c(ai). We additionally specify a domain D for the costs.

COST-OPTIMAL PLANNING (COP(C, D))

Instance: A tuple P = 〈V,A, I,G, c〉 such that 〈V,A, I,G〉 is in C and c : A → D is a cost function.

Parameter: A non-negative integer k.

Question: Does P have a plan ω of cost c(ω) ≤ k?

The following result is straightforward, but included for completeness since we are not aware of any explicit result in the literature covering all cases, i.e. Z+, Z0, Q+ and Q0.

Theorem 2. Problem COP(SAS+,Q0) is in PSPACE and problem COP(SAS+, Z+) is PSPACE-hard.

Proof sketch. Cycles in the state space cannot improve the plan cost. Guess a cycle-free plan, one action at a time, and check the cost incrementally. This is in NPSPACE=PSPACE. Hardness by reduction from LOP(SAS+), which is PSPACEcomplete [Bylander, 1994], using unit action cost.

4 Complexity of Cost-optimal Planning

In this section we analyse the parameterised complexity of cost-optimal planning, first for positive integer costs and then for non-negative integer and positive rational costs. The results are summarized in Figure 1.

4.1 Positive Integers

We start with hardness for some restricted SAS+ classes.

Theorem 3. Problem COP(SAS+-R, Z+) is W[1]-hard for R ∈ {UBS, B0 3 , B1 1 } and W[2]-hard for R ∈ {BS, B0 ∗+}.

Proof. LOP(C) fpt reduces trivially to COP(C, Z+) with unit costs. The result follows since LOP(C) is W[1]-complete for R ∈ {UBS, B0 3 , B1 1 } and W[2]-complete for R ∈ {BS, B0 ∗+} [B¨ackstr¨om et al., 2012; B¨ackstr¨om et al., 2013].

Having established these hardness bounds, we turn to membership, first proving that COP(SAS+, Z+) is in W[2].

The following construction maps an instance P with positive integer action costs into an instance P′ without action costs. Each action a in P with cost c(a) is replaced with a chain of actions a1, . . . , ac(a). The lock variable vlock and the uai variables guarantee that these actions must occur in sequence and not be interleaved with any other actions. Hence, the sequence a1, . . . , ac(a) has the same precondition and effect as a, but length c(a) instead of cost c(a). We write a : P c⇒ E to define an action a with precondition P, effect E and cost c, omitting c when the cost is irrelevant. We also write v = x in P (or E) for P [v] = x (or E[v] = x).

Construction 4. Let C be a class of SAS+ instances and let 〈P, k〉 be an instance of COP(C, Z+), where P = 〈V,A, I,G, c〉. Construct a LOP(C) instance 〈P′ , k′ 〉, where k′ = k and P′ = 〈V ′ , A′ , I ′ , G′ 〉 is defined as:

• V ′ = V ∪ {vlock} ∪ {uai | a ∈ A and 1 ≤ i ≤ c(a)}, where D(vlock) = {0, 1} and D(uai ) = {0, 1} for all a ∈ A and 1 ≤ i ≤ c(a).
• For each a ∈ A, if c(a) = 1, then A′ contains the action
• a1 : pre(a), vlock = 0 ⇒ eff(a)

and otherwise A′ contains the actions

• a1 : pre(a), vlock = 0 ⇒ ua1 = 1, vlock = 1,
• ai : uai-1 =1⇒uai-1 =0, uai =1, (1 < i < c(a)),
• ac(a) : uac(a)-1= 1⇒eff(a), uac(a)-1= 0, vlock= 0.
• I ′ [v] = I[v] for all v ∈ V and otherwise I ′ [v] = 0.
• G′ [v] = G[v] for all v ∈ V and otherwise G′ [v] = 0.

We now use this construction to prove that COP is in W[2] if all action costs are positive integers and polynomially bounded in the instance size,

Theorem 5. Let p be an arbitrary polynomial. Then COP(SAS+, Z+) is inW[2] if it is restricted to cost functions c such that for every instance P = 〈V, A, I, G, c〉 it holds that c(a) ≤ p(|P|) for all a ∈ A.

Proof. Let 〈P, k〉 be an instance of COP(SAS+, Z+), where P = 〈V,A, I,G, c〉, and let 〈P′ , k′ 〉, where P′ = 〈V ′ ,A′ , I ′ ,G′ 〉, be the corresponding LOP(SAS+) instance according to Construction 4. Obviously, P has a plan of cost k if and only if P′ has a plan of length k′ = k. This is an fpt reduction from COP(SAS+, Z+) to LOP(SAS+) since k′ = k and we assume that c(a) ≤ p(|P|) for all a ∈ A. It follows that COP(C, Z+) is in W[2] since LOP(SAS+) is in W[2] [B¨ackstr¨om et al., 2012].

-

-

The restriction to polynomial costs allows for a simple proof, but is not necessary. It can be avoided by adapting the model-checking technique used in B¨ackstr¨om et al. [2012].

Membership in W[1] for SAS+-U is open, but all PUBS classes that are not W[1]-hard are fixed-parameter tractable.

Theorem 6. COP(SAS+-P, Z+) is in FPT.

Proof. Modify the fpt algorithm for LOP(SAS+-P) [B¨ackstr¨om et al., 2012, Theorem 5] to check the plan cost, instead of the length, against k. The complexity result still holds since the cost can never be lower than the length in this case.

4.2 Non-negative Integers and Positive Rationals

We now show that COP is considerably harder if we additionally allow actions to have zero cost or positive rational cost. We also need the PLAN SATISFIABILITY (PSAT) problem, which only asks if there is a plan or not, with no parameter.

Theorem 7. Let C be an arbitrary subclass of SAS+. If PSAT(C) is NP-hard, then COP(C, Z0) is para-NP-hard.

Proof. Let P be an arbitrary PSAT(SAS+) instance, where P = 〈V, A, I, G〉. Define a corresponding COP(SAS+, Z0)0 instance 〈P′ , k′ 〉, where k′ = 0, P′ = 〈V,A, I,G, c〉 and c(a) = 0 for all a ∈ A. This is a polynomial-time reduction from PSAT(C) to COP(C, Z0)0 for any subclass C ⊆ SAS+, since it does not alter the instance except for adding action costs. The result thus follows from Corollary 1 when PSAT(C) is NP-hard.

Corollary 8. Problem COP(SAS+-R, Z0) is para-NP-hard for R∈{UB, BS, B1 1+, B2+ 2 }.

Proof. Follows from Thm. 7 since PSAT(SAS+-R) is NPhard for R ∈ {UB, BS} [B¨ackstr¨om and Nebel, 1995] and for R ∈ {B1 1+, B2+ 2 } [Bylander, 1994].

Theorem 9. Let C be an arbitrary subclass of SAS+. If LOP(C) is NP-hard, then COP(C,Q+) is para-NP-hard.

Proof. Let 〈P, k〉 be an arbitrary LOP(SAS+) instance, where P = 〈V,A, I,G〉. Define a corresponding COP(SAS+,Q+)1 instance 〈P′ , k′ 〉, where k′ = 1, P′ = 〈V,A, I,G, c〉 and c(a) = 1/k for all a ∈ A. This is a polynomial-time reduction from LOP(C) to COP(C,Q+)1

for any subclass C ⊆ SAS+, since it does not alter the instance except for adding action costs. The result thus follows from Corollary 1 when LOP(C) is NP-hard.

Corollary 10. ProblemCOP(SAS+-R,Q+) is para-NP-hard for R∈{PUB, PBS, UBS, B0 2 , B0 3+, B1+ 1+ }.

Proof. Follows from Thm. 9 since LOP(SAS+-R) is NPhard for R ∈ {PUB, PBS,UBS} [B¨ackstr¨om and Nebel, 1995] and for R ∈ {B0 2 , B0 3+, B1+ 1+ } [Bylander, 1994].

The following observation explains why we cannot escape the difficulty by scaling positive rationals to positive integers.

Observation 11. A COP(SAS+, Q+) instance can be polynomially reduced to a COP(SAS+, Z+) instance by multiplying all costs and the parameter with a suitable value α. This is, however, not an fpt reduction since α will typically not depend on the parameter (only), which contradicts condition (3) for fpt reductions.

Such reductions can be fpt reductions if we add further constraints, eg. by choosing α as the lowest common denominator of the costs and additionally require that also α is bounded by k. More properly, we could use one or more additional parameters to bound the costs in various ways, but that is out of the scope of this paper.

We do not prove any corresponding membership results, and it is not obvious that COP(SAS+, Z0) and COP(SAS+,Q+) are even in para-NP, since the plan length may be exponential in the number of variables. Some cases remain open for non-negative integers, but the SAS+-PUS case is easy even for non-negative rationals.

Theorem 12. Problem COP(SAS+-PUS,Q0) is in P.

Proof sketch. A length-optimal plan can be found in polynomial time, using a determnistic fixpoint algorithm [B¨ackstr¨om, 1992]. This plan is the unique subset-minimal plan and thus also cost optimal.

5 Complexity of Net-benefit Planning

The net-benefit problem is a so called oversubscription problem, where we do not expect to satisfy all of the goal. In addition to action costs, each goal variable v has a utility value U(v). Let s be a state. The utility U(v, s) in s of a variable v ∈ vars(G) is U(v) if s[v] = G[v], and otherwise U(v, s) = 0. The utility of s is U(s) = ∑v∈vars(G) U(v, s).

If ω is a plan from I to s, then the difference U(s) - c(ω) is called the net benefit of ω. The objective of the net-benefit problem is to find the maximal net benefit over all plans to any state. The functions c and U are assumed polynomial-time.

NET-BENEFIT PLANNING (NBP(C, D))

Instance: A tuple P = 〈V,A, I,G, c,U〉 where

〈V,A, I,G〉 is in C, c : A → D is a cost func-

tion and U : vars(G) → D is a utility function.

Parameter: A non-negative integer k.

Question: Is there a state s ∈ S(V ) and a plan ω

from I to s such that U(s) - c(ω) ≥ k?

van den Briel et al. [2004] show that net-benefit planning is PSPACE-complete for non-negative costs and utilities. They do not specify if they consider integer or rational values, but this should not matter for PSPACE-completeness. Keyder and Geffner [2009] as well as Aghighi and Jonsson [2014] present transformations from NBP to planning. However, neither of these is an fpt reduction so the upper bounds for planning in the previous section do not automatically carry over to NBP.

We prove in this section that the net benefit problem is para-NP-hard even if the action costs and utilities are restricted to positive integers. That is, in contrast to costoptimal planning, it is not obviously simpler to plan with positive integers than with non-negative integers or positive rationals. This holds also for very restricted classes.

Construction 13. Let 〈P, k〉 be a LOP(SAS+) instance, where P = 〈V,A, I,G〉. Without losing generality, assume that vars(G) = {v1, . . . , vm}. Define a corresponding NBP(SAS+, Z+)1 instance 〈P′ , k′ 〉, where k′ = 1 and P′ = 〈V ′ , A′ , I ′ , G′ , c, U〉 is defined as:

• V ′ = V ∪ {w, u1, . . . , um}, where D(w) = D(u1) = · · · = D(um) = {0, 1}.
• A′ = {a′ | a ∈ A} ∪ {bw, b1, . . . , bm}, where
• a′ : pre(a),w = 0 m⇒ eff(a), for all a ∈ A,
• bw : w = 0 1⇒w = 1,
• b1 : v1 = G[v1],w = 1 k⇒ u1 = 1,
• bi : vi =G[vi], ui-1 = 1 k⇒ui = 1, (2 ≤ i ≤m).
• I ′ [v] = I[v] for all v ∈ V and otherwise I ′ [v] = 0.
• G′ [um] = 1 and G′ is otherwise undefined.
• U(um) = 2km+ 2.

Theorem 14. Problems NBP(SAS+-PUB, Z+) and NBP(SAS+-B2 1+, Z+) are para-NP-hard.

Proof. Construction 13 maps an instance 〈P, k〉 of LOP(SAS+) to an instance 〈P′ , k′ 〉 of NBP(SAS+, Z+)1. Suppose P has a plan ω = a1, . . . , ak of length k. Then ω′ = a′1 , . . . , a′k , bw, b1, . . . , bm is a plan for P′ , where c(ω′ ) = km + 1 + mk = 2km + 1 and U(ω′ ) = 2km + 2, i.e. the net benefit is 1 = k′ . To the contrary, suppose P′ has a plan ω′ with net benefit of k′ = 1, or more, to some state s. This is only possible if s[um] = 1, which requires the actions β = bw, b1, . . . , bm, in that order. Hence, ω′ must have a prefix α = a′1 , . . . , a′ℓ that is a plan from I to some state s′ such that β is a plan from s′ to s and s′ [v] = G[v]

for all v ∈ vars(G). This implies that the action sequence a1, . . . , aℓ that corresponds to α is a plan for P. Furthermore, c(ω′ ) = ℓm+1+mk = (ℓ+k)m+1 and U(ω′ ) = 2km+2, so ω′ can have a net benefit of 1 or more only if ℓ ≤ k. We conclude that P has a plan of length k, or less, if and only if P′ has a plan with net benefit k′ ≥ 1.

This construction is a polynomial-time reduction from LOP(SAS+) to NBP(SAS+, Z+)1. Since SAS+-PUB is closed under this reduction and it adds only one precondition, the result follows from Corollary 1 since both LOP(SAS+-PUB) is NP-hard [B¨ackstr¨om and Nebel, 1995] and LOP(SAS+-B1 1+) is NP-hard [Bylander, 1994].

Theorem 15. NBP(SAS+-PBS, Z+) is para-NP-hard.

Proof sketch. Analogous to the proof of Theorem 14 but modified as follows. Replace each variable vi with two variables va i and vb i . These are always set simultaneously to the same value, which is possible since the actions need not be unary. We can now test the va i variables in the preconditions of the a′ actions and the vb i variables in the preconditions of the bj actions. We also replace variable w with two variables, wf and wt , which always have opposite values, i.e. w = 0 if wf = 1 and w = 1 if wt = 1. This new instance satisfies restriction S but not restriction U, and is otherwise equivalent to the instance in Construction 13.

For SAS+-UBS we reduce from the MSC problem, which is NP-complete. [Garey and Johnson, 1979, Problem SP5].

MINIMUM SET COVER (MSC)

Instance: A set S and a set C of subsets of S.

Parameter: A positive integer k.

Question: Does S have a cover of size k, i.e. a

subset C ′ ⊆ C such that ∪c∈C′ = S and |C′ | = k?

Theorem 16. NBP(SAS+-UBS, Z+) is para-NP-hard.

Proof. We first define a reduction from MINIMUM SET COVER (MSC) to NBP(SAS+-UBS, Z+)1. Let 〈I, k〉 be an MSC instance where I = 〈S,C〉, S = {x1, . . . , xn} and C = {c1, . . . , cm}. Define the corresponding instance 〈P, k′ 〉 of NBP(SAS+-UBS, Z+)1, where k′ = 1 and P = 〈V, A, I, G, c, U〉 is defined as follows:

• V = {xi, vi | xi ∈ S} ∪ C, all with domain {0, 1}.
• A contains the following actions:
• eni : ∅ n⇒ ci = 1, for all ci ∈ C,

• I[v] = 0 for all v ∈ V .
• G[vn] = 1 and G is otherwise undefined.
• U(vn) = 3kn+1.

Suppose I has a cover of size k. Then P has a plan ω with k en actions, n set actions and all n vfy actions, i.e. c(ω) = 3kn, so the net benefit is 1 = k′ . Instead suppose P has a plan with net benefit k′ ≥ 1. It must contain n set actions and the n vfy actions, with total cost 2kn. The plan cost is at most 3kn so there are at most k en actions. Hence, I has a cover of size k. This is a polynomial-time reduction from MSC to NBP(SAS+-UBS, Z+)1 since P ∈ SAS+- UBS. Hence, NBP(SAS+-UBS, Z+)1 is NP-hard since MSC is NP-complete. It follows fromCorollary 1 that NBP(SAS+- UBS, Z+) is para-NP-hard.

For the final cases we reduce from INDEPENDENT SET, which is W[1]-complete [Downey and Fellows, 1999].

INDEPENDENT SET (IS)

Instance: A graph G = 〈V, E〉.

Parameter: A positive integer k.

Question: Is there a subset V ′ ⊆ V such that

{u, v} ̸∈ E for all u, v ∈ V ′ and |V ′ | = k?

Theorem 17. NBP(SAS+-PUBS, Z+) is W[1]-hard.

Proof. Proof by reduction from INDEPENDENT SET (IS). Let 〈G, k〉 be an instance of IS, where G = 〈V,E〉. Construct an instance 〈P, k′ 〉 of NBP(SAS+, Z+), where k′ = k and P = 〈V ′ , A, I, G, c, U〉 is defined as follows:

• V ′ = V , where D(v) = {0, 1} for all v ∈ V ′ .
• For each v ∈ V , A contains the action
• av : {u = 0 | {u, v} ∈ E} 1⇒ v = 1.
• For all v ∈ V , I[v] = 0, G[v] = 1 and U(v) = 2.

Obviouly, G has an independent set of size k if and only if P has a plan with net benefit k′ = k. P is in SAS+-PUBS, so this is an fpt reduction from IS to NBP(SAS+-PUBS, Z+). The result follows since IS is W[1]-complete.

The NBP results coincide with COP(C,Q+) in Figure 1, except that SAS+-PUBS and SAS+-PUS are W[1]-hard.

6 Discussion

A somewhat similar, yet different, theoretical analysis was done by Helmert [2002], who studied the classical complexity of planning for different cases of using numerical variables and arithmetic actions, but without action costs. Practical approaches to combining numerical variables and action costs exist, though, (cf. Ivankovic et al. [2014]).

Analyses of different cost domains are usually based on practical experience, e.g. Richter and Westphal [2010] note that their planner LAMA does not perform well with costoptimising heuristics. Indeed, in the International planning comeptition (IPC) 2008, none of the cost-optimising planners performed as well as the baseline planner, which ignored costs. It is not an isolated problem that cost-optimising planning seems not to deliver as expected [Cushing et al., 2010]. One reason is zero-cost actions. If the cheapest plans are very long, with many zero-cost actions, then a cost-optimising planner might time out, while a length-optimising planner may find a good enough plan. This correlates very well with our theoretical findings. A similar case arises for big spans in action costs, resulting in long and cheap plans with many cheap actions, called the ε-cost trap by Cushing et al. [2010]. Their argument scales the costs to the interval [0,1]. Our results raise the question whether this seemingly harmless scaling might, in fact, contribute to the problem.

Cooper et al. [2011] may seem to avoid these problems, since they only allow positive integer costs. However, they transform the instance into a CSP instance and add virtual zero-cost actions. This raises the question if the favourable properties of positive integers are lost or not, and how to generally do such transformations? For instance, is it safe to simulate multiple goal states (cf. [Yang et al., 2008])?

Our results also suggest an obvious way to improve efficiency. Non-negative integers can be mapped to positive integers by a linear transformation c′ (a) = λ · c(a) + b, for some positive integer constants λ and b. We get

This moves the problem from being para-NP-hard to being W[2]-complete, at the expense of overestimating the optimal solutions. This mapping enforces a balance between optimising the cost and the length, a balance which can be tuned by the constants λ and b. However, this is already used in practice to improve efficiency, eg. LAMA uses a heuristic that puts equal weight to the length and the cost of the plan [Richter and Westphal, 2010]. This is yet another correlation between our theoretical results and practical experience.

Other cost-based heuristics also depend on our results. For instance, Corollary 10 suggests that the h+ heuristic [Hoffmann, 2005] is very difficult to compute, unless restricted to positive integers; it is usually approximated in practice since it is NP-complete even for unit cost. An interesting example is Betz and Helmert [2009], who allow non-negative integer costs and prove that the h+ heurstic cannot be approximated within a constant. The proof, however, uses a technique similar to our Construction 4 to avoid using zero-cost actions, even though it would have been much simpler with such actions. In retrospect, this was a good decision since our results indicate that their result is stronger without zero costs.

In this paper, we analysed classes based on the PUBS restrictions and the number of preconditions and effects. Another way is to restrict the structure of the causal graphs and/or the domain-transition graphs (DTGs). There are numerous classical complexity results for cost-based planning under such restrictions (cf. Katz and Domshlak [2008]). Parameterised results are scarce, though. One exception is B¨ackstr¨om [2014] who shows that COP(C, Q0) is in FPT for acyclic DTGs, using a combination of parameters on the causal graph and the DTGs.

One reason why COP(SAS+, Z+) is easier than NBP(SAS+, Z+) is most likely that the parameter implicitly bounds also the plan length in the first case, but not in the second case, where the parameter only bounds the difference between the utility and the cost of a plan. One may consider adding further parameters, for instance, the plan length. This is similar to a common variant of NBP which assigns a cost budget B and asks for a plan with maximum utility under the constraint that the plan cost does not exceed B [Mirkis and Domshlak, 2013]. This problem can be viewed as a parameterised problem with two parameters, the budget B and the desidered utility k, which could be easier.