2019

DDM: Fast Near-Optimal Multi-Robot Path Planning using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics

Han, Shuai D., Yu, Jingjin

Understand

We propose a novel centralized and decoupled algorithm, DDM, for solving multi-robot path planning problems in grid graphs, targeting on-demand and automated warehouse-like settings.

Two settings are studied: a traditional one whose objective is to move a set of robots from their respective initial vertices to the goal vertices as quickly as possible, and a dynamic one which requires frequent re-planning to accommodate for goal configuration adjustments.
Among other techniques, DDM is mainly enabled through exploiting two innovative heuristics: path diversification and optimal sub-problem solution databases.
The two heuristics attack two distinct phases of a decoupling-based planner: while path diversification allows the more effective use of the entire workspace for robot travel, optimal sub-problem solution databases facilitate the fast resolution of local path conflicts.

Built on

J. van den Berg, M. C. Lin, and D. Manocha, “Reciprocal velocity obstacles for real-time multi-agent navigation,” in
1935
Earlier work this paper cites.
O. Goldreich, “Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard,” 1984, laboratory for Computer Science, Massachusetts Institute of Technology, Unpublished manuscript
1984
Earlier work this paper cites.
M. A. Erdmann and T. Lozano-Pérez, “On multiple moving objects,” in
1986
Earlier work this paper cites.
D. Rus, B. Donald, and J. Jennings, “Moving furniture with teams of autonomous robots,” in
1995
Earlier work this paper cites.
J. S. Jennings, G. Whelan, and W. F. Evans, “Cooperative search and rescue with a team of mobile robots,” in
1997
Earlier work this paper cites.
S. M. LaValle and S. A. Hutchinson, “Optimal motion planning for multiple robots having independent goals,”
1998
Earlier work this paper cites.
D. Fox, W. Burgard, H. Kruppa, and S. Thrun, “A probabilistic approach to collaborative multi-robot localization,”
2000
Earlier work this paper cites.
G. Sanchez and J.-C. Latombe, “Using a prm planner to compare centralized and decoupled planning for multi-robot systems,” in
2002
Earlier work this paper cites.
M. Bennewitz, W. Burgard, and S. Thrun, “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots,”
2002
Earlier work this paper cites.
Y. Guo and L. E. Parker, “A distributed and optimal motion planning approach for multiple mobile robots,” in
2002
Earlier work this paper cites.
S. Poduri and G. S. Sukhatme, “Constrained coverage for mobile sensor networks,” in
2004
Earlier work this paper cites.
J. van den Berg and M. Overmars, “Prioritized motion planning for multiple robots,” in
2005
Earlier work this paper cites.
E. J. Griffith and S. Akella, “Coordinating multiple droplets in planar array digital microfluidic systems,”
2005
Earlier work this paper cites.
A. Felner and A. Adler, “Solving the 24 puzzle with instance dependent pattern databases,” in
2005
Earlier work this paper cites.
M. Saha and P. Isto, “Multi-robot motion planning by incremental coordination,” in
2006
Earlier work this paper cites.
P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,” in
2007
Earlier work this paper cites.
A. Felner, R. E. Korf, R. Meshulam, and R. C. Holte, “Compressed pattern databases.”
2007
Earlier work this paper cites.
P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,”
2008
Earlier work this paper cites.

Similar

M. S. Branicky, R. A. Knepper, and J. J. Kuffner, “Path and trajectory diversity: Theory and algorithms,” in
2008
Cited alongside, same era.
J. van den Berg, J. Snoeyink, M. Lin, and D. Manocha, “Centralized path planning for multiple robots: Optimal decoupling into sequential plans,” in
2009
Cited alongside, same era.
B. Smith, M. Egerstedt, and A. Howard, “Automatic generation of persistent formations for multi-agent networks under range constraints,”
2009
Cited alongside, same era.
R. A. Knepper and M. T. Mason, “Path diversity is only part of the problem,” in
2009
Cited alongside, same era.
R. Tedrake, “Lqr-trees: Feedback motion planning on sparse randomized trees,” 2009
2009
Cited alongside, same era.
S. Rodriguez and N. M. Amato, “Behavior-based evacuation planning,” in
2010
Cited alongside, same era.
T. Standley and R. Korf, “Complete algorithms for cooperative pathfinding problems,” in
2011
Cited alongside, same era.
K.-H. C. Wang and A. Botea, “Mapp: a scalable multi-agent path planning algorithm with tractability and completeness guarantees,”
2011
Cited alongside, same era.
J. Snape, J. van den Berg, S. J. Guy, and D. Manocha, “The hybrid reciprocal velocity obstacle,”
2011
Cited alongside, same era.
R. A. Knepper and D. Rus, “Pedestrian-inspired sampling-based multi-robot collision avoidance,” in
2012
Cited alongside, same era.
P. Surynek, “Towards optimal cooperative path planning in hard setups through satisfiability solving,” in
2012
Cited alongside, same era.
J. Yu and S. M. LaValle, “Distance optimal formation control on graphs with a tight convergence time guarantee,” in
2012
Cited alongside, same era.

Then

G. Wagner and H. Choset, “Subdimensional expansion for multirobot path planning,”
2015
Later among the works it cites.
E. Boyarski, A. Felner, R. Stern, G. Sharon, O. Betzalel, D. Tolpin, and E. Shimony, “Icbs: The improved conflict-based search algorithm for multi-agent pathfinding,” in
2015
Later among the works it cites.
A. Adler, M. De Berg, D. Halperin, and K. Solovey, “Efficient multi-robot motion planning for unlabeled discs in simple polygons,” in
2015
Later among the works it cites.
K. Solovey, J. Yu, O. Zamir, and D. Halperin, “Motion planning for unlabeled discs with optimality guarantees,” in
2015
Later among the works it cites.
J. Yu and S. M. LaValle, “Optimal multi-robot path planning on graphs: Complete algorithms and effective heuristics,”
2016
Later among the works it cites.
L. Cohen, T. Uras, T. Kumar, H. Xu, N. Ayanian, and S. Koenig, “Improved bounded-suboptimal multi-agent path finding solvers,” in
2016
Later among the works it cites.
Y.-H. Lyu, Y. Chen, and D. Balkcom, “
2016
Later among the works it cites.
H. Ma, J. Li, T. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in
2017
Later among the works it cites.
K. Hauser, “Learning the problem-optimum map: Analysis and application to global optimization in robotics,”
2017
Later among the works it cites.
J. Yu, “Constant factor time optimal multi-robot routing on high-dimensional grids in mostly sub-quadratic time,”
Original
2018
Later among the works it cites.
R. Chinta, S. D. Han, and J. Yu, “Coordinating the motion of labeled discs with optimality guarantees under extreme density,” in
2018
Later among the works it cites.
R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar,
Original
2019
Closest in time.
K. Vedder and J. Biswas, “X*: Anytime multiagent planning with bounded search,” in
2019
Closest in time.
D. Sigurdson, V. Bulitko, S. Koenig, C. Hernandez, and W. Yeoh, “Automatic algorithm selection in multi-agent pathfinding,”
Original
2019
Closest in time.
W. Hoenig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Persistent and robust execution of mapf schedules in warehouses,”
2019
Closest in time.
K. Okumura, M. Machida, X. Défago, and Y. Tamura, “Priority inheritance with backtracking for iterative multi-agent path finding,”
Original
2019
Closest in time.
L. H. Erickson and S. M. LaValle, “Survivability: Measuring and ensuring path diversity,” in
2073
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…