Bertoli

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.