On Producing Shortest Cost-Optimal Plans

Katz, Michael and Röger, Gabriele and Helmert, Malte. (2022) On Producing Shortest Cost-Optimal Plans. In: Proceedings of the Fifteenth International Symposium on Combinatorial Search (SoCS 2022). pp. 100-108.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/93541/

Downloads: Statistics Overview


Cost-optimal planning is at the heart of planning research, with many existing planners that produce provably optimal solutions. While some applications pose additional restrictions, such as producing shortest (in the number of actions) among the cost-optimal plans, standard cost-optimal planning does not provide such a guarantee. We discuss two possible approaches to produce provably the shortest among the costoptimal plans, one corresponding to an instantiation of costalgebraic A∗, the other based on a cost transformation. We formally prove that the new cost-transformation method indeed produces the shortest among the cost-optimal plans and empirically compare the performance of the approaches in different configurations.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Röger, Gabriele and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Identification Number:
edoc DOI:
Last Modified:17 Feb 2023 13:55
Deposited On:15 Feb 2023 10:41

Repository Staff Only: item control page