A new approach to tractable planning

Patrik Haslum*

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    4 Citations (Scopus)

    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.

    Original languageEnglish
    Title of host publicationICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
    Pages132-139
    Number of pages8
    Publication statusPublished - 2008
    Event18th International Conference on Automated Planning and Scheduling, ICAPS 2008 - Sydney, NSW, Australia
    Duration: 14 Sept 200818 Sept 2008

    Publication series

    NameICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling

    Conference

    Conference18th International Conference on Automated Planning and Scheduling, ICAPS 2008
    Country/TerritoryAustralia
    CitySydney, NSW
    Period14/09/0818/09/08

    Fingerprint

    Dive into the research topics of 'A new approach to tractable planning'. Together they form a unique fingerprint.

    Cite this