In Search of Tractability for Partial Satisfaction Planning

1 Introduction

While in classical planning the concern is solely around the cost of achieving all goals, in partial satisfaction planning the restriction is relaxed, allowing to achieve only some of the goals. This comes not without a price, resulting in an empty plan being a trivial valid solution and requiring to aim at achieving as large as possible value. However, the cost of achieving these values must also be accounted for. In netbenefit planning, the cost of achieving the values and the values themselves are assumed to be comparable and the objective is to maximize the achieved goals value minus the cost of its achievement. Net-benefit planning was shown to be PSPACE-complete [Briel et al., 2004] and to have a practical mapping to classical planning [Keyder and Geffner, 2009]. A complexity investigation for restricted fragments of netbenefit planning was recently performed [Aghighi and Jonsson, 2014; Aghighi and B¨ackstr ¨om, 2015], focusing on PUBS fragments [B¨ackstr¨om and Nebel, 1995]. Further, Aghighi and Jonsson (2014) in their discussion suggest that it might be possible to obtain tractable fragments of net-benefit planning by restricting the causal graph structure.

Vitaly Mirkis

Huawei Technologies, Israel vitaly.mirkis@huawei.com

In oversubscription planning the cost of achieving the values and the values themselves are not assumed to be comparable. To take the cost into account, a bound on the cost or a budget is introduced [Smith, 2004], and the objective is to maximize the achieved goals value, while the cost is constrained by the given budget. While heuristic search has been playing a significant role in the progress of both cost-optimal classical and net-benefit planning, optimal oversubscription planning remained almost completely untouched. A significant performance improvement for optimal oversubscription planning was reported for the first time almost a decade after the oversubscription planning problem was initially introduced [Mirkis and Domshlak, 2013], exploiting a heuristic search approach with admissible heuristics based on the explicit abstraction paradigm [Edelkamp, 2001]. The abstract oversubscription planning problems, tractable due to their small size, were then additively composed to derive informative admissible estimates. The reported heuristic performance, compared to the baseline algorithm, in some cases, reduced the search space by three orders of magnitude.

The success of exploiting polynomial complexity fragments for deriving admissible estimates for optimal oversubscription planning was not surprising, as in the classical planning literature the picture was virtually the same. However, in contrast to both classical and net-benefit planning, oversubscription planning remains completely unexplored in terms of complexity analysis. Optimal oversubscription planning is PSPACE-complete even when severely restricting the value function, as a result of a straightforward reduction from costoptimal classical planning. Even this result, however, to the best of our knowledge does not appear in the literature.

To alleviate this gap, we investigate the tractability of both optimal oversubscription and net-benefit planning for certain classes of problems specified by their causal graph structure and variable domain sizes [Helmert, 2004; Katz and Domshlak, 2010]. Focusing on a most common class of value functions, we show that the most structurally restricted fragments are weakly NP-complete for optimal oversubscription planning and polynomial for optimal net-benefit planning. We continue by relaxing the structural restriction and describe a boundary of tractability for both net-benefit and oversubscription planning. Furthermore, for a restricted class of value functions, we present a generic result relating tractable fragments of oversubscription and classical planning. We conclude by summarizing our results and presenting future research directions. We find that net-benefit versions of tractable cost-optimal planning problems tend to be tractable as well, while complexity results for oversubscription problems carry over only in the presence of certain limiting assumptions concerning the value function.

2 Background

In line with the SAS+ formalism for deterministic planning [B¨ackstr¨om and Klein, 1991; B¨ackstr¨om and Nebel, 1995], a planning task structure is given by a pair hV↪Oi, where V is a set of n finite-domain state variables, and O is a finite set of operators. Each complete assignment to V is called a state, and S = dom(v1)⇥▷ ▷ ▷⇥dom(vn) is the state space of the structure hV↪Oi. A partial assignments to V is called a partial state. Each operator o is a pair hpre(o)↪ e↵(o)i of partial states called preconditions and effects, respectively. Denoting by V(p) ✓ V the subset of variables instantiated by a partial state p, operator o is applicable in a state s iff s[v] = pre(o)[v] for all v 2 V(pre(o)). Applying o changes the value of each v 2 V(e↵(o)) to e↵(o)[v]. The resulting state is denoted by sJoK; by sJho1↪ ▷ ▷ ▷ ↪ okiK we denote the state obtained from sequential application of the (applicable in turn) operators o1↪ ▷ ▷ ▷ ↪ ok starting at state s.

The causal graph of a planning task structure hV↪Oi is a digraph CG = hV↪Ei over the set of nodes V that contains an arc (v↪ v0 ) iff v 6= v0 and both v 2 V(pre(o)) [ V(e↵(o)) and v0 2 V(e↵(o)) for some o 2 O. The domain transition graph DTG(v) of a variable v 2 V is an arc-labeled digraph with nodes dom(v) that contains an arc (#↪ #0 ) labeled with pre(o) ∩ pre(o)[v] iff e↵(o)[v] = #0 and either pre(o)[v] = # or v 62 V(pre(o)).

In classical planning, a planning task ⇧ = hV↪ O; s0↪ G↪ Ci extends its structure with an initial state s0 2 S, a goal specification G, typically modeled as a partial state, and an operator cost function C : O ! R0+. An operator sequence ⇡ is called a plan if it is applicable in s0, and G ✓ sJ⇡K. A plan is optimal if the sum of its operator costs is minimal among all plans. The objective in classical planning is to find a plan of as low cost as possible, with optimal classical planning being devoted to searching for optimal plans only.

The causal graph of the planning task ⇧ is the causal graph of its structure. In this paper we investigate several previously studied causal graph structures, exampled in Figure 1. First, fork and inverted fork structures are directed graphs G = (N↪E) such that there exists a node r 2 N for which (u↪ v) 2 E () u = r, if the structure is a fork, and (u↪ v) 2 E () v = r, if the structure is an inverted fork. We refer to planning problems whose causal graphs are (inverted) forks as (inverted) fork structured planning problems. Optimal planning has been shown to be tractable for fork structured planning problems if ♣dom(r)♣ = 2 and NP-complete for ♣dom(r)♣ > 2. For inverted fork structured planning problems optimal planning is tractable for any ♣dom(r)♣ 2 O(1) [Katz and Domshlak, 2010; Katz and Keyder, 2012]. Another previously studied structure is a polytree. A polytree is a directed graph whose underlying undirected graph is a tree. Plan generation for problems with polytree casual graphs and binary variable domains is NPhard, but becomes tractable when imposing a constant bound on causal graph in-degree [Brafman and Domshlak, 2003; Gim´enez and Jonsson, 2008]. Moreover, imposing this restriction makes even optimal planning tractable [Katz and Domshlak, 2008a]. Alternatively, restricting the operators to have at most one precondition also makes optimal planning for binary polytrees tractable [Katz and Domshlak, 2008a]. Lastly, a semifork structure consists of a fork structure, and the remaining nodes, called a hat, have edges either among themselves or to the root of the fork (called a center), and hourglass structure consists of both a fork and an inverted fork rooted at the same variable (also called a center). Semiforks with binary center variable domain and constantly bounded hat and hourglasses with binary center variable domain and operators with at most one precondition are tractable for optimal planning [Katz and Keyder, 2012].

2.1 Oversubscription Planning

In contrast to classical planning, an oversubscription planning task ⇧ = hV ↪O; s0 ↪ C↪ u↪ bi extends its structure with four components: an initial state s0 2 S and an operator cost function C : O ! R0+ as above, plus a succinctly represented and efficiently computable state value function u : S ! R0+, and a cost budget b 2 R0+. An operator sequence ⇡ is called a plan if it is applicable in s0, and Po2⇡ C(o)  b; by ˆu(⇡) we refer to the value of the endstate of ⇡, that is, ˆu(⇡) = u(s0J⇡K). While an empty operator sequence is always a plan, the objective in oversubscription planning is to find a plan that achieves an as valuable state as possible, and optimal oversubscription planning is devoted to searching for optimal plans only: A plan ⇡ is optimal if ˆu(⇡) is maximal among all the plans.

In what follows, we mostly focus on additive state value functions, computed as a sum over the state variables u(s) def = Pv2V u(s[v]). However, in some cases a value function can be given explicitly. One such special case is the so-called 0-binary value function, with its image restricted to at most 2 values [Domshlak and Mirkis, 2015]. Originally, 0-binary value functions were used in the context of explicit abstractions, and were defined on a small set of explicitly stated abstract states. We extend the definition to general oversubscription planning tasks, however restricting ourselves to 0binary value functions compactly represented by a set of partial states with non-zero values.

2.2 Net-Benefit Planning

Similarly, a net-benefit planning task ⇧ = hV ↪O; s0 ↪ C↪ ui extends its structure with three components: an initial state s0 2 S, an operator cost function C : O ! R0+, and a succinctly represented and efficiently computable state value function u : S ! R0+, as above. An operator sequence ⇡ is a plan if it is applicable in s0. The cost of a plan is defined as a sum of its operators costs, and the value is defined by the value of the reached state. The objective of net-benefit planning is to find a plan that maximizes the difference between its value and its cost.

2.3 The Knapsack Problem

In what follows we will exploit two variants of the so-called knapsack problem. The first variant is the 0-1 knapsack problem. Given n items to pack in some knapsack of capacity c, each with a profit p and a weight w, the problem is to choose which items to pack, such that the profit sum is maximized without having the weight sum exceed c. The second variant is the multiple choice knapsack problem. Given k classes N1↪ ▷ ▷ ▷ ↪Nk of items to pack in some knapsack of capacity c. Each item j 2 Ni has a profit pij and a weight wij, the problem is to choose one item from each class such that the profit sum is maximized without having the weight sum exceed c. Both 0-1 and multiple choice knapsack are NP-hard, but both can be solved through dynamic programming in time polynomial in the problem description size and in the unary representation size of c [Dudzi´nski and Walukiewicz, 1987].

3 Oversubscription Planning

In what follows we present a tractability analysis of the optimal oversubscription planning for fragments characterized by variable domain size and causal graph structure.

3.1 Additive State Value Function

Focusing on the additive state value functions, we start with a discouraging result, even for a severely structurally restricted fragment.

Theorem 1 Optimal oversubscription planning for tasks with additive state value function, binary variable domains, and a causal graph with no edges, is weakly NP-complete.

Proof: Membership in NP: cheapest plans are never required to change the value of any variable more than once, since all variables are independent of each other. The proof of hardness is by reduction from the 0-1 knapsack problem. Given items N, with a profit pi and a weight wi, for i 2 N, and a capacity c, the oversubscription planning problem ⇧ = hV ↪ O; s0 ↪ C↪ u↪ bi is defined as follows. The variables V = ¶vi ♣ i 2 N♦, each with domain ¶0↪ 1♦ represent the items N. The initial state consists of all variables having the value 0. The value function u is defined to be pi for the value 1 of variable vi, and 0 otherwise, and the bound b is c. The operators O = ¶oi ♣ i 2 N♦ with pre(oi) = ¶vi = 0♦, e↵(oi) = ¶vi = 1♦, and C(oi) = wi, changing each variable from its initial value, with the cost equal to the weight of the item. A solution to the optimal oversubscription planning problem corresponds to the solution for the 0-1 knapsack problem and vice versa.

While the result sounds extremely discouraging, recall that the knapsack problem can be solved through dynamic programming in time polynomial in the problem description size and in the unary representation size of c, or a pseudopolynomial time. Thus, in what follows, we search for a boundary of weak-NP-completeness. The first fragment of oversubscription planning we consider is a fork-structured causal graph with binary root domain and an additive state value function.

Theorem 2 Given an oversubscription planning task ⇧ = hV ↪ O; s0 ↪ C↪ u↪ bi with an additive state value function and a fork causal graph rooted at r 2 V , if ♣dom(r)♣ = 2, then an optimal plan for ⇧ can be found in time polynomial in ♣♣⇧♣♣ and the unary budget representation.

Proof: Let succ = V ∩ ¶r♦ denote the leaf variables of ⇧. Observe that the fork structure of the causal graph CG(⇧) implies that all the operators in ⇧ are unary-effect, and each leaf variable v 2 succ preconditions only the operators affecting v itself.

First, for ♣dom(r)♣ = 2, the algorithm below is based on the following three properties satisfied by the cheapest plans ⇡ for ⇧ among those that achieve the same value. In what follows, we restrict our attention to cheapest plans only.

• (i) For any leaf variable v 2 succ, the path ⇡#v from s0[v] induced by ⇡ in the domain transition graph of v, DTG(v), is either cycle-free or contains only zerocost cycles. This is the case because otherwise all the nonzero-cost cycles can be eliminated from ⇡#v while preserving its validity, violating the assumption that ⇡ is cheapest among those that achieve the same value. Without loss of generality, in what follows we assume that this path ⇡#v in DTG(v) is cycle-free; in the case of fork causal graphs, we can always select a cost-minimal ⇡ that satisfies this requirement for all v 2 succ. Thus, we have ♣⇡#v ♣  ♣dom(v)♣ - 1.
• (ii) Having fixed a sequence of value changes of r, the fork's leaves become mutually independent; that is, our ability to change the value of one does not affect our ability to change the value of any of the others.
• (iii) Because r is binary-valued, if v 2 succ is the "most demanding" leaf variable in terms of the number of value changes required from r by the operator preconditions along ⇡#v, then these are the only value changes of r along ⇡, except for, possibly, a final value change to obtain a different value of r. Thus, in particular, we have ♣⇡#r ♣ maxv2succ ♣dom(v)♣.

From (iii), it is sufficient to go over the polynomial number of value changing sequences of the root variable r, finding for each such sequence the best plan in which the root variable performs exactly that sequence. Thus, in what follows, assume that σ is the sequence of value changes performed by the root variable r. From (ii), all other variables become mutually independent. Thus, for v 2 succ, and for each domain value # 2 dom(v), let ⇡σ v (#) denote the cheapest sequence of operators that corresponds to a path in DTG(v) from the initial value s0[v] to # that can be achieved under the support of σ. In other words, ⇡σ v (#) can be extended by σ to a plan for the task obtained by projecting away all other successors of r. Since finding such a sequence corresponds to solving oversubscription planning optimally for a planning task with 2 variables, all such sequences for all domain values can be obtained in polynomial time.

We now construct a multiple choice knapsack MK(σ) problem as follows:

• ÷ For each state variable v 2 succ we have a class Nv = ¶# 2 dom(v) ♣ u[v](#) > 0♦[¶s0[v]♦ of items to pack.
• ÷ The weight of each item # 2 Nv is the cost of ⇡σ v (#).
• ÷ The profit of each item # 2 Nv is the value u[v](#).
• ÷ The overall capacity c is set to be b-C(σ), where C(σ) is the cost of a cheapest sequence of operators performing the sequence of changes σ of the variable r.

Solving the multiple choice knapsack MK(σ) problem optimally results in one value #v 2 Nv ✓ dom(v) being selected for each v, maximizing the summed value such that the sum of the costs of the cost-minimal paths from s0[v] to #v is under the capacity b - C(σ). A corresponding plan ⇡σ is then constructed by appending the cost-minimal paths ⇡σ v (#v) between the r-changing operators, constructing a cost-minimal path from s0[v] to #v for each v. Note that the plan ⇡σ achieves the maximal value among all plans in which the value changes of r are exactly σ. The cost of the resulted plan ⇡σ is thus C(⇡σ) = C(σ) + Pv2succ C(⇡σ v (#v))  b. Going over the polynomial number of possible sequences σ, we can now find the plan that achieves the maximal value among all the plans ⇡σ.

It is straightforward to verify that the complexity of the above procedure equals to the complexity of the multiple choice knapsack problem, which can be solved in time polynomial in the problem description size and in the unary representation size of c. Since c  b, the complexity of the above procedure is polynomial in ♣♣⇧♣♣ and the unary representation size of b. To prove correctness, we show that the plan ⇡0 returned by the procedure for the task ⇧ satisfies ˆu(⇡0 ) ≥ ˆu(⇡) for some optimal plan ⇡ for ⇧. Given an oversubscription planning task ⇧, let ⇡ be an optimal plan for ⇧ with C(⇡)  b and all ⇡#v for the leaf variables v being cycle-free. Let σ be the corresponding sequence of value changes of r. It is sufficient to show that for the plan ⇡σ found by our algorithm we have ˆu(⇡σ) ≥ ˆu(⇡). For each v 2 succ, we have ⇡#v corresponding to a path in DTG(v) from the initial value s0[v] to #v = s0J⇡K[v] that can be achieved under the support of σ. Thus, C(⇡#v) ≥ C(⇡σ v (#)), the cheapest such path. Therefore, the collection ¶#v ♣ v 2 succ♦ is a (not necessarily optimal) solution to the multiple choice knapsack problem. Thus, Pv2succ u(s0J⇡K[v])  Pv2succ u(s0J⇡σK[v]). Since the root value for the resulting state for ⇡ is the same as for ⇡σ, we thus have ˆu(⇡)  ˆu(⇡σ), as desired.

Since additive state value functions may be used for encoding classical planning goals, hardness results from classical planning can be translated into corresponding results for oversubscription planning. In particular, relaxing the restriction on the root variable domain size causes the cost-optimal classical planning fragment become (strongly) NP-complete [Katz and Keyder, 2012], giving us the corresponding result for oversubscription planning.

Theorem 3 Optimal oversubscription planning for tasks with an additive value function and a fork causal graph rooted at a ternary domain variable is strongly NP-complete.

Proof: Membership in NP: cheapest plans are never required to change the value of any non-root variable v more than ♣dom(v)♣ times, and r, the only variable that can support such changes, changes its value at most ♣dom(r)♣ = 3 times to support each change. The proof of hardness is by reduction from bounded classical planning. Given a classical planning task ⇧G = hV↪ O; s0↪ G↪ Ci with fork structured causal graph rooted at r 2 V with ♣dom(r)♣ = 3 and a bound b, the additive state value function u is defined by mapping the goal values G[v] for v 2 V(G) to 1 and others to 0. Thus, the value of a goal state will be exactly ♣V(G)♣, and strictly smaller for all non-goal states. Thus, optimal oversubscription planning plans that achieve the value ♣V(G)♣ correspond to bounded planning plans and vice versa.

We now move to the second fragment, an inverted forkstructured causal graph with constant-bounded sink domain.

Theorem 4 Given an oversubscription planning task ⇧ = hV ↪O; s0 ↪ C↪ u↪ bi with an inverted fork causal graph with sink r 2 V , if ♣dom(r)♣ = O(1), then an optimal plan for ⇧ can be found in time polynomial in ♣♣⇧♣♣ and the unary budget representation.

Proof: Let pred = V ∩ ¶r♦ denote the predecessors of r and let ♣dom(r)♣ = d. Observe that the inverted-fork structure of the causal graph CG(⇧) implies that all the operators in ⇧ are unary-effect, and that the sink r preconditions only the operators affecting r itself. Hence, in what follows we assume that u[r](#) > 0 for some # 2 dom(r); otherwise ⇧ breaks down to an oversubscription planning problem over a set of independent variables, which can be solved by a multiple choice knapsack. Likewise, from the above properties of ⇧ it follows that, if ⇡ is a cheapest plan for ⇧ among those that achieve the same value, then the path ⇡#r from s0[r] to s0J⇡K[r] induced by ⇡ in DTG(r) is either cycle-free or contains only zero-cost cycles. The latter can be safely eliminated from ⇡, and thus we can assume that ⇡#r is cycle-free. The algorithm below is based on the following three properties satisfied by the cheapest plans ⇡ for ⇧ among those that achieve the same value. In what follows, we restrict our attention to cheapest plans only.

• (i) There are ⇥(♣O♣d ) cycle-free paths in the domain transition graph DTG(r) from s0[r] to all #r 2 dom(r).
• (ii) Having fixed a sequence σ of value changing operators of r, the inverted fork's parents change their values to support the preconditions required along σ independently of each other.
• (iii) For each variable v 2 pred, and each pair of v's values x↪ y 2 dom(v), the cost-minimal path ⇡v(x↪ y) from x to y in DTG(v) can be computed in poly-time. The whole set of such cost-minimal paths can be computed using ♣V ♣ - 1 applications of the Floyd-Warshall algorithm on the domain transition graphs of the sink's parents pred, in O(Pv2pred ♣dom(v)♣3 ).

We now construct a multiple choice knapsack MK(σ) problem as follows:

From (i), it is sufficient to go over the polynomial number of value changing sequences of the sink variable r, finding for each such sequence the best plan in which the sink variable performs exactly that sequence. Thus, in what follows, assume that σ is the sequence of value changing operators of the sink variable r. Given σ, for each v 2 pred, let ⇡v be some cheapest sequence of v-changing operators achieving the values of v in the order they appear in the preconditions along the sequence σ. Such sequences can be constructed by a simple concatenation of the sequences computed in (iii), with the last achieved value for each parent v is the precondition value that appears last in the sequence σ, with ⇡v being empty if no precondition is required from v along σ. Let ⇢σ be the applicable sequence of operators obtained by merging σ with all ⇡v for v 2 pred and let sσ = s0J⇢σK be the state resulting from applying ⇢σ in the initial state.

• ÷ For each state variable v 2 pred we have a class Nv = ¶# 2 dom(v) ♣ u[v](#) > 0♦[¶sσ[v]♦ of items to pack.
• ÷ The weight of each item # 2 Nv is set to be the cost of ⇡v (sσ [v]↪ #).
• ÷ The profit of each item # 2 Nv is the value u[v](#).
• ÷ The overall capacity c is set to be b-C(⇢σ).

Solving the multiple choice knapsack MK(σ) problem optimally results in one value #v 2 Nv ✓ dom(v) being selected for each v, maximizing the summed value such that the sum of the costs of the cost-minimal paths from sσ[v] to #v is bounded by b-C(⇢σ). A corresponding plan ⇡σ is then constructed by appending the cost-minimal paths ⇡v(sσ[v]↪ #v) to the end of ⇢σ. Note that ⇡σ achieves maximal value among all plans in which the value changes of r are exactly σ. The cost of ⇡σ is thus C(⇡σ) = C(⇢σ) + Pv2pred C(⇡v(sσ[v]↪ #v))  b. Going over the polynomial number of possible sequences σ, we can now find the plan that achieves the maximal value among all the plans ⇡σ.

The complexity of the above procedure equals to the complexity of the multiple choice knapsack problem, which can be solved in time polynomial in the problem description size and in the unary representation size of c. Since c  b, the complexity of the above procedure is polynomial in ♣♣⇧♣♣ and the unary representation size of b. To prove correctness, we show that the plan ⇡0 found by running the procedure on task ⇧ satisfies ˆu(⇡0 ) ≥ ˆu(⇡) for some optimal plan ⇡ for ⇧. Given an oversubscription planning task ⇧, let ⇡ be an optimal plan for ⇧ with C(⇡)  b and ⇡#r for the sink variable r being cycle-free. Let σ be the corresponding sequence of value changes of r. It is sufficient to show that for the plan ⇡σ found by our algorithm we have ˆu(⇡σ) ≥ ˆu(⇡). For each v 2 pred, we have ⇡#v corresponding to a path in DTG(v) from the initial value s0[v] to #v = s0J⇡K[v], passing through the precondition values required along σ. Let sv be the last such value, if exists, otherwise sv = s0[v]. Note that sv = sσ[v] for all parents v 2 pred. The value sv separates the sequence of operators ⇡#v into two sequences ⇡#v (s0[v]↪ sv) from the initial value to sv and ⇡#v (sv↪ #v) from sv to the final value #v. Thus, C(⇡#v (sv↪ #v)) ≥ C(⇡v(sσ[v]↪ #v)), the cheapest such path. Therefore, the collection ¶#v ♣ v 2 pred♦ is a (not necessarily optimal) solution to the multiple choice knapsack problem. Thus, Pv2pred u(s0J⇡K[v])  Pv2pred u(s0J⇡σK[v]). Since the sink value for the resulting state for ⇡ is the same as for ⇡σ, we thus have ˆu(⇡)  ˆu(⇡σ), as desired.

Here as well, relaxing the restriction on sink variable domain size make optimal oversubsctiption planning (strongly) NP-complete, even if the domain transition graphs of all the state variables are strongly connected.

Theorem 5 Optimal oversubscription planning for tasks with an additive value function and an inverted fork causal graph with strongly connected domain transition graphs of all the state variables is strongly NP-complete.

Proof: Membership in NP: cheapest plans are never required to change the value of the sink variable r more than ♣dom(r)♣ times, and for an operator o changing the sink variable, each parent v can achieve o's precondition with at most ♣dom(v)♣ value changes. The proof of hardness is by reduction from bounded classical planning. Given a classical planning task ⇧G = hV↪O; s0↪G↪ Ci with inverted fork structured causal graph with sink r 2 V and a bound b, the additive state value function u is defined by mapping the goal values G[v] for v 2 V(G) to 1 and other to 0. Thus, the value of a goal state will be exactly ♣V(G)♣, and strictly smaller for all non-goal states. Thus, optimal oversubscription planning plans that achieve the value ♣V(G)♣ correspond to bounded planning plans and vice versa, and the hardness stems from the corresponding result for cost optimal planning [Helmert, 2004].

3.2 0-Binary Value Function

The results of Theorem 1 leave virtually no hope for deriving tractable fragments of oversubscription planning for the additive state value functions, and thus here we turn our attention to other families of value functions. One such family that was shown useful for deriving heuristic values is 0-binary value function [Mirkis and Domshlak, 2013]. In case of a 0binary value function compactly described by a set of partial states with a non-zero value, let us denote such a set by Sf for a value function f. The following theorem establishes a connection between tractable fragments of cost-optimal classical planning and oversubscription planning with the aforementioned restriction on the value function.

Theorem 6 Given an oversubscription planning task ⇧ = hV ↪ O; s0 ↪ C ↪ u↪ bi with a 0-binary value function u described by a set Su of partial states with a non-zero value, if the classical planning task ⇧G = hV↪O; s0↪G↪ Ci is optimally solvable in time polynomial in ♣♣⇧G♣♣ for any G 2 Su, then optimal oversubscription planning for ⇧ is also solvable in time polynomial in ♣♣⇧♣♣ and ♣Su♣.

Proof: For each partial state G 2 Su, solve the classical planning task ⇧G = hV↪O↪ s0↪G↪ Ci optimally. Let ⇡G be some cost-optimal plan for the classical planning task ⇧G. If for some G 2 Su we have C(⇡G)  b, then ⇡G is an optimal plan for ⇧. Otherwise, the empty plan is an optimal plan for ⇧.

Note that even with such 0-binary value functions optimal oversubscription planning is at least as hard as cost bounded classical planning for tasks of the same structure, for the same reasons as for additive value functions.

Following Theorem 6, we can obtain tractable fragments of oversubscription planning from the tractable fragments of cost-optimal planning whose tractability is not dependent on a specific goal state. In particular, the following tractable fragments fit the setting of Theorem 6: forks with binary root variable domain and inverted forks with constantly bounded sink variable domain [Katz and Domshlak, 2008b]; polytrees with either 1-dependent operators or O(1)-bounded in-degree [Katz and Domshlak, 2008a]; hourglasses with binary center variable domain and operators with at most one precondition or semiforks with binary center variable and O(1)-bounded size hat [Katz and Keyder, 2012].

4 Net-Benefit Planning

Following the suggestion of Aghighi and Jonsson (2014), we now turn our attention to the net-benefit planning. Focusing on the additive state value functions, observe that the reformulation suggested by Keyder and Geffner (2009) can be adapted to the multi-valued SAS+ formalism as follows. Let ⇧ = hV ↪O; s0 ↪ C↪ ui be a net-benefit planning task. The cost-optimal planning encoding X(⇧) = hV↪O0 ; s0↪G↪ C 0 i of ⇧ is constructed by adding an auxiliary value ✏v to each variable v with non-zero utility values. The goal G is the collection of these values. Let mv = max¶u(#) ♣ # 2 dom(v)♦ be the maximal utility value for each variable. First, the operator set O0 includes all the operators O from the netbenefit planning task. Further, for each varaible v and each value # 2 dom(v), O0 consists of an operator o(v↪ #) with pre(o(v↪ #)) = ¶v = #♦, e↵(o(v↪ #)) = ¶v = ✏v♦, and C 0 (o(v↪ #)) = mv - u(#). Each such operator changes a single variable, and thus does not contribute any edges to the causal graph. In words, the reformulation allows to achieve the goal from any state by paying the difference between the maximal possible utility and the obtained one. The suggested encoding turns out to be a useful tool, allowing us to derive tractability of optimal net-benefit planning from the results for cost-optimal planning. We start with the fork fragment.

Theorem 7 Given a net-benefit planning task ⇧ = hV ↪O; s0 ↪ C↪ ui with an additive state value function and a fork causal graph rooted at r 2 V , if ♣dom(r)♣ = 2, optimal net-benefit planning for ⇧ is polynomial in ♣♣⇧♣♣.

Proof: Let X(⇧) be the cost-optimal planning task obtained from ⇧ by the adapted reformulation of Keyder and Geffner (2009). Thus, X(⇧) has a fork structure with an at most ternary root variable domain. In the case of a ternary root domain, the goal value of the root is a terminal value, with no outgoing edges, and thus the proof of Theorem 4 in Katz and Domshlak (2010) can trivially be adapted to X(⇧).

Note that the simplest fragment from Theorem 1 for oversubscription planning, namely binary variable domains and causal graph with no edges is a subcase of the fork fragment above, and thus is also polynomial, in contrast to the results of Theorem 1. While the fork fragment requires a minor adaptation of the original proof for the cost-optimal planning fragment, the tractability of the inverted fork fragment stems directly from the cost-optimal planning result.

Theorem 8 Given a net-benefit planning task ⇧ = hV ↪ O; s0 ↪ C↪ ui with an inverted fork causal graph with sink r 2 V , if ♣dom(r)♣ = O(1), optimal net-benefit planning for ⇧ is polynomial in ♣♣⇧♣♣.

Proof: Let X(⇧) be the cost-optimal planning task obtained from ⇧ by the adapted reformulation of Keyder and Geffner (2009). X(⇧) has an inverted fork structure with constant valued root variable domain, and thus is tractable due to Theorem 5 of Katz and Domshlak (2010).

The hardness results also hold for fragments that correspond to Theorems 3 and 5. The proofs follow the same path as the proofs for these theorems and thus are omitted here.

5 Summary and FutureWork

We presented new results for the complexity of optimal oversubscription and net-benefit planning for additive state value functions, drawing a boundary between tractable and NPcomplete cases for net-benefit planning and between weakly NP-complete and strongly NP-complete cases for oversubscription planning. We show several fragments that are polynomial for optimal net-benefit planning but weakly-NPcomplete for optimal oversubscription planning. As even severely structurally restricted fragments of optimal oversubscription planning are already weakly NP-complete, the feasibility of exploiting these fragments for deriving informative utility estimates remains an open question. Further, an investigation is needed into which additional restrictions should be imposed to make optimal oversubscription planning tractable. Theorem 1 hints that the only possible direction is to restrict the value functions.

Following that direction, for 0-binary value functions, we present a general result relating tractable fragments of oversubscription and classical planning, for value functions that are compactly represented by a set of partial states for nonzero utility values. Another option would be to compactly represent a 0-binary value function by the set of states with zero utility values. One interesting question is whether similar results can be devised for such value functions.

Acknowledgments

We thank Emil Keyder for discussions and comments that greatly improved the paper.