From Conformant into Classical Planning: Efficient Translations That May be Complete Too

All Papers

Focusing on the computation of conformant plans whose verification can be done efficiently, we have recently proposed a polynomial scheme for mapping conformant problems P with deterministic actions into classical problems K(P). The scheme is sound as the classical plans are all conformant, but is incomplete as the converse relation does not always hold. In this paper, we extend this work and consider an alternative, more powerful translation based on the introduction of epistemic tagged literals KL/t where L is a literal in P and t is a set of literals in P unknown in the initial situation. The translation ensures that a plan makes KL/t true only when the plan makes L certain in P given the assumption that t is initially true. We show that under general conditions the new translation scheme is complete and that its complexity can be characterized in terms of a parameter of the problem that we call conformant width. We show that the complexity of the translation is exponential in the problem width only, find that the width of almost all benchmarks is 1, and show that a conformant planner based on this translation solves some interesting domains that cannot be solved by other planners. This translation is the basis for T_0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.