Optimality Certificates for Classical Planning

Mugdan, Esther and Christen, Remo and Eriksson, Salomé. (2023) Optimality Certificates for Classical Planning. In: Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023), 33. Palo Alto, California USA, pp. 286-294.

[img] PDF - Published Version

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

Downloads: Statistics Overview


Algorithms are usually shown to be correct on paper, but bugs in their implementations can still lead to incorrect results. In the case of classical planning, it is fortunately straightforward to check whether a computed plan is correct. For optimal planning, however, plans are additionally required to have minimal cost, which is significantly more difficult to verify. While some domain-specific approaches exists, we lack a general tool to verify optimality for arbitrary problems. We bridge this gap and introduce two approaches based on the principle of certifying algorithms, which provide a computer-verifiable certificate of correctness alongside their answer. We show that both approaches are sound and complete, analyze whether they can be generated and verified efficiently, and show how to apply them to concrete planning algorithms. The experimental evaluation shows that verifying optimality comes with a cost, but is still practically feasible. Furthermore, it confirms that the tested planner configurations provide optimal plans on the given instances, as all certificates were verified successfully.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Christen, Remo and Mugdan, Esther and Eriksson, Salomé
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
Related URLs:
edoc DOI:
Last Modified:19 Sep 2023 06:35
Deposited On:29 Aug 2023 09:25

Repository Staff Only: item control page