Parallel Non-Binary Planning in Polynomial Time

Abstract

This paper formally presents a class of planning problems which allows non-binary state variables and parallel execution of actions. The class is proven to be tractable, and we provide a sound and complete polynomial time algorithm for planning within this class. This result means that we are getting closer to tackling realistic planning problems in sequential control, where a restricted problem representation is often sufficient, but where the size of the problems make tractability an important issue. 1 Introduction A large proportion of earlier papers about planning focus either on implementation of planners, or on representation problems, using logic or otherwise, and do not address computational issues at all. Among earlier work on planning complexity, Chapman [ 1987 ] has designed an algorithm, called TWEAK, which captures the essentials of constraint-posting nonlinear planners. TWEAK is proven correct, but does not always terminate. Chapman has proven that the class of problems...