Figure 2. The main idea is to introduce a new "null" value (denoted by " ") into the domains of each of the DCSP variables. We then model an inactive DCSP variable as a CSP variable which takes the value . The constraint that a particular variable P be active is modeled as P . Thus, activity constraint of the form G1 A1 Active P1 ; P2; P3 is compiled to the standard CSP constraint

$$A_{1}\qquad P_{1}$$

G1 A1 P1 P2 P3 It is worth noting here that the activation constraints above are only concerned about ensuring that propositions that are preconditions of a selected action do take non- values. They thus allow for the possibility that propositions can become active (take non- values) even though they are strictly not supporting preconditions of any selected action. Although this can lead to inoptimal plans, the mutex constraints ensure that no unsound plans will be produced (Kautz & Selman, 1999). To avoid unnecessary activation of variables, we need to add constraints to the effect that unless one of the actions needing that variable as a precondition has been selected as the value for some variable in the earlier (higher) level, the variable must have value. Such constraints are typically going to have very high arity (as they wind up mentioning a large number of variables in the previous level), and may thus be harder to handle during search.

Finally, a mutex constraint between two propositions

$$A c t i v e\ p_{1}1$$
Active p11 Active p12 ))

## Is Compiled Into P11 P12 :

Since action mutex constraints are already in the standard CSP form, with this compilation, all the activity constraints are converted into standard constraints and thus the entire CSP is now a standard CSP. It can now be solved by any of the standard CSP search techniques (Tsang, 1993).3 The direct method has the advantage that it closely mirrors the Graphplan's planning graph structure and its backward search. Because of this, it is possible to implement the approach on the plan graph structure without explicitly representing all the constraints. Furthermore, as I will discuss in Section 6, there are some distinct advantages for adopting the DCSP view in implementing EBL/DDB on Graphplan. The compilation to CSP requires that plan graph be first converted into an extensional CSP. It does however allow the use of standard algorithms, as well as supports nondirectional search (in that one does not have to follow the epoch-by-epoch approach in assigning variables).4 Since my main aim is to illustrate the utility of CSP search techniques in the context of the Graphplan algorithm, I will adopt the direct solution method for the DCSP. For a study of the tradeoffs offered by the technique of compiling the planning graph into a CSP, the reader is referred to (Do & Kambhampati, 2000).