Incremental Planning

. Ambros-Ingerson and Steel suggested to interleave planning and execution through incremental planning, ie. using a planner that can output valid prefixes of the final plan before it has finished planning. This method could considerably bring down the time lost in planning, especially in dynamic domains, where replanning has to occur frequently. We improve on the basic idea, avoiding certain problems, by presenting an incremental planner with provable properties for a restricted class of planning problems, the 3S class. Finding out whether a 3S instance is solvable or not is computationally tractable, despite the fact that generating a plan is inherently intractable. By first testing whether an instance is solvable or not, we can avoid outputting prefixes of invalid plans in the latter case. Furthermore, making the reasonable assumption that natural problems have non-exponential-size solutions, we can also plan efficiently in practice since we need not waste time on non-solvable insta..