Welcome to the UPF Digital Repository

Width and serialization of classical planning problems

Show simple item record

dc.contributor.author Geffner, Héctor
dc.contributor.author Lipovetzky, Nir
dc.date.accessioned 2013-05-08T14:49:03Z
dc.date.available 2013-05-08T14:49:03Z
dc.date.issued 2012
dc.identifier.citation Lipovetzky, Nir, Geffner, Hector. Width and serialization of classical planning problems. Frontiers in artificial intelligence and applications. ECAI 2012; 242: 540-545. DOI 10.3233/978-1-61499-098-7-540
dc.identifier.issn 0922-6389
dc.identifier.uri http://hdl.handle.net/10230/20578
dc.description.abstract We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance.
dc.description.sponsorship H. Geffner is partially supported by grants TIN2009-10232,MICINN, Spain, and EC-7PM-SpaceBook.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher IOS Press
dc.rights © 2012 The Author(s). This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License.
dc.subject.other Intel·ligència artificial
dc.subject.other Planificació -- Informàtica
dc.title Width and serialization of classical planning problems
dc.type info:eu-repo/semantics/conferenceObject
dc.identifier.doi http://dx.doi.org/10.3233/978-1-61499-098-7-540
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/publishedVersion


This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

Compliant to Partaking