Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics

By Jingjin Yu, Steven M. LaValle. IEEE Transactions on robotics, 2015

355 citations recorded by the source corpus.

We study optimal multirobot path planning on graphs (MPP) over four minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. Having established previously that these objectives are distinct and NP-hard to optimize, in this paper, we focus on efficient algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and a special type of multiflow network. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first that is capable of solving extremely challenging problems with robot-vertex ratios as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of slight optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/c8224e6ddc5f203ae45f62032e915b8bff749ad0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

A Survey on Aerial Swarm Robotics (2018, methodology): “Optimality in the multirobot path planning problem (7) may be with respect to any number of different objectives, including integrated control effort, maximum single-robot travel distance, last arrival time, and total distance or time [90].”
Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios (2020, methodology): “Some of the prior works, known as centralized methods , such as those by Schwartz and Sharir (1983), Yu and LaValle (2016), and Tang et al. (2018), assume that the actions of all agents are determined by a central server aware of comprehensive knowledge about all agents’ intents (e.g., initial…”