Abstract:
An important aspect of nonlinear planning is the resolution of conflicts between actions inserted into a plan. We present a technique for automatically deciding which conflicts should be resolved during planning, and which should be delayed until planning is otherwise complete. In particular we show that many potential conflicts can be provably delayed until the end; that is, if the planner can find a plan for the goal while ignoring these conflicts, there is a guarantee that the partial ordering in the resulting plan can be extended to eliminate the conflicts.