Cooperative multi-agent systems make it possible to employ miniature robots in order to perform different experiments for data collection in wide open areas to physical interactions with test subjects in confined environments such as a hive. This paper proposes a new multi-agent path-planning approach to determine a set of trajectories where the agents do not collide with each other or any obstacle. The proposed algorithm leverages a risk-aware probabilistic roadmap algorithm to generate a map, employs node classification to delineate exploration regions, and incorporates a customized genetic framework to address the combinatorial optimization, with the ultimate goal of computing safe trajectories for the team. Furthermore, the proposed planning algorithm makes the agents explore all subdomains in the workspace together as a formation to allow the team to perform different tasks or collect multiple datasets for reliable localization or hazard detection. The objective function for minimization includes two major parts, the traveling distance of all the agents in the entire mission and the probability of collisions between the agents or agents with obstacles. A sampling method is used to determine the objective function considering the agents' dynamic behavior influenced by environmental disturbances and uncertainties. The algorithm's performance is evaluated for different group sizes by using a simulation environment, and two different benchmark scenarios are introduced to compare the exploration behavior. The proposed optimization method establishes stable and convergent properties regardless of the group size.

Artificial Intelligence Center Faculty of Electrical Engineering Czech Technical University Prague Prague Czechia

Swarm and Computational Intelligence Laboratory Department of Computer Science Durham University Durham United Kingdom

Zobrazit více v PubMed

Agha-mohammadi A., Chakravorty S., Amato N. M. (2014). Firm: sampling-based feedback motion-planning under motion uncertainty and imperfect measurements. Int. J. Robotics Res. 33, 268–304. 10.1177/0278364913501564 DOI

Ahn C. W., Ramakrishna R. (2002). A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Trans. Evol. Comput. 6, 566–579. 10.1109/tevc.2002.804323 DOI

Amigoni F., Banfi J., Basilico N. (2017). Multirobot exploration of communication-restricted environments: a survey. IEEE Intell. Syst. 32, 48–57. 10.1109/mis.2017.4531226 DOI

Bahaidarah M., Rekabi-Bana F., Marjanovic O., Arvin F. (2024). Swarm flocking using optimisation for a self-organised collective motion. Swarm Evol. Comput. 86, 101491. 10.1016/j.swevo.2024.101491 DOI

Barbosa F. S., Lacerda B., Duckworth P., Tumova J., Hawes N. (2021). “Risk-aware motion planning in partially known environments,” in 2021 60th IEEE Conference on Decision and Control (IEEE; ), 5220–5226.

Barmak R., Stefanec M., Hofstadler D. N., Piotet L., Schönwetter-Fuchs-Schistek S., Mondada F., et al. (2023). A robotic honeycomb for interaction with a honeybee colony. Sci. Robotics 8, eadd7385. 10.1126/scirobotics.add7385 PubMed DOI

Bengio Y., Lodi A., Prouvost A. (2021). Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur. J. Operational Res. 290, 405–421. 10.1016/j.ejor.2020.07.063 DOI

Biswas S., Anavatti S. G., Garratt M. A. (2017). “Obstacle avoidance for multi-agent path planning based on vectorized particle swarm optimization,” in Intelligent and evolutionary systems. Editors Leu G., Singh H. K., Elsayed S. (Cham: Springer International Publishing; ), 61–74.

Blum C., Puchinger J., Raidl G. R., Roli A. (2011). Hybrid metaheuristics in combinatorial optimization: a survey. Appl. Soft Comput. 11, 4135–4151. 10.1016/j.asoc.2011.02.032 DOI

Cai K., Wang C., Song S., Chen H., Meng M. Q.-H. (2021). Risk-aware path planning under uncertainty in dynamic environments. J. Intelligent Robotic Syst. 101, 47–15. 10.1007/s10846-021-01323-3 DOI

Dalmasso M., Garrell A., Domínguez J. E., Jiménez P., Sanfeliu A. (2021). “Human-robot collaborative multi-agent path planning using Monte Carlo tree search and social reward sources,” in 2021 IEEE international conference on robotics and automation (ICRA), 10133–10138.

Das P., Behera H., Panigrahi B. (2016). Intelligent-based multi-robot path planning inspired by improved classical q-learning and improved particle swarm optimization with perturbed velocity. Eng. Sci. Technol. Int. J. 19, 651–669. 10.1016/j.jestch.2015.09.009 DOI

Di Mario E., Talebpour Z., Martinoli A. (2013). “A comparison of pso and reinforcement learning for multi-robot obstacle avoidance,” in 2013 IEEE congress on evolutionary computation, 149–156.

Dorri A., Kanhere S. S., Jurdak R. (2018). Multi-agent systems: a survey. IEEE Access 6, 28573–28593. 10.1109/access.2018.2831228 DOI

Galceran E., Carreras M. (2013). A survey on coverage path planning for robotics. Robotics Aut. Syst. 61, 1258–1276. 10.1016/j.robot.2013.09.004 DOI

Juan A. A., Faulin J., Grasman S. E., Rabe M., Figueira G. (2015). A review of simheuristics: extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Res. Perspect. 2, 62–72. 10.1016/j.orp.2015.03.001 DOI

Kala R. (2012). Multi-robot path planning using co-evolutionary genetic programming. Expert Syst. Appl. 39, 3817–3831. 10.1016/j.eswa.2011.09.090 DOI

Kavraki L., Svestka P., Latombe J.-C., Overmars M. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robotics Automation 12, 566–580. 10.1109/70.508439 DOI

Li M., Richards A., Sooriyabandara M. (2021). “Reliability-aware multi-uav coverage path planning using a genetic algorithm,” in Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, 1584–1586.

Liu Z., Chen B., Zhou H., Koushik G., Hebert M., Zhao D. (2020). “Mapper: multi-agent path planning with evolutionary reinforcement learning in mixed dynamic environments,” in IEEE/RSJ International Conference on Intelligent Robots and Systems IROS, 11748–11754.

Nawaz F., Ornik M. (2023). Multi-agent, multi-target path planning in markov decision processes. IEEE Trans. Automatic Control 68, 7560–7574. 10.1109/tac.2023.3286807 DOI

Nazarahari M., Khanmirza E., Doostie S. (2019). Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Syst. Appl. 115, 106–120. 10.1016/j.eswa.2018.08.008 DOI

Okubo T., Takahashi M. (2023). Multi-agent action graph based task allocation and path planning considering changes in environment. IEEE Access 11, 21160–21175. 10.1109/access.2023.3249757 DOI

Pereira A. A., Binney J., Hollinger G. A., Sukhatme G. S. (2013). Risk-aware path planning for autonomous underwater vehicles using predictive ocean models. J. Field Robotics 30, 741–762. 10.1002/rob.21472 DOI

Qie H., Shi D., Shen T., Xu X., Li Y., Wang L. (2019). Joint optimization of multi-uav target assignment and path planning based on multi-agent reinforcement learning. IEEE Access 7, 146264–146272. 10.1109/access.2019.2943253 DOI

Rafai A. N. A., Adzhar N., Jaini N. I. (2022). A review on path planning and obstacle avoidance algorithms for autonomous mobile robots. J. Robotics 2022, 1–14. 10.1155/2022/2538220 DOI

Ravankar A. A., Ravankar A., Emaru T., Kobayashi Y. (2020). Hpprm: hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots. IEEE Access 8, 221743–221766. 10.1109/access.2020.3043333 DOI

Rekabi-Bana F., Hu J., Krajník T., Arvin F. (2024). Unified robust path planning and optimal trajectory generation for efficient 3d area coverage of quadrotor uavs. IEEE Trans. Intelligent Transp. Syst. 25, 2492–2507. 10.1109/tits.2023.3320049 DOI

Rekabi-Bana F., Shirazi F. A., Sadigh M. J. (2020). Distributed nonlinear h control algorithm for multi-agent quadrotor formation flying. ISA Trans. 96, 81–94. 10.1016/j.isatra.2019.04.036 PubMed DOI

Rekabi-Bana F., Shirazi F. A., Sadigh M. J., Saadat M. (2021). Distributed output feedback nonlinear formation control algorithm for heterogeneous aerial robotic teams. Robotics Aut. Syst. 136, 103689. 10.1016/j.robot.2020.103689 DOI

Rekabi-Bana F., Stefanec M., Ulrich J., Keyvan E. E., Rouček T., Broughton G., et al. (2023). “Mechatronic design for multi robots-insect swarms interactions,” in 2023 IEEE International Conference on Mechatronics (ICM), 1–6.

Rizk Y., Awad M., Tunstel E. W. (2019). Cooperative heterogeneous multi-robot systems: a survey. ACM Comput. Surv. 52, 1–31. 10.1145/3303848 DOI

Romano D., Donati E., Benelli G., Stefanini C. (2019). A review on animal–robot interaction: from bio-hybrid organisms to mixed societies. Biol. Cybern. 113, 201–225. 10.1007/s00422-018-0787-5 PubMed DOI

Rouček T., Pecka M., Čížek P., Petříček T., Bayer J., Šalanský V., et al. (2020). “Darpa subterranean challenge: multi-robotic exploration of underground environments,” in Modelling and simulation for autonomous systems. Editors Mazal J., Fagiolini A., Vasik P. (Springer International Publishing; ), 274–290.

Safe M., Carballido J., Ponzoni I., Brignole N. (2004). “On stopping criteria for genetic algorithms,” in Advances in artificial intelligence – sbia 2004. Editors Bazzan A. L. C., Labidi S. (Springer Berlin Heidelberg; ), 405–413.

Semnani S. H., Liu H., Everett M., de Ruiter A., How J. P. (2020). Multi-agent motion planning for dense and dynamic environments via deep reinforcement learning. IEEE Robotics Automation Lett. 5, 3221–3226. 10.1109/lra.2020.2974695 DOI

Stefanec M., Hofstadler D. N., Krajník T., Turgut A. E., Alemdar H., Lennox B., et al. (2022). A minimally invasive approach towards “ecosystem hacking” with honeybees. Front. Robotics AI 9, 791921. 10.3389/frobt.2022.791921 PubMed DOI PMC

Stern R., Sturtevant N., Felner A., Koenig S., Ma H., Walker T., et al. (2019). Multi-agent pathfinding: definitions, variants, and benchmarks. Proc. Int. Symposium Comb. Search 10, 151–158. 10.1609/socs.v10i1.18510 DOI

Štibinger P., Báča T., Saska M. (2020). Localization of ionizing radiation sources by cooperating micro aerial vehicles with pixel detectors in real-time. IEEE Robotics Automation Lett. 5, 3634–3641. 10.1109/lra.2020.2978456 DOI

Sun R., Tang C., Zheng J., Zhou Y., Yu S. (2019). “Multi-robot path planning for complete coverage with genetic algorithms,” in Intelligent Robotics and Applications: 12th International Conference, ICIRA 2019, Shenyang, China, August 8–11, 2019 (Springer; ), 349–361283.

Tranzatto M., Miki T., Dharmadhikari M., Bernreiter L., Kulkarni M., Mascarich F., et al. (2022). Cerberus in the darpa subterranean challenge. Sci. Robotics 7, eabp9742. 10.1126/scirobotics.abp9742 PubMed DOI

Vinyals O., Babuschkin I., Czarnecki W. M., Mathieu M., Dudzik A., Chung J., et al. (2019). Grandmaster level in starcraft ii using multi-agent reinforcement learning. nature 575, 350–354. 10.1038/s41586-019-1724-z PubMed DOI

Xiang X., Jouvencel B., Parodi O. (2010). Coordinated formation control of multiple autonomous underwater vehicles for pipeline inspection. Int. J. Adv. Robotic Syst. 7, 3. 10.5772/7242 DOI

Yu J., LaValle S. M. (2013). “Multi-agent path planning and network flow,” in Algorithmic foundations of robotics X. Editors Frazzoli E., Lozano-Perez T., Roy N., Rus D. (Springer Berlin Heidelberg; ), 157–173.

Žampachů K., Ulrich J., Rouček T., Stefanec M., Dvořáček D., Fedotoff L., et al. (2022). “A vision-based system for social insect tracking,” in 2022 2nd International Conference on Robotics, Automation and Artificial Intelligence (RAAI) (IEEE; ), 277–283.

Zlot R., Stentz A., Dias M., Thayer S. (2002). “Multi-robot exploration controlled by a market economy,” in Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), 3016–3023.3