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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Warehousing systems from Kiva Systems [40] can work effectively with hundreds of robots. However, these robots essentially live on a grid within a structured environment.
- 2.
Due to limited space, detailed description of the ILP algorithm (Sect. 4) and larger versions of some figures are included in the online material available at http://arxiv.org/abs/1505.00200. An accompanying video demonstrating our algorithm and software developed in this paper are available from the corresponding author’s website.
- 3.
Note that our algorithmic framework also applies to other time- and distance-based optimality objectives through the use of an appropriate discrete planning algorithm.
- 4.
- 5.
These tilings are: triangular, trihexagonal, square, elongated triangular, hexagonal, truncated square, truncated trihexagonal, truncated hexagonal, snub square, rhombitrihexagonal, snub hexagonal.
References
Alonso-Mora, J.: Collaborative Motion Planning for Multi-Agent Systems. Ph.D. thesis, ETH Zurich, March 2014
Bien, Z., Lee, J.: A minimum-time trajectory planning method for two robots. IEEE Trans. Robot. Autom. 8(3), 414–418 (1992)
Buckley, S.J.: Fast motion planning for multiple moving robots. In: ICRA (1989)
Cgal, Computational Geometry Algorithms Library. http://www.cgal.org
Erdmann, M.A., Lozano-Pérez, T.: On multiple moving objects. In: ICRA (1986)
Ghosh, S.K., Maheshwari, A., Pal, S.P., Saluja, S., Madhavan, C.V.: Characterizing and recognizing weak visibility polygons. Comput. Geom. 3(4), 213–233 (1993)
Ghrist, R., O’Kane, J.M., LaValle, S.M.: Computing Pareto optimal coordinations on roadmaps. IJRR 24(11), 997–1010 (2005)
Griffith, E.J., Akella, S.: Coordinating multiple droplets in planar array digital microfluidic systems. IJRR 24(11), 933–949 (2005)
Gurobi Optimization Inc. Gurobi optimizer reference manual (2015)
Hopcroft, J.E., Schwartz, J.T., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the “warehouseman’s problem”. IJRR 3(4), 76–88 (1984)
Kant, K., Zucker, S.: Towards efficient trajectory planning: the path velocity decomposition. IJRR 5(3), 72–89 (1986)
Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
Knepper, R.A., Rus, D.: Pedestrian-inspired sampling-based multi-robot collision avoidance. In: RO-MAN (2012)
Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: FOCS (1984)
Krontiris, A., Sajid, Q., Bekris, K.: Towards using discrete multiagent pathfinding to address continuous problems. In: AAAI-WoMP (2012)
LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning. Technical report, Iowa State University, October 1998. Computer Science Department TR 98-11
LaValle, S.M., Hutchinson, S.A.: Optimal motion planning for multiple robots having independent goals. IEEE Trans. Robot. Autom. 14(6), 912–925 (1998)
Lozano-Pérez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22(10), 560–570 (1979)
O’Donnell, P.A., Lozano-Pérez, T.: Deadlock-free and collision-free coordination of two robot manipulators. In: ICRA (1989)
Peasgood, M., Clark, C., McPhee, J.: A complete and scalable strategy for coordinating multiple robots within roadmaps. IEEE Trans. Robot. 24(2), 283–292 (2008)
Peng, J., Akella, S.: Coordinating multiple robots with kinodynamic constraints along specified paths. In: Boissonat, J.-D., Burdick, J., Goldberg, K., Hutchinson, S. (eds.) Algorithmic Foundations of Robotics V, pp. 221–237. Springer, Berlin (2002)
Robert, W.: The Geometrical Foundation of Natural Structure. A Source Book of Design. Dover, New York (1978)
Ryan, M.R.K.: Exploiting subgraph structure in multi-robot path planning. J. Artif. Intell. Res. 31, 497–542 (2008)
Schwartz, J., Sharir, M.: On the piano movers’ problem: III. coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers. IJRR 2(3), 46–75 (1983)
Snape, J., Guy, S.J., van den Berg, J., Manocha, D.: Smooth coordination and navigation for multiple differential-drive robots. In: Khatib, O., Kumar, V., Sukhatme, G. (eds.) Experimental Robotics. Springer, Heidelberg (2014)
Snape, J.R.: Smooth and collision-free navigation for multiple mobile robots and video game characters. Ph.D. thesis, University of North Carolina at Chapel Hill (2012)
Solovey, K., Halperin, D.: \(k\)-color multi-robot motion planning. In: WAFR (2012)
Solovey, K., Salzman, O., Halperin, D.: Finding a needle in an exponential haystack: discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. In: WAFR (2014)
Solovey, K., Yu, J., Zamir, O., Halperin, D.: Motion planning for unlabeled discs with optimality guarantees. In: RSS (2015)
Standley, T., Korf, R.: Complete algorithms for cooperative pathfinding problems. In: IJCAI (2011)
Švestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23(3), 125–152 (1998)
Turpin, M., Michael, N., Kumar, V.: Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In: ICRA (2013)
van den Berg, J., Lin, M.C., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: ICRA (2008)
van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: IROS (2005)
van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: RSS (2009)
van den Berg, J., Snape, J., Guy, S.J., Manocha, D.: Reciprocal collision avoidance with acceleration-velocity obstacles. In: ICRA (2011)
van der Stappen, A.F., Karamouzas, I., Geraerts, R.: Space-time group motion planning. In: WAFR (2012)
Wagner, G., Choset, H.: M*: a complete multirobot path planning algorithm with performance bounds. In: IROS (2011)
Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Combinat. Theo. (B) 16, 86–96 (1974)
Wurman, P.R., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag. 29(1), 9–19 (2008)
Yu, J., LaValle, S.M.: Fast, near-optimal computation for multi-robot path planning on graphs. In: AAAI (2013). Late breaking papers
Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: ICRA (2013)
Yu, J., LaValle, S.M.: Structure and intractability of optimal multi-robot path planning on graphs. In: AAAI (2013)
Yu, J., Rus, D.: Pebble motion on graphs with rotations: efficient feasibility tests and planning. In: WAFR (2014)
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.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Yu, J., Rus, D. (2018). An Effective Algorithmic Framework for Near Optimal Multi-robot Path Planning. In: Bicchi, A., Burgard, W. (eds) Robotics Research. Springer Proceedings in Advanced Robotics, vol 2. Springer, Cham. https://doi.org/10.1007/978-3-319-51532-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-51532-8_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-51531-1
Online ISBN: 978-3-319-51532-8
eBook Packages: EngineeringEngineering (R0)