Abstract
Multi-Agent Path Planning is important in many applications involving multiple mobile robots. In this paper, we present a novel algorithm to solve the Multi-Agent Pathfinding problem by using Collective Decision-making and indirect communication (stigmergy). We call this planning method Collective Conflict Resolution (CCR). The algorithm has two components: A mechanism to create a prioritization graph through collective decisions and a planning mechanism that is able to plan paths consistent with the priorities given by the graph. The CCR algorithm can be used both in global planning with full knowledge of all paths, and in decentralized settings with limited knowledge and communication. In our experiments, we compare our new planner with two state-of-the-art algorithms: Conflict-based Search (CBS) and Prioritized Planning. Furthermore, we analyze how a limited planning horizon can affect the planning cost. The results show that the proposed method offers a good trade-off between planning cost and solution quality, which results in a better success rate compared to Prioritized Planning, which sometimes does not find a solution. In addition, the algorithm is able to achieve a good solution quality with lower cost compared to the more complex CBS algorithm.
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.
The code is available at https://www.ci.ovgu.de/Research/Codes.html. The benchmark files are available at https://mapf.info.
- 2.
We do not report the number of calls to the A* algorithm for Prioritized planning because we use a caching mechanism for the true-cost heuristic. In our implementation, this value can not be compared fairly between Prioritized Planning and CBS/CCR.
References
Atzmon, D., Felner, A., Wagner, G., Stern, R., Bart, R.: k-robust multi-agent path finding. In: SoCS, vol. 1, pp. 157–158 (2017)
van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent collision avoidance. In: Proceedings of IEEE International Conference on Robotics and Automation, pp. 1928–1935 (2007)
Cohen, L., Koenig, S.: Bounded suboptimal multi-agent path finding using highways. In: IJCAI International Joint Conference on Artificial Intelligence, January 2016, pp. 3978–3979 (2016)
Cohen, L., Uras, T., Koenig, S.: Feasibility study: using highways for bounded-suboptimal multi-agent path finding. In: Proceedings of the 8th Annual Symposium on Combinatorial Search, SoCS 2015, January 2015, pp. 2–8 (2015)
Dorigo, M., Stützle, T.: Ant colony optimization: overview and recent advances. Technical report, TR/IRIDIA/2009-013, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, May 2009
Font Llenas, A., Talamali, M.S., Xu, X., Marshall, J.A.R., Reina, A.: Quality-sensitive foraging by a robot swarm through virtual pheromone trails. In: Dorigo, M., Birattari, M., Blum, C., Christensen, A.L., Reina, A., Trianni, V. (eds.) ANTS 2018. LNCS, vol. 11172, pp. 135–149. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00533-7_11
Gazi, V., Passino, K.M.: Swarm Stability and Optimization. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18041-5
Hamann, H.: Swarm robotics: a formal approach (2018). https://doi.org/10.1007/978-3-319-74528-2
Honig, W., Kiesel, S., Tinka, A., Durham, J.W., Ayanian, N.: Persistent and robust execution of MAPF schedules in warehouses. IEEE Robot. Autom. Lett. 4(2), 1125–1131 (2019). https://doi.org/10.1109/LRA.2019.2894217
Honig, W., Preiss, J.A., Kumar, T.K., Sukhatme, G.S., Ayanian, N.: Trajectory planning for quadrotor swarms. IEEE Trans. Rob. 34(4), 856–869 (2018). https://doi.org/10.1109/TRO.2018.2853613
Jansen, M.R., Sturtevant, N.R.: Direction maps for cooperative pathfinding. In: Proceedings of the 4th Artificial Intelligence and Interactive Digital Entertainment Conference, AIIDE 2008, pp. 185–190 (2008)
Li, Q., Gama, F., Ribeiro, A., Prorok, A.: Graph neural networks for decentralized multi-robot path planning (2019). http://arxiv.org/abs/1912.06095
Mai, S., Deubel, M., Mostaghim, S.: Multi-objective roadmap optimization for multiagent navigation (2022)
Mai, S., Mostaghim, S.: Modeling pathfinding for swarm robotics. In: Dorigo, M., et al. (eds.) ANTS 2020. LNCS, vol. 12421, pp. 190–202. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60376-2_15
Mai, S., Traichel, N., Mostaghim, S.: Driving swarm: a swarm robotics framework for intelligent navigation in a self-organized world. Accepted at ICRA 2022 (2022)
Raymond, A., Malencia, M., Paulino-Passos, G., Prorok, A.: Agree to disagree: subjective fairness in privacy-restricted decentralised conflict resolution. Front. Robot. AI 9, February 2022. https://doi.org/10.3389/frobt.2022.733876
Reynolds, C.W.: Steering behaviors for autonomous characters. In: Game Developers Conference (1999). http://www.red3d.com/cwr/steer/gdc99/
Sharon, G., Stern, R., Felner, A., Sturtevant, N.: Meta-agent conflict-based search for optimal multi-agent path finding. In: Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012, pp. 97–104 (2012)
Silver, D.: Cooperative pathfinding. In: Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, pp. 117–122 (2005). http://www.aaai.org/Library/AIIDE/aiide05contents.php
Stern, R., et al.: Multi-agent pathfinding: definitions, variants, and benchmarks. In: AAAI Conference on Artificial Intelligence (AAAI) (2019)
Surynek, P., Felner, A., Stern, R., Boyarski, E.: An empirical comparison of the hardness of multi-agent path finding under the makespan and the sum of costs objectives. In: Proceedings of the 9th Annual Symposium on Combinatorial Search, SoCS 2016 (SoCS), January 2016, pp. 145–146 (2016)
Van Den Berg, J.P., Overmars, M.H.: Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, pp. 430–435 (2005). https://doi.org/10.1109/IROS.2005.1545306
Weise, J., Mai, S., Zille, H., Mostaghim, S.: On the scalable multi-objective multi-agent pathfinding problem. In: Accepted at Congress on Evolutionary Computing CEC 2020 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Mai, S., Mostaghim, S. (2022). Collective Decision-Making for Conflict Resolution in Multi-Agent Pathfinding. In: Dorigo, M., et al. Swarm Intelligence. ANTS 2022. Lecture Notes in Computer Science, vol 13491. Springer, Cham. https://doi.org/10.1007/978-3-031-20176-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-20176-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20175-2
Online ISBN: 978-3-031-20176-9
eBook Packages: Computer ScienceComputer Science (R0)