Width and serialization of classical planning problems
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Geffner, Héctorca
- dc.contributor.author Lipovetzky, Nirca
- dc.date.accessioned 2013-05-08T14:49:03Z
- dc.date.available 2013-05-08T14:49:03Z
- dc.date.issued 2012ca
- 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.en
- dc.description.sponsorship H. Geffner is partially supported by grants TIN2009-10232,MICINN, Spain, and EC-7PM-SpaceBook.
- dc.format.mimetype application/pdfca
- 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-540ca
- dc.identifier.doi http://dx.doi.org/10.3233/978-1-61499-098-7-540
- dc.identifier.issn 0922-6389ca
- dc.identifier.uri http://hdl.handle.net/10230/20578
- dc.language.iso engca
- dc.publisher IOS Pressca
- dc.relation.projectID info:eu-repo/grantAgreement/ES/3PN/TIN2009-10232
- 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.ca
- dc.rights.accessRights info:eu-repo/semantics/openAccessca
- dc.subject.other Intel·ligència artificial
- dc.subject.other Planificació -- Informàtica
- dc.title Width and serialization of classical planning problemsca
- dc.type info:eu-repo/semantics/conferenceObjectca
- dc.type.version info:eu-repo/semantics/publishedVersionca