Recent Progress in Multi-Robot/Agent Motion Planning
Wednesday, April 6th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)
Tzvika Geft, Tel Aviv University
Abstract:
In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of
robots from given start to target positions. Multi-Agent Path Finding (MAPF) is
a discretized version of MRMP, where the robots are agents moving on a graph.
In this talk, I will describe recent results and work in progress for a few
MAPF variants. For the flow time objective, where the goal is to minimize the
sum of arrival times of all agents, I will present a restricted case in which
the problem becomes tractable. I will then shift to describing a heuristic
algorithm for the total distance objective, where the aim is to minimize the
total distance travelled. The algorithm’s main innovation is a global
outlook-based method of dynamic prioritization and adaptive paths. Experiments
show that the algorithm quickly finds solutions better than 1.05-optimal for
grids that have up to 25% of their vertices occupied by agents. This part of
the talk is based on joint work with Noam Geller, Michael Bilevich, and Dan
Halperin. If time permits, I will discuss progress on additional MAPF/MRMP
variants.