A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs

1 Introduction

A common approach for identifying tractable fragments of planning is to analyse the causal graph [Knoblock, 1994], a directed graph where the vertices represent variables and the arcs represent certain dependencies between variables. By combining restrictions on the structure of this graph with bounds on certain problem-specific parameters, many different tractability results have been obtained. It was early noted that if the causal graph is acyclic, then all actions are unary, i.e. change one variable only, yet such restricted instances can be useful even in practice [Williams and Nayak, 1997]. Helmert [2006] pioneered the idea of defining heuristics based on subgraphs of the causal graph.

∗This is an extended abstract of the paper "A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs" which won the best-paper award at the SoCS-2018 conference.

†Contact Author

He removed arcs in the graph to be able to find acyclic subgraphs, which made it easier to define heuristics. However, not even acyclicity is sufficient in the general case; planning is still PSPACE-complete even when restricted to arbitrary acyclic causal graphs [Jonsson et al., 2014]. Hence, there has been much focus on various restricted types of acyclic graphs, for example forks, inverted forks and hourglasses. Cost-optimal planning is NP-hard if the causal graph is of either of these types with no further restrictions, but becomes tractable for all three types if we also bound the variable domain size by a constant [Katz and Keyder, 2012; Katz and Domshlak, 2010].

A directed graph is a polytree if it is acyclic and its underlying undirected graph is a tree. Problems with causal graphs that are polytrees have been intensively studied in the literature. It is easy to verify that (inverted) forks and hourglasses are polytrees. Aghighi et al. [2015] show that costoptimal planning is tractable for instances with bounded domain size and a polytree causal graph with bounded diameter, the length of the longest path in the underlying undirected graph. Another popular parameter is the in-degree of the causal graph, i.e. the maximum number of arcs that go into a vertex. The in-degree is 1 for forks but unbounded for inverted forks and hourglasses. Cost-optimal planning is tractable for instances with polytree causal graphs, domain size 2 and bounded in-degree [Katz and Domshlak, 2008]. This result cannot be generalised to arbitrarily large domains: even satisficing planning is NP-hard for domain size 5 and in-degree 1 [Gim´enez and Jonsson, 2009]. St˚ahlberg [2017] considered the depth of the causal graph, i.e. the length of the longest directed path (which is obviously upper bounded by the diameter). He showed that cost-optimal planning is tractable for instances with bounded domain size and polytree causal graphs with bounded depth and in-degree. We improve on his result, showing that it is sufficient to bound only the depth and the domain size to achieve tractability. The resulting tractable fragment is maximal for polytrees in the sense that we cannot drop the domain size bound nor the depth bound with retained tractability; it is known that costoptimal planning is NP-hard for causal graphs of arbitrary depth, even if the domain size is 2 [Gim´enez and Jonsson, 2008] and for inverted-fork causal graphs and unbounded domain size [Domshlak and Dinitz, 2001].

The structure of this extended abstract follows the original full paper [B¨ackstr¨om et al., 2018], using the same sections and the same numbering of results.

2 Preliminaries

A SAS+ planning instance is a tuple P = 〈V,A, sI, sG, c〉 where V is a set of variables, with an implicit domain D, A is a set of actions and c : A → Q≥0 is a cost function. The initial state sI is a total state and the goal sG is a partial state. Each action a ∈ A has two partial states the precondition pre(a) and the effect eff(a). An action sequence ω is a plan for P if transforms sI to a state s that satisfies sG. The length |ω| of ω is the number of actions in ω and the cost c(ω) is the total cost of the actions in ω. We also define C(v, ω) as the number of value changes of v when executing ω. Furthermore, ω is a cost-optimal plan for P if there is no plan ω′ for P such that c(ω′ ) < c(ω); and ω is a shortest cost-optimal plan for P if it is cost optimal and there is no plan ω′ for P such that c(ω′ ) = c(ω) and |ω′ | < |ω|. The latter concept is important in the presence of zero-cost actions, since a costoptimal plan can then be arbitrarily long. In order to find a cost-optimal plan, it is obviously sufficient to find a shortest cost-optimal plan. The projection of P to a subset V ′ ⊆ V is denoted P[V ′ ] and is identical to P except that all components are restricted to the variables in V ′ . The projection ω[V ′ ] of a plan ω to a set V ′ ⊆ V of variables is the subsequence of actions in ω with an effect on at least one variable in V ′ .

The causal graph CG(P) for P describes how the variables depend on each other, as implicitly defined by the actions. It is defined as the directed graph CG(P) = 〈V,E〉 where for all distinct v,w ∈ V , 〈v,w〉 ∈ E if there is some action that either has a precondition on v and an effect on w or it has effects on both v and w. An action is unary if it has an effect on exactly one variable, and it is immediate that all actions must be unary if CG(P) is acyclic, and the following proposition is immediate since a shortest (cost-optimal) plan cannot have any redundant actions.

Proposition 1. Let P be a unary SAS+ instance. If ω is a shortest or shortest cost-optimal plan for P, then |ω[v]| = C(v, ω) for all v ∈ V .

A directed graph G = 〈V,E〉 is a polytree if it is acyclic and the undirected variant of it is a tree, i.e. if we ignore the direction of the edges then G must be connected and contain no cycles. The depth d(v) of a vertex v ∈ V is the length of the longest directed path from v to any sink in G.

3 Planning for Polytrees

We focus on planning for instances where the causal graph is a polytree, first deriving a bound on the complexity of costoptimal planning for such instances given that we know how many variable changes we must consider. Then we present such a bound as a function B(s, d) of the domain size and the depth, such that for every variable v and every shortest costoptimal plan ω, it holds that C(v, ω) ≤ B(s, d(v)). Finally, we combine this into our main result (Theorem 4).

3.1 Planning as CSP

We first improve a known complexity result.

Lemma 2. Let P = 〈V,A, sI, sG, c〉 be a SAS+ instance such that CG(P) is a polytree. Let B be an upper bound on C(v, ω) for all v ∈ V and all shortest cost-optimal plans ω for P. Then cost-optimal planning can be solved in time O((BsB+1 )6n), where n = ‖P‖ is the instance size.

Proof. If we know an upper bound k on the number of walks that has to be considered in any domain-transition graph (DTG), then plan satisfiability can be solved in time O((ks)6n) B¨ackstr¨om [2014]. This result uses a CSP encoding based on a tree decomposition of the causal graph, exploiting that CSP can be solved in time O(NCD2C) for tree primal graphs [Dechter and Pearl, 1989], where NC is the number of CSP variables and DC their domain size. B¨ackstr ¨om [2014] also shows how to solve cost-optimal planning this way, but no explicit complexity figure is given. However, since also cost-optimal CSP can be solved in time O(NCD2C) [Cooper and Schiex, 2004, Theorem 5.4] for tree primal graphs, it follows from the proof of Theorem 12 in B¨ackstr¨om [2014] that also cost-optimal planning can be solved in time O((ks)6n). Let B be an upper bound on the length of the subplan for any variable in a shortest costoptimal plan. Then there are at most ∑Bi=0 (s - 1)i ≤ BsB walks of length B in any DTG, so it follows that we can find a shortest cost-optimal plan in time O((BsB+1 )6n)

3.2 Bounds for Polytree Causal Graphs

In the derivation and definition of the bound function B, we need a function τ, defined such that τ(s, h) is the number of nodes in a maximal tree of height h where the root has branching factor s and all other interior nodes have branching factor s - 1. The reason for this definition will become clear later. For all s ≥ 2 and h ≥ 1, we thus have

which can be bounded from above as τ(s, h) ≤ 3(s - 1)h . We can now define the bound function B of the domain size s and the depth d as

We will show that this function is an upper bound on the number of variable changes in all shortest cost-optimal plans, and it can itself be upper bounded by a 'tower function' with d levels of exponentiation of the form

.

Lemma 3. Let P = 〈V,A, sI, sG, c〉 be a SAS+ instance with a polytree causal graph. If ω is a shortest cost-optimal plan for P, then C(v, ω) ≤ B(s, d(v)) for all v ∈ V .

We will sketch the proof of this lemma in Sec. 4, and can now state our main result.

Theorem 4 (Main result). Let P = 〈V,A, sI, sG, c〉 be a SAS+ instance such that CG(P) is a polytree with maximum depth d. If P is solvable, we can find a cost-optimal plan for it in time O((B(s, d) · sB(s,d)+1 )6 · ‖P‖).

Proof. It is sufficient to find a shortest cost-optimal plan, so the result follows from Lemmas 2 and 3.

4 Plan Lengths for Polytree Causal Graphs

In this section we will informally sketch the proof of Lemma 3 using examples (we refer the reader to the original publication [B¨ackstr¨om et al., 2018] for the full formal proof). The proof is by induction over the depth of vertices (i.e. variables) in the causal graph. Figure 1 shows an example of a polytree which is drawn such that the vertices are aligned according to depth. We will use this polytree as an example for illustrating the induction.

The base case consists of all variables at depth 0 (1-5 in the example). Since a variable v at depth 0 has no outgoing arcs, no other variables depend on it. Hence, the subplan ω[v] for this variable cannot contain any cycles, since ω is a shortest cost-optimal plan. Thus, in the worst case ω[v] is a Hamilton cycle in the DTG for v, i.e. of length s - 1. It follows that C(v, ω) ≤ s - 1 = B(s, 0) for all v such that d(v) = 0.

In the induction step, we must prove that if C(v, ω) ≤ B(s, d(v)) for all v ∈ V with d(v) ≤ d, for some d, then it also holds that C(v, ω) ≤ B(s, d(v)) for all v ∈ V with d(v) = d+1. We will explain the induction step by example, assuming the claim holds up to depth 1, i.e. we want to prove the claim for depth 2. We assume an arbitrary variable u at depth d + 1 and let v1, . . . , vm denote the incident variables of its outgoing arcs. As an example, we choose u = 9 as an arbitrary variable at this depth, so we get v1 = 2 and v2 = 7. At least one of v1, . . . , vm must be at depth d, while the others can be at any depth ≤ d. In the example we have v2 at depth 1 but v1 at depth 0. If we were to remove the outgoing arcs from u, we would partition the graph into three sets V1, V2 and U such that v1 ∈ V1, v2 ∈ V2 and u ∈ U. This partitioning is illustrated in Figure 2.

The remainder of this proof sketch is divided into three steps as in the original full proof.

Step I. Let χ1 be the sequence of defined preconditions on u in the actions in subplan ω[v1] and define χ2 analogously for v2. Also let ψ be the sequence of values that u passes, from the initial value to the goal value. We define a releasetime function r that maps the indices of χ1 and χ2 to indices of ψ, witnessing that χ1 and χ2 are subsequences of ψ. We write r1 and r2 for the restrictions of r to χ1 and χ2 respectively. We further say that r1 is minimal if every index in χ1 is mapped as early as possible in χ. Note that if there exists a release-time function for χ1, then there must also exist a unique minimal one. Figure 3 shows two different releasetime functions, r1 and r′1 , for χ1, where r′1 , but not r1, is minimal. Furthermore, the function r is minimal if both r1 and r2 are minimal.

We further note that the minimal release-time function always maps each sequence χi to the shortest possible prefix of ψ. In Figure 3 we see that r′1 maps χ1 to a shorter prefix than r1 does. Furthermore, if two consecutive elements in χ1 have the same value, then the minimal release-time function must map these to the same index in ψ. Hence, we may assume that χ1 is an alternating sequence in the worst case. Clearly, χ1 and χ2 must be subsequences of ψ in this case.

We note that the partition of V into the sets V1, V2 and U also implies a corresponding partition of the plan ω into three subplans ω[V1], ω[V2] and ω[U], where every action occurence in ω belongs to exactly one of these three subplans since all actions are unary. In Figure 2 we see that the only arc from U to V1 is from u to v1, so the only variable in V1 that depends on some variable in U is v1 and it depends only on u. Analogously, only v2 in V2 depends on u. Furthermore, no variable in V1 depend on any variable in V2 and vice versa. It follows that the subplans ω[V1] and ω[V2] are independent of each other, but both depend on the subplan ω[U]. However, since there are only arcs from u to v1 and v2, we only need to syncrhonise the subplans ω[v1] and ω[v2] with the subplan ω[u], which will be exploited later in the proof. Since ω[V1] and ω[V2] do not depend on each other, the corresponding release-time functions r1 and r2 are independent of each other, i.e. we can choose subsequences in ψ for χ1 and χ2 independently of each other. It follows that it is always possible to reorder ω into a plan ω′ that contains exactly the same action occurences as ω but where the release-time function for χ1 and χ2 is minimal. This is illustrated in Figure 4. We first split ω into ω[V1], ω[V2] and ω[U]. We retain the internal order of each of these three subplans, but reorder them with respect to each other. More precisely, we can interleave these subplans freely as long as we syncrhonise ω[v1] with

ω[u] and ω[v2] with ω[u]. In particular, we can interleave them such that the release time functions r1 and r2 are both minimal. The point of this reordering is that ω′ is a permutation of ω, so it has the same length and cost as ω, but it is easier to analyse since we know that the release-time functions are minimal.

Step II. For this step we need a slightly more complex example, so assume that variable u has four outgoing arcs to variables v1, . . . , v4, with corresponding sequences χ1, . . . , χ4 of preconditions on u. Also suppose that χ1 = 131, χ2 = 132, χ3 = 312, χ4 = 323 and ψ = 123123. We can then build a prefix tree T that contains a node for every prefix of these four sequences, and then define a minimal tree mapping rT from the nodes of T to ψ as follows. The root of the prefix tree is the empyt prefix ϵ, which we map to 0, i.e. rT (ϵ) = 0. For all other nodes n, if n = x1 . . . xm is a child of n′ in T, then n′ = x1 . . . xm-1, so we let rT (n) be the smallest index such that rT (n′ ) < rT (n) and position rT (n) in ψ has value xm. That is, rT is a witness for the earliest occurence in ψ of each prefix in T. This minimal tree mapping is unique. Note that we can always reconstruct the unique minimal release-time function from this minimal tree mapping. Furthermore, let Tmax be the maximal prefix tree with the same depth as T , i.e. it contains all possible alternating prefixes of this length. Then T must be a subtree of Tmax. Figure 5 shows Tmax in green overlayed by the subtree T in thick black lines, and the unique minimal tree mapping from T to ψ is shown with blue dashed arrows.

Step III. Let rT be the unique minimal tree mapping from T to ψ. In Figure 5, rT does not map any node in T to the second index in ψ, marked in red. Since we do not know how many such unmapped indices may exist in general, we cannot use the size of T to bound the length of ψ. However, we can use Tmax to provide such a bound. We construct a partial tree mapping r′T from Tmax to ψ such that r′T is minimal and extends rT . For each index i in ψ which is not mapped by rT , we can always find at least one unique node n in Tmax which is not in T such that if r′T is defined for n, then r′T (n) = i must hold. In the example we can choose either n = 2 or n = 12 as the node to map to index 2. Hence, the number of indices in ψ that are not mapped by R are at most as many as the number of nodes in Tmax that are not in T. Since T is a subtree of Tmax, the length of ψ is bounded by the size of Tmax (plus ≤ s - 1 actions for achieving the goal). If Tmax has height h, the size of Tmax is τ(s, h) so |ψ| ≤ τ (s, h + 1) + (s - 1). We thus get that C(u, ω) = |ψ| - 1 ≤ τ (s, h+1)+(s-1)-1 = τ (s, h+1)+s-2 ≤ τ (s, B(s, d)+ 1) + s - 2 = B(s, d + 1) which ends the induction.

5 Concluding Remarks

We have presented a polynomial-time algorithm for costoptimal planning restricted to polytree causal graphs, bounded depth, and bounded domain size. It, thus, advances the tractability frontier since previous tractability results using these restrictions also require further restrictions. Our algorithm is based on transforming cost-optimal planning into VCSP, using a transformation originally suggested by B¨ackstr¨om [2014]. The main technical result is a bound on the number of variable changes defined in terms of the depth of the causal graph and the domain size. This result is maximal in the sense that dropping the domain size bound or the depth bound size leads to an NP-hard problem. A natural open question is thus how to generalise the tractability result to larger classes of planning instances. It is not obvious what other parameter bounds would lead to tractability so it may be easier to consider larger classes of causal graphs than polytrees. The obvious generalisation is to consider causal graphs that have bounded tree-width-this is a method that have led to a large number of tractability results in many different areas of computer science, with a few examples also in planning [Brafman and Domshlak, 2006; Domshlak and Nazarenko, 2013; B¨ackstr ¨om, 2014]. The very same planning algorithm would be useful also in this case: it runs in polynomial time whenever the tree-width of the causal graph and the number of variable changes are bounded. Unfortunately, it is not at all clear how to generalise the bound on variable changes when the causal graph has bounded treewidth larger than one. Although our algorithm is polynomialtime, its running time is admittedly not impressive. However, previous tractability results like Aghighi et al. [2015] and St˚ahlberg [2017], have similar tower functions despite using more restrictions than we do. We believe that our bounds can be considerably improved by an even more careful analysis, combining these proof techniques with others to give an even more refined picture of optimal plans.

Acknowledgments

B¨ackstr¨om is partially supported by the Swedish Research Council (VR) under grant 621-2014-4086.