A New Approach To Tractable Planning

Patrik Haslum

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.

URL: http://users.rsise.anu.edu.au/~patrik/

Subjects: 1.11 Planning; 9.2 Computational Complexity

Submitted: Jun 23, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.