Multiagent Stochastic Shortest Path Problem

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

IJCAI 20260 citations

Multiagent Stochastic Shortest Path Problem

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

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.

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

BibTeX

@inproceedings{ijcai2026_multiagentstocha,
  title = {Multiagent Stochastic Shortest Path Problem},
  author = {Martin Jonáš and Antonín Kučera and Vojtěch Kůr and Jan Mačák and Vojtěch Řehák},
  booktitle = {IJCAI 2026},
  year = {2026}
}