A new approach to tractable planning

Abstract

We describe a restricted class of planning problems and polynomial time membership and plan existence decision algorithms for this class. The definition of the problem class is based on a graph representation of planning problems, similar to Petri nets, and the use of a graph grammar to characterise a subset of such graphs. Thus, testing membership in the class is a graph parsing problem. The planning algorithm also exploits this connection, making use of the parse tree. We show that the new problem class is incomparable with, i.e., neither a subset nor a superset of, previously known classes of tractable planning problems.