Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects

Mostra el registre complet Registre parcial de l'ítem

  • dc.contributor.author Segovia-Aguas, Javier
  • dc.contributor.author Jiménez, Sergio
  • dc.contributor.author Jonsson, Anders, 1973-
  • dc.date.accessioned 2025-01-19T16:48:19Z
  • dc.date.available 2025-01-19T16:48:19Z
  • dc.date.issued 2024
  • dc.description.abstract Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State-space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g. integers.
  • dc.description.sponsorship This work has been co-funded by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M), TAILOR (H2020 #952215) and AIPlan4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jiménez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
  • dc.format.mimetype application/pdf
  • dc.identifier.citation Segovia-Aguas J, Jiménez S, Jonsson A. Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects. Artif Intell. 2024 May;330:104097. DOI: 10.1016/j.artint.2024.104097
  • dc.identifier.doi http://dx.doi.org/10.1016/j.artint.2024.104097
  • dc.identifier.issn 0004-3702
  • dc.identifier.uri http://hdl.handle.net/10230/69166
  • dc.language.iso eng
  • dc.publisher Elsevier
  • dc.relation.ispartof Artificial Intelligence. 2024 May;330:104097
  • dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/952215
  • dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/101016442
  • dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-108141 GB-I00
  • dc.relation.projectID info:eu-repo/grantAgreement/ES/3PE/PID2021-127647NB-C22
  • dc.rights © 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
  • dc.rights.accessRights info:eu-repo/semantics/openAccess
  • dc.rights.uri http://creativecommons.org/licenses/by-nc/4.0/
  • dc.subject.keyword Generalized planning
  • dc.subject.keyword Classical planning
  • dc.subject.keyword Heuristic search
  • dc.subject.keyword Planning and learning
  • dc.subject.keyword Domain-specific control knowledge
  • dc.subject.keyword Program synthesis
  • dc.subject.keyword Programming by example
  • dc.title Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects
  • dc.type info:eu-repo/semantics/article
  • dc.type.version info:eu-repo/semantics/publishedVersion

Col·leccions

Articles (Departament de Tecnologies de la Informació i les Comunicacions)
Documents OpenAIRE (Open Access Infrastructure for Research in Europe)