Multiagent Stochastic Shortest Path Problem

Jonáš, Martin; Kucera, Antonin; Kůr, Vojtěch; Mačák, Jan; Rehak, Vojtech

doi:10.24963/ijcai.2026/19

Multiagent Stochastic Shortest Path Problem

Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 163-171.

https://doi.org/10.24963/ijcai.2026/19

Keywords

Agent-based and Multi-agent Systems: Multi-agent planning
Agent-based and Multi-agent Systems: Coordination and cooperation

Abstract

We introduce and study the multi-agent stochastic shortest path (MSSP) problem, in which k agents strive to reach a target state, aiming to minimize the expected time to reach the target by any agent. We analyze the computational and strategy-complexity of the problem in both autonomous and coordinated settings, and we design efficient strategy-synthesis algorithms. The algorithms are experimentally evaluated on instances of increasing size against natural baselines.

Martin Jonáš, Antonin Kucera, Vojtěch Kůr, Jan Mačák, and Vojtech Rehak. 2026. Multiagent Stochastic Shortest Path Problem. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 163–171. https://doi.org/10.24963/ijcai.2026/19

@inproceedings{ijcai2026p19,
  title     = {Multiagent Stochastic Shortest Path Problem},
  author    = {Jonáš, Martin and Kucera, Antonin and Kůr, Vojtěch and Mačák, Jan and Rehak, Vojtech},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {163--171},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/19},
  url       = {https://doi.org/10.24963/ijcai.2026/19},
}

TY  - CPAPER
TI  - Multiagent Stochastic Shortest Path Problem
AU  - Jonáš, Martin
AU  - Kucera, Antonin
AU  - Kůr, Vojtěch
AU  - Mačák, Jan
AU  - Rehak, Vojtech
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 163
EP  - 171
DO  - 10.24963/ijcai.2026/19
UR  - https://doi.org/10.24963/ijcai.2026/19
ER  -