Heuristic Search + Symbolic Model Checking = Efficient Conformant Planning

Abstract

Planning in nondeterministic domains has gained more and more importance. Conformant planning is the problem of finding a sequential plan that guarantees the achievement of a goal regardless of the initial uncertainty and of nondeterministic action effects. In this paper, we present a new and efficient approach to conformant planning. The search paradigm, called heuristic-symbolic search, relies on a tight integration of symbolic techniques, based on the use of Binary Decision Diagrams, and heuristic search, driven by selection functions taking into account the degree of uncertainty. An extensive experimental evaluation of our planner HSCP against the state of the art conformant planners shows that our approach is extremely effective. In terms of search time, HSCP gains up to three orders of magnitude over the breadth-first, symbolic approach of CMBP, and up to five orders of magnitude over the heuristic search of GPT, requiring, at the same time, a much lower amount of memory.