Tomas Rybecky presents Robotics RG

On 2021-11-12 - 2021-11-12 09:00:00 at JP:B-335
Dear colleagues,
let me invite you to the next robotics reading group, which takes place Friday
(12.11) at 9:00 in CIIRC: JP:B-335 (sorry for the late announcement). Tomas
Rybecky will present the following paper:

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, and Sven Koenig. 2021.
Anytime Multi-Agent Path Finding via Large Neighborhood Search. International
Joint Conference on Artificial Intelligence (IJCAI), pages 4127-4135

Paper link:

Video call link:

RG homepage:

Multi-Agent Path Finding (MAPF) is the challenging problem of computing
collision-free paths for multiple agents. Algorithms for solving MAPF can be
categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that
can find high-quality solutions for small problems. At the other end are
unbounded-suboptimal algorithms that can solve large problems but usually find
low-quality solutions. In this paper, we consider a third approach that
the best of both worlds: anytime algorithms that quickly find an initial
solution using efficient MAPF algorithms from the literature, even for large
problems, and that subsequently improve the solution quality to near-optimal as
time progresses by replanning subgroups of agents using Large Neighborhood
Search. We compare our algorithm MAPFLNS against a range of existing work and
report significant gains in scalability, runtime to the initial solution, and
speed of improving the solution.
Responsible person: Petr Pošík