TY - GEN
T1 - A new approach to tractable planning
AU - Haslum, Patrik
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58849113616&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577353867
T3 - ICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
SP - 132
EP - 139
BT - ICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
T2 - 18th International Conference on Automated Planning and Scheduling, ICAPS 2008
Y2 - 14 September 2008 through 18 September 2008
ER -