Operator-Potential Heuristics for Symbolic Search
Daniel Fišer, Alvaro Torralba, Joerg Hoffmann
[AAAI-22] Main Track
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.
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.
Introduction Video
Sessions where this paper appears
-
Poster Session 3
Blue 4 -
Poster Session 12
Blue 4 -
Oral Session 12
Blue 4