Graphplan already has a primitive form of EBL built into its memoization strategy. In fact, Blum
& Furst (1997) argue that with memoization and a minimal action set selection (an action set is considered minimal if it is not possible to remove an action from the set and still support all the goals for which the actions were selected), the ordering of goals will have little effect (especially in the earlier levels that do not contain a solution).

Another reason for the ineffectiveness of the dynamic variable ordering heuristic may have to do with the differences between the CSP and DCSP problems. In DCSP, the main aim is not just to quickly find an assignment for the the current level variables, but rather to find an assignment for the current level which is likely to activate fewer and easier to assign variables, whose assignment in turn leads to fewer and easier to assign variables and so on. The general heuristic of picking the variable with the smallest (live) domain does not necessarily make sense in DCSP, since a variable with two actions supporting it may actually be much harder to handle than another with many actions supporting it, if each of the actions supporting the first one eventually lead to activation of many more and harder to assign new variables. It may thus be worth considering ordering strategies that are more customized to the dynamic CSP models–e.g. orderings that are based on the number (and difficulty) of variables that get activated by a given variable (or value) choice.

We have recently experimented with a value-ordering heuristic that picks the value to be assigned to a variable using the distance estimates of the variables that will be activated by that choice
(Kambhampati & Nigenda, 2000). The planning graph provides a variety of ways of obtaining these distance estimates. The simplest idea would be to say that the distance of a proposition p is the level at which p enters the planning graph for the first time. This distance estimate can then be used to rank variables and their values. Variables can be ranked simply in terms of their distances–the variables that have the highest distance are chosen first (akin to fail-first principle). Value ordering is a bit trickier–for a given variable, we need to pick an action whose precondition set has the lowest distance. The distance of the precondition set can be computed from the distance of the individual preconditions in several ways:
Maximum of the distances of the individual propositions making up the preconditions.

Sum of the distances of the individual propositions making up the preconditions.

The first level at which the set of propositions making up the preconditions are present and are non-mutex.

In (Kambhampati & Nigenda, 2000), we evaluate goal and value ordering strategies based on these ideas, and show that they can lead to quite impressive (upto 4 orders of magnitude in our tests) speedups in solution-bearing planning graphs. We also relate the distances computed through planning graph to the distance transforms computed by planners like HSP (Bonet, Loerincs, &
Geffner, 1999) and UNPOP (McDermott, 1999). This idea of using the planning graph as a basis for computing heuristic distance metrics is further investigated in the context of state-space search in (Nguyen & Kambhampati, 2000). An interesting finding in that paper is that even when one is using state-space instead of CSP-style solution extraction, EBL can still be useful as a lazy demanddriven approach for discovering n-ary mutexes that can improve the informedness of the heuristic. Specifically, Long & Kambhampati describe a method where a limited run of Graphplan's backward search, armed with EBL/DDB is used as a pre-processing stage to explicate memos ("n-ary mutexes") which are then used to significantly improve the effectiveness of the heuristic on the state-search.