(b) Memos only subsume no-goods made up of proposition variables from the same planning graph level.

2. The matching cost is reduced by both the fact that considerably fewer no-goods are ever learned, and the fact that Graphplan stores no-goods (memos) separately for each level, and only consults the memos stored at level j, while doing backwards search at a level j,
The above discussion throws some light on why the so-called "EBL utility" problem is not as critical for Graphplan as it is for EBL done on normal CSPs.

## 6.1 Scenarios Where Memoization Is Too Conservative To Avoid Rediscovery Of The Same Failures

The discussion above also raises the possibility that Graphplan (even with EBL/DDB) memoization is too conservative and may be losing some useful learning opportunities only because they are not in the required syntactic form. Specifically, before Graphplan can learn a memo of the form

$P^i_2$. 

```
P i
 1 P i
       2    P i
              m ;

```

it must be the case that *each* of the dmpossible assignments to the m propositional variables must be a no-good. Even if one of them is not a no-good, Graphplan avoids learning the memo, thus potentially repeating the failing searches at a later time (although the loss is made up to some extent by learning several memos at a lower level).

Consider for example the following scenario: we have a set of variables P i 1    P i m    P i n at some level i that are being assigned by backward search. Suppose the search has found a legal partial assignment for the variables P i 1    P i m1, and the domain of P i m contains the k values v1    vk . In trying to assign the variables P i m    P i n, suppose we repeatedly fail and backtrack up to the variable P i m, re-assigning it and eventually settling at the value v7. At this point once again backtracking occurs, but this time we backtrack *over* P i m to higher level variables P i 1    P i m and re-assigning them. At this point, it would have been useful to remember some no-goods to the effect that none of the first 6 values of P i m are going to work so all that backtracking does not have to be repeated.

Such no-goods will take the form:

$$P_{m}^{i}\;\;\;\;\;v_{j}\;\;\;\;P_{m+1}^{i}\;\;\;\;\;\;\;\;\;\;\;P_{m+2}^{i}$$
m+2    P i

$$P_{n}^{i}$$

where j ranges over    6, for all the values of P i m that were tried and found to lead to failure while assigning the later variables. Unfortunately, such no-goods are not in the syntactic form of memos and so the memoization procedure cannot remember them. The search is thus forced to rediscover the same failures.

## 6.2 Sticky Values As A Partial Antidote

One way of staying with the standard memoization, but avoiding rediscovery of the failing search paths, such as those in the case of the example above, is to use the "sticky values" heuristic (Frost
& Dechter, 1994; Kambhampati, 1998). This involves remembering the current value of a variable while skipping over it during DDB, and trying that value first when the search comes back to that variable. The heuristic is motivated by the fact that when we skip over a variable during DDB, it means that the variable and its current assignment have not contributed to the failure that caused