AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
A Translation-based Approach to Contingent Planning
Alexandre Albore, Héctor Palacios, Héctor Geffner

Last modified: 2009-06-26

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.

Full Text: PDF