Novel Structural Parameters for Acyclic Planning Using Tree Embeddings

1 Introduction

Causal graphs are widely used in planning for analyzing planning instances. In particular, instances with acyclic causal graphs (which we refer to as acyclic planning) have attracted a great deal of attention. One should note that satisficing acyclic planning is PSPACE-complete [Jonsson et al., 2014], i.e. it is as hard as unrestricted propositional planning. Many tractability results for acyclic planning have appeared in the literature-examples include [Williams and Nayak, 1997; Jonsson and B¨ackstr¨om, 1998; Brafman and Domshlak, 2003; Gim´enez and Jonsson, 2008]-but they have also been utilized in decomposing planning instances into action hierarchies [Knoblock, 1994; Bacchus and Yang, 1994] and to compute domain-independent heuristics [Helmert, 2006; Katz and Domshlak, 2010]. In recent years, polytree causal graphs have become popular for defining tractable subclasses [Katz and Keyder, 2012; Katz and Domshlak, 2010; Aghighi et al., 2015; St˚ahlberg, 2017]. A directed graph is a polytree if its underlying undirected graph is a connected tree. The work on polytree causal graphs has lead to interesting work concerning for instance structural pattern heuristics [Katz and Domshlak, 2010]. The usefulness of such heuristics increases with the availability of large causal graph fragments such that cost-optimal planning can be solved in polynomial time. Graph fragments such as forks and inverted forks were used quite early in this research and have gradually evolved into more expressive types of graphs.

Due to the highly restricted structure of polytree, it is natural to try to find new tractability results that are not based on polytrees. To this end, we suggest two structural parameters up-depth and down-depth in this paper. Structural parameters based on graph representations are very common in computer science and are becoming increasingly used in artificial intelligence: examples include SAT and constraint satisfaction [Paulusma et al., 2016; Ganian et al., 2017; Gaspers and Szeider, 2013], knowledge representation [Gottlob et al., 2010], and answer set programming [Bliem et al., 2017; 2016]. An acyclic graph D has up-depth k if it can be embedded into a transitive up-tree of height k, and down-depth is defined analogously using transitive down-trees. One may note that forks have up-depth 1 and inverted forks have downdepth 1. One should also note that every directed graph has a well-defined up-depth and down-depth.

We demonstrate that our new structural parameters can be used for obtaining new tractability results: cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. Naturally, this can be viewed as an alternative proof of the fact that cost-optimal planning with (inverted) forks and bounded domains can be solved in polynomial time. The important difference between this result and polytree based classes is that our algorithm is applicable to every acyclic graph. Another related result is presented by Brafman and Domshlak [2006]. They prove that acyclic planning is tractable when both the treewidth of the causal graph and the local depth are bounded. The local depth is a bound on the number of variable changes in an optimal solution, and this parameter may be prohibitively difficult to estimate.

From a parameterized complexity view, we show that costoptimal planning with bounded down-depth and bounded domain is fixed-parameter tractable while planning with bounded up-depth is W[1]-hard. This implies that planning with bounded up-depth is computationally more expensive under standard complexity assumptions. In fact, we show that our algorithm for bounded down-depth runs in linear time with respect to the number of variables. We also show that computing the up- and down-depth is a fixed-parameter tractable problem, allowing us to compute the parameters quite efficiently, at least when they are small.

The paper is structured as follows: Section 2 contains basic definitions and Section 3 introduces our structural parameters and shows how to compute the parameters. Section 4 and Section 5 contain the algorithms for planning with bounded up- and down-width, respectively, together with the results concerning parameterized complexity.

2 Preliminaries

We refer to the handbook by Diestel (2012) for standard graph terminology. Let T be an undirected rooted tree and v ∈ V (T ). We denote by UT (v) and LT (v) the set of all ancestors respectively descendants of v in T and by UT [v] and LT [v] the sets UT (v)∪{v} and LT (v)∪{v}, respectively. We denote by Tv the subtree of T rooted at v. The depth of v in T , denoted by wT (v), is the number of vertices on the unique path from v to the root of T and the height of v in T is equal to the maximum number of vertices from v to any leaf of Tv. The depth and height of T, denoted by wT respectively hT , are the maximum depth respectively height of any vertex in T. Note that the above definitions can be naturally extended to rooted forests instead of trees, where a rooted forest is a forest consisting of a disjoint union of rooted trees. For a directed graph G we denote by ˜G its underlying undirected graph.

2.1 Sequences

Let s be a sequence. We denote by s[i] the i-th element of s for every i with 1 ≤ i ≤ |s|. We denote by cp(s) the compressed sequence of s, i.e., the sub-sequence of s obtained after removing every element that is equal to its successor in s. We call a sequence s compact if cp(s) = s. We say that a sequence s is an extension of a sequence s′ if cp(s) = s′ .

Let X be a finite set and let S be a set of sequences over X. We denote by LCSS(S) the length of a longest sequence sL (over X) such that: (S1) every sequence s ∈ S is a subsequence of sL and (S2) no sub-sequence of sL satisfies (S1). For a given integer l and set X we are interested in the maximum number, in the following denoted by TLCSS(l, |X|), such that there is a set S of sub-sequences over X each having length at most l such that TLCSS(l, |X|) = LCSS(S).

Proposition 1. Let X be a finite set and l a natural number. Then TLCSS(l, |X|) ≤ |X|l l.

2.2 Parameterized Complexity

In parameterized algorithmics [Downey and Fellows, 2013] the run-time of an algorithm is studied with respect to a parameter k ∈ N and input size n. The basic idea is to find a parameter that describes the structure of the instance such that the combinatorial explosion can be confined to this parameter. In this respect, the most favorable complexity class is FPT (fixed-parameter tractable) which contains all problems that can be decided by an algorithm running in time f(k) · nO(1) , where f is a computable function. Problems that can be solved in this time are called fixed-parameter tractable (fpt). Moreover, we say that a problem is linear-time fixed-parameter tractable if it can be solved in time f(k) · n. Aside from the complexity class FPT, we will also make use of the complexity class W[1] (proving hardness for W[1] is often used to show that a problem is unlikely to be in FPT).

2.3 Planning

Let V = {v1, . . . , vn} be a finite set of variables over a finite domain D and let D+ = D ∪ {u}, where u is a special "undefined" value not present in D. Then Dn is the set of total states and (D+)n is the set of partial states over V and D. Clearly, Dn ⊆ (D+)n . The value of a variable v in a state s ∈ (D+)n is denoted by s〈v〉 and the projection of a state s to a set of variables V ′ ⊆ V is denoted by s〈V ′ 〉. We say that a total state t over some set of variables V ′ is compatible with a partial state p over V ′ , denoted by t ∼ p if for every v ∈ V ′ either p〈v〉 = u or p〈v〉 = t〈v〉. A SAS+ instance is a tuple P = 〈V,D,A, I,G,∆〉 where V is a set of variables, D is a domain, A is a set of actions, I ∈ Dn is the initial state, G ∈ (D+)n is the (partial) goal state, and ∆ : A → Q≥0 is a cost function for the actions. Each action a ∈ A has a precondition pre(a) ∈ (D+)n and an effect eff(a) ∈ (D+)n . We will frequently use the convention that a variable has value u in a precondition/effect unless a value is explicitly specified. Let a ∈ A and s ∈ Dn . Then a is valid in s if s is compatible with pre(a). Furthermore, the result of a in s is a state t ∈ Dn defined such that for all v ∈ V , t〈v〉 = eff(a)〈v〉 if eff(a)〈v〉 ̸= u and t〈v〉 = s〈v〉 otherwise. Let s0, sℓ ∈ Dn and let ω = 〈a1, . . . , aℓ〉 be a sequence of actions (of length ℓ). Then ω is a plan from s0 to sℓ if either (i) ω = 〈〉 and ℓ = 0, or (ii) there are states s1, . . . , sℓ-1 ∈ Dn such that for all 1 ≤ i ≤ ℓ, ai is valid in si-1 and si is the result of ai in si-1. A state s ∈ Dn is a goal state if for all v ∈ V , either G〈v〉 = s〈v〉 or G〈v〉 = u. An action sequence ω is a plan for P if ω is a plan from I to some goal state. We say a plan ω is minimal for P if no proper subsequence of ω is a plan for P. The cost of a plan ω, denoted by ∆(ω), is equal to the sum of the cost of all actions in ω, i.e., ∆(ω) = ∑|ω| i=1 ∆(ω[i]). We say that ω is cost-optimal for P if there is no plan ω′ for P with ∆(ω′ ) < ∆(ω). We will consider the following computational problems for planning. Given a SAS+ instance P = 〈V, D, A, I, G, ∆〉. PLANNING is the problem of deciding whether P has a plan and COST OPTIMAL PLANNING is the problem of deciding whether P has a plan of cost at most c for some given number c ∈ Q≥0.

Let V ′ be a subset of V . For an action a ∈ A we denote by a〈V ′ 〉 the action a projected to the variables in V ′ , i.e., a〈V ′ 〉 has precondition pre(a)〈V ′ 〉 and effect eff(a)〈V ′ 〉 and we denote by A〈V ′ 〉 the set {a〈V ′ 〉 | a ∈ A}. The planning instance induced by V ′ , denoted by P[V ′ ], is the instance 〈V ′ ,D,A〈V ′ 〉, I〈V ′ 〉,G〈V ′ 〉,∆〉. Since there is a one-to-one correspondence between A and A〈V ′ 〉, we will often not distinguish between them; for instance we will say that a sequence of actions in A is a plan for P[V ′ ], meaning that the corresponding actions in A〈V ′ 〉 are a plan for P[V ′ ]. We denote by AV ′ the set of actions { a ∈ A | eff(a)〈V ′ 〉 ̸= u}. For a sequence ω of actions we denote by ω〈V ′ 〉 the restriction of ω to actions in AV ′ , i.e., ω〈V ′ 〉 is obtained from ω after removing all actions not in AV ′ . We often use v as a shortcut for {v}. For a sequence ρ of (partial) states, we denote by proj(ρ, V ′ ) the sequence 〈ρ[1]〈V ′ 〉, . . . , ρ[|ρ|]〈V ′ 〉〉. We say that a sequence ρ of total states over V ′ is compatible with a sequence ρ′ of partial states over V ′ , denoted by ρ ∼ ρ′ if |ρ| = |ρ′ | and ρ[i] ∼ ρ′ [i] for every i with 1 ≤ i ≤ |ρ|.

For a sequence of actions ω, we denote by PRu(ω, V ′ ) the sequence of preconditions of the actions in ω on the variables in V ′ , i.e., the sequence proj(〈pre(a1), . . . , pre(al)〉, V ′ ) and we denote by PR(ω, V ′ ) the sequence obtained from PRu(ω, V ′ ) after removing all states that are completely undefined. For a plan ω for P, we denote by STP(ω) the sequence of all states achieved during the execution of ω on P, including the initial and the goal state. Moreover, for two subsets V1 and V2 of V , we denote by STP(ω, V1) the sub-sequence of STP(ω) retaining only the states that were achieved before the execution of an action in AV1 , i.e., the sequence STP(ω)[α(1)], . . . , STP(ω)[α(|ω′ |)] (where α = subF〈ω, ω′ 〉 and ω′ := ω〈V1〉), and we denote by STP(ω, V1, V2) the sequence proj(STP(ω, V1), V2). We omit the subscript if the planning instance is clear from the context.

The causal graph of P, denoted by GC(P), has vertex set V and contains a directed arc from v to u if there is an action a ∈ A such that eff(a)〈u〉 ̸= u and either pre(a)〈v〉 ̸= u or eff(a)〈v〉 ̸= u. Informally, the causal graph models dependencies between planning variables given by the actions. We set amax :=maxv∈V |Av|, i.e., amax is the maximum number of actions effecting any variable.

3 Introducing Up-depth and Down-depth

In this section we will introduce our novel decompositional parameters for planning. Our parameters, which we call updepth and down-depth can be seen as natural directed versions of the well-known decompositional parameter treedepth [Nesetril and de Mendez, 2012]. The treedepth of an undirected graph H, denoted by td(H), is the smallest natural number k such that there is an undirected rooted forest F with vertex set V (H) of height at most k for which H is a subgraph of C(F), where C(F) is called the closure of F and is the undirected graph with vertex set V (F ) having an edge between u and v if and only if u is an ancestor of v in F. Informally a graph has treedepth at most k if it can be embedded in the closure of a forest of height k.

Our parameters up-depth and down-depth are now defined very similar to treedepth; the main difference is that we are using upward-closures and downward-closures instead of (undirected) closures. That is the upward-closure/downwardclosure of an undirected rooted forest F, denoted by C ↑ (F)/C ↓ (F), is the directed graph with vertex set V (F) having an edge from u to v if v is an ancestor/descendant of u in F . The up-depth/down-depth of a directed acyclic graph G is then the smallest natural number k such that there is an undirected rooted forest F with vertex set V (D) and height at most k such that D is a subgraph of C ↑ (F)/C ↓ (F). Note that our notions of up-depth and down-depth require that the graph is acyclic since the upward and downward closure of a forest is always acyclic. On the other hand every acyclic graph G has up-depth and down-depth at most |V (G)| since any acyclic graph is a subgraph of the upward and downward closure of an undirected path, whose vertices are ordered against/according to the topological ordering of G. The following theorem shows the relationship between our new parameters and treedepth.

Theorem 2. Let G be a directed acyclic graph. Then td( ˜G) ≤ min{dep↑ (G), dep↓ (G)}.

Proof. The theorem follows immediately from the observation that if a directed acyclic graph G is a subgraph of either C ↓ (F ) or C ↓ (F) of the rooted undirected forest F, then ˜G is also a subgraph of C(F ).

In order to employ the new parameters for our algorithms for planning, we first need to be able to compute them. Namely we want to be able to solve the following problem.

UP-DEPTH

Input:

A directed acyclic graph G and a natural number k.

Parameter: k

Question: Decide whether dep↑ (G) ≤ k and if so output a undirected forest witnessing this.

The corresponding problem for computing the down-depth, which we call the DOWN-DEPTH problem, is analogously defined by replacing dep↑ (G) with dep↓ (G) in the above definition.

The following theorem shows that computing updepth/down-depth is NP-complete, however, as we will see below (as it is also the case for their undirected counterpart treedepth) both parameters can be efficiently computed if the input graph has small depth, which will be sufficient for our algorithms for COST OPTIMAL PLANNING.

Theorem 3. DOWN-DEPTH and UP-DEPTH are NP -complete.

Proof Sketch. We reduce from the corresponding problem for treedepth, which is well known to be NP -complete [Bodlaender et al., 1998]. Since the proof is almost identical for DOWN-DEPTH and UP-DEPTH, we will only give it for DOWN-DEPTH. Hence let H be a connected undirected graph and let G be the directed graph obtained from H after replacing every edge {u,w} ∈ E(H) with a new vertex ve and the two arcs (u, ve) and (w, ve). One can now show that td(H) + 1 = dep↓ (G), which concludes the proof of the theorem.

We now provide our main theorem of this section showing that both up-depth and down-depth are linear-time fixedparameter tractable. The main ingredient for the proof is an interesting characterization of up-depth/down-depth in terms of a partition of the vertex set. Using this characterization, we can then show that the UP-DEPTH and DOWN-DEPTH problems can be reduced to the model checking problem of Monadic Second Order Logic, which due to a well-known theorem by Courcelle (1990) is fixed-parameter tractable parameterized by the length of the input formula and the treedepth of the input structure (in our case a directed graph). Together with Theorem 2 this then implies the result.

Theorem 4. DOWN-DEPTH and UP-DEPTH are linear-time fixed-parameter tractable.

4 Planning on Up-Trees

In this section we present our algorithm for Planning on uptrees, which shows that COST OPTIMAL PLANNING can be solved in polynomial-time for planning instances with bounded domain |D| and bounded up-depth. In the following let P = 〈V,D,A, I,G,∆〉 be a SAS+ instance, G the (acyclic) causal graph of P, and F an undirected forest with vertex set V (G) such that G is contained in the upward-closure of F . For a plan ω for P and a variable v ∈ V , we denote by δω(v) the number of times the value of v changes during the execution of ω on P. One of the crucial observations for our algorithm is that δω(v) can be bounded solely in terms of wF (v) and |D| as shown in the following lemma. Let f ↑ (x) : N → N be the function defined recursively by setting f ↑ (1) = |D| -1 and f ↑ (x + 1) = (|D| - 1)((∑xy=1 f ↑ (y)) + 1). A straightforward computation shows that f ↑ (x) ≤ (x)!(|D| - 1)x .

Lemma 5. Let ω be a minimal plan for P and v ∈ V . Then δω(v) ≤ f ↑ (wF (v)) ≤ (wF (v)!)(|D| - 1)wF (v) ).

Proof. The proof is via induction on wF (v). For the base case it holds that v is a root of F and as such does not appear in a precondition of any action effecting a variable other than v. Consequently we obtain that δω(v) ≤ |D| - 1, as required.

Towards showing the induction step, let v ∈ V and because of the induction hypothesis it holds that δω(w) ≤ f ↑ (wF (w)) for every w with wF (w) < wF (v). The main property of up-depth allowing us to bound the number of changes for v in ω is the fact that because G is contained in the upwardclosure of F, it holds that the only actions in ω having a precondition on v (other than actions effecting v) are actions that effect one of the ancestors of v in F. Since there are at most wF (v) - 1 ancestors of v in F and the number of actions in ω effecting any ancestor w of v is by the induction hypothesis at most f ↑ (wF (w)), we obtain that there are at most ∑wF (v)-1 d=1 f ↑ (d) actions in ω that have a precondition on v. Since every such precondition requires at most |D| - 1 changes to the value of v and at most |D| - 1 changes to the value of v are required by ω to get v to its goal state, we obtain δ(v) ≤ (|D| - 1)((∑wF (v)-1 x=1 f ↑ (x)) + 1) = f ↑ (wF (v)).

Theorem 6. COST OPTIMAL PLANNING can be solved in time O(|amaxwF |ℓ(wF ) ℓ(wF )(wF - 1 + |D|2 )|V |), where ℓ(i) = ∑<i j=1 f ↑ (j) ≤ f ↑ (i). Hence COST OPTIMAL PLANNING can be solved in polynomial-time if wF +|D| is constant.

Proof. We will show the theorem by providing a dynamic programming algorithm for COST OPTIMAL PLANNING that proceeds bottom-up on the forest F . The algorithm computes a set R(v) of records for every vertex v ∈ V (F), where each record (ω, c) in R(v) consists of a sequence of actions in AUF (v) and a number c ∈ Q≥0. The semantics of a record is as follows. (ω, c) ∈ R(v) if and only if:

(R3) c is the minimum cost of ω+〈LF [v]〉, where ω+ is a cost-optimal plan for P[UF (v) ∪ LF [v]] such that ω+〈UF (v)〉 = ω.

Note that |ω| ≤ ℓ(wF (v)) for any sequence ω satisfying (R1). Before we show how to construct the set of records for every node of F , let us briefly comment on how we obtain a solution for P once we have computed the set of records for every node. Since a solution for F can be obtained by putting together solutions for each connected component of F (since the planning instances induced by different components of F are independent), we can assume that F is a tree with only one root r. Because of the semantics of the records, we have that R(r) contains at most one record and if it contains a record then the record is of the form (〈〉, c), where c is the minimum cost of a plan for P. Moreover if R(r) = ∅ then we know that P does not have a plan.

We now show how to compute the set of all records for every vertex v of F , via a bottom-up dynamic programming algorithm starting at the leaves of F. To achieve this it is sufficient to show how the set of all records can be computed: (A) for a leaf of F and (B) for an internal vertex v of F provided that the sets of all records for all children of v in F have already been computed. Towards (A), let l be a leaf of F. Because of the semantics of a record, we can compute the set R(l) of records for l by enumerating all sequences ω of actions in AUF (l) that satisfy (R1), checking for each of them whether they satisfy (R2) and if so computing the number c as defined in (R3). Checking whether ω satisfies (R2) can be achieved in time O(|ω||UF (l)|) by simply executing ω on P[UF (l)]. The following claim shows that the number c satisfying (R3) can also be computed efficiently.

Claim 1. Let ω be a plan for P[UF (l)], then the minimum cost c of ω+〈l〉, where ω+ is a cost-optimal plan for P[UF [l]] such that ω+〈UF (l)〉 = ω can be computed in time O(|ω||D|2 ).

Hence the total time required to check whether ω satisfies (R2) and to compute the number c satisfying (R3) is at most O(ℓ(wF (l))(wF - 1 + |D|2 )). Moreover since there are at most |amaxwF (l)|ℓ(wF (l)) such sequences satisfying (R1), we obtain O(|amaxwF (l)|ℓ(wF (l)) ℓ(wF (l))(wF - 1 + |D|2 )) as the total running time required to compute R(l).

Towards (B), let v be an internal node with children v1, . . . , vr and assume that the sets of records for v1, . . . , vr have already been computed. The following claim, characterizes the existence of a record (ω, c) ∈ R(v).

Claim 2. Let ω be a sequence of actions in AUF (v) satisfying (R1) and (R2). Then (ω, c) ∈ R(v) if and only if c is the minimum number such that for every i with 1 ≤ i ≤ r there is a record (ωv, ci) ∈ R(vi), where ωv is any sequence of actions in AUF [v] (satisfying (R1) and (R2)) such that ω = ωv〈UF (v)〉, and c = (∑li=1 ci) + ∆(ωv〈v〉).

With the help of the above claim we now show how to compute the set of records for an internal node v. The computation of the set of records for v is achieved in two steps.

First we compute the set R that contains every pair (ω, c) such that for every i with 1 ≤ i ≤ r there is a ci with (ω, ci) ∈ R(vi) and moreover c = ∑ri=1 ci. The computation of R can be done by "joining" the sets of records R(v1), . . . ,R(vr) one by one in time that is linear in the maximum number of records in any R(vi), the maximum length of any sequence ω with (ω, c) ∈ R, and the number r of children of v, i.e., the computation of R can be achieved in time O(|amaxwF (vi)|ℓ(wF (vi)) ℓ(wF (vi))r).

In the second step we aggregate the records in R, which represent sequences of actions ω effecting variables in UF (v) ∪ {v}, onto sequences of actions that effect only the variables in UF (v). Note that the correctness of the computation of R(v) follows immediately from Claim 2. Moreover R(v) can be computed from R using a simple run of all (ω, c) ∈ R in time O(|amaxwF (vi)|ℓ(wF (vi)) ℓ(wF (vi))r). The total running-time of the algorithm is then the sum of the running-times over all nodes of F, which is at most O(|amaxwF |ℓ(wF ) ℓ(wF )(wF - 1 + |D|2 )|V |).

The above algorithm shows that COST OPTIMAL PLANNING is solvable in polynomial-time if both the domain D and the depth wF of F are bounded by a constant. It is natural to ask whether the algorithm can be improved to a fixed-parameter algorithm parameterized by D and wF . The following theorem shows that this is unlikely by showing that already PLANNING is W[1]-hard parameterized by wF even if |D| = 2.

Theorem 7. PLANNING is W[1]-hard parameterized by wF even for planning instances with binary domain.

5 Planning on Down-Trees

In this section we show that COST OPTIMAL PLANNING is fixed-parameter tractable parameterized by domain size and down-depth. In the following let P = 〈V,D,A, I,G,∆〉 be a SAS+ instance, G the (acyclic) causal graph of P, and F be an undirected forest with vertex set V (G) such that G is contained in the downward-closure of F. The crucial observation behind our algorithm is the following lemma, which shows that we can assume that the length of the sequence of states of the ancestors of a variable v in F that are required by actions effecting a variable v or its descendants in a plan for P can be bounded in terms of only |D| and hF (v). This allows us later to remember only a limited amount of information about all sub-plans for the descendants of v that are contained in a plan for P; this is because if the sequence of such states has bounded length then so does the sequence of required preconditions of the actions effecting v or descendants of v. Let f ↓ (x) : N → N be the function defined recursively by setting f ↓ (1) = |D| - 1 and f ↓ (x) = (TLCSS(f ↓ (x - 1), |D|wF -x ) + 1)|D|.

Lemma 8. Let ω be a plan for P. Then there is a plan ω′ for P whose cost is at most the cost of ω such that for every v ∈ V it holds that:

Proof Sketch. We will transform ω into ω′ using a bottomup procedure starting at the leaves of F. Namely, we will start by showing how the transformation procedure is applied to the leaves of F and then under the assumption that the transformation has already been applied for all children of an internal node v of F , we will apply the transformation to v.

Hence let ω be the given plan and v be a leaf of F. Since v does not appear in a precondition of an action that does effect a variable other than v, it follows that there is no reason to set v to a value that it had before. Hence if |ω〈v〉| > |D| - 1 then ω〈v〉 contains unnecessary actions that can be removed from ω to obtain ω′ . But then |ω′ 〈v〉| ≤ |D| - 1, which implies in particular that |cp(ST(ω′ , LF [v], UF [v]))| ≤ |ST(ω′ , LF [v], UF [v])| = |ω′ 〈v〉| ≤ |D| -1 = f ↓ (1). Hence ω′ satisfies (P1) for the node v and it also satisfies (P2) since we only removed actions from ω.

Towards showing the transformation of ω into ω′ for an internal node of F , let v be an internal node of F with children v1, . . . , vr and let ω′ be the plan obtained from ω after we have already applied the transformation for all descendants of v in F . Then |cp(ST(ω′ , LF [u], UF [u]))| ≤ f ↓ (hF (u)) for every u ∈ LF (v). We now show how to transform ω′ such that it satisfies (P1) and (P2) also for the node v.

Let X be the set consisting of all total states of the variables in UF [v]. Then s := ST(ω,LF (v),UF [v]) and si := cp(ST(ω′ ,LF [vi],UF (vi))) for every i with 1 ≤ i ≤ r are sequences over X. Let S be the set {s1, . . . , sr}. Then because ω′ already satisfies (P1) for all children of v, we have that |si| ≤ f ↓ (hF (v) - 1). Also s satisfies (S1) for the set S of sequences (by definition). Let s′ be a subsequence of s satisfying (S1) and (S2) for S. Then because of Proposition 1, s′ has length at most TLCSS(f ↓ (hF (v) - 1), |X|). We show now that by reordering the actions effecting variables in LF (v), we can transform ω′ into a plan ω′′ such that cp(ST(ω′′ ,LF (v),UF [v])) = s′ . Informally, we obtain ω′′ from ω′ by aligning the action sequences ω〈LF [vi]〉 with the first occurrence of si in s′ . By doing so we ensure that ω′′ 〈LF [vi]〉 = ω′ 〈LF [vi]〉 and all preconditions of the actions in ω′′ 〈LF [vi]〉 on UF [v] are still satisfied, which implies that ω′′ is still a plan for P. Then cp(ST(ω′′ ,LF (v),UF [v])) = s′ and hence ω′′ satisfies (P2) and moreover |cp(ST(ω′′ , LF (v), UF [v]))| = |s′ | ≤ TLCSS(f ↓ (hF (v) - 1), |X|). It hence only remains to deal with the actions in Av, which can be done by showing that at most (|D|-1)(|s′ |+1) of those need to appear in ω, which implies |cp(ST(ω, LF [v], UF [v]]))| ≤ |s′ |+(|s′ |+1)(|D|-1) ≤ (|s′ | + 1)|D| ≤ f ↓ (hF (v)).

Since the actions effecting a variable v can only have preconditions on the ancestors of v in F , it holds that amax can be bounded only in terms of |D| and dF , which implies that our algorithm for COST OPTIMAL PLANNING presented below runs in linear-time w.r.t. the number of variables of P.

Theorem 9. COST OPTIMAL PLANNING can be solved in time O((|D|wF +1)2f ↓ (hF ) f ↓ (wF )|V |amaxwF ) and is hence linear-time fixed-parameter tractable parameterized by wF and |D|.

Proof. Similar to the algorithm given in Theorem 6 we will provide a dynamic programming algorithm for COST OPTIMAL PLANNING that proceeds bottom-up on the forest F. That is we will compute a set R(v) of records for each node of F, where a record is a pair (ρ, c) consisting of a compact sequence ρ of total states on the variables in UF [v] of length at most f ↓ (hF (v)) and c ∈ Q≥0. For a variable v ∈ V and a sequence ρ of total states over some set of variables containing v, we denote by cp(ρ, v) the sequence obtained from ρ after removing every element whose position is in { i | ρ[i]〈v〉 = ρ[i +1]〈v〉 }, i.e., we compress ρ w.r.t. changes of v.

For a vertex v ∈ V (F) and a compact sequence ρ of total states on the variables in UF [v], we say that a sequence ω of actions in ALF [v] is compatible with ρ if:

• (C1) ω is a plan for P[LF [v]].
• (C2) For every i with 1 ≤ i ≤ |ωv|, where ωv := ω〈v〉, we have that pre(ωv[i])〈UF [v]〉 ∼ cp(ρ, v)[i] and eff(ωv[i])〈v〉 = cp(ρ, v)[i +1]〈v〉. Moreover, |ωv| = |cp(ρ, v)| - 1.
• (C3) There is an extension ρ′ of some sub-sequence of ρ such that ρ′ ∼ PR(ωR, UF [v]), where ωR := ω〈LF (v)〉.

Intuitively (C2) ensures that the sequences of changes to variable v resulting from ω is modeled exactly by proj(ρ, v) and moreover the preconditions of the actions in ω used to achieve these changes are compatible with the sequence of states of the variables in UF [v] given by ρ. (C3) ensures that the sequence of preconditions on the variables in UF [v] that are required by the actions in ωR := ω〈LF (v)〉 are contained in ρ.

The semantics of a record is as follows. (ρ, c) ∈ R(v) if and only if ρ is compact, |ρ| ≤ f ↓ (hF (v)) and c is the minimum cost of any sequence ω of actions (from ALF [v]) that is compatible with ρ; if no such plan exists then (ρ, c) /∈ R(v). Intuitively, the set R(v) of records contains the information about all cost-optimal plans ω for P[LF [v]] whose sequence of required preconditions on the variables in UF [v], i.e., the sequence PR(ω, UF [v]), can be satisfied by a given sequence ρ of total states on the variables in UF [v] of length at most f ↓ (hF (v)). It then follows from Lemma 8 that it is sufficient to only consider sequences ρ of this length since it shows the existence of a cost-optimal plan having Property (P1).

It is now easy too see how to obtain a solution from the sets of records (see also the proof of Theorem 6). We will hence skip this part and come directly to the computation of the records for (A) a leaf node and (B) an internal node of F.

Towards (A), let l be a leaf of F. Then the following claim, which is a special case of Claim 5 below, characterizes the existence of a record (ρ, c) in R(l).

Claim 3. Let ρ be a compact sequence of total states on the variables in UF [l] of length at most f ↓ (1) = |D| - 1. Then (ρ, c) ∈ R(v) if and only if c is the cost of a cost-optimal plan ωv for P[v] that satisfies (C2) w.r.t. ρ.

See Claim 5 for a proof of the above claim. Because of the above claim, we can compute the set R(l) of records for l by enumerating all compact sequences ρ of total states of the variables in UF [v] of length at most |D| -1 and for each such sequence ρ we compute the cost of a cost-optimal plan ωv for P[v] that satisfies (C2) w.r.t. ρ. The following claim shows that this can be achieved in time O((|D| - 1)amaxwF ) (the claim even shows a more general statement that we will use for the computation of the records for inner nodes later on).

Claim 4. Let v be a node of F and ρ be a (compact) sequence of total states on the variables in UF [v]. Then a cost-optimal plan for P[v] that satisfies (C2) w.r.t. ρ can be computed in time O(|ρ|amaxwF (v)).

Since there are at most (|D|wF + 1)|D|-1 compact sequences of total states of the variables in UF [v] of length at most |D| - 1 and using the above claim we need time at most O((|D| - 1)amaxwF ) for every such sequence, we obtain O((|D|wF +1)|D|-1 (|D| -1)amaxwF ) as the total time required to compute R(l).

Towards (B), let v be an internal node with children v1, . . . , vr. The following claim, which is a generalization of Claim 3, characterizes the existence of a record (ρ, c) ∈ R(v).

Claim 5. Let ρ be a compact sequence of total states on the variables in UF [v] of length at most f ↓ (hF (v)). Then (ρ, c) ∈ R(v) if and only if c is the minimum number satisfying c ≥ cv + ∑ri=1 ci, where:

1. cv is the minimum cost of a plan ωv for P[v] that satisfies (C2) w.r.t. ρ and
2. for every i with 1 ≤ i ≤ r, ci is the minimum number such that there is a record (ρi, ci) ∈ R(vi) such that cp(proj(ρi, UF [v])) is a sub-sequence of ρ.

Because of the above claim, we can compute the set R(v) of records by enumerating all compact sequences ρ of total states of the variables in UF [v] of length at most f ↓ (hF (v)) and for each such sequence ρ computing cv defined by (1) and c1, . . . , cr defined by (2). Hence let ρ be such a compact sequence of total states for the variables in UF [v] of length at most f ↓ (hF (v)). Because of Claim 4, cv can be computed in time O(f ↓ (hF (v))amaxwF (v)). Moreover, we can compute ci by finding the minimum c′ such that there is a record (ρ′ , c′ ) ∈ R(vi) and cp(proj(ρ′ ,UF [v])) is a sub-sequence of ρ. A straightforward analysis then shows that the total running of the algorithm is at most O((|D|wF + 1)2f ↓ (hF ) f ↓ (wF )|V |amaxwF ).

6 Conclusion

We view this paper as an initial step towards a better understanding of acyclic planning based on exploiting structural parameters on the causal graph. There are a few algorithms based on bounding the treewidth reported in the literature [Brafman and Domshlak, 2006; B¨ackstr¨om, 2014; Domshlak and Nazarenko, 2013]. The most relevant in our context is the algorithm by Brafman and Domshlak. A shortcoming with their algorithm is that the number of variable changes must be somehow estimated and this is typically a non-trivial task. In the case of up-trees and down-trees, we do have bounds on the number of variable changes (Lemma 5 and Lemma 8). A natural step would thus be to obtain bounds for the number of variable changes for causal graphs with bounded treewidth. How to do this is, unfortunately, highly unclear. Another way forward may be to generalize our results to other structural parameters such as treedepth. This is probably easier than trying to approach treewidth directly.