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

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.