Heuristic Search Planning with BDDs.
Stefan Edelkamp · 2000
. In this paper we study traditional and enhanced BDDbased exploration procedures capable of handling large planning problems. On the one hand, reachability analysis and model checking have eventually approached AI-Planning. Unfortunately, they typically rely on uninformed blind search. On the other hand, heuristic search and especially lower bound techniques have matured in effectively directing the exploration even for large problem spaces. Therefore, with heuristic symbolic search we address the unexplored middle ground between single state and symbolic planning engines to establish algorithms that can gain from both sides. To this end we implement and evaluate heuristics found in state-of-the-art heuristic single-state search planners. 1 Introduction One currently very successful trend in deterministic fully-automated planning is heuristic single-state space search. The search space incorporates states as lists of instantiated predicates (also called atoms or fluents). The succes...