EUVIMEDEUVIMED entdecken
Crossref

Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning

Rasmus G. Tollund, Álvaro Torralba

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →