activity flags for the variables, the domains of the variables, and the constraints on the legal variablevalue combinations. In a DCSP, initially only a subset of the variables is active, and the objective is to find assignments for all active variables that is consistent with the constraints among those variables. In addition, the DCSP specification also contains a set of "activity constraints." An activity constraint is of the form: "if variable x takes on the value vx, then the variables y; z; w::: become active."
The correspondence between the planning-graph and the DCSP should now be clear. Specifically, the propositions at various levels correspond to the DCSP variables2, and the actions supporting them correspond to the variable domains. There are three types of constraints: *action mutex* constraints, fact (proposition) mutex constraints and *subgoal activation constraints*.

Since actions are modeled as values rather than variables, action mutex constraints have to be modeled indirectly as constraints between propositions. If two actions a1 and a2 are marked mutex with each other in the planning graph, then for *every pair* of propositions p11 and p12 where a1 is one of the possible supporting actions for p11 and a2 is one of the possible supporting actions for p12, we have the constraint:

## P11 A1 P12 A2

Fact mutex constraints are modeled as constraints that prohibit the simultaneous activation of the two facts. Specifically, if two propositions p11 and p12 are marked mutex in the planning graph, we have the constraint:
Active p11 Active p12 ))
Subgoal activation constraints are implicitly specified by action preconditions: supporting an active proposition p with an action a makes all the propositions in the previous level corresponding to the preconditions of a active.

Finally, only the propositions corresponding to the goals of the problem are "active" in the beginning. Figure 1 shows the dynamic constraint satisfaction problem corresponding to the example planning-graph that we discussed.

## 2.2.1 Solving A Dcsp

There are two ways of solving a DCSP problem. The first, direct, approach (Mittal & Falkenhainer, 1990) involves starting with the initially active variables, and finding a satisfying assignment for them. This assignment may activate some new variables, and these newly activated variables are assigned in the second epoch. This process continues until we reach an epoch where no more new variables are activated (which implies success), or we are unable to give a satisfying assignment to the activated variables at a given epoch. In this latter case, we backtrack to the previous epoch and try to find an alternative satisfying assignment to those variables (backtracking further, if no other assignment is possible). The backward search process used by the Graphplan algorithm (Blum &
Furst, 1997) can be seen as solving the DCSP corresponding to the planning graph in this direct fashion.

The second approach for solving a DCSP is to first compile it into a standard CSP, and use the standard CSP algorithms. This compilation process is quite straightforward and is illustrated in