Tractable plan existence does not imply tractable plan generation

We present a class, 3S, of planning instances such that the plan existence problem is tractable while plan generation is provably intractable for instances of this class. The class is defined by simple structural restrictions, all of them testable in polynomial‐time. Furthermore, we show that plan generation can be carried out in time bounded by a polynomial in the size of the input and the size of the generated solution. For this class, we propose a provably sound and complete incremental planner, i.e., a planner that can usually output an executable prefix of the final plan before it has generated the whole plan. This revised version was published online in June 2006 with corrections to the Cover Date.