Show simple item record Bonet, Blai Geffner, Héctor 2023-03-27T06:25:39Z 2023-03-27T06:25:39Z 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.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 (
dc.title General policies, representations, and planning width
dc.type info:eu-repo/semantics/article
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


This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


Compliant to Partaking