Expressing and exploiting the common subgoal structure of classical planning domains using sketches

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Drexler, Dominik
• dc.contributor.author Seipp, Jendrik
• dc.contributor.author Geffner, Héctor
• dc.date.accessioned 2023-02-07T07:10:15Z
• dc.date.available 2023-02-07T07:10:15Z
• dc.date.issued 2021
• dc.description Comunicació presentada a 18th International Conference on Principles of Knowledge Representation and Reasoning (KR2021), celebrat del 3 al 12 de novembre de 2021 de manera virtual.
• dc.description.abstract Width-based planning methods deal with conjunctive goals by decomposing problems into subproblems of low width. Algorithms like SIW thus fail when the goal is not easily serializable in this way or when some of the subproblems have a high width. In this work, we address these limitations by using a simple but powerful language for expressing finer problem decompositions introduced recently by Bonet and Geffner, called policy sketches. A policy sketch R over a set of Boolean and numerical features is a set of sketch rules that express how the values of these features are supposed to change. Like general policies, policy sketches are domain general, but unlike policies, the changes captured by sketch rules do not need to be achieved in a single step. We show that many planning domains that cannot be solved by SIW are provably solvable in low polynomial time with the SIW_R algorithm, the version of SIW that employs user-provided policy sketches. Policy sketches are thus shown to be a powerful language for expressing domain-specific knowledge in a simple and compact way and a convenient alternative to languages such as HTNs or temporal logics. Furthermore, they make it easy to express general problem decompositions and prove key properties of them like their width and complexity.
• dc.description.sponsorship This work was partially supported by an ERC Advanced Grant (grant agreement no. 885107), by project TAILOR, funded by EU Horizon 2020 (grant agreement no. 952215), and by the Knut and Alice Wallenberg Foundation. Hector Geffner is a Wallenberg Guest Professor at Linkoping University, Sweden. We used compute resources from the Swedish National Infrastructure for Computing (SNIC), partially funded by the Swedish Research Council through grant agreement no. 2018-05973.
• dc.format.mimetype application/pdf
• dc.identifier.citation Drexler D, Seipp, J, Geffner H. Expressing and exploiting the common subgoal structure of classical planning domains using sketches. In: Bienvenu M, Lakemeyer G, Erdem E, editors. Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning; 2021 Nov 3-12; online. [place unknown]: IJCAI Organization; 2021. p. 258-68. DOI: 10.24963/kr.2021/25
• dc.identifier.doi http://dx.doi.org/10.24963/kr.2021/25
• dc.identifier.issn 2334-1033
• dc.identifier.uri http://hdl.handle.net/10230/55648
• dc.language.iso eng
• dc.publisher IJCAI Proceedings
• dc.relation.ispartof Bienvenu M, Lakemeyer G, Erdem E, editors. Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning; 2021 Nov 3-12; online. [place unknown]: IJCAI Organization; 2021. p. 258-68.
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/952215
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/885107
• dc.rights © 2021 International Joint Conferences on Artificial Intelligence. This is the published version of a paper available at https://doi.org/10.24963/kr.2021/25 that appeared in the Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning.
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Decision making
• dc.subject.keyword Reasoning about actions and change
• dc.subject.keyword Action languages
• dc.title Expressing and exploiting the common subgoal structure of classical planning domains using sketches
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/publishedVersion