A translation-based approach to contingent planning
Alexandre Albore, Héctor Palacios, Héctor Geffner · 2009
The problem of planning in the presence of sens-ing has been addressed in recent years as a non-deterministic search problem in belief space. In this work, we use ideas advanced recently for compiling conformant problems into classical ones for intro-ducing a different approach where contingent prob-lems P are mapped into non-deterministic prob-lems X(P) in state space. We also identify a con-tingent width parameter, and show that for prob-lems P with bounded contingent width, the transla-tion is sound, polynomial, and complete. We then solve X(P) by using a relaxation X+(P) that is a classical planning problem. The formulation is tested experimentally over contingent benchmarks where it is shown to yield a planner that scales up better than existing contingent planners. 1