The Role of Macros in Tractable Planning over Causal Graphs

1 Introduction

Most successful planners exploit structure in a planning domain to generate valid plans. In particular, factored planners exploit independence within a domain to decompose the domain into several subproblems that can be solved independently and combined to produce a global plan. Hierarchical planners factor domains into a hierarchy of increasingly abstract subproblems [8; 9]. Other factored planners solve each subproblem separately and coordinate the solutions to produce a coherent global plan [1; 4; 6; 10].

The causal graph underlying a planning domain appears to capture relevant information about domain structure. Jonsson and B¨ackstr¨om [7] proved that plan existence is polynomial in a class of domains with acyclic causal graphs, although the plans may have exponential length. Brafman and Domshlak [3] designed a polynomial-time algorithm for plan generation in domains whose causal graphs are polytrees with bounded indegree. Helmert [5] used causal graph analysis to design an efficient heuristic for planning.

We present a novel algorithm for plan generation in a subclass of domains with unary operators and acyclic causal graphs. Just like other factored planners, the algorithm decomposes a planning domain into several subproblems. However, unlike other planners, partial plans generated in a subproblem are stored in memory as macros. In subsequent subproblems, the algorithm retrieves macros from memory and uses them as part of the solution. We show that the algorithm is complete, i.e., it always generates a plan if one exists. In addition, the algorithm is optimal for a subclass of domains.

Our algorithm takes a dynamic programming approach to planning: instead of solving the same subproblem repeatedly, solve the subproblem once and cache the resulting partial plan in memory. Whenever the solution is needed, retrieve the partial plan frommemory. In many domains, this approach dramatically reduces the complexity of generating valid plans. In addition, macros generated in one domain can be stored and reused in similar domains. If approximation techniques are used that require backtracking, macros can retain the solution to some subproblems when a deadend is reached.

Helmert [5] showed that the structure of a planning domain becomes much more explicit when the domain is represented using multi-valued variables. Since we share this view and want to exploit structure, we use the SAS+ formalism [2] to represent planning domains using multi-valued variables. We show that for a subset of domains in our class, our algorithm runs in polynomial time. Experimental results demonstrate the utility of our algorithm and verify theoretical results.

Brafman and Domshlak [4] suggested that factored planning is likely to work well in domains with limited local depth whose causal graph has limited tree-width. Informally, the local depth is the minmax number of times any state variable has to change its value on a valid plan. Our algorithm provably solves Tower of Hanoi in polynomial time, a domain whose local depth is exponential in the number of state variables and whose causal graph has maximal tree-width. The algorithm computes the transitive reduction of the causal graph, which often has much smaller tree-width. In addition, exponential length plans can be expressed using relatively few macros, drastically reducing the local depth.

2 Notation

We define a SAS+ planning domain instance as a tuple P = 〈V, s0, c∗, A〉, where:

• V = {v1, . . . , vn} is a set of state variables, each with finite domain D(vi). Let DC = ×vi∈CD(vi) be the joint domain of a subset C ⊆ V of variables. A context c ∈ DC is an assignment of values to variables in C; c assigns the value c[vi] ∈ D(vi) to each vi ∈ C. A capitalized context denotes its associated subset of variables. A state s ∈ DV assigns a value to each variable in V.

• s0 is an initial state.
• c∗ is a goal context.
• A = {a1, . . . , am} is a set of operators of the form ak = 〈prek, postk, prvk〉, where the contexts prek, postk, and prvk denote the pre-, post- and prevail-condition of operator ak, respectively. For each operator ak ∈ A, Prek = Postk and Prek ∩ Prvk = ∅.

We define two operations on contexts. Let fW(c) be the projection of context c onto the subset W ⊆ V of state variables. The result of fW(c) is a context x such that X = C∩W and x[vi] = c[vi] for each vi ∈ X. Also, let c⊕w be the composition of contexts c and w. The result of c ⊕w is a context x such that X = C ∪W, x[vi] = w[vi] for each vi ∈ W and x[vi] = c[vi] for each vi ∈ C-W. Note the asymmetry; the right operand overrides the values of the left operand.

An operator ak ∈ A is applicable in state s if fPrek (s) = prek and fPrvk (s) = prvk . The result of successfully applying ak in state s is s ⊕ postk. We add a dummy operator a∗ to A whose prevail-condition equals the goal context c∗.

In this paper, we study the restricted class of SAS+ domains that satisfy the following two definitions:

Definition 2.1 A planning domain P has unary operators if, for each operator ak ∈ A, |Prek| = 1.

For a planning domain with unary operators, we can form the set Ai = {ak ∈ A | Prek = {vi}} of operators that affect state variable vi ∈ V. The causal graph of a planning domain with unary operators is a graph with one node per state variable. There is a directed edge between state variables vj and vi if there is an operator ak ∈ Ai such that vj ∈ Prvk.

Definition 2.2 A planning domain P is tree-reducible if its causal graph is acyclic and the transitive reduction of the causal graph is a tree, i.e., weakly connected with no undirected cycles and with all edges pointing towards the root.

The transitive reduction of a graph only retains edges necessary to maintain connectivity, and is unique for acyclic graphs. Figure 1 illustrates the causal graph and its transitive reduction for a planning problem in our restricted class.

3 A planning algorithm

We present an algorithm that uses macros to solve planning domains in our restricted class. The algorithm divides a planning domain into n subproblems Pi, i = 1, . . . , n. Let Ci denote the set of state variables of subproblemPi. Ci contains vi as well as all ancestors of vi in the causal graph. Without loss of generality, assume that v1, . . . , vn is a topological sort of the nodes. Since the transitive reduction graph is a tree, vn is a descendant of each other node, so Cn = V, and Pn corresponds to the original domain P. Our algorithm solves the subproblems bottom-up starting with P1.

Let Mi be the set of macros that our algorithm generates in subproblem Pi, and let Pai ⊂ V be the set of parent nodes of vi in the transitive reduction of the causal graph. The set of operators of subproblem Pi is Oi = Ai ∪ (∪vj∈PaiMj), i.e., operators that affect vi and macros generated in parent subproblemPj for each parent node vj ∈ Pai.

Definition 3.1 In subproblem Pi, a macro is a tuple mi = 〈cxi , op, cyi 〉, composed of an initial context cxi , an operator sequence op ∈ O∗ i , and a goal context cyi .

We use superscript to distinguish between contexts that assign values to the same subset of state variables, in this case Ci. A macro is associated with a specific initial context even if its operator sequence could be applied in other contexts.

The idea of introducingmacros in subproblemPi is to capture all relevant subplans involving state variable vi and its ancestors. A subplan is relevant precisely when it satisfies the prevail-condition of an operator that affects a descendant of vi. To determine relevant subplans, we project the prevailconditions of such operators onto Ci. Let Zi be the set of contexts z, |Z| ≥ 1, that equal the projected prevail-condition fCi (prvk) of some operator ak ∈ Aj , j > i.

Our algorithm constructs the domain graph of Ci in which nodes are contexts in DCi . Let the initial context be fCi (s0), the initial state projected onto Ci. When we visit a context ci, we add edges to the graph for each operator ak ∈ Ai such that prek = ci[vi]. For each parent vj ∈ Pai, we determine the set of macros mj = 〈fCj (ci), op, cj〉 ∈ Mj such that fPrvk (cj) = fCj (prvk). Each such macro starts in ci and ends in a context that satisfies the prevail-condition of ak.

Since the transitive reduction of the causal graph is a tree, the parent nodes of vi have no common ancestors. Consequently, applying a macro generated in parent subproblemPj has no impact on the values of state variables in other parent subproblems. To achieve the prevail-condition of ak, we can apply the macros of parent subproblems in any order. For each combination of parent macros, we add an edge from ci to cxi in the domain graph, where cxi is the context that results from applying each of the parent macros followed by ak. The weight of the edge equals the total length of the operator sequences of the macros plus one, the cost of applying ak.

We use Dijkstra's algorithm to traverse the domain graph in order of shortest paths. We only add nodes and edges to the graph as necessary, never representing the complete graph. Consequently, the algorithm only visits contexts that are reachable from fCi (s0). For each context, we record the shortest operator sequence for reaching it from fCi (s0). Dijkstra ensures that the algorithm always finds the shortest operator sequence in O∗ i for reaching a context.

At a context ci, we use the projected prevail-conditions to determine macros. We find each projected prevail-condition z ∈ Zi such that either vi /∈ Z or z[vi] = ci[vi]. For each parent vj ∈ Pai, we find each macro mj = 〈fCj (ci), op, cj 〉 ∈ Mj such that fZ(cj) = fCj (z). For each combination of parent macros, let cxi be the context that results from applying the parent macros starting in ci, and let opm ∈ O∗ i be

Algorithm 1: MACROPLANNER(P)

1 for each i = 1, . . . , n 2 Ci ←set of vi and its ancestors 3 Mi ← ∅ 4 L← list containing projected initial state fCi (s0) 5 while L is non-empty 6 ci ← remove first context in L 7 construct the domain graph of Ci starting at ci 8 H ←hash table mapping contexts to operator sequences 9 run Dijkstra and record macros from ci in H 10 for each 〈cxi , op〉 ∈ H 11 append the macro 〈ci, op, cxi 〉 to Mi 12 if cxi not previously visited 13 append cxi to L 14 if no macro generated to projected goal context 15 stop; there is no valid plan

the corresponding sequence of macros. Let opc ∈ O∗ i be the shortest operator sequence for reaching ci from fCi (s0), and let 〈opc, opm〉 denote opc followed by opm. If 〈opc, opm〉 is the shortest operator sequence for reaching cxi so far, generate a macro 〈fCi (s0), 〈opc, opm〉, cxi 〉 in Mi, replacing any previous macro to cxi . The algorithmmay construct a macro from a context to itself with operator sequence length 0.

For each context ci such that ci is the goal context of any macro generated by our algorithm, we repeat Dijkstra with ci as the initial context. If it is not possible to reach the projected goal context fCi (c∗) from ci, we can remove all macros whose goal context equals ci. If it is not possible to reach the projected goal context from the projected initial state, there exists no valid global plan.

Algorithm 1 summarizes our planner for domains in the restricted class. To ensure constant-time lookup, we use hash tables to store operators, projected prevail-conditions and macros. In subproblem Pn, Cn = V, so the projected initial state fV(s0) = s0 corresponds to the initial state itself. The only projected prevail-condition is that of the dummy operator a∗, which equals fV(c∗) = c∗. Any macro in Mn starts in s0 and ends in a state s such that fC∗ (s) = c∗. Thus, the macro in Mn with shortest operator sequence corresponds to the optimal global plan.

3.1 Example

We illustrate our algorithm using an example domain. Let V = {v1, . . . , v5} with D(vi) = {0, 1} for each vi ∈ V. Let the initial state be s0 = (0, 0, 0, 0, 0), and let the goal context be c∗ = (v3 = 0, v4 = 0, v5 = 1). Assume that the causal graph of the domain is the one illustrated in Figure 1, and that there are two operators in A5:

Assume that M3 and M4 contain the following macros:

where len(opi) = 1 for i = 1, 3, . . . , 6 and len(op2) = 2.

Figure 2 illustrates the domain graph for subproblem P5 that our algorithm constructs. The algorithm starts in the projected initial state (0, 0, 0, 0, 0). There is one operator in A5 whose pre-condition equals v5 = 0, namely a15. Two macros in M3, m13 and m23 , satisfy the prevail-condition v3 = 1 of a15 . One macro in M4, m14 , satisfies the prevail-condition v4 = 1 of a15. That gives us two possible combinations of parent macros: 〈m13 ,m14 〉 and 〈m23 ,m14 〉. Applying 〈m13 ,m14 〉 followed by a15 has total length 3 and results in the state (0, 0, 1, 1, 1). Applying 〈m23,m14〉 followed by a15 has total length 4 and results in the state (1, 0, 1, 1, 1). The algorithm adds the corresponding edges and nodes to the domain graph.

The only projected prevail-condition in Z5 is that of the dummy operator a∗, which equals the goal context c∗. At (0, 0, 1, 1, 1), there is one macro in M3, m33 , that satisfies v3 = 0, and one macro in M4, m24, that satisfies v4 = 0. The only possible combination of parent macros is 〈m33 ,m24 〉 with total length 2 and resulting in state (0, 0, 0, 0, 1). Consequently, the algorithm adds a macro from (0, 0, 0, 0, 0) to (0, 0, 0, 0, 1) with operator sequence length 5. At (1, 0, 1, 1, 1), the only combination of parent macros that satisfy c∗ is 〈m43, m24〉, resulting in a macro from (0, 0, 0, 0, 0) to (1, 0, 0, 0, 1) with length 6. At (0, 0, 1, 1, 1), it is also possible to apply operator a25 , resulting in the state (0, 0, 1, 1, 0), but that does not lead to a state satisfying a projected prevailcondition. Note how the algorithm never represents most of the 25 = 32 possible states.

4 Completeness and optimality

In this section, we prove that our algorithm is complete, i.e., it always generates a valid plan if one exists. In addition, our algorithm is optimal, i.e., it always generates the shortest possible valid plan.

Definition 4.1 A context ci matches a projected prevailcondition z ∈ Zi if fZ(ci) = z.

Definition 4.2 Let cxi →i cyi denote that there exists an operator sequence in O∗ i from a context cxi to a context cyi .

Let Gi, i = 1, . . . , n, be the subset of contexts that appear either as the initial context or the goal context of at least one macro inMi. In other words, for each context cxi ∈ Gi, there exist op ∈ O∗ i and cyi ∈ DCi such that 〈cxi , op, cyi 〉 ∈ Mi or 〈cyi , op, cxi 〉 ∈ Mi.

First, we prove that the macros generated by our algorithm correspond to the shortest operator sequences for reaching a context that matches a projected prevail-condition.

Lemma 4.3 For each context cxi ∈ Gi and each context cyi , if cxi →i cyi and cyi matches a projected prevail-condition z ∈ Zi, our algorithm generates a macro 〈cxi , op, cwi 〉 ∈ Mi such that cwi matches z and such that op ∈ O∗ i is part of a shortest operator sequence from cxi to cyi .

Proof By induction on i. For i = 1, the set of applicable operators is O1 = A1. Since |Z| ≥ 1 for each z ∈ Z1, a context cy1 matches z if and only if cy1 = z. Dijkstra is guaranteed to find a shortest path to any context that is reachable from cx1, corresponding to an operator sequence in A∗1. Hence, if cx1 →1 cy1 and cy1 matches z, our algorithm generates a macro 〈cx1 , op, cy1 〉 ∈ M1 such that op ∈ O∗ 1 is a shortest operator sequence from cx1 to cy1 .

For i > 1, if |Pai| = 0, the proof is analogous to i = 1. For |Pai| > 0, we first treat the case that vi ∈ Z and cxi [vi] = z[vi]. If cxi matches z, the algorithm generates a macro 〈cxi , ∅, cxi 〉 ∈ Mi, and trivially ∅ is part of a shortest operator sequence from cxi to cyi . Otherwise, for some parent nodes vj ∈ Pai, it must be that fCj (z) ∈ Zj. Since our algorithm only uses macros in Mj to change the values of state variables in Cj, it follows that fCj (cxi ) ∈ Gj for each such vj ∈ Pai. We can remove any operators not affecting state variables inCj from the operator sequence cxi →i cyi to obtain fCj (cxi ) →j fCj (cyi ). Since cyi matches z, it must be that fCj (cyi ) matches fCj (z).

By hypothesis of induction, for each such parent node vj ∈ Pai, our algorithm generates a macro 〈fCj (cxi ), opj, cj〉 ∈ Mj such that cj matches fCj (z) and opj is part of a shortest operator sequence from fCj (cxi ) to fCj (cyi ). As a consequence, our algorithm generates a macro 〈cxi , op, cwi 〉 ∈ Mi, where cwi is the context that results from applying all such parent macros in sequence. Since the goal context cj of each parent macro matches fCj (z), it follows that cwi matches z. Since opj is part of a shortest operator sequence from fCj (cxi ) to fCj (cyi ), it follows that op is part of a shortest operator sequence from cxi to cyi .

In case vi ∈ Z and cxi [vi] ̸= z[vi], the operator sequence cxi →i cyi must include operators in Ai to change the value of vi from cxi [vi] to z[vi]. Our algorithm adds edges from cxi for each operator ak ∈ Ai such that prek = cxi [vi]. For some parent nodes vj ∈ Pai, fCj (prvk) ∈ Zj, and we know that fCj (cxi ) ∈ Gj. For each context cj such that fCj (cxi ) →j cj and that matches fCj (prvk ), by induction our algorithm generates a macro 〈fCj (cxi ), opj, cwj 〉 ∈ Mj such that cwj matches fCj (prvk ) and opj is part of a shortest operator sequence from fCj (cxi ) to cj .

As long as the projection onto Cj remains within Gj for each parent node vj ∈ Pai, our algorithm is guaranteed to add edges for each applicable operator ak ∈ Ai. If an operator sequence achieves the prevail-condition prvk of an operator ak ∈ Ai at a context cwj /∈ Gj, it follows by induction that our algorithm generates a macro to a context that matches prvk and that is on the shortest path to cwj . Thus, it is never possible to construct a shorter path from cxi to cyi by leaving Gj. In particular, whatever context we use to achieve the prevail-condition of the last operator in Ai, there is a context on the shortest path whose projection onto Cj is in Gj . As a result, our algorithm generates a path in the domain graph from cxi to a context cwi such that cwi [vi] = z[vi] and cwi is on the shortest path from cxi to cyi . Since fCj (cwi ) ∈ Gj for each parent node vj ∈ Pai, we can use the reasoning from the case cxi [vi] = z[vi] to prove the lemma.

In case vi /∈ Z, it is not necessary to change the value of vi to satisfy z. This is analogous to the case vi ∈ Z, cxi [vi] = z[vi]. However, it is possible to construct tasks such that the optimal plan satisfies z in a context that assigns a different value to vi. For this reason, our algorithm constructs macros to contexts that match z for each value of vi. In this case, the proof is analogous to the case vi ∈ Z, cxi [vi] ̸= z[vi].

Theorem 4.4 (Completeness and optimality) If there exists a valid global plan, our algorithm generates the optimal global plan.

Proof The set of state variables of subproblem Pn is Cn = {v1, . . . , vn} = V. Unless Mn is empty, at least one macro must start at the projected initial state fV(s0) = s0, in which case s0 ∈ Gn. The only projected prevail-condition of subproblem Pn is that of the dummy operator a∗, which equals fV(c∗) = c∗. Any valid global plan is a sequence of operators from s0 to a state s that matches c∗, which means that s0 →n s. For each such state s, it follows from Lemma 4.3 that our algorithm generates a macro 〈s0, op, sw 〉 ∈ Mn such that sw matches c∗ and op is part of a shortest operator sequence from s0 to s. One of these macros must correspond to the optimal global plan.

5 Complexity

In subproblem Pi, the complexity of generating macros is polynomial in the size of the domain graph that our algorithm constructs. In the worst case, the size of the domain graph is exponential in the number of ancestors of vi. In many cases, however, the size of the domain graph is much smaller. In particular, there is one case for which the complexity of our algorithm is provably polynomial.

Theorem 5.1 Assume that for each i = 1, . . . , n, the prevailcondition of each operator in Ai specifies a value for each ancestor of vi. Then the proposed algorithm runs in polynomial time with complexity O(|V||A|3 ).

Proof For each value d ∈ D(vi) in the domain of vi, let Adi = {ak ∈ Ai | postk = d} be the set of operators that change the value of vi to d. Since prevail-conditions specify a value for each ancestor, it follows that vi ∈ Z for each z ∈ Zi. Let Z d i = {z ∈ Zi | z[vi] = d} be the set of projected prevail-conditions that specify the value d for vi. Any context in the domain graph that specifies the value d for vi has to either match the prevail-condition of an operator in Adi or a projected prevail-condition in Z d i . Since each prevailcondition specifies values for each preceding state variable, only a single context matches each prevail-condition. The number of projected prevail-conditions is bounded by the number of operators, so the number of nodes in the domain

The complexity of Dijkstra is quadratic in the number of nodes in the domain graph, or O(|A|2 ). We may have to repeat Dijkstra for each context that satisfies a projected prevail-condition. There can be at most |A| such contexts. Consequently, the complexity of generating macros in subproblem Pi is O(|A||A|2 ) = O(|A|3 ). The total complexity of our algorithm is O(∑ni=1 |A|3 ) = O(|V||A|3 ).

6 Extending the algorithm

So far, we presented an algorithm that generates optimal plans in tree-reducible planning domains. In this section, we discuss an extension to domains whose transitive reduction graphs are polytrees. Unlike trees, polytrees may not be weakly connected and have unbounded outdegree. We can apply the algorithm to each weakly connected group of state variables, but unbounded outdegree is more challenging.

Consider the following domain, with V = {v1, v2, v3} and D(v1) = {0, 1, 2}, D(v2) = D(v3) = {0, 1}. The initial state is s0 = (0, 0, 0), the goal context is c∗ = (v2 = 1, v3 = 1), and A contains the following operators:

Figure 3 shows the causal graph of the domain, identical to its transitive reduction in this case. From the point of view of state variable v2, it is possible to set v2 to 1: apply a11 to change v1 from 0 to 1, followed by a12 to change v2 from 0 to 1. From the point of view of v3, it is possible to set v3 to 1 by applying a21 followed by a13 . Nevertheless, there is no valid plan that solves the domain, and our algorithm is currently unable to handle this case.

Williams and Nayak [10] required that operators are reversible, i.e., that other operators can reverse their effect.

Definition 6.1 A polytree-reducible planning domain P is branch-decomposable if, for each vi with outdegree > 1 in the transitive reduction graph, eachmj ∈ Oi is reversible.

Let vi be a state variable with outdegree > 1 in the transitive reduction graph. The definition requires each operator that affects vi as well as each parent macro of vi to be reversible. In other words, changing the values of state variables in Ci does not prevent some future context ci from occuring. Thus, it is safe to decompose the planning domain as before and solve each branch downstream from vi separately. The context ci that results from solving one branch becomes the initial context of the solution to the next branch. This guarantees completeness, but not optimality.

As an example, consider the same planning domain as above, but with the following two additional operators:

Since there are no parent macros, each operator ak ∈ O1 is reversible, so the new domain is branch-decomposable. First, consider the solution to the branch containing v2. This solution is the same as before: apply a11 to change v1 from 0 to 1, followed by a12 to change v2 from 0 to 1. The resulting context v1 = 1 becomes the initial context of the solution to the branch containing v3. To change v3 to 1, it is necessary to apply a31 and a21 to change v1 from 1 to 0 to 2, followed by a13 to change v3 from 0 to 1. Note that it is perfectly possible to solve the branches in opposite order.

7 Experimental results

To test our algorithm, we ran experiments in two domains: Tower of Hanoi (ToH) and a modified version of GRIPPER. ToH can be modeled as a SAS+ instance with one state variable per disc. The domain of each state variable is the three pegs that each disc can occupy. For each disc, there are six operators for moving the disc between each pair of pegs, each with a prevail-condition on the location of each smaller disc. Figure 4 shows the causal graph and transitive reduction of ToH with 5 discs. The transitive reduction is a chain from the smallest to largest disc, i.e., ToH is tree-reducible. In addition, each operator affecting a state variable vi has a prevailcondition on each ancestor of vi, so it follows from Theorem 5.1 that our algorithm solves ToH in polynomial time.

The results of the experiments in ToH appear in Table 1. We varied the number of discs in increments of 10 and recorded the running time of our algorithm across 100 trials. The table also shows the number of macros generated by our algorithm, and out of those, how many were used to represent the resulting global plan. For example, 27 out of 82 generated macros formed part of the solution to ToH with 10 discs. Since the solution to ToH requires a number of operators exponential in the number of state variables, any algorithm that generates a complete operator sequence has exponential complexity. In contrast, our algorithm is able to quickly generate a macro that compactly represents the optimal plan. Naturally, executing the resulting plan has exponential complexity.

GRIPPER was one of the domains used at the first planning competition at AIPS 1998. Since our algorithm requires unary operators, we assume unlimited load capacity of the robot. In this case, GRIPPER can be modeled as a SAS+ instance with one state variable, v1, representing the location of the robot and one state variable for each ball, representing the location of that ball. Operators for picking and dropping balls have prevail-conditions on the robot's location, so the transitive reduction graph is a polytree (cf. Figure 3 for two balls). In other words, GRIPPER is polytree-reducible, and only v1 has outdegree > 1. Assuming that the robot can reach any location from any other location, GRIPPER is also branchdecomposable. Thus, it is possible to solve GRIPPER using macros by transporting one ball at a time to the goal location.

We modified GRIPPER such that instead of two rooms, the environment consists of a maze with 967 rooms. To transport balls, the robot must navigate through the maze to the goal location. The robot can only pick balls at the initial location and drop them at the goal location. The results of the experiments appear in Figure 2. The resulting plans are not optimal since the robot could carry all balls at once. However, the experiments illustrate that although the resulting solution length is linear in the number of balls, our algorithm only needs to generate macros once for moving through the maze. If the algorithm is extended to handle non-unary operators, macros can generate a large advantage in domains such as this.

8 Conclusion

We have presented an algorithm that uses macros to generate valid plans for a subclass of planning domains with unary operators and acyclic causal graphs. The algorithm is complete for all domains in the class and optimal for a subclass of domains. Macros make it possible to generate exponential length plans in polynomial time by storing partial plans in memory that can be reused as many times as necessary. This opens up new possibilities for solving classes of planning domains that were previously thought to be intractable.

The complexity of the algorithm depends on the size of local transition graphs constructed by the algorithm, which in turn depends on the number of macros generated in other subproblems. The current version of the algorithm generates macros indiscriminately, many of which are never used as part of a global plan. A possible improvement of the algorithm would be to use inference to distinguish useful macros from superfluous ones.

Another possible extension is to consider domains with non-unary operators and whose causal graphs are not acyclic. Helmert [5] describes a strategy for approximating acyclic causal graphs by excluding some prevail-conditions of operators. In some cases, this leads to deadends, in which case it is necessary to backtrack and include some of the excluded prevail-conditions. Macros are useful in this case since they retain partial plans in subproblems, obviating the need to generate a completely new plan from scratch. If the SAS+ representation included a notion of objects, it would be possible to generate macros for one object and share those macros among identical objects. Finally, macros generated in one domain could be stored and reused in other domains.

Acknowledgements

The author would like to thank Hector Geffner, Blai Bonet, Omer Gimenez and the anonymous reviewers for their valuable comments and feedback.