Towards a Theory of Conflict Detection and Resolution in Nonlinear Plans

Abstract

This paper deals with a well known problem in AI planning: detecting and resolving conflicts in nonlinear plans. We sketch a theory of restricted conflict detection and resolution that subsumes conflict handling in classical nonlinear planners. By relaxing the restrictions, we develop a more general concept of conflicts suggesting practical and theoretical limitations of conflict handling in nonlinear plans. 1 The problem Nonlinear planning was invented [Saccrdoti, 1977, Tate, 1977] as a lea, st commitment strategy for operator ordering. A nonlinear plan specifies a strict partial ordering on operators that can be interpreted to represent every linear ordering compatible with it. (Note that NOAH [Saccrdoti, 1977], e.g., uses a specialization of this interpretation as it does not allow every compatible linear ordering but considers ordering whole branches only.) While being efficient in that it allows whole areas of the space of linear plans to be searched at once, nonlinear planning poses a new problem compared to linear planning: one has to decide whether really every linear ordering of operators in a nonlinear plan results in a correct operator sequence to be executed. This is the well known problem of detecting and if necessary—resolving conflicts in nonlinear plans. Of course, conflicts also arise in linear plans: a STRIPS [Fikes et. a/., 1971] plan, e.g., containing what we call a conflict would simply be incorrect or incomplete. But as linear plans are special cases of nonlinear ones, conflict handling in linear plans proves to be less complex. Although every nonlinear planner has to detect and resolve conflicts in one way or another, there is no coherent theory of conflict handling. Instead, this is described anew for every planner, and it seems that some planner implementors have deviated from the path of generality without mentioning that they have done so. In this paper, we deliver a sketch of a theory of conflict detection and resolution in nonlinear plans. The emphasis is on the coherence of the theory developed; we do not claim all the ideas we present here are new. 2 The