homeresources & publications › memory-efficient symbolic heuristic search


Memory-efficient symbolic heuristic search


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*. Since the memory requirements of A* limit its scalability, we show how to integrate symbolic search with a more memory-efficient strategy for heuristic search. We analyze the resulting search algorithm, consider the factors that affect its behavior, and show that it achieves state-of-the-art performance in finding optimal solutions to STRIPS planning problems.


Jensen, R. M.; Hansen, E. A.; Richard, S.; Zhou, R. Memory-efficient symbolic heuristic search. The Sixteenth International Conference on Automated Planning and Scheduling (ICAPS-06); 2006 June 6-10; English Lake District, Cumbria; UK. Menlo Park, CA: AAAI Press; 2006; 304-313.