@inbook{b61e096d1f3e4df5bb94c5c19c16c80d,
title = "An effective algorithmic framework for near optimal multi-robot path planning",
abstract = "We present a centralized algorithmic framework for solving multi-robot path planning problems in general, two-dimensional, continuous environments while minimizing globally the task completion time. The framework obtains high levels of effectiveness through the composition of an optimal discretization of the continuous environment and the subsequent fast, near-optimal resolution of the resulting discrete planning problem. This principled approach achieves orders of magnitudes better performance with respect to both speed and the supported robot density. For a wide variety of environments, our method is shown to compute globally near-optimal solutions for 50 robots in seconds with robots packed close to each other. In the extreme, the method can consistently solve problems with hundreds of robots that occupy over 30% of the free space.",
keywords = "Continuous Environment, Discrete Plane, Multi-robot Path Planning, Robot Density, Task Completion Time",
author = "Jingjin Yu and Daniela Rus",
note = "Funding Information: Acknowledgements This work was supported in part by ONR projects N00014-12-1-1000 and N00014-09-1-1051, and the Singapore-MIT Alliance on Research and Technology (SMART) Future of Urban Mobility project. We are grateful for the funding support that we receive. We also thank the reviewers for their insightful comments that helped significantly improve the quality of the paper. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.",
year = "2018",
doi = "10.1007/978-3-319-51532-8_30",
language = "English (US)",
series = "Springer Proceedings in Advanced Robotics",
publisher = "Springer Science and Business Media B.V.",
pages = "495--511",
booktitle = "Springer Proceedings in Advanced Robotics",
}