Multiagent Stochastic Shortest Path Problem
For researchers in multi-agent systems and stochastic optimization, this work formalizes a new problem and provides algorithms, though the experimental gains are not quantified with concrete numbers.
The paper introduces the multi-agent stochastic shortest path problem, where k agents aim to minimize the expected time for any agent to reach a target. It provides computational complexity analysis and efficient strategy-synthesis algorithms, with experimental evaluation showing improvements over baselines.
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.