Probabilistic Robust Multi-Agent Path Finding
- Dor Atzmon
- Roni Stern
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Nathan R. Sturtevant
- Sven Koenig
In a multi-agent path finding (MAPF) problem, the task is to move a set of agents to their goal locations without conflicts. In the real world, unexpected events may delay some of the agents. In this paper, we therefore study the problem of finding a p-robust solution to a given MAPF problem, which is a solution that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that given solutions are p-robust. We also introduce an optimal CBS-based algorithm, called pR-CBS, and a fast suboptimal algorithm, called pR-GCBS, for finding such solutions. Our experiments show that a p-robust solution reduces the number of conflicts compared to optimal, non-robust solutions.
Citation
D. Atzmon, R. Stern, A. Felner, N. Sturtevant, S. Koenig. "Probabilistic Robust Multi-Agent Path Finding". ICAPS, (ed: J. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi), pp 29-37, October 2020.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Atzmon+al:ICAPS20,
author = {Dor Atzmon and Roni Stern and Ariel Felner and Nathan R. Sturtevant
and Sven Koenig},
title = {Probabilistic Robust Multi-Agent Path Finding},
Editor = {J. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas,
Shirin Sohrabi},
Pages = {29-37},
booktitle = {},
year = 2020,
}Last Updated: September 10, 2020Submitted by Sabina P
