UAV Trajectory Planning Strategy In Complex Environments With Multiple Task Nodes And Obstacles

This paper investigates the unmanned aerial vehicle (UAV) trajectory planning problem in environments with multiple task nodes and obstacles. To address this problem, we first propose a hybrid algorithm, namely GA-RRT*, which utilizes genetic algorithm (GA) to determine the visiting order of the task nodes, while considering rapidly-exploring random trees star (RRT*) to explore feasible paths and provide path length feedback to the GA fitness function. Additionally, considering that the GA-RRT* algorithm hardly obtains sufficiently short paths as the number of UAVs increases, we further propose a novel algorithm, namely colored planning algorithm (CPA), which transforms the complex multi-UAVs trajectory planning problem with multiple task nodes and obstacles into a specialized colored traveling salesman problem (CTSP). In particular, we develop a multi-factor fitness function and an improved single-chromosome encoding scheme for GA-RRT* to effectively solve this specialized CTSP, and further analyze the corresponding solution space. Simulation results show that the proposed trajectory planning strategy can successfully traverse all task nodes while avoiding obstacles, producing short flight paths and achieving high efficiency in terms of flight time under complex environments. Moreover, the proposed strategy exhibits broad applicability and outperforms the traditional GA and RRT* algorithms in terms of both path length and computational efficiency.