An Enhanced Multi-Target Collision-Free Path Planning Algorithm for UAV Networks

Unmanned Aerial Vehicles (UAVs) provide a wide range of opportunities for the service sector, such as last-mile deliveries, surveillance, and data gathering. Finding an optimal collision-free path is necessary to enable UAVs to complete their mission successfully. However, most of the existing path-planning solutions focus on a single UAV and a single target only while overlooking the case of a UAV swarm that collaborates to find collision-free service delivery paths spanning multiple targets or points of interest within a three-dimensional (3D) map. Therefore, to overcome this limitation we propose a novel Multi-UAV Direct Goal Bias Rapidly Exploring Random Trees Star (MDGB-RRT*) algorithm to provide robust path solutions where multiple UAVs traverse a shared 3D urban environment, with each having unique identified goal positions whilst traversing the map with collision-free guarantees. In contrast to RRT*, MDGB-RRT* directly connects the expanding tree to the target location within a predefined search radius, which reduces both the initial pre-validated path length and computation time. The simulation results obtained show that MDGB-RRT* achieves a notable performance advantage compared to existing algorithms for both single and dual-UAV urbanised 3D environment. In addition, MDGB-RRT* maintains its performance advantages with the introduction of two UAVs within the same environment.