One action is enough to plan

1 Introduction

In the stream of research that aims to speed up practical task planners, we propose a new approach to efficiently deal with large problems. Even though task planners have made very substantial progress over the last years, they are still limited in their use. Indeed, they are sometimes overwhelmed by very simple or even trivial problems. Our motivation stems also from the fact that there are domains which heavily influence the "structure" of the task state space; learning such a "structure" will certainly help in building efficiently a solution for a problem of the domain subclass 1 . Our aim is to develop a domain independent planner that will exhibit and learn the "structure" of a given domain subclass. The main difficulty (and the key contribution) in this framework is to face the combinatorial problem of the task space exploration.

In order to solve larger problems, all planners in the literature try to prune the state space. To do this, there are several ways: a first solution consists in having a "good metrics" of the domain in order to guide the search (heuristics). The heuristics can be automatically computed (domain independent planning - e.g. [Bonet and Geffner, 1999; Hoffmann, 2000]) or given by the user (domain dependent planning - e.g. [Doherty and Kvarnstrom, 1999]).

1 In this paper, we call a domain subclass the set of planning problems defined by a set of operators and a set of objects. For example, the 10-blocks-world is a subclass of the blocks-world domain. The 20-blocks is another subclass of the same domain.

A second way consists in restricting the search to a superset of accessible states from the initial state; such restriction allows to reduce the search space during the backward planning process (e.g. the graph expansion of GraphPlan [Blum and Furst, 1997]).

A third way involves the analysis of the domain "structure" like invariant (e.g. [Gerevini and Schubert, 1998]), type detection, problem decomposition or problem symmetries (e.g. [Fox and Long, 1998; 1999]).

We would like is to develop a new, complete and domain independent method to efficiently solve large problems. To do so, we both restrict the search space through a set of accessible states and deal with a large class of domain symmetries (represented by states which have the same shape 2 ).

For instance, the ferry problemoverwhelms classical planners because of the very high number of possible applicable actions (which may create many redundant states) even though moving one car or another has the same result for the goal. However, it appears clearly that the state space is highly redundant: there is only 2n + 1 distinguishable shapes for n cars. Dealing with such shapes will certainly increase the planner capabilities by reducing the search space in a drastic manner.

ShaPer 3 is a new planner which is able to detect all different shapes of the state space for a given domain subclass. This method is composed of two steps: first the planner builds a shape graph of the domain subclass. This step is performed off-line and only once for a given domain subclass, e.g. ShaPer builds the shape graph for the subclass of ferry domain with 50 cars. Then, ShaPer is able to solve on-line any planning problem in this class by connecting two shape graphs. As we will see, the connection makes use of only one action; this ensures the efficiency of the solution extraction step.

The next section explains how to build such shape graph. Section 3 presents an expansion algorithm that guarantee ShaPer completeness. We then describe the solution extraction process (section 4). A first version of the planner has been implemented and has produced very promising results. All sections are illustrated by examples obtained by running such an implementation. The last section presents and discusses a number of tests which are compared with some of the best current planners (from AIPS-2000 competition).

2 The shape of a state, defined more precisely in the next section, can be viewed as a partially instantiated state pattern.

3 Shape based Planner

2 The Shape Graph: G

A planning problem is usually expressed as a triple (O;; I;; J ) where O corresponds to the set of instantiated actions, I the initial state and J the goal. In the STRIPS [Fikes and Nilsson, 1971] formalism, an action o 2 O is described by its preconditions P o (P o  S means that o is applicable to the state S), its Addlist A o and its Dellist D o . Applying the operator o from state S results in the new state o(S)  (S;D o )[A o . A state is an instantiated predicate set according to the closedworld assumption.

The purpose of this section is to present the shape graph construction process (only extract "relevant" states). This state space exploration is performed off-line and once only for each domain subclass from a valid state S begin .

Indeed, if we restrict ourselves to the STRIPS framework, there is a priori no mean to check if a state is valid or not, except by applying a valid sequence of action to a valid one (S begin - user-defined).

This is the reason why the shape graph is an accessibility graph G. Now, the main difficulty comes from the combinatorial explosion of states and applicable actions; this is why we build a graph that only contains "relevant" states.

2.1 Relevant states

The relevance of a state is defined according to the state description of the current graph G. A state S is relevant (i.e. it "augments" G with new information ) iff there exists no g 2 G such that g is a substitution  of S: (g) = S (i.e. the state g can be instantiated by a variable permutation ). Consider for instance the two blocks-world states g and S:

with g = fClear(A);;On(A;; B);;OnTable(B);; Clear(C);; OnTable(C)g and S = fClear(A);; OnTable(B);; Clear(B);; OnT able(C);; On(A;; C)g.

The state g where A is substituted to A, B to C and C to B is equal to S ( = fA=A;; C=B;; B=Cg). In this case, g and S are said to have the same shape 4 .

When S has the same shape as g, we can conclude that all shapes accessible from g are also accessible from S: if P is a sequence of action applicable to g, then (P) is applicable to S and ((P))(S) = (P(g)). Developing the state S is then not informative: S does not lead to a new shape.

4 In order to prevent possible misunderstandings due to the previous figure, let us emphasize on the fact that a shape does not characterize a tower, but more generally the structure of a planning problem (i.e. there exists a substitution between S and g).

Build Graph(O,S begin ) To Dev fS begin g G fS begin g While To Dev 6=  do s pop(To Dev) For each o 2 O such that P o  s do If 9g 2 G and 9 such that o(s) = (g) Then If o(s) = g Then Add the edge (s;; g) to G Else Mark s in G with  and g Else Add the vertex o(s) and the edge (s;; o(s)) to G To Dev To Dev [ fo(s)g

2.2 Building the shape graph G

In order to reduce the graph size, we only develop relevant states. The algorithm, presented in table 1, is similar to a breadth-first search algorithm. Relevant states are sequentially developed by applying all possible actions o. The algorithmdetects links to other substitutions as well as cycles in a given substitution (when o(s) = g); in this case, a new edge is added.

In the case of a non-identical substitution , we keep in s the name of the corresponding shape in G and . Owing to the relation o(s) = (g), the accessibility from s to o(s) can be, if necessary, quickly retrieved. Indeed, several substitutions may produce the same result because of the commutativity of the logical and, i.e. (g) =  0 (g) does not imply  =  0 .

2.3 An example

The graph construction algorithm is illustrated by figure 1 with an example from the gripper domain. The goal is to move 3 balls from table T 1 to table T 2 . To do this, the robot is able to pick and place a ball and to move from a table to the other. The robot has two arms. The graph expansion begins with the valid state S 1 (all three balls are on T 1 and the robot is near T 1 ). Four actions are applicable to S 1 : P ick(X;; T 1 ), P ick(Y;; T 1 ), P ick(Z;; T 1 ) and move(T 1 ;; T 2 ); as shown on figure 1 Pick(X;; T 1 )(S 1 ) = S 2 and move(T 1 ;; T 2 )(S 1 ) = S 3 . We can note that P ick(Y;; T 1 )(S 1 ) is not added to the graph, since there exists a substitution  = fY=X;;X=Y;; Z=Z;; T 1 =T 1 ;; T 2 =T 2 ;; g l =g l ;; g r =g r g 5 such that (S 2 ) = Pick(Y;; T 1 )(S 1 ). Similarly, there exists a substitution between P ick(Z;; T 1 )(S 1 ) and S 2 ; we note it on the figure by a dashed line to S 2 . Then S 2 is developed in S 4 and S 5 and so on . . .

The graph G finally contains nine vertices which model all possible shapes accessible from the valid state S 1 .

5 Note that in this example, even through the substitution only permutes balls X, Y and Z, the substitution  must contain g l (gripper left), g r (gripper right) and the two tables T 1 and T 2 because they are variables too. See for instance the state S 9 which has the same shape as the state S 8 when the robot takes a ball.

2.4 G and the state space

This method makes it possible to drastically reduce the size of the state space when the domain contains many (functionally similar) "objects" (variables with possible substitutions). Indeed, in the blocks-world and in the gripper domain, the state space grows exponentially comparing to the shape graph size as shown table 2.

As mentioned previously, ShaPer needs a valid state, S begin , to build the graph G. Although G contains all shapes accessible from S begin , in the case of a disjoint state space, ShaPer is unable to construct graphs from the other connected components of state space (their states are not accessible). Therefore, the user must give one state per connexity; otherwise, the shape of S init (the initial state of a planning problem) might not be present in G, which will constraint the planner to generate a complementary shape graph from S init during the on-line process.

2.5 A first step through solution extraction

To perform efficient on-line solution extraction, ShaPer takes advantage of the shape graph G built off-line. Three steps are necessary to find a plan: first, generate the graph G init (resp.

G goal ) associated to the initial state S init (resp. S goal ). Then ShaPer searches for one action o 2 O that connects G init with G goal via s i and s g (s i 2 G init ,s g 2 G goal and s g = o(s i )). Finally it is enough to find a path from S init to s i in G init and from s g to S goal in G goal .

To better understand this intuitive algorithm, let us explain it through the 3-balls-gripper example. There are three balls, two tables and two grippers; initially balls A and B are on table T 1 and the ball C is in the left gripper near table T 2 . This state has the same shape as S 5 of the figure 1 where fC=X;;A=Y;;B=Zg. The goal is to obtain the three balls on T 2 . To do so, we instantiate the shape graph G with the initial state substitution (resp. goal) and obtain the graph G init (resp. G goal ). Then the algorithm looks for one action which connects a state of G init to a state of G goal , as illustrated by figure 2 with the action T ake(B;; g r ;; T 1 ).

3 G and completeness

The method, for solution extraction (proposed in the previous section) is generally very efficient, however in specific case, it is not always possible to connect the two graphs with a single action. To obtain a solution, the planner may need to connect several substitutions of the graph G; but looking for such transitions may be as costly as planning "from scratch".

Fortunately, we can compute off-line a meta-graph H which contains all necessary substitutions of G to solve any instance of the problem (from the learned domain) in only one action (between H init and G goal ).

3.1 H: a meta-graph of G

In order to ensure the completeness for our method, we propose an expansion algorithm of the graph G to H. The main idea is the following: if all substitutions accessible from S begin are accessible fromH too, then there exists an action o 2 O which connects H init to G goal .

To perform such expansion, we begin with H = G. H must contain all graph G that allow to connect graph G 0 such that G 0 is not directly connected to H. For each o(h) (with h 2 H and o(h) =2 H), generate the graph G o(h) . For each o 0 (g) (with g 2 G o(h) and o 0 (g) =2 G o(h) ), check if G o 0 (g) is directly accessible from H; if it is not the case, then add G o(h) to H. This algorithm stops when H becomes invariant. In other words, H corresponds to the "transitive closure" of G in terms of substitutions.

S2

Figure 3: The graph G for 4-blocksworld domain restricted to 3 stacks.

3.2 An expansion example

To better understand this expansion, we illustrate it on the 4-blocks-world domain restricted to three stacks. Figure 3 presents the shape graph G and its substitutions (e.g. S 0 4 is a substitution of the state S 4 ). Intuitively, to reverse blocks Z and T in this domain, it is necessary to use two substitutions of S 4 ; so find a solution with only one action may be impossible only by using G.

To expand G presented in figure 3, ShaPer must examine states S 1 4 , S 1 2 , S 2 4 , S 3 4 , S 2 2 and S 1 3 (states which leave G). Developing G 0 , the shape graph from S 1 4 , allows to generate G 00 via S 1 4 0 (see figure 4). Note that there does not exist any action to connect a state of G to a state of G 00 ; this means that G 0 allows to access to new substitutions. Consequently, it is added to H. The graph presented in figure 5 corresponds to the invariant of H after having examined all the other states.

Naturally, all the graphs included in H differ only by a substitution. Therefore, H can be expressed by only using substitutions and G, e.g. in figure 5, H is described by two substitutions on G.

4 Solution extraction

G and H being computed off-line, ShaPer performs on-line plan extraction for any possible problem from the learned domain by searching for one action.

4.1 An efficient algorithm

Table 3 presents the three-steps algorithm used to extract a plan from an initial state S init to S goal . As the graph G is computed off-line, it is also possible to compute the best path for any couple of vertices in G. Let Plan(g 1 ;; g 2 ) be the optimal plan from g 1 to g 2 in G and C(g 1 ;; g 2 ) the number of actions of this plan. Considering the cost C, it is possible to find the best solution using only two shape graphs and one action. Indeed, the algorithmexamines iteratively all possible connections, ordered by an increasing cost (the cost is defined by C(S init ;; s) + 1 + C(o(s);; S goal )). Such procedure makes it possible to obtain non-optimal, because of the graph learning, but good solutions. This is illustrated by the number of plan steps in the results presented in table 4.

Figure 6 shows an example of a solution extraction in 4blocks-world domain restricted to three stacks. First, ShaPer instantiates the graph H with the initial state ( init = fD=X;;B=Y;;A=Z;;C=Tg) obtaining H init , and G with the goal ( goal = fD=X;;C=Y;;B=Z;;A=Tg) obtaining G goal . Then, in order to find a connection between H init and G goal , the algorithm examines (following an increasing cost) the states S 1 4 . . .S 1 3 and S 1 4 0 . . .S 1 3 0 (see figure 3) and finds S 4 0 ! S 3 4 0 as first connection. Then, to build a valid plan, it is enough to find a plan in H init and a plan in G goal . Thus, the plan extracted by ShaPer is the following: [MoveToTable(D,B), Move(B,A,D), MoveToTable(A,C)], Move(B,D,A), [MoveFromTable(C,B)].

4.2 Bounds for Computation Time and plan length

Having the shape graph computed off-line leads to an interesting property: the solution extraction algorithm is time bounded and the plans have a known maximal length.

Indeed, the algorithm presented in table 3 examines iteratively a set of triples (s;; g 00 ;; ) of (G). The test consists in checking equality between two states. As H is computed off-line, we know in advance how many triples there are, e.g. for 15 blocks there are only 7186 triples. Consequently, we can compute an upper limit for the on-line solution extraction computation time.

In the same way, we can compute an upper limit n for the longest path P in G. The length of the longest plan (maximum number of plan steps) will then be bounded by 2n + 1.

The results, presented in table 4, include a max column for number-of-steps and computation time bounds.

4.3 Completeness

This subsection present the main ideas to prove the completeness of ShaPer in informal way.

For a substitution , (A [ B) = (A) [ (B) and (A\B) = (A)\(B). So we can demonstrate the following theorem: (o(s)) = ((o))((s)) with o being an action applicable to the state s 6 .

The algorithm to build G ensures that for any state s in G and any action o such that o(s) =2 G, there exists a substitution  of a state g of G with o(s) = (g). Then it is possible to demonstrate that G contains all accessible shapes. Given s 2 G and e = o(s) =2 G. Suppose that e allows to access to the state s 0 = o 0 (e) which has a new shape. From G definition, 9 ^ g 2 G:(g) = e. The action  ;1 (o 0 ) is applicable to g; if  ;1 (o 0 )(g) =2 G then 9 0 (g 0 ) =  ;1 (o 0 )(g) such that ( ;1 (o 0 )(g)) = o 0 ((g)) = o 0 (e) and    0 (g 0 ) = o 0 (e) so g 0 has the same shape as e.

Similarly, H satisfies the following property: for any state h in H and g in G 0 (G 0 is connected to H by one action through the substitution ), all accessible substitutions from G 0 are also accessible from H. H is the transitive closure of G in terms of substitutions. It is also possible to recursively prove that ShaPer finds a plan if there exists one. Given s 2 H and a plan P = a n  : : :a 1 such that goal = P(s). If a 1 (s) =2 H then there exists (h) = a 1 (s) with a 1 (s) 2 G 0 and h 2 H. Given i and the state e = a i;1  : : :  a 1 (s) and e 0 = a i (e) with e 2 G 0 and e 0 =2 G 0 . So e 0 2 G 00 (connected to G 0 by the state g 0 2 G 0 and a substitution : (g 0 ) = e 0 ). Owing to H's property, there exists a state h 0 of H and a substitution such that  (g 0 ) = e 0 . That means ShaPer is able to find a plan between s and e 0 (connect H to G 00 with one action); apply recursively this reasoning 7 on a n  : : :  a i , demonstrates the completeness.

6 Indeed (o(s)) = ((s ; D o ) [ A o ) = ((s) ; (D o )) [ (A o ) = ((o))((s))

7 If the plan P uses a third shape graph G 3 (one-action-connected to G 00 which is also one-action-connected to H) , the previous rea-

5 Results

In this section, we compare our planner with the most efficient planners from AIPS-2000 competition. FF [Hoffmann, 2000] and HSP [Bonet and Geffner, 1999] use heuristics based on a relaxed problem (plan without Dellist). IPP [Koehler et al., 1997] and STAN [Fox and Long, 1999] are derived from GraphPlan [Blum and Furst, 1997]. In addition, they use an on-line mechanism that allows to deal with some symmetries; that is reason why it is interesting to compare them with ShaPer which is able to deal with a larger class of symmetries.

In this comparison, we do not mention TalPlan [Doherty and Kvarnstrom, 1999] because it is a domain dependent planner; the comparison can then be only made with ShaPer solution extraction step. In such a case, TalPlan exhibits clearly better results than ShaPer: the made-by-hand heuristics is still the best.

All running time presented in table 4 are measured on a Sparc Ultra 5 with 128Mb. '-' means that the planner does not find any solution in 3600sec. and '*' means that the shape graph has already been computed for a previous problem (same domain subclass).

The ferry and the gripper domains are interesting because they overwhelm the majority of the planners by the number of their applicable actions. Despite their ability to treat state symmetries, IPP and STAN can not solve large problems in both ferry and gripper domain. Ferry and gripper domains are easy for ShaPer because of their low number of shapes (resp. 2n + 1 for n cars and 3n for n balls). Thanks to their good heuristics, HSP and FF solve easily all these problems (however, note that HSP solves gripper problems with an inefficient number of steps).

Blocks-world domains give surprising results for HSP and FF. HSP solves '-3' and '-2' problems more easily than '-1' problems. For FF, the situated is opposite. Problems labeled '-i' correspond to i-stacks problems: a goal for a '-1' problem is to put the first block under the stack (without changing the order of the other blocks); for '-2' and '-3' problems, the goal is to build one "interleaved" stack composed of all the blocks from the initial stacks (e.g. move stacks s 1 ;; s 2 : : : and p 1 ;; p 2 : : : into s 1 ;; p 1 ;; s 2 ;; p 2 : : :).

With several problems in the same domain subclass, e.g. all problems with 15 blocks, we better understand the importance of the off-line process (computed more efficiently than some HSP or FF solution): the graph building step is performed only once. The small number of shapes allows to have a very short computation time upper limit.

In conclusion, ShaPer solves all problems in less than 1 second; in addition it builds the graph and solves all problems faster than IPP and STAN (and often HSP) and extracts all problems faster than FF with a near-optimal number of plan steps.

6 Conclusion

We have proposed an original approach to task planning that allows to deal efficiently with large problems. It has been implemented in a domain independent task planner, called ShaPer. It performs in two steps. The first step is performed off-line and only once for a given domain subclass. It allows ShaPer to "capture the structure" of the state space and to store it in a data structure called the shape Graph. The main contribution here is the ability of ShaPer to build a very compact description when compared to the size of the complete state space. The shape graph is then used on-line by ShaPer to answer very efficiently to planning requests.

soning allows to prove that there exists a connection with one action between H and G 3 .

ShaPer exhibits several interesting properties: 1) it is complete, 2) It is possible to determine, after the shape Graph construction, the upper limit for the on-line solution extraction computation time as well as length of the longest plan, 3) it produces "good" (near-optimal) solutions.

Our future work will be devoted to a state decomposition method. Indeed, we would like to decompose a state into several disjoint parts in order to minimize interferences in action applicability. This should allow to generate sub-graphs and to deal with sub-shapes resulting in an even more compact state space description.

This would help to re-use shape graph created for a given domain subclass (e.g. 10 blocks) in order to generate shapes for "bigger" subclasses (e.g. 15 blocks) Besides, we hope to be able to exploit the structure of the shape graph for conformant and contingent planning as in [Gu´er´e and Alami, 1999].