Probabilistic Robust Multi-Agent Path Finding

Dor Atzmon, Roni Stern, Ariel Felner, Nathan R. Sturtevant, Sven Koenig

PosterID: 13 PDF Poster BibTeX

In a multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents to their goals without collisions. In the real world, unexpected events may delay some of the agents, and following the intended plan may not be possible. In this paper, we study the problem of finding a p-robust plan, which is a plan that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that a given plan is p-robust and introduce an optimal algorithm and a fast, suboptimal algorithm for finding such a plan. Our experiments show that using a p-robust plan reduces the number of collisions that occur during executions compare to optimal, non-robust plans.

Session E9: Multi-Agent Planning
Canb 10/27/2020, 21:00 – 22:00
10/31/2020, 04:00 – 05:00
Paris 10/27/2020, 11:00 – 12:00
10/30/2020, 18:00 – 19:00
NYC 10/27/2020, 06:00 – 07:00
10/30/2020, 13:00 – 14:00
LA 10/27/2020, 03:00 – 04:00
10/30/2020, 10:00 – 11:00