General policies, representations, and planning width

Mostra el registre complet Registre parcial de l'ítem

• 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.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.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.doi http://dx.doi.org/10.1609/aaai.v35i13.17398
• dc.identifier.issn 2159-5399
• dc.identifier.uri http://hdl.handle.net/10230/56349
• 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.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN-2015-67959-P
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/885107
• dc.rights © 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org)
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Deterministic Planning
• dc.title General policies, representations, and planning width
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/acceptedVersion