Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36429-36437
DOI: 10.1609/aaai.v40i43.40964 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Rasmus G. Tollund und 1 weiteren Autor:innen.
Abstract (Originalsprache)
In many planning problems there are non-deterministic actions for which the outcome cannot be fully controlled by the planning agent. For critical tasks, we need to find a strategy that achieves the goal within a predictable time-frame and/or cost. Thus, we consider an adversarial planning setting and compute optimal policies that optimize the worst-case cost to reach the goal. In this work, we introduce domain-independent optimal heuristic search algorithms for this adversarial setting. To guide the search, we show how to leverage classical planning heuristics by applying single-outcome determinization. We also generalize dominance techniques, that analyse when a state is as good as another, to the non-deterministic setting and apply them to prune the search space. Our experimental analysis shows that both methods greatly help to compute optimal policies across multiple domains.
Zitieren
APA
Tollund, R. G., & Torralba, Á. (2026). Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36429-36437. https://doi.org/10.1609/aaai.v40i43.40964
Vancouver
Tollund RG, Torralba Á. Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36429-36437. doi:10.1609/aaai.v40i43.40964
BibTeX
@article{Tollund2026,
author = {Tollund, Rasmus G. and Torralba, Álvaro},
title = {Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36429--36437},
doi = {10.1609/aaai.v40i43.40964}
}
EUVIMED