Skip navigation
Skip navigation

Planning graphs and propositional clause-learning

Rintanen, Jussi

Description

The planning graph of Blum and Furst is one of the frequently used tools in planning. It is a data structure which can be visualized as a bipartite graph with state variables and actions as nodes and which approximates (upper bound) the set of reachable states with a given number of sets of simultaneous actions. We show that the contents of planning graphs follow from two more general notions: extended clause learning restricted to 2-literal clauses and the representation of parallel plans...[Show more]

dc.contributor.authorRintanen, Jussi
dc.contributor.editorG. Brewka
dc.contributor.editorJ. Lang
dc.coverage.spatialSydney Australia
dc.date.accessioned2015-12-10T22:24:19Z
dc.date.createdSeptember 16-19 2008
dc.identifier.isbn9781577353843
dc.identifier.urihttp://hdl.handle.net/1885/53199
dc.description.abstractThe planning graph of Blum and Furst is one of the frequently used tools in planning. It is a data structure which can be visualized as a bipartite graph with state variables and actions as nodes and which approximates (upper bound) the set of reachable states with a given number of sets of simultaneous actions. We show that the contents of planning graphs follow from two more general notions: extended clause learning restricted to 2-literal clauses and the representation of parallel plans consisting of STRIPS actions in the classical propositional logic. This is the first time planning graphs have been given an explanation in terms of the inference methods used in SAT solvers. The work helps in bridging the gap between specialized algorithms devised for planning and general-purpose algorithms for automated reasoning.
dc.publisherAAAI Press
dc.relation.ispartofseriesInternational Conference on Principles of Knowledge Representation and Reasoning (KR 2008)
dc.sourceProceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning
dc.source.urihttp://www.informatik.uni-trier.de/~ley/db/conf/kr/kr2008.html
dc.subjectKeywords: Automated reasoning; Bipartite graphs; Classical propositional logic; Clause learning; Inference methods; Planning graphs; SAT solvers; State variables; Upper Bound; Algorithms; Data structures; Formal logic; Knowledge representation
dc.titlePlanning graphs and propositional clause-learning
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.ariespublicationu8803936xPUB267
local.type.statusPublished Version
local.contributor.affiliationRintanen, Jussi , College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage535
local.bibliographicCitation.lastpage543
dc.date.updated2016-02-24T11:43:57Z
local.identifier.scopusID2-s2.0-78650613101
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Rintanen_Planning_graphs_and_2008.pdf53.42 kBAdobe PDF    Request a copy
02_Rintanen_Planning_graphs_and_2008.pdf1.06 MBAdobe PDF    Request a copy
03_Rintanen_Planning_graphs_and_2008.pdf159.65 kBAdobe PDF    Request a copy
04_Rintanen_Planning_graphs_and_2008.pdf1.05 MBAdobe PDF    Request a copy


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

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator