Collaborative Path Planning for Multi-UAVs by Evolutionary Computing

This paper addresses the challenges of path planning and cooperative control for multiple Unmanned Aerial Vehicles (UAVs) operating in large scale environments. Given the unique characteristics of large-scale environments, such as minimal terrain restrictions, vast monitoring scope, and a potentially high number of monitoring points, it becomes inherently difficult to effectively manage and optimize UAV operations over the large coverage are and the potential for a high number of target points. In response to this challenge, we propose an innovative UAV path planning strategy that capitalizes on the strengths of both evolutionary computing and clustering algorithms. As a first step, we propose an advanced version of the k-means algorithm to cluster multiple target points along the drone patrol route. This approach not only facilitates division of the extensive target area into manageable sections, but also aims to equalize the patrol distances for each UAV. This effort optimizes load balancing and boosts overall operational efficiency. Next, we implement a customized genetic algorithm to formulate an optimized path planning scheme for the UAVs, with a specific focus on the clustered sub-target points as derived from the k-means algorithm. The primary objective of our proposed scheme is to further minimize the differences in cruise path lengths among individual UAVs, thereby achieving load balancing and enhancing overall system efficiency. Simulation results demonstrate that our proposed k-means algorithm significantly improves load balancing during UAV trajectory planning.