Multiagent Stochastic Shortest Path Problem

Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák
5/7/2026
cs.MA

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems

84% match2025

Cooperative Path Planning with Asynchronous Multiagent Reinforcement Learning

82% match2024

Bayesian learning for the stochastic shortest path problem

81% match2026

Scalable Mechanism Design for Multi-Agent Path Finding

80% match1 repo52024

Synthesis of Communication Policies for Multi-Agent Systems Robust to Communication Restrictions

80% match2025

Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding

80% match1 repo412023

Cite this paper

@article{jon2026multiagent,
  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},
  year   = {2026},
  eprint = {2605.06056},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2605.06056v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2605.06056.svg)](https://codeofpaper.com/paper/2605.06056)

Discussion