A new approach to tractable planning
Download (281.76 kB)
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.author | Haslum, Patrik | |
---|---|---|
dc.coverage.spatial | Sydney Australia | |
dc.date.accessioned | 2015-12-10T22:21:45Z | |
dc.date.created | September 14-18 2008 | |
dc.identifier.isbn | 9781577353867 | |
dc.identifier.uri | http://hdl.handle.net/1885/52349 | |
dc.description.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. | |
dc.publisher | AAAI Press | |
dc.relation.ispartofseries | International Conference on Automated Planning and Scheduling (ICAPS 2008) | |
dc.source | Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008) | |
dc.source.uri | http://www.informatik.uni-trier.de/~ley/db/conf/aips/index.html | |
dc.subject | Keywords: 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.title | A new approach to tractable planning | |
dc.type | Conference paper | |
local.description.notes | Imported from ARIES | |
local.description.refereed | Yes | |
dc.date.issued | 2008 | |
local.identifier.absfor | 080199 - Artificial Intelligence and Image Processing not elsewhere classified | |
local.identifier.ariespublication | u8803936xPUB244 | |
local.type.status | Published Version | |
local.contributor.affiliation | Haslum, Patrik , College of Engineering and Computer Science, ANU | |
local.description.embargo | 2037-12-31 | |
local.bibliographicCitation.startpage | 132 | |
local.bibliographicCitation.lastpage | 139 | |
dc.date.updated | 2016-02-24T11:43:49Z | |
local.identifier.scopusID | 2-s2.0-58849113616 | |
Collections | ANU Research Publications |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
01_Haslum_A_new_approach_to_tractable_2008.pdf | 281.76 kB | Adobe PDF | ![]() |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 19 May 2020/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator