Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width
This work addresses the challenge of scaling up conformant planning for AI systems dealing with uncertainty, representing an incremental improvement by reformulating the problem to leverage existing classical planning tools.
The authors tackled the problem of conformant planning under uncertainty by automatically converting deterministic conformant problems into classical planning problems, which can then be solved using off-the-shelf classical planners. They showed that this translation is sound and complete under certain conditions, with complexity exponential in a bounded parameter called conformant width, and their planner T0 achieved best performance in the 2006 International Planning Competition.
Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.