Abstract
We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restrictions (for example, autonomous vehicles may not want to share their locations or intents with other vehicles or even to a central server). The key insight that allows us to solve this problem is to stochastically distribute the robots across different routes in the environment by assigning them paths in different topologically distinct classes, so as to lower congestion and the overall travel time for all robots in the environment. We outline the computation of topologically distinct paths in a spatio-temporal configuration space and propose methods for the stochastic assignment of paths to the robots. A fast replanning algorithm and a potential field based controller allow robots to avoid collision with nearby agents while following the assigned path. Our simulation and experiment results show a significant advantage over shortest path following under such a coordination-free setup.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
References
Wang, X., Sahin, A., Bhattacharya, S.: Coordination-free Multi-robot Path Planning for Congestion Reduction Using Topological Reasoning. arXiv (2022). https://doi.org/10.48550/ARXIV.2205.00955. https://arxiv.org/abs/2205.00955
Silver, D.: Cooperative pathfinding. In: Proceedings of the Aaai Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 1, pp. 117–122 (2005)
Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219, 40–66 (2015)
Han, S.D., Yu, J.: Ddm: Fast near-optimal multi-robot path planning using diversified-path and optimal sub-problem solution database heuristics. IEEE Robotics and Automation Letters 5(2), 1350–1357 (2020)
Wagner, G., Choset, H.: M*: A complete multirobot path planning algorithm with performance bounds. In: Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference On, pp. 3260–3267 (2011). IEEE
Mohanan, M.G., Salgoankar, A.: A survey of robotic motion planning in dynamic environments. Robotics and Autonomous Systems 100, 171–185 (2018). https://doi.org/10.1016/j.robot.2017.10.011
Kushleyev, A., Likhachev, M.: Time-bounded lattice for efficient planning in dynamic environments. In: 2009 IEEE International Conference on Robotics and Automation, pp. 1662–1668 (2009)
Cai, K., Wang, C., Cheng, J., De Silva, C.W., Meng, M.Q.-H.: Mobile robot path planning in dynamic environments: A survey. arXiv e-prints, 2006–14195 (2020) https://arxiv.org/abs/2006.14195arXiv:2006.14195 [cs.RO]
Hasan, A.H., Mosa, A.M.: Multi-robot path planning based on max-min ant colony optimization and d* algorithms in a dynamic environment. In: 2018 International Conference on Advanced Science and Engineering (ICOASE), pp. 110–115 (2018)
Ziebart, B.D., Ratliff, N., Gallagher, G., Mertz, C., Peterson, K., Bagnell, J.A., Hebert, M., Dey, A.K., Srinivasa, S.: Planning-based prediction for pedestrians. In: 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3931–3936 (2009). IEEE
Kretzschmar, H., Spies, M., Sprunk, C., Burgard, W.: Socially compliant mobile robot navigation via inverse reinforcement learning. The International Journal of Robotics Research 35(11), 1289–1307 (2016)
Kirby, R., Simmons, R., Forlizzi, J.: Companion: A constraint-optimizing method for person-acceptable navigation. In: RO-MAN 2009-The 18th IEEE International Symposium on Robot and Human Interactive Communication, pp. 607–612 (2009). IEEE
Sisbot, E.A., Marin-Urias, L.F., Alami, R., Simeon, T.: A human aware mobile robot motion planner. IEEE Transactions on Robotics 23(5), 874–883 (2007)
Ferrer, G., Garrell, A., Sanfeliu, A.: Social-aware robot navigation in urban environments. In: 2013 European Conference on Mobile Robots, pp. 331–336 (2013). IEEE
Shiomi, M., Zanlungo, F., Hayashi, K., Kanda, T.: Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model. International Journal of Social Robotics 6(3), 443–455 (2014)
Atzmon, D., Stern, R., Felner, A., Sturtevant, N.R., Koenig, S.: Probabilistic robust multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 30, pp. 29–37 (2020)
Santos, V.G., Chaimowicz, L.: Hierarchical congestion control for robotic swarms. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4372–4377 (2011). IEEE
Toutouh, J., Alba, E.: A swarm algorithm for collaborative traffic in vehicular networks. Vehicular Comms. 12, 127–137 (2018)
Antoniou, P., Pitsillides, A., Blackwell, T., Engelbrecht, A., Michael, L.: Congestion control in wireless sensor networks based on bird flocking behavior. Computer Networks 57(5), 1167–1191 (2013). https://doi.org/10.1016/j.comnet.2012.12.008
Tatomir, B., Rothkrantz, L.: Hierarchical routing in traffic using swarm-intelligence. In: 2006 IEEE Intelligent Transportation Systems Conference, pp. 230–235 (2006). https://doi.org/10.1109/ITSC.2006.1706747
Gunes, M., Sorges, U., Bouazizi, I.: Ara-the ant-colony based routing algorithm for manets. In: Proceedings. International Conference on Parallel Processing Workshop, pp. 79–85 (2002). IEEE
Di Caro, G., Ducatelle, F., Gambardella, L.M.: Anthocnet: an adaptive nature-inspired algorithm for routing in mobile ad hoc networks. European Transactions on Telecommunications 16(5), 443–455 (2005)
Street, C., Pütz, S., Mühlig, M., Hawes, N., Lacerda, B.: Congestion-aware policy synthesis for multirobot systems. IEEE Transactions on Robotics (2021)
Stump, E., Michael, N.: Multi-robot persistent surveillance planning as a vehicle routing problem. In: IEEE International Conference on Automation Science and Engineering, pp. 569–575 (2011)
Leahy, K., Zhou, D., Vasile, C.-I., Oikonomopoulos, K., Schwager, M., Belta, C.: Persistent surveillance for unmanned aerial vehicles subject to charging and temporal logic constraints. Auton. Robots 40(8), 1363–1378 (2016). https://doi.org/10.1007/s10514-015-9519-z
Kusnur, T., Mukherjee, S., Saxena, D.M., Fukami, T., Koyama, T., Salzman, O., Likhachev, M.: A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction. In: Proceedings of the 12th Conference on Field and Service Robotics (2019)
Thakur, D., Likhachev, M., Keller, J., Kumar, V., Dobrokhodov, V., Jones, K., Wurz, J., Kaminer, I.: Planning for Opportunistic Surveillance with Multiple Robots. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (2013)
Van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE International Conference on Robotics and Automation, pp. 1928–1935 (2008). IEEE
Mavrogiannis, C.I., Knepper, R.A.: Multi-agent path topology in support of socially competent navigation planning. The International Journal of Robotics Research 38(2–3), 338–356 (2019)
Mavrogiannis, C., Balasubramanian, K., Poddar, S., Gandra, A., Srinivasa, S.S.: Winding through: Crowd navigation via topological invariance. IEEE Robotics and Automation Letters 8(1), 121–128 (2022)
LaValle, S.M.: Robot motion planning: A game-theoretic foundation. Algorithmica 26(3), 430–465 (2000)
He, C., Wan, Y., Gu, Y., Lewis, F.L.: Integral reinforcement learning-based multi-robot minimum time-energy path planning subject to collision avoidance and unknown environmental disturbances. IEEE Control Systems Letters 5(3), 983–988 (2020)
Bhattacharya, S., Likhachev, M., Kumar, V.: Topological constraints in search-based robot path planning. Autonomous Robots, 1–18 (2012). DOI: https://doi.org/10.1007/s10514-012-9304-1
Bhattacharya, S., Ghrist, R.: Path homotopy invariants and their application to optimal trajectory planning. Annals of Mathematics and Artificial Intelligence 84(3–4), 139–160 (2018)
Wang, X., Bhattacharya, S.: A topological approach to workspace and motion planning for a cable-controlled robot in cluttered environments. IEEE Robotics and Automation Letters 3(3), 2600–2607 (2018). https://doi.org/10.1109/LRA.2018.2817684
Govindarajan, V., Bhattacharya, S., Kumar, V.: Human-robot collaborative topological exploration for search & rescue applications. In: Intl. Symp. on Distributed Autonomous Robotic Sysystems (2014)
Bhattacharya, S., Ghrist, R., Kumar, V.: Persistent homology for path planning in uncertain environments. IEEE Transactions on Robotics (T-RO) 31(3), 578–590 (2015)
Wu, W., Bhattacharya, S., Prorok, A.: Multi-robot path deconfliction through prioritization by path prospects. In: Proceedings of IEEE Intl. Conference on Robotics and Automation (ICRA) (2020)
Bhattacharya, S., Kim, S., Heidarsson, H., Sukhatme, G., Kumar, V.: A topological approach to using cables to separate and manipulate sets of objects. International Journal of Robotics Research 34(6), 799–815 (2015). https://doi.org/10.1177/0278364914562236
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G.A., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. Theory, Algorithms, and Implementations. MIT Press, Cambridge, MA, Principles of Robot Motion (2005)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK (2004)
Fox, D., Burgard, W., Thrun, S.: Active markov localization for mobile robots. Robotics and Autonomous Systems 25(3), 195–207 (1998). Autonomous Mobile Robots
Zhang, L., Prorok, A., Bhattacharya, S.: Pursuer assignment and control strategies in multi-agent pursuit-evasion under uncertainties. Frontiers in Robotics and AI 8, 262 (2021). https://doi.org/10.3389/frobt.2021.691637
d’Andrea-Novel, B., Bastin, G., Campion, G.: Dynamic feedback linearization of nonholonomic wheeled mobile robots. In: Proceedings 1992 IEEE International Conference on Robotics and Automation, pp. 2527–2528 (1992). IEEE Computer Society
Jia, Y., Yan, X., Xu, Y.: A survey of simultaneous localization and mapping for robot. In: 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), vol. 1, pp. 857–861 (2019). IEEE
Daniel, K., Nash, A., Koenig, S., Felner, A.: Theta*: Any-angle path planning on grids. Journal of Artificial Intelligence Research 39, 533–579 (2010)
Bhattacharya, S.: Towards optimal path computation in a simplicial complex. The International Journal of Robotics Research 38(8), 981–1009 (2019)
Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant No. CCF-2144246.
Funding
This work was partially supported by the National Science Foundation (Grant No. CCF-2144246).
Author information
Authors and Affiliations
Contributions
Xiaolong Wang was responsible for implementation of the proposed algorithms for topological planning, stochastic path choice and fast replanning, and helped run the simulations and experiments. Alp Sahin was responsible for implementation of the proposed controllers for fast replanning and local collision avoidance, and helped run the simulations and experiments. Subhrajit Bhattacharya was responsible for inception of the main ideas behind the research effort, development of the proposed algorithms, development of the mathematical formulations/models, overseeing the implementation of the algorithms, and coordination of the research activities. All authors contributed equally in writing the paper.
Corresponding author
Ethics declarations
Conflicts of interest
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supplementary Information
Below is the link to the electronic supplementary material.
Supplementary file 1 (mp4 16957 KB)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Wang, X., Sahin, A. & Bhattacharya, S. Coordination-free Multi-robot Path Planning for Congestion Reduction Using Topological Reasoning. J Intell Robot Syst 108, 50 (2023). https://doi.org/10.1007/s10846-023-01878-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-023-01878-3