Abstract: Symbolic search, using Binary Decision Diagrams (BDDs) to represent

sets of states, is a competitive approach to optimal planning. Yet

heuristic search in this context remains challenging. The many

advances on admissible planning heuristics are not directly

applicable, as they evaluate one state at a time. Indeed, progress

using heuristic functions in symbolic search has been limited and even

very informed heuristics have been shown to be detrimental.

Here we show how this connection can be made stronger for LP-based

potential heuristics. Our key observation is that, for this family of

heuristic functions, the change of heuristic value induced by each

operator can be precomputed. This facilitates their smooth integration

into symbolic search. Our experiments show that this can pay off

significantly: we establish a new state of the art in optimal symbolic

planning.