Planning under Partial Observability by Classical Replanning: Theory and Experiments
Blai Bonet and Hector Geffner
Planning with partial observability can be formulated as a non-deterministic search problem in belief space. The problem is harder than classical planning due to two main reasons: keeping track of beliefs is harder than keeping track of single states, and searching for a policy or tree is harder than searching for an action sequence. In this work, we develop a framework for partial observability that avoids these two bottlenecks, and which leads to a partially observable planner that scales up to much larger problems. For this, the class of problems that is addressed is restricted to those that are deterministic, and where 1) the non-unary clauses representing uncertainty about the initial situation are invariant, and 2) the fluents that are hidden initially, do not appear in the bodies of conditional effects. We show first that such problems can be translated in linear time into equivalent fully observable non-deterministic planning problems, and that an slight extension of this translation, renders the original problem solvable by means of classical planners. The whole approach is sound and complete provided that in addition to the restrictions above, the state-space is connected, while it remains sound under much broader conditions. The basic scheme is then extended with deal with non-deterministic actions with observable effects, and a number of experiments are reported.