---
title: "Multiagent Stochastic Shortest Path Problem"
authors:
  - "Martin Jonáš"
  - "Antonín Kučera"
  - "Vojtěch Kůr"
  - "Jan Mačák"
  - "Vojtěch Řehák"
doi: "10.24963/ijcai.2026/19"
url: "https://ijcai.org/proceedings/2026/19"
pdf: "https://ijcai.org/proceedings/2026/0019.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "163-171"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Multi-agent planning"
  - "Agent-based and Multi-agent Systems: Coordination and cooperation"
---

# Multiagent Stochastic Shortest Path Problem

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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 163-171. DOI: [10.24963/ijcai.2026/19](https://doi.org/10.24963/ijcai.2026/19)

## 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.