"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."

本文针对多任务节点与障碍物环境下的无人机（unmanned aerial vehicle, UAV）轨迹规划问题展开研究。为解决该问题，本文首先提出一种混合算法GA-RRT*：该算法利用遗传算法（genetic algorithm, GA）确定任务节点的访问顺序，同时结合快速探索随机树*（rapidly-exploring random trees star, RRT*）探索可行路径，并将路径长度反馈至GA适应度函数。此外，考虑到随着无人机数量增多，GA-RRT*算法难以获得足够短的路径，本文进一步提出一种新型着色规划算法（colored planning algorithm, CPA），将带有多任务节点与障碍物的复杂多无人机轨迹规划问题转化为一类特殊的着色旅行商问题（colored traveling salesman problem, CTSP）。具体而言，本文为GA-RRT*算法设计了多因素适应度函数与改进的单染色体编码方案，以有效求解该类特殊着色旅行商问题，并进一步分析了对应的解空间。仿真结果表明，所提轨迹规划策略可在规避障碍物的前提下顺利遍历所有任务节点，生成较短的飞行路径，且在复杂环境下实现飞行时间效率的提升。此外，所提策略具备广泛的适用性，且在路径长度与计算效率两方面均优于传统遗传算法与RRT*算法。