A Translation-Based Approach to Contingent Planning

Abstract

The problem of planning in the presence of sensing 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 introducing a different approach where contingent problems P are mapped into non-deterministic problems X(P) in state space. We also identify a contingent width parameter, and show that for problems P with bounded contingent width, the translation 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. Alexandre Albore, H�ctor Palacios, H�ctor Geffner