张 康，陈建平

（南京航空航天大学航空学院，南京 210016）

0 引言

航迹规划是指在任务空间中找到无人机（Unmanned Aerial Vehicle，UAV）从初始状态到指定目标状态的可行航迹，其应用背景十分广泛，如无人驾驶汽车、计算机辅助外科手术、移动机器人等［1-3］。

现有的航迹规划算法主要分为确定性方法和随机性方法。确定性方法有人工势场法［4］、A*算法［5］、智能算法等。人工势场法需要根据环境信息预先构建势场，容易陷入局部最优，且在狭窄通道里会出现摆动现象，不适合复杂环境的应用；A*算法在高维空间中会出现组合爆炸的问题；以粒子群［6］为代表的智能算法通常会用来求解满足性能指标的最优航迹问题，但一般需要大量迭代才能收敛，计算开销大，运算时间长。

概率路线图（Probabilistic Road Map，PRM）法［7］和快速扩展随机树（Rapidly-exploring Random Tree，RRT）法［8］是当前使用最广泛的随机采样方法，相较于确定性方法的优势在于使用碰撞检测技术避免了对障碍物的显示建模，直接在当前任务空间中生成可行航迹，具有实时处理复杂环境下航迹规划问题的能力。PRM 算法的性能对障碍物形状严重依赖，难以在不确定环境中发挥作用。相比之下，RRT 算法对环境波动不敏感，且支持非完整约束。这些优点使得RRT 在近年来得到了广泛的应用和发展。最具代表性的是文献［9］中提出的具有渐进最优性的快速扩展随机树（Rapidly-exploring Random Tree star，RRT*）算法，它针对RRT算法非最优性的缺点，在每次迭代中通过对新扩展节点的近邻优化来保证算法的渐进最优性。但该算法仍然存在一些不足：1）寻路没有方向性，规划过程中会出现很多重复探索；……