Efficient symbolic search for cost-optimal planning

Álvaro Torralba*, Vidal Alcázar, Peter Kissmann, Stefan Edelkamp

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

30 Citations (Scopus)

Abstract

In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-CUT across many different domains.

Original languageEnglish
JournalArtificial Intelligence
Volume242
Pages (from-to)52-79
Number of pages28
ISSN0004-3702
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes

Keywords

  • Cost-optimal planning
  • Image computation
  • State invariants
  • Symbolic search

Fingerprint

Dive into the research topics of 'Efficient symbolic search for cost-optimal planning'. Together they form a unique fingerprint.

Cite this