dc.contributor.author |
Bonet, Blai |
dc.contributor.author |
Geffner, Héctor |
dc.date.accessioned |
2023-03-27T06:25:39Z |
dc.date.available |
2023-03-27T06:25:39Z |
dc.date.issued |
2021 |
dc.identifier.citation |
Bonet B, Geffner H. General policies, representations, and planning width. Proc Conf AAAI Artif Intell. 2021;35(13):11764-73. DOI: 10.1609/aaai.v35i13.17398 |
dc.identifier.issn |
2159-5399 |
dc.identifier.uri |
http://hdl.handle.net/10230/56349 |
dc.description.abstract |
It has been observed that in many of the benchmark planning domains, atomic goals can be reached with a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width. Such problems have indeed a bounded width: a width that does not grow with the number of problem variables and is often no greater than two. Yet, while the notion of width has become part of the state- of-the-art planning algorithms like BFWS, there is still no good explanation for why so many benchmark domains have bounded width. In this work, we address this question by relating bounded width and serialized width to ideas of generalized planning, where general policies aim to solve multiple instances of a planning problem all at once. We show that bounded width is a property of planning domains that admit optimal general policies in terms of features that are explicitly or implicitly represented in the domain encoding. The results are extended to the larger class of domains with bounded serialized width where the general policies do not have to be optimal. The study leads also to a new simple, meaningful, and expressive language for specifying domain serializations in the form of policy sketches which can be used for encoding domain control knowledge by hand or for learning it from traces. The use of sketches and the meaning of the theoretical results are all illustrated through a number of examples. |
dc.description.sponsorship |
The research is partially funded by an ERC Advanced Grant (No 885107), by grant TIN-2015-67959-P from MINECO, Spain, and by the Knut and Alice Wallenberg (KAW) Foundation through the WASP program. H. Geffner is a also Wallenberg Guest Professor at Linkoping University, Sweden. |
dc.format.mimetype |
application/pdf |
dc.language.iso |
eng |
dc.publisher |
Association for the Advancement of Artificial Intelligence (AAAI) |
dc.relation.ispartof |
Proceedings of the AAAI Conference on Artificial Intelligence. 2021;35(13):11764-73. |
dc.rights |
© 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org) |
dc.title |
General policies, representations, and planning width |
dc.type |
info:eu-repo/semantics/article |
dc.identifier.doi |
http://dx.doi.org/10.1609/aaai.v35i13.17398 |
dc.subject.keyword |
Deterministic Planning |
dc.relation.projectID |
info:eu-repo/grantAgreement/ES/1PE/TIN-2015-67959-P |
dc.relation.projectID |
info:eu-repo/grantAgreement/EC/H2020/885107 |
dc.rights.accessRights |
info:eu-repo/semantics/openAccess |
dc.type.version |
info:eu-repo/semantics/acceptedVersion |