Conditional Planning under Partial Obserbability as Heuristic-Symbolic Search in Belief Space

Planning under partial observability is one of the most significant and challenging planning problems. It combines the need to deal with belief states, as in conformant planning, with the need for and-or search, typical of conditional planning. In this paper, we tackle the problem of planning under partial observability within the framework of planning via symbolic model checking. We propose a new algorithm for planning under partial observability, able to generate conditional plans that are guaranteed to achieve the goal despite of the uncertainty in the initial condition, the uncertain effects of actions, and the partial observability of the domain. The experimental evaluation compares the heuristic-symbolic algorithm with a recently proposed approach based on a depth-first search (/DFS) style. We show that, while /DFS search may often result in deep plans, and suffers sometimes from inefficiencies resulting from a `bad` initial choice, heuristic-symbolic search, even considering only a fixed simple selection function, constructs plans of better quality, and, for certain classes of problems may significantly improve the efficiency of the search