# oversubscription_planning_complexity_and_compilability__e952e651.pdf

Oversubscription Planning: Complexity and Compilability

Meysam Aghighi and Peter Jonsson Department of Computer and Information Science Link oping University Link oping, Sweden {meysam.aghighi, peter.jonsson} at liu.se

Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder & Geffner.

1 Introduction

Classical propositional planning is the problem of finding a sequence of operators that achieves a set of goals from a given initial state. An important feature of this problem is that a solution plan must achieve all goals simultaneously. Unfortunately, this is not possible in many realworld problems. For instance, Smith (2004) notes that many NASA planning problems have a large number of possible goals and the planning system has to find a feasible subset of the goals. This kind of planning is known as oversubscription planning. Ordinary planning systems cannot handle oversubscription planning and, in response to this, several custom-made planners and heuristics have been suggested, cf. (Benton, Do, and Kambhampati 2009; Mirkis and Domshlak 2013; van den Briel et al. 2004). Compared to classical planning, it is fair to say that the algorithmics of oversubscription planning is not very wellunderstood and the number of available planners is quite limited. It is also fair to say that the computational complexity of oversubscription planning is not very well-understood either: besides the fact that oversubscription planning is PSPACE-complete (van den Briel et al. 2004), very little is known. The aim of this paper is two-fold:

1. to study the computational complexity of oversubscription planning under various restrictions, and

2. to present a new way of compiling oversubscription planning into classical planning.

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

We study two different problems: the partial satisfaction problem (PSP) where the number of achieved goals is to be maximized, and the net benefit problem (NBP) where the total weight of the achieved goals minus the cost of the plan is to be maximized. These problems are analyzed in Sections 3 and 4, respectively, and the results are summarized in Section 5. Our complexity analysis considers two types of restrictions: syntactically restricted preand postconditions (Bylander 1994) and the P,U,B,S restrictions (B ackstr om and Klein 1991). We concentrate on these restrictions since they (or slight variations of them) are quite popular when studying different aspects of planning complexity, cf. (B ackstr om et al. 2012; Gim enez and Jonsson 2012; Katz and Domshlak 2008). A small number of cases are left open in both cases and this reflects that we do not have a full understanding of the complexity of the plan existence problem (PE) under neither Bylander s nor the P,U,B,S restrictions. Despite this, there are several observations to be made. One important observation is that, in many cases, oversubscription planning is not substantially harder than classical planning. For instance, if the PE problem for some set of instances X (under mild additional assumptions) is NP-complete, then PSP for X is NP-complete, too. Another observation is that (in the cases where we can exactly pinpoint the complexity), PSP and NBP have the same complexity. This is, of course, not always the case and we give an example of instances that strongly separates the two problems. However, our results indicate that PSP, NBP, and classical planning are more closely related than one may initially suspect. We demonstrate this close relationship in a different way in Section 6. We present a polynomial-time reduction from the decision version of NBP to PE such that the number of variables of the resulting instance is slowly growing in the size of the original instance or, put differently, the number of nodes in the corresponding search space increases only moderately. Such a reduction is interesting since algorithms for PE can be used for solving NBP problems with limited slowdown. One should additionally note that PE, cost-optimal planning, and PSP can be trivially reduced to NBP. Thus, these four problems are tightly connected, and algorithms for PE, i.e. ordinary classical planners, may be a viable alternative for performing both oversubscription planning and cost-optimal planning. This result is inspired by Keyder &

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

Geffner (2009) who have presented a method for compiling the optimization version of NBP into cost-optimal planning.

2 Planning Framework We use the SAS+ planning framework (B ackstr om and Nebel 1995) as our basic formalism. A SAS+ planning instance is a tuple Π = (V, A, I, G) where V = {v1, . . . , vn} is the set of variables over a finite domain D. We add a value u to D (where u stands for undefined) resulting in the set D+. Dn is the set of total states and Dn + is the set of partial states. The value of a variable v in a state s Dn + is denoted as s[v], and we let s = |{v V | s[v] = u}|. I Dn is the initial state and G Dn + is the goal state. A is the set of actions where every action a A has a precondition pre(a) Dn + and a postcondition post(a) Dn +. For two states s1, s2, we write s1 s2 if and only if for all v V , either s1[v] = u or s1[v] = s2[v]. An action a is applicable in a state s Dn if and only if pre(a) s. The result of a in s, if a be applicable in s, is a state t Dn such that for all v V , t[v] = s[v] if post(a)[v] = u, otherwise t[v] = post(a)[v]. We say action a affects variable v in state s, if s[v] = t[v] where t is the result of a in s. Given two states I Dn and G Dn +, a sequence of actions ω = (a1, . . . , am) is called a plan from I to G if and only if there exists a sequence of total states (s1, . . . , sm 1) such that s1 is the result of a1 in I, si is the result of ai in si 1 for all 2 i m 1, and G s G where s G is the result of am in sm 1. Let Θ be an arbitrary set of SAS+ instances. The SAS+ plan existence problem PE(Θ) has the following definition: INSTANCE: A SAS+ instance Π = (V, A, I, G) Θ. QUESTION: Does Π have a solution, i.e. a plan from I to G? We will also consider the bounded cost plan existence problem (BCPE(Θ)): INSTANCE: A tuple Π = (V, A, I, G, c, K) where (V, A, I, G) Θ, c is a function assigning a non-negative integer weight to each a A, and K is an integer. QUESTION: Does Π have a solution (a1, . . . , an) such that Pn i=1 c(ai) K? For historical reasons (but also notational convenience), we will sometimes use a different notation for restricted SAS+ instances. Consider the following restrictions (B ackstr om and Klein 1991) on instances (V, A, I, G): P: (Post-unique) for every v V and every d D, there is at most one a A such that post(a)[v] = d. U: (Unary) for every a A, post(a) = 1. B: (Binary) |D| = 2. S: (Single-valued) for every v V and every a, b A, if pre(a)[v] = u, pre(b)[v] = u and post(a)[v] = post(b)[v] = u, then pre(a)[v] = pre(b)[v]. We write PE-R to denote the PE problem restricted to instances satisfying the restrictions in R, i.e. PE-PU means PE(Θ) where Θ contains all instances satisfying restrictions P and U. We also study another type of restrictions (introduced by Bylander (1994)) which is based on restricting the sign and number of preconditions and postconditions of actions (the sign restriction is only discussed when we already

have restriction B). For example, by SAS+-B1 2+, we mean PE for instances having |D| = 2 and allowing at most one precondition and two positive postconditions per action. When dealing with two-valued domains, we always assume that D = {0, 1} and we use a simplified way of defining actions. We write x to denote that variable x has (or is assigned) value 0. Then we may simply write x, y z when referring to the action having preconditions x = 1, y = 0 and postcondition z = 1. If an action has no preconditions, then this is indicated with the symbol . Finally, we let Y = { y | y Y }.

3 The Partial Satisfaction Problem Let Θ denote a set of SAS+ instances. The partial satisfaction problem PSP(Θ) has the following definition: INSTANCE: A tuple (V, A, I, G, K) where (V, A, I, G) Θ and K is a positive integer. QUESTION: Is there a state G G such that G K and (V, A, I, G ) has a solution? We define the PSP problem as a decision problem which allow us to simplify the forthcoming proofs. Viewing it as an optimization problem instead does not affect the complexity substantially: a decision problem in P will have a corresponding optimization problem in FP (the functional analogue of P), an NP-complete decision problem will have an optimization problem in FPNP (by using binary search), and a PSPACE-complete decision problem will have an optimization problem in FPSPACE. Furthermore, we use integer values instead of rational values. Rational values can easily be replaced by integers via multiplication with suitable factors, and this reformulation leads to an equivalent instance whose size is only marginally larger. These observations also apply to the NET BENEFIT problems that we will introduce later on. Note that PE(Θ) can be viewed as an instance of PSP(Θ) (simply by setting K = G ) and recall that PSP(Θ) is in PSPACE (van den Briel et al. 2004)). We say that Θ is closed under goal substitution if for arbitrary (V, A, I, G) Θ, all instances (V, A, I, G ) such that G D|V | + are members of Θ. Clearly, the sets of instances satisfying the P,U,B,S and/or Bylander s restrictions are closed under goal substitution. Lemma 1. Let Θ be a set of SAS+ instances that is closed under goal substitution. If PE(Θ) NP, then PSP(Θ) NP.

Proof. Let Π = (V, A, I, G, K) be an arbitrary instance of PSP(Θ). Nondeterministically guess a state G G such that G K. We know that (V, A, I, G ) is an instance of PE(Θ), too. Hence, we can nondeterministically guess a polynomially bounded certificate X showing that (V, A, I, G ) is solvable. It follows that (X, G ) is a polynomial-time verifiable certificate for Π .

Thus, there is a close connection between PE(Θ) and PSP(Θ): if Θ is closed under goal substitution and PE(Θ) is NPor PSPACE-complete, then PSP(Θ) is NPor PSPACEcomplete, respectively. We can now concentrate on instance sets Θ such that PE(Θ) is solvable in polynomial time.

Theorem 1. PSP-B0 2+ and PSP-B1+ 1+ are NP-hard.

Proof. We begin with PSP-B0 2+. The proof is by a polynomial-time reduction from the NP-complete problem VERTEX COVER, (Garey and Johnson 1979, GT1): INSTANCE: Graph G = (V, E) and integer K |V |. QUESTION: Is there a vertex cover of size K or less for G, i.e., a subset V V with |V | K such that for each edge {u, v} E at least one of u and v belongs to V ? Assume that we have an instance (V, E, K) of VERTEX COVER where V = {v1, . . . , vn}, E = {e1, . . . , em} V2, and 0 K |V|. Define a PSP-B0 2+ instance Π = (V, A, I, G, K ) as follows: V = {v1, . . . , vn} {el j|1 j m, 0 l 1}, I = (0, . . . , 0), K = 2m + n K, and G[vi] = 0 for every 1 i n. Furthermore, for every 0 l 1 and every 1 j m such that ej = (u, w) E, let G[el j] = 1 and let A contain the actions al j : el j, u and bl j : el j, w. Assume Π has a solution ω and, additionally, assume that ω achieves the highest possible number of goals. Let t and s be the number of vi and el j variables that are equal to 1, respectively, in the state s G resulting from applying ω to I. We first show that s G[el j] = 1 for all i, j and, consequently, that s = 2m. Assume to the contrary that s G[el j] = 0 for some l, j. If s G[e1 l j ] = 1, then we can set el i to 1, too, by using either the action al j or bl j. Note that this can be done without assigning the value 1 to any additional vi variables. This new plan achieves a strictly higher number of goals which contradicts the choice of ω. If s G[e0 j] = s G[e1 j] = 0, then we can set both of them to 1 by using actions a0 j and a1 j . This gives us two new satisfied goals and, possibly, one less vi variable satisfying its goal. All in all, this new plan achieves a strictly higher number of goals which once again contradicts the choice of ω. Hence, all el j variables can be assumed to have value 1 and s = 2m. Finally, note that n t is the number of vi variables that are given the value 0 and, thus, contribute to the number of satisfied goals. It follows that s + n t K 2m+n t 2m+n K t K. Consequently, (V, E, K) has a solution. If (V, E, K) has a solution V V, then let A = {a1, . . . , ap} contain the actions a A satisfing post(a)[v ] = u for some v V . Let ω = (a1, . . . , ap) and note that ω is applicable in I. Furthermore, it will achieve at least 2m + n K goals. The proof for PSP-B1+ 1+ is virtually identical: the only major difference is that we replace actions of the type al j : el j, u with the two actions u and u el j, and we do an analogous replacement for bl j actions.

Theorem 2. PSP-PUBS+ is NP-hard.

Proof. Proof by reduction from the NP-complete problem INDEPENDENT SET, (Garey and Johnson 1979, GT20): INSTANCE: Graph G = (V, E) and integer K |V |. QUESTION: Does G contain an independent set of size K or more? i.e., a subset V V such that |V | K and such that no two vertices in V are joined by an edge in E.

Assume that (V, E, K) is an instance of INDEPENDENT SET where V = {v1, . . . , vn}. We define an instance of PSPPUBS+ Π = (V, A, I, G, K) as follows: V = {v1, . . . , vn}, A = {a1, . . . , an}, I = (0, . . . , 0), G = (1, . . . , 1), and for every vi V we define ai : vi1, . . . , vit vi where vi1, . . . , vit are the neighbours of vi. It is straightforward to verify that this instance is an instance of PSP-PUBS+. Let {vi1, . . . , vip} V be a solution to (V, E, K). We immediately see that (ai1, . . . , aip) is a solution to Π; merely note that once a vertex vi has been selected (by inserting ai into the plan), all of its neighbours are blocked from further consideration by the choice of preconditions. Similarly, if Π has a solution (ai1, . . . , aip), then {vi1, . . . , vip} is a solution to (V, E, K).

4 The Net Benefit Problem Given a goal state G Dn + and a utility vector U Nn 0 (where N0 denotes the set of non-negative integers), we let m G,U(S) = P{U[i] | S[i] = G[i] = u}, i.e. m G,U(S) denotes the total utility of a state S given a goal state G and the utilities of the components of G. Let Θ denote a set of SAS+ instances. The net benefit problem NBP(Θ) has the following definition: INSTANCE: A tuple (V, A, I, G, c, U, K) where (V, A, I, G) Θ, c is a function from A to N0, U Nn 0, and K is a positive integer. QUESTION: Is there a plan p = (a1, . . . , at) starting from I and leading to a state S such that m G,U(S) Pt i=1 c(ai) K?

The value m G,U(S) Pt i=1 c(ai) is called the net benefit of the plan p. Note that NBP always has a solution with net benefit 0: the empty plan. PSP(Θ) is trivially polynomialtime reducible to NBP(Θ) by letting the action cost function c always return 0 and choosing U = {1}n. We next prove that there is a connection between BCPE and NBP that is analogous to the connection between PE and PSP established in Lemma 1.

Lemma 2. Let Θ be a set of SAS+ instances that is closed under goal substitution. If BCPE(Θ) NP, then NBP(Θ) NP.

Proof. Let Π = (V, A, I, G, c, U, K) be an arbitrary instance of NBP(Θ). Nondeterministically guess (1) two numbers υ, γ N0 such that υ γ K, (2) a state S such that m G,U(S) υ, and (3) a certificate X showing that there exists a plan ω = (a1, . . . , an) for (V, A, I, S) with γ Pn i=1 c(ai). X exists for some guess of S and can be verified in polynomial time since BCPE(Θ) is in NP. Hence, (υ, γ, S, X) exists if and only if Π has a solution, and the certificate (υ, γ, S, X) can be verified in polynomial time.

We are now ready to prove the necessary complexity results for NBP. We begin with a tractability result.

Theorem 3. NBP0 1 is in P.

Proof. Let Π = (V, A, I, G, c, U, K) be an arbitrary instance of NBP0 1. Let A contain those actions that achieves

some component of the goal G, and if there are multiple actions for the same component, then pick one action with the lowest cost according to function c. Finally, let {a1, . . . , an} denote the actions a A satisfying u c(a) > 0 where u is the utility of the goal achieved by a. Let S be the state resulting from applying (a1, . . . , an) to I. It is clear that Π has a solution if and only if m G,U(S) Pn i=1 c(ai) K.

Next, we prove that certain NBP problems are members of NP by showing that the corresponding BCPE problems are in NP and using Lemma 2. The complexity of finding shortest solutions for these problems is well-studied (B ackstr om and Nebel 1995; Bylander 1994) but we need results for arbitrarily weighted actions. Given a solvable instance Π = (V, A, I, G, K) of BCPE, let S(Π) contain the solutions to Π with lowest possible cost and let S (Π) contain the members of S(Π) having minimum length.

Theorem 4. NBP0 is in NP.

Proof. We show that BCPE0 is in NP and use Lemma 2. Let Π = (V, A, I, G, c, K) be an arbitrary solvable instance of BCPE0 and arbitrarily choose ω S (Π). We claim that every action in ω occurs at most once and, consequently, that |ω| |A| and BCPE0 is NP since we can simply list the actions in the plan. Assume to the contrary that there is an action a that occurs in ω more than once. Construct a new plan ω by deleting all occurrences of a except the last one. Clearly, ω is still a plan from I to G: the actions in A have no preconditions so the removal of a will not affect the applicability of other actions. If c(a) > 0, then the total cost of ω is strictly lower than the total cost of ω which leads to a contradiction. If c(a) = 0, then ω and ω have the same cost but |ω | < |ω| which leads to a contradiction, too.

Theorem 5. NBP-B+ is in NP.

Proof. We show that BCPE-B+ is in NP and use Lemma 2. Let Π = (V, A, I, G, c, K) be an arbitrary solvable instance of BCPE-B+ and arbitrarily choose ω S (Π). Each action in ω changes at least one variable from 0 to 1 and no action changes it back. Hence, |ω| |V | and we are done.

Theorem 6. NBP-US and NBP-B+ 1 are in NP.

Proof. We show that NBP-US is in NP; this immediately implies that NBP-B+ 1 is in NP, too. By Lemma 2, it is sufficient to prove that BCPE-US is in NP. Let Π = (V, A, I, G, c, K) be an arbitrary solvable instance of BCPE-US and arbitrarily choose ω = (a1, . . . , at) S (Π). We claim that every action appears at most twice in ω and that |ω| 2|A|. For every v V , let ωv = (a1, . . . , ak) denote the subsequence of ω containing those actions changing variable v, and let Xv = (x0, x1, x2, . . . , xk) be defined such that x0 = I[v] and pre(ai)[v] = xi 1, post(ai)[v] = xi for 1 i k. Since Π satisfies restriction S, we know that for every v V and every a, b A, if pre(a)[v] = u, pre(b)[v] = u and post(a)[v] = post(b)[v] = u, then pre(a)[v] = pre(b)[v]. Let yv denote this unique prevail value for v if it exists and let yv = u otherwise. Arbitrarily choose v V and consider the following three cases:

None of the values in Xv equals yv. We claim that no action appears more than one time in ωv. Assume to the contrary that for some i < j, the action ai is the same as action aj. Then, the subsequence (ai, ai+1, . . . , aj 1) produces v values that are not needed in the precondition of any other actions or the goal. Recall that these actions only affect variable v (due to restriction U) so we can simply remove them from ωv. This results in a plan with either lower cost or shorter length than ω which leads to a contradiction. At least two of the values in Xv equal yv. If xi = xj = yv for some i < j, then we can delete actions (ai+1, . . . , aj 1, aj) from ωv the reason behind this is similar to the previous case. Hence, this cannot occur. Exactly one value in Xv equals yv. Assume that xi = yv and divide ωv into ω1 v = (a1, . . . , ai 1) and ω2 v = (ai+1, . . . , ak). In each part, every action can appear at most once since, otherwise, the actions between the two occurrences can be deleted (once again in a fashion similar to the first and second cases) and this results in a cheaper and/or shorter plan. This leads to a contradiction so every action appears at most two times in ωv. By restriction U, every action appears in at most one of the ωv sequences which implies, by the three cases above, that each action in A appears at most two times in ω.

5 Summary of Complexity Results

We will now summarize the complexity results for PSP and NBP. To do so, we need a few more hardness results.

Theorem 7. (B ackstr om and Nebel 1995; Bylander 1994) PE-B1+ , PE-B1, PE-B2+ 2 , PE-UB, and PE-BS are PSPACEcomplete problems.

Bylander (1994) does not explicitly state that PE-B1+ is PSPACE-complete but it is a direct consequence of his PSPACE-completeness proof for PE-B1. The complexity results for PSP and NBP under Bylander s restrictions can be found in Tables 1 4. The * symbol means that there is no restriction on the number of preor postconditions while 2 implies that the result holds for any fixed number 2. The tables also contain information about the PE problem from (B ackstr om and Nebel 1995; Bylander 1994): the symbol indicates when we know for sure (under the assumption P = NP) that the complexity of PE differs from the complextiy of PSP and NBP. The difference is always the same, namely, the PE problem is in P while the oversubscription problem is NP-complete. One sees that the complexity of PE and oversubscription planning only differs in a small number of borderline cases. The results can be inferred as follows: both PSP and NBP problem are members of PSPACE (van den Briel et al. 2004). PSPACE-hardness follows from Theorem 7 combined with the fact that PE(Θ) polynomial-time reduces to PSP(Θ) and NBP(Θ) for all Θ. NP-hardness follows from the results in Section 3 recall that if PSP(Γ) is NP-hard, then NBP(Γ) is NP-hard, too. The NP membership results is shown in Section 4 note that if NBP(Θ) is in NP, then PSP(Θ) is in NP, too. Finally, the tractability results follow from Theorem 3. Results for the P,U,B,S restrictions are collected in Figure 1.

Table 1: Results for PSP and NBP post 1 2

0 P NP-c. NP-c. 1 NP-h. NP-h. PSPACE-c. 2 NP-h. PSPACE-c. PSPACE-c. PSPACE-c. PSPACE-c. PSPACE-c.

Unrestricted

PU PS PB US UB BS

PUS PUB PBS UBS

Figure 1: Results for P,U,B,S restrictions

These results and the results in Table 1 hold for arbitrary domains D satisfying |D| 2. Tables 2 4 contain results for two-valued domains where we restrict ourselves to positive preand/or postconditions. Once again, the complexity of PSP and NBP coincide in all cases. It may be slightly surprising that the PSP and NBP problems have the same complexity but this is inherent in the restrictions we consider. Of course, this is not true for all instance sets: Jonsson (1999, Sec. 4) shows that there is a set Θ of planning instances that (1) always have a solution but (2) finding the shortest solution is PSPACE-hard. (1) implies that PSP(Θ) is trivially solvable in polynomial time while (2) implies that NBP(Θ) is PSPACE-complete.

6 Compiling NBP into PE We continue by presenting a method to compile NBP into PE. The basic motivation behind this reduction is to provide a method for using ordinary planners for solving the NBP problem. Our main concern is to make the reduction as lean as possible, i.e. we want the reduction to increase the size of the resulting instance as little as possible. The previously presented complexity results cannot be inferred from

Table 2: Results for + prec. / free postc. post 1 2

0 P NP-c. NP-c. 1 NP-c. NP-h. PSPACE-c. 2 NP-c. PSPACE-c. PSPACE-c. NP-c. PSPACE-c. PSPACE-c.

Table 3: Results for free prec. / + postc. + post 1 2

0 P NP-c. NP-c. 1 NP-c. NP-c. NP-c. 2 NP-c. NP-c. NP-c. NP-c. NP-c. NP-c.

Table 4: Results for + prec. / + postc. + post 1 2

0 P NP-c. NP-c. 1 NP-c. NP-c. NP-c. 2 NP-c. NP-c. NP-c. NP-c. NP-c. NP-c.

this reduction since it is not guaranteed to preserve any of the properties except B. The method is based on a certain kind of counter which we introduce next. The counter is very important in the reduction since it is used for keeping track of the net benefit during the course of the plan. Given an integer 0 m, we let (mn 1 . . . m1m0)2 denote m written in binary where mn 1 is the most significant bit and m0 the least significant. Given a sequence of binary variables X = (xn 1, . . . , x0), we can easily use such a sequence to represent the number m: let xi = 1 if mi = 1 and xi = 0, otherwise. Define (X m) = {xi | mi = 1} { xi | mi = 0}. For instance, if X = (x2, x1, x0), the action (X 3) (X 5) equals x2, x1, x0 x2, x1, x0. Given a state S over variable sequence X, we let JSK denote the number that X represents. Let X = (xk 1, . . . , x0) be a sequence of variables. If 0 n < k and JXK < 2k 2n, then X is transformed into a new state X such that JX K = JXK + 2n by exactly one of the following k n actions:

an 1 : xn xn an 2 : xn+1, xn xn+1, xn ... an k n : xk 1, xk 2, . . . , xn xk 1, xk 2, . . . xn

We use these actions to build a counter with arbitrary step size and the ability to count both upwards and downwards. Arbitrarily choose an integer 0 x < 2k and a step length 0 s < 2k. Introduce upward trigger variables C = {ci | 0 i < k}, downward trigger variables D = {di | 0 i < k}, and for every 0 i < k and 1 l k i, introduce actions

inci l : ci, pre(ai l) ci, post(ai l)

deci l : di, post(ai l) di, pre(ai l)

Consider a planning instance (V, A, I, G) where V = X C D, A contains the actions above, I specifies the values of the X variables such that JI[X]K = x, the C variables equal C s and the D variables equal 0. Finally, let G[v] = u for v X D and G[v] = 0 for v C. It is not hard to see that

this instance has a solution and it reaches a state S where JS[X]K = x + s. Similarly, if we want to lower X with s steps, we use the downward trigger variables in D instead of C. Note that if the X and D variables are representing numbers x and d such that x < d, then the counter cannot set all D variables to 0: this way, underflows can be detected and prevented. We now use the counter for compiling NBP into PE. Given an instance I = (V, A, I, G, c, U, K) of NBP, we construct an instance of PE where we have a global counter (to keep track of the net benefit) over variables X. Initially, X is loaded with the value M = P|V | i=1 U[i], i.e. the highest possible net benefit. This is done in order to avoid negative numbers. Each action in the plan decreases the counter with its corresponding weight. If the value goes below 0, then the NBP instance has no solution. After having found a plan with total cost γ, we increase the counter with the total utility υ achieved by this plan. At this point, the counter has value M γ +υ and we want to check whether this value is larger or equal to M + K (in order to verify that υ γ K). This is done by allowing free decreasing of the counter until reaching the goal value M + K. Construction 1. Let Π = (V, A, I, G, c, U, K) be an instance of NBP such that A = {a1, . . . , ap}. Construct a SAS+ instance Π = (V , A , I , G ) as follows: let M = P|V | i=1 U[i] and m = [log M] + 1. We will use a counter over variables X, C, D on m bits in the construction. Define V = V X C D B E where B = {bi|1 i [log |A|] + 1} are variables used to prevent action interference and E = {endg|G[g] = u} are variables used to guarantee that after starting to count the utility of the goals, no other action is applicable. Also, I [v] = I[v] for v V , I [xi] = pi for 1 i m where M = (pm . . . p1)2, and I [v] = 0 otherwise. G [xi] = qi for 1 i m where M + K = (qm . . . q1)2, and G [v] = u otherwise. We define A as follows: for every ai A, extend A with

a i : pre(ai), B, E (B i), (D c(ai)) and

a i : (B i), D B, post(ai).

For every vi V such that G[vi] = u, extend A with

g i : B, endvi, C, (vi = G[vi]) endvi, (C U[vi])

Finally, add the following actions to A :

freesubtractl : post(a0 l ) pre(a0 l ), 1 l m.

We note that the instance built in Construction 1 can easily be constructed in polynomial-time and that the size of the instance increases slowly compared to the size of the original NBP instance. Since |X| = |C| = |D| = m, |B| = log |A| and |E| = |G|, the total number of variables in Π is |V | = |V | + 3m + log |A| + |G|. Here, one should recall that |A| (|D| + 1)|V | (|D| + 1)|V |, implying that log |A| 2|V | log (|D| + 1), and that m is the logarithm of the sum of the utility vector U. Theorem 8. Construction 1 is a reduction from NBP to PE.

Proof. Let Π be an instance of NBP and let Π be the PE instance obtained via Construction 1. Assume Π has a solution

ω = (a1, . . . , ar) and that it satisfies the goals for variables v1, . . . , vs (for simplicity). It can be seen that

ω = (a 1, 1, a 1, a 2, 2, a 2, . . . , a r, r, a r, g 1, 1, g 2, 2, . . . , g s, s, )

is a solution for Π where i is a sequence of actions decreasing the counter initiated by a i, j is a sequence of actions increasing the counter initiated by g j, and is a sequence of freesubtract actions that decrease the counter by net benefit of ω minus K. Since ω is a solution for Π with net benefit at least K, ω is applicable and the counter value right before applying actions is at least M + K. Note that the minimum and maximum value of the counter are always kept in the interval [0, 2M] that the counter covers. The other direction is similar and thus omitted.

7 Discussion

In the first part of this paper, we presented complexity results for the PSP and NBP problems. Clearly, there are many complexity issues in connection with oversubscription planning that are worth studying. One example is to consider instances with restricted causal graphs. Classical planning problems for such instances have been intensively studied (Brafman and Domshlak 2003; Chen and Gim enez 2010; Katz and Domshlak 2008). In particular, it is interesting to see that the structure of the causal graph can be exploited to identify tractable BCPE problems (Katz and Domshlak 2008). This suggests that tractability results for NBP may be obtained this way, too. Another relevant topic is to study the parameterized complexity of oversubscription planning. Lately, many parameterized complexity results for planning have appeared (B ackstr om et al. 2012; de Haan, Roub ıckov a, and Szeider 2013; Kronegger, Pfandler, and Pichler 2013) In the second part of the paper, we presented a way of compiling NBP into PE. Both compiling different planning problems into each other (Keyder and Geffner 2009; Palacios and Geffner 2009; Taig and Brafman 2013) and compiling planning into other problems (Cashmore, Fox, and Giunchiglia 2012; van den Briel and Kambhampati 2005; Kautz and Selman 1992) have been very active research areas for quite some time. It is both exciting and slightly surprising to see that competetive planning algorithms result from compilation: for instance, Keyder & Geffner (2009) report encouraging results for benchmark oversubscription problems from the 2008 IPC competition. Experimental evaluation of our compilation method is an obvious direction for future research. In particular, using it to solve costoptimal planning with the aid of ordinary, non-optimizing planners is an interesting possibility. One should also note that the compilation method can be extended in different directions: for instance, modifying it to handle negative utilities is straightforward.

Acknowledgements

Meysam Aghighi is partially supported by the National Graduate School in Computer Science (CUGS), Sweden.

B ackstr om, C., and Klein, I. 1991. Planning in polynomial time: the SAS-PUBS class. Computational Intelligence 7(3):181 197. B ackstr om, C., and Nebel, B. 1995. Complexity results for SAS+ planning. Computational Intelligence 11(4):625 655. B ackstr om, C.; Chen, Y.; Jonsson, P.; Ordyniak, S.; and Szeider, S. 2012. The complexity of planning revisited a parameterized analysis. In Proc. of the 26th AAAI Conference on Artificial Intelligence (AAAI-2012). Benton, J.; Do, M.; and Kambhampati, S. 2009. Anytime heuristic search for partial satisfaction planning. Artif. Intell. 173(5-6):562 592. Brafman, R. I., and Domshlak, C. 2003. Structure and complexity in planning with unary operators. J. Artif. Intell. Res. 18:315 349. Bylander, T. 1994. The computational complexity of propositional strips planning. Artif. Intell. 69(1):165 204. Cashmore, M.; Fox, M.; and Giunchiglia, E. 2012. Planning as quantified boolean formula. In Proc. 20th European Conference on Artificial Intelligence (ECAI-2012), 217 222. Chen, H., and Gim enez, O. 2010. Causal graphs and structurally restricted planning. J. Comput. Syst. Sci. 76(7):579 592. de Haan, R.; Roub ıckov a, A.; and Szeider, S. 2013. Parameterized complexity results for plan reuse. In Proc. of the 27th AAAI Conference on Artificial Intelligence (AAAI-2013). Garey, M. R., and Johnson, D. S. 1979. Computers and intractability, volume 174. Freeman New York. Gim enez, O., and Jonsson, A. 2012. The influence of kdependence on the complexity of planning. Artif. Intell. 177179:25 45. Jonsson, P. 1999. Strong bounds on the approximability of two PSPACE-hard problems in propositional planning. Ann. Math. Artif. Intell. 26(1-4):133 147. Katz, M., and Domshlak, C. 2008. New islands of tractability of cost-optimal planning. J. Artif. Intell. Res. 32:203 288. Kautz, H. A., and Selman, B. 1992. Planning as satisfiability. In Proc. 10th European Conference on Artificial Intelligence (ECAI-2012), 359 363. Keyder, E., and Geffner, H. 2009. Soft goals can be compiled away. J. Artif. Intell. Res. 36:547 556. Kronegger, M.; Pfandler, A.; and Pichler, R. 2013. Parameterized complexity of optimal planning: A detailed map. In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013). Mirkis, V., and Domshlak, C. 2013. Abstractions for oversubscription planning. In Proc. 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013). Palacios, H., and Geffner, H. 2009. Compiling uncertainty away in conformant planning problems with bounded width. J. Artif. Intell. Res. 35:623 675.

Smith, D. 2004. Choosing objectives in over-subscription planning. In Proc. 14th International Conference on Automated Planning and Scheduling (ICAPS-2004), 393 401. Taig, R., and Brafman, R. I. 2013. Compiling conformant probabilistic planning problems into classical planning. In Proc. 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013). van den Briel, M., and Kambhampati, S. 2005. Optiplan: Unifying IP-based and graph-based planning. J. Artif. Intell. Res. 24:919 931. van den Briel, M.; Nigenda, R. S.; Do, M. B.; and Kambhampati, S. 2004. Effective approaches for partial satisfaction (over-subscription) planning. In Proc. 19th National Conference on Artificial Intelligence (AAAI-2004), 562 569.