| Title: |
Planning with Uncertain Action Models |
| Authors: |
Percassi, Francesco; Saetti, Alessandro; Scala, Enrico |
| Contributors: |
Koenig, Sven; Jenkins, Chad; Taylor, Matthew E. |
| Source: |
Percassi, F, Saetti, A & Scala, E 2026, Planning with Uncertain Action Models. in S Koenig, C Jenkins & M E Taylor (eds), The Fortieth AAAI Conference on Artificial Intelligence : Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence. vol. 40, Proceedings of AAAI Conference on Artificial Intelligence, no. 43, vol. 40, AAAI press, pp. 36343-36350, The 40th Annual AAAI Conference on Artificial Intelligence, Singapore, 20/01/26. https://doi.org/10.1609/aaai.v40i43.40954 |
| Publisher Information: |
AAAI press |
| Publication Year: |
2026 |
| Description: |
Uncertainty over model knowledge is a core challenge in planning and has been addressed through various approaches tailored to different scenarios. In this paper, we focus on scenarios where the agent does not initially know the exact outcome of its actions but gains knowledge upon execution, i.e., each action reveals its actual effect, removing uncertainty about future occurrences. We refer to this formulation as Planning with Uncertain Models of Actions (PUMA). We show that PUMA can be compiled in polynomial time in both Fully Observable Non-Deterministic planning and, perhaps more unexpectedly, classical planning, providing a constructive proof that PUMA remains PSPACE-complete despite its apparent exponential uncertainty. Finally, we experimentally evaluate both compilations with benchmark domains that capture the key aspects of the problem. The results show the practical feasibility of our approach and reveal a complementary behavior between the two compilations. |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| ISBN: |
978-1-57735-906-7; 1-57735-906-2 |
| ISSN: |
15773590 |
| Relation: |
info:eu-repo/semantics/altIdentifier/isbn/1577359062; info:eu-repo/semantics/altIdentifier/isbn/9781577359067; urn:ISBN:1577359062; urn:ISBN:9781577359067 |
| DOI: |
10.1609/aaai.v40i43.40954 |
| Availability: |
https://pure.hud.ac.uk/en/publications/c83da935-9c5f-430e-b0b8-b09e747fb30d; https://doi.org/10.1609/aaai.v40i43.40954; https://ojs.aaai.org/index.php/AAAI/issue/view/725 |
| Rights: |
info:eu-repo/semantics/closedAccess |
| Accession Number: |
edsbas.FD698C04 |
| Database: |
BASE |