Memory-Efficient Symbolic Heuristic Search

Rune Møller Jensen, Eric A. Hansen, Simon Richards, Rong Zhou

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


A promising approach to solving large state-space search problems is to integrate heuristic search with symbolic search. Recent work shows that a symbolic A* search algorithm that uses binary decision diagrams to compactly represent sets of states outperforms traditional A* in many domains. Since the memory requirements of A* limit its scalability, we show how to integrate symbolic search with a memory-efficient strategy for heuristic search. We analyze the resulting search algorithm, consider the factors that affect its behavior, and evaluate its performance in solving benchmark problems that include STRIPS planning problems.
Original languageEnglish
Title of host publicationProceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS-06)
Number of pages10
PublisherAAAI Press
Publication date2006
ISBN (Print)9781577352709
Publication statusPublished - 2006


  • Heuristic Search
  • Symbolic Search
  • Binary Decision Diagrams
  • A* Algorithm
  • STRIPS Planning Problems


Dive into the research topics of 'Memory-Efficient Symbolic Heuristic Search'. Together they form a unique fingerprint.

Cite this