Skip navigation
Skip navigation

A new approach to tractable planning

Haslum, Patrik

Description

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...[Show more]

dc.contributor.authorHaslum, Patrik
dc.contributor.editorJ. Rintanen
dc.contributor.editorB. Nebel
dc.contributor.editorJ.C. Bech
dc.contributor.editorE. Hansen
dc.coverage.spatialSydney Australia
dc.date.accessioned2015-12-10T22:21:45Z
dc.date.createdSeptember 14-18 2008
dc.identifier.isbn9781577353867
dc.identifier.urihttp://hdl.handle.net/1885/52349
dc.description.abstractWe 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.
dc.publisherAAAI Press
dc.relation.ispartofseriesInternational Conference on Automated Planning and Scheduling (ICAPS 2008)
dc.sourceProceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008)
dc.source.urihttp://www.informatik.uni-trier.de/~ley/db/conf/aips/index.html
dc.subjectKeywords: Decision algorithms; Graph grammars; Graph parsing; Graph representations; New approaches; Parse trees; Planning algorithms; Planning problems; Polynomial-time; Formal languages; Graph theory; Marine biology; Petri nets; Polynomial approximation; Scheduli
dc.titleA new approach to tractable planning
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2008
local.identifier.absfor080199 - Artificial Intelligence and Image Processing not elsewhere classified
local.identifier.ariespublicationu8803936xPUB244
local.type.statusPublished Version
local.contributor.affiliationHaslum, Patrik , College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage132
local.bibliographicCitation.lastpage139
dc.date.updated2016-02-24T11:43:49Z
local.identifier.scopusID2-s2.0-58849113616
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Haslum_A_new_approach_to_tractable_2008.pdf281.76 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator