AAAI Publications, Sixth European Conference on Planning

Font Size: 
Conditional Planning under Partial Observability as Heuristic-Symbolic Search in Belief Space
Piergiorgio Bertoli, Alessandro Cimatti, Marco Roveri

Last modified: 2014-05-21


Planning under partial observability in nondeterministic domains is a very significant and challenging problem, which requires dealing with uncertainty together with and-or search. In this paper, we propose a new algorithm for tackling this problem, able to generate conditional plans that are guaranteed to achieve the goal despite of the uncertainty in the initial condition and the uncertain effects of actions. The proposed algorithm combines heuristic search in the and-or space of beliefs with symbolic BDD-based techniques, and is fully amenable to the use of selection functions. The experimental evaluation shows that heuristic-symbolic search may behave much better than state-of-the-art search algorithms, based on a depth-first search (DFS) style, on several domains.

Full Text: PDF