An Efficient NSGA-II-Based Algorithm for Multi-Robot Coverage Path Planning

Foster, AJI, Gianni, M ORCID: 0000-0001-5410-2377, Aly, A and Samani, H (2025) An Efficient NSGA-II-Based Algorithm for Multi-Robot Coverage Path Planning In: 2025 IEEE International Conference on Robotics and Automation (ICRA), 2025-5-19 - 2025-5-23, Atlanta, USA.

Text ICRA25_3055_MS_ACCEPTED.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (884kB) | Preview

Abstract

This work presents an algorithm based on the Nondominated Sorting Genetic Algorithm II (NSGA-II) to solve multi-objective offline Multi-Robot Coverage Path Planning (MCPP) problems. The proposed algorithm embeds a donation-mutation operator and a multiple-parent crossover that generates solutions which maintain the longest path while minimizing the average path length. The algorithm also uses a library of elitism-selected high-fitness robot paths, and tournament-selected high min-max fitness paths, to construct high multi-objective fitness offspring. We evaluate the performance of our proposed algorithm against the state-of-the-art NSGA-II extended with an improved Heuristic Genetic Algorithm Crossover, and we demonstrate that for different instances of the MCPP problem, the Pareto-fronts of our proposed algorithm are not dominated by any of the points of the fronts generated by the state-of-the-art NSGA-II. A comparison has also been performed in a virtual environment simulating five drones inspecting three wind turbines. Results show that our approach exhibits a higher convergence rate for higher values of the ratio between the number of points to visit and the number of drones.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	4605 Data Management and Data Science, 46 Information and Computing Sciences, 4602 Artificial Intelligence
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	10 Feb 2025 10:32
Last Modified:	23 May 2026 09:45
DOI:	10.1109/ICRA55743.2025.11128792
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3190085
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.