

![0_image_0.png](0_image_0.png) 

Variables: G1;    ; G4 ; P1    P6 Domains: G1 : fA1; ?g; G2 : fA2; ?gG3: fA3; ?gG4: fA4 ; ?g P1: fA5 ; ?gP2: fA6 ; A11 ; ?gP3: fA7; ?gP4: fA8; A9 ; ?g P5: fA10 ; ?gP6: fA10; ?g Constraints (normal):P1 = A5 ) P4 6= A9 P2 = A6 ) P4 6= A8 P2 = A11 ) P3 6= A7 Constraints (Activity): G1 = A1 ) P1 6=? ^P2 6=? ^P3 6=? G2 = A2 ) P4 6=? G3 = A3 ) P5 6=? G4 = A4 ) P1 6=? ^P6 6=? Init State: G1 6=? ^G2 6=? ^G3 6=? ^G4 6=?

![0_image_2.png](0_image_2.png)

![0_image_1.png](0_image_1.png)

from the level k action list that supports it, such that no two actions selected for supporting two different goals are mutually exclusive (if they are, we backtrack and try to change the selection of actions). At this point, we recursively call the same search process on the k level planning-graph, with the preconditions of the actions selected at level k as the goals for the k level search. The search succeeds when we reach level (corresponding to the initial state).

Consider the (partial) planning graph shown in Figure 3 that Graphplan may have generated and is about to search for a solution. G1    G4 are the top level goals that we want to satisfy, and A1    A4 are the actions that support these goals in the planning graph. The specific actionprecondition dependencies are shown by the straight line connections. The actions A5    A11 at the left-most level support the conditions P1    P6 in the planning-graph. Notice that the conditions P2 and P4 at level k are supported by two actions each. The x-marked connections between the actions A5; A9, A6; A8 and A7; A11 denote that those action pairs are mutually exclusive. (Notice that given these mutually exclusive relations alone, Graphplan cannot derive any mutual exclusion relations at the proposition level P1    P6.)

## 2.2 Connections Between Graphplan And Csp

The Graphplan algorithm as described above bears little resemblance to previous classical planning algorithms. In (Kambhampati et al., 1997), we explicate a number of important links between the Graphplan algorithm and previous work in planning and constraint satisfaction communities.

Specifically, I show that a planning-graph of length k can be thought of (to a first approximation) as a disjunctive (unioned) version of a k-level search tree generated by a forward state-space refinement, with the action lists corresponding to the union of all actions appearing at kth level, and proposition lists corresponding to the union of all states appearing at the kth level. The mutex constraints can be seen as providing (partial) information about which subsets of a proposition list actually correspond to legal states in the corresponding forward state-space search. The process of searching the planning graph to extract a valid plan from it can be seen as a dynamic constraint satisfaction problem. Since this last link is most relevant to the work described in this paper, I will review it further below.

The dynamic constraint satisfaction problem (DCSP) (Mittal & Falkenhainer, 1990) is a generalization of the constraint satisfaction problem (Tsang, 1993), that is specified by a set of variables,