Compiling Uncertainty Away in Conformant Planning Problems with Bounded
  Width
  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.
