Planners of the Graphplan family (Graphplan, IPP, STAN...) are currently considered to be the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of actions. The sets of actions generated by Graphplan satisfy a strong independence property which allows one to manipulate each set as a whole. We present a detailed formal analysis that demonstrates that the independence criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Indeed, two actions at a same level of the planning-graph do not need to be marked as mutually exclusive if there exists a possible ordering between them that respects a criterion of "authorization", less constrained than the criterion of independence. The ordering between the actions can be set up after the plan has been generated, and the extraction of the solution plan needs an extra checking process that guarantees that an ordering can be found for actions considered simultaneously, at each level of the planning-graph. This study lead us to implement a modified Graphplan, LCGP (for "Least Committed GraphPlan"), which is still sound and complete and generally produces plans that have fewer levels than those of Graphplan (the same number in the worst cases). We present an experimental study which demonstrates that, in classical planning domains, LCGP solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN...). In most cases, LCGP also outperforms the other planners. Introduction In recent years, the development of a new family of planning systems based on the planner Graphplan [2; 3] has lead to numerous evolutions in planning. Graphplan develops, level after level, a compact search space called a planning-graph. During this construction stage, it does not use all the relations among state variables or actions that are taken into account in other planning techniques like state space search or search in the space of partial plans. In Graphplan, these constraints are only computed and memoized at each level as mutual exclusions, so that the planning-graph can be seen as a Dynamic CSP [10; 11; 18; 23]. The search space is easier to develop, but a second stage, called the extraction stage, is necessary in order to try to extract a valid plan from the planning-graph and the sets of mutual exclusions. Several techniques have been employed to improve Graphplan: reduction of the search space before the extraction stage [7; 19], improvement of the domain representation language [9; 14; 15; 22; 23], improvement of the extraction stage [8; 10; 11; 13; 16; 24]. In all these works, the structure of the generated plans remains the same whatever the graph construction method is. A plan of Graphplan can thus be represented as a minimal sequence of sets of actions considered simultaneously: each step of the algorithm produces a level of the planning-graph, each level being connected to a set of actions of the plan. Every set Q of actions that appears in a sequence produced by Graphplan is such that the computation of the final situation Ef, produced by the application of the actions of Q, starting from an initial situation Ei, is independent of the order in which these actions are applied. This is because all the sets of actions kept by Graphplan during the extraction stage verify a property I (Independence), easy to test, that permit them to be excuted in parallel. The final situation Ef is directly computed from the initial situation Ei and from the global application of the actions of the set Q. We have established another property A (Authorization) which is less restrictive than I (I implies A) and easier to verify. This property guarantees the existence of at least one serialization S of the actions of Q (but does not require its computation). The application of this sequence to an initial situation Ei can still be computed as if the sets of actions verified the independence property. The final situation Ef can still be considered to be the result of the global application of the actions of Q, but these actions cannot be always executed in parallel: a valid ordering (that can contain parallel actions) must be found. We have developed a Graphplan-like planner called LCGP (Least Committed Graphplan, see [4; 5] ) which works in the same way: it incrementally constructs a stratified graph, then searches it to extract a plan. The graph that Graphplan would have built is a subgraph of LCGP graph (cf. example below) at the same level. So, goals generally appear sooner (at the same time in the worst cases). LCGP then transforms the produced plan into a Graphplan-like plan. The faster computation of a solution has a cost: the plans obtained with LCGP may not be optimal, in the sense that they can have more levels than the ones produced by Graphplan. In practice, LCGP rapidly gives a solution on many classical benchmarks (Logistics, Blocks-world, Ferry...) where Graphplan is unable to produce a plan after a significant running time. We introduce below, on a small example, the basic idea of the authorization relation and the changes it implies for Graphplan. Let us first recall informally the basic elements of Graphplan. Objects of the world are represented by ground atoms (called propositions), states of the world are lists of propositions, and actions are triples of lists of propositions: preconditions (propositions that must be present in the state before the execution of the action), add effects (propositions added to the state) and del effects (propositions deleted from the state). The Graphplan algorithm first builds the planning-graph, a stratified graph that interleaves two kinds of nodes: proposition nodes and action nodes. These nodes are collected into levels, that contain one set of proposition nodes and one set of action nodes each. The first level only contains the propositions of the initial state of the world. The second level contains the actions that are applicable in the initial state (actions that have all their preconditions present in the initial state), and the no-ops for every proposition in the initial state. A no-op is an action whose precondition is a proposition and add effect is the same proposition. No-ops permit Graphplan to solve the frame-problem: a proposition not deleted by an action will be present in the next state if the corresponding no-op is applied. The second level also contains the add effects of every action in the second level (including the propositions of the initial state, thanks to the no-ops). At each level, binary mutual exclusions are recorded. Two propositions are mutually exclusive when every pair of actions that produce them are mutually exclusive, and two actions are mutually exclusive when they have mutually exclusive preconditions or when they are not independent. Two actions are independent when neither of them deletes a precondition or an add effect of the other. Actions will not be added in the next level if any of their preconditions are mutually exclusive. This process continues until the following property is verified: either all the propositions of the goal are present in the last level and none of the goal propositions are mutually exclusive, or the problem is proved to be unsolvable with respect to a more complex property (cf. [3] for details). If the problem is not unsolvable, then a solution can be extracted by a backward chaining algorithm that will be briefly described in the example below. If no solution is found, the planning-graph is extended with one more level and the extraction stage starts again until a solution is found or the problem is proved to be unsolvable. Now comes an example that illustrates the difference between Graphplan and LCGP. The set of propositions is P = {a, b, c, d} and the set of actions is A = {A, B, C}, with: Preconditions of A = {a} Preconditions of B = {a} Preconditions of C = {b, c} Add effects of A = {b} Add effects of B = {c} Add effects of C = {d} Del effects of A = {} Del effects of B = {a} Del effects of C = {} The initial state of the problem is I = {a}, and the goal is G = {d}. The planning-graph of Graphplan is depicted in Figure 1 . A full black line from a proposition to an action (from left to right) represents a precondition link, and from an action to a proposition it represents an add effect. Dashed lines represent del effects, and grey lines represent no-ops. because the no-op of b and the action B are not mutually exclusive. At level 3, the action C can be applied and the goal d appears. The solution can now be extracted by the backward chaining algorithm. A goal list is created that only contains d. The algorithm looks for actions that assert the propositions of the goal list at level 3. The only action that asserts d is C. The goal list is now the union of the preconditions of every considered actions: {b, c}. The algorithm records that C belongs to the current plan at level 3, and looks for actions at level 2 that assert the proposition of the goal list. Some pairs of actions cannot be chosen, because they are mutually exclusive: {A, B}, {A, no-op of c}, {no-op of b, no-op of c}. The only possible choice is {no-op of b, B} which is recorded in the current plan at level 2. The goal list is now {b, a}, and the only possible actions at level 1 are {A, no-op of a}. The produced plan (without no-ops, which are only useful for the construction of the graph and the extraction stage) is 〈A, B, C〉. The authorization relation is a partial relaxation of the independence relation, and is not symmetrical. An action A authorizes an action B when A does not delete a precondition of B and B does not delete an add effect of A, so the action B can be applied after the action A and the resulting state contains the union of the add effects of A and B. Two actions are now mutually exclusive when they have mutually exclusive preconditions or when neither of these two actions authorizes the other. Figure 2 depicts the planning-graph of LCGP. Thus, at level 1, the propositions b and c are not mutually exclusive, and the action C can be applied at level 2. The goal d now appears at level 2 and the extraction stage can be performed. The goal list is initialized with {d}, and the algorithm looks for an action that asserts d: the action C is then recorded in the current plan at level 2. The goal list is now the preconditions of C: {b, c}. The only actions that assert the propositions of the goal list are now the actions A and B which are not mutually exclusive as before, because A authorizes B. The algorithm must perform an extra test, to ensure that an ordering of these actions can be found. As we have only two actions, the ordering is obvious and the produced plan is the one produced by Graphplan: 〈A, B, C〉. A problem can occur when the algorithm considers at least three actions simultaneously. Indeed, if we consider the three actions C, D, E such that C authorizes D but D does not authorize C, D authorizes E but E does not authorize D, and E authorizes C but C does not authorize E, no ordering of {C, D, E} can be found: 〈C, D, E〉 and 〈C, E, D〉 are impossible because C does not authorize E; and with a circular permutation of these two orderings, all the other orderings are impossible. An example of a classical benchmark domain in which this problem can occur is the Blocks-world domain with the following actions: MoveFromTable(A, B), MoveFromTable(B, C) and MoveFromTable(C, A). In the initial state, the three blocks A, B and C are on the table, and the goal is {on (A, B) , on(B, C), on(C, A)} which is obviously impossible; but that needs to be proved by the planner. The three actions described above produce the propositions of the goal, and there is no pair of mutually exclusive actions. Indeed, MoveFromTable(B, C) authorizes MoveFromTable(A, B): after moving B on C, it is still possible to move A on B. But MoveFromTable(A, B) does not authorizes MoveFromTable(B, C): after moving A on B, B is not clear, so it cannot be taken (a block can be moved only when it is clear). We are exactly in the case described above with the actions C, D, E. It is important to note that the search for an ordering can be performed in polynomial time by a topological sort algorithm. In Section 2, we present a formal analysis of the independence and authorization relations. In Section 3 we describe the way to modify Graphplan in order to produce authorization based plans, and to transform them into independence based plans. In Section 4 we show experimental results that compare the efficiency of our approach to that of classical Graphplan. Related work is discussed in Section 5, and our conclusions are given in Section 6.  First, we formalize the structure of the plans of Graphplan (cf. § 2.1). Then, we suggest that Graphplan, using the independence criterion, over-constrains the choice of the actions into the sets of actions considered simultaneously (cf. § 2.2). We then demonstrate that this criterion can be relaxed in order to obtain plans with a different structure. These plans can be easily transformed into plans that Graphplan could have produced (cf § 2.3), and which lead to the same resulting state. The most important element of a plan is an action, which is an instance of an operator. In Graphplan, operators are Strips-like operators, without negation in their preconditions. We use a first order logic language L, constructed from the vocabularies Vx, Vc, Vp that respectively denote finite disjoint sets of symbols of variables, constants and predicates. We do not use function symbols. An operator, denoted by o, is a triple 〈pr, ad, de〉 where pr, ad and de denote finite sets of atomic formulas of the language L. Prec(o), Add(o) and Del(o) respectively denote the sets pr, ad and de of the operator o. O denotes the finite set of operators. A state is a finite set of ground atomic formulas (i.e. without any variable symbols). A ground atomic formula is also called a proposition. P denotes the set of all the propositions that can be constructed with the language L. An action denoted by a is a ground instance oθ = 〈prθ, adθ, deθ〉 of an operator o which is obtained by applying a substitution θ defined with the language L such that prθ, adθ and deθ are ground and adθ and deθ are disjoint sets. Prec(a), Add(a), Del(a) respectively denote the sets prθ, adθ, deθ and represent the preconditions, adds and deletes of a. A denotes the finite set of actions, which are all the possible ground instanciations of the operators of O. The main structure we will use in the following, the sequence of sets of actions, will represent the plans of Graphplan and LCGP: it defines the order in which the sets of actions are considered from the point of view of the execution of the actions they contain. All sequences and sets of actions will be finite. A sequence of sets of actions S is noted 〈Qi〉n, with n ∈ . If n = 0, S is the empty sequence: S = 〈Qi〉0 = 〈〉; if n > 0, S can be noted 〈Q1, Q2, ..., Qn〉. If the sets of actions are singletons (i.e. Q1 = {a1}, Q2 = {a2}, ..., Qn = {an}), the associated sequence of sets of actions is called a sequence of actions and will be noted
REF introduce the notion of authorized linearizations, which implies an order for the execution of two actions.
Least commitment in graphplan
Artificial Intelligence
Mathematics Computer Science