无人机航迹规划技术研究综述

樊 娇， 雷 涛， 韩 伟， 王 锐

(1.陕西科技大学 电子信息与人工智能学院，陕西 西安 710021； 2.青岛恒星科技学院 信息学院，山东 青岛 266100； 3.国防科技大学 系统工程学院，湖南 长沙 410073)

0 引言

随着航空技术的日益成熟，无人机在各个领域展现出了良好的应用前景。无人机不仅成本低，而且能够持续高强度作战，同时可以避免人员伤亡。无人机航迹规划是无人机任务分配中的一个重要问题，作为无人机执行任务的基础，近些年来，引发了大量的研究。简而言之，无人机航迹规划就是在满足无人机自身性能和各种威胁等约束条件下，规划出从起始点到目标点的一条或多条实际可飞的航线。一般规划的航迹要尽可能最优，尽量避开威胁，同时航迹代价要最小。

本文首先对无人机航迹规划的研究现状进行综述，然后对航迹规划过程中的影响因素等问题进行分析，其次对关键技术等方面进行综述，最后分析存在的问题并对发展趋势进行展望。

1 研究现状

目前，国内外学者对无人机航迹规划问题已经开展了大量研究工作。20世纪90年代初，国外很多学者将研究重点放在单架无人机静态航迹规划和平面二维环境建模的研究上。由于无人机在飞行过程中环境复杂、突发威胁较多，产生了许多动态实时航迹规划和三维环境建模的研究成果，同时，考虑到单架无人机完成任务能力有限，为了提高效率，又对多无人机协同任务及航迹规划进行研究。Ramchurn等[1]在动态环境下，对多无人机任务分配中的人机协作进行研究，采用多无人机监督和多主体协调算法在动态环境中对人为决策进行支持，避免了动态环境中执行许多搜索任务时可能导致无人机掉线的问题。Ruz等[2]在规划中采用混合整数线性规划对威胁和障碍进行检测。威胁区域是雷达检测区域，用该方法使非线性雷达检测风险函数逼近线性。Shiri等[3]利用均场博弈理论控制方法研究了用于关键任务应用的大规模无人机自主控制。在初始源对无人机进行一次状态交换，并采用机器学习模型解决多无人机状态下计算量太大的问题，这种方法有效避免了碰撞。Hota等[4]研究了固定翼微型飞行器在三维空间中如何规划航迹的问题，将轨迹用最小转弯半径的圆和直线相连，并用平滑的方式在2个连续的航路点之间进行过渡。

国内早些年由于经济、政治等因素影响，对无人机的研究起步较晚，一直处于跟踪国外技术的阶段，但如今中国在无人机技术研究上已经取得了蓬勃的发展。张佳龙等[5]提出了复合矢量人工势场方法，利用引力追踪目标，利用斥力避开障碍，有效实现了多无人机编队在三维空间的避障。Luo等[6]采用K-means算法和模拟退火算法对复杂约束下的多任务多无人机进行航迹规划，增加了巡航有效区域中子目标区域的覆盖范围。Zhang等[7]在航迹规划过程中，采用层次定向动态规划解决了动态规划在特殊地形环境的适用性和算法复杂性问题，提高了计算效率。杨健等[8]在使用应用分层优化法解决多协作式无人机任务规划问题时，首先将Dubins和B样条曲线融合并规划出所有可选航线，然后估计每段航线的时间消耗，最后又把组合算法规划的初始航线作为下一层使用最优控制方法规划精细航迹的初始解，解决了B样条算法在进行优化时不能考虑无人机始末状态约束的问题。

从总体来看，对航迹规划的研究主要分为3个方面：一是在考虑各种威胁的环境中初步规划无人机的飞行航迹；二是通过优化搜索算法进一步寻优，找到最佳航线；三是进行航迹平滑处理。在航迹规划算法方面，主要是对各类智能算法(如A*算法、遗传算法、蚁群算法、粒子群算法等)的改进应用，并且在具体运用中根据不同的特征对各类算法进行混合。

2 约束条件分析

无人机在飞行空域中以及进行航迹规划时有很多影响因素，不仅需要无人机满足自身性能约束，还需要满足任务、环境等约束。自身性能约束包括最小航迹段长度、最小转弯半径、最大俯仰角、最低和最高飞行高度、最大航迹长度等；任务约束有任务完成时间、起始点、目标点、固定航向角等；环境约束有各种威胁场约束、禁飞区约束等[9]，同时要求无人机满足突防要求，战场环境中还需要注意无人机的隐蔽性。下面介绍几种主要的约束条件。

2.1 空气动力学约束

航迹规划中对空气动力学的研究比较少，但无人机飞行时处于大气中，大气对其有一定影响，所以不得不考虑空气动力学约束。空气对无人机的作用主要表现在空气动力和空气动力矩上，前者的升力和重力的相互作用可以使无人机飞行，阻力影响到无人机应装燃料的多少，而后者可以使无人机保持稳定。

2.2 无人机自身性能约束

(1)最小航迹段长度。无人机在改变飞行姿态前必须保持的最短直飞距离，也即最小步长。这一约束不仅与无人机的机动性能有关，还与无人机的导航要求有关。一般情况下，希望无人机避免迂回行进或频繁转弯，因此要求每段飞行航迹不小于最小航迹段长度。

(2)最小转弯半径。无人机改变航向时需要相应的时间和转弯半径，航迹每一转弯点的曲率半径小于无人机最小转弯半径时航迹不可飞，因此航迹规划过程中需要考虑最小转弯半径，并要求转弯处航迹点的曲率半径大于等于最小转弯半径。

(3)最大俯仰角。三维空间航迹规划中影响无人机俯仰角的因素有无人机自身机动性能、飞行高度和气候状况等，该约束限制了无人机只能在特定角度内进行俯仰动作，要求无人机在某一航迹点的俯仰角不大于最大俯仰角。

(4)最低和最高飞行高度。无人机作战时需要在尽可能低的高度上飞行，依赖地形保护无人机，使敌方探测器难以发现或避免被地面防御系统摧毁，但又要保证不与地形障碍物相撞，因此需要在两者间进行折中。航迹搜索过程中每一个可达航迹点的最低高度要求不小于某一给定的安全高度，同时由于一些受地面站控制的无人机需要与地面站联系，所以飞行高度也要求不大于最高飞行高度。

(5)最大航迹长度。整个飞行过程中，无人机的总航程受到油耗和时间配给的影响，因此飞行航迹的总长度必须小于等于预先设置的最大距离。

2.3 环境约束

(1)威胁场约束。无人机在飞行过程中需要考虑各种威胁(恶劣天气、敌方武器阵地、鸟类等空中飞行物、地形障碍等)的位置、威胁半径以及威胁程度等，并且必须及时地获取威胁信息，保障无人机的安全。一些学者将恶劣天气的威胁简化为圆柱形，将山峰、坡地、雷达等威胁简化为圆锥形等模型，很大程度上简化了计算过程。

(2)禁飞区约束。无人机需要避免飞入国家法律明文规定的一些区域，比如军事重地、机场和一些敏感地区，还要避开高压线、高楼以及人群密集的地方等。

3 航迹规划技术

无人机航迹规划的关键技术主要包括地形获取、威胁及代价建模、航迹规划算法、航迹平滑处理等。下面针对每项关键技术，介绍近些年的研究现状。

笔者搭建了8阵元天线阵列，对基于LMS算法和RLS算法进行智能天线波束形成仿真研究，并利用MATLAB仿真软件对数据进行处理，对比分析两种算法所得的误差收敛曲线，得出如下结论：①对比图2和图3可以看出LMS算法的收敛误差对比于RLS算法的收敛误差来说误差较大，RLS算法相对来说更精确。②RLS算法在算法的后期收敛阶段，其性能和LMS算法相差不明显，但在算法的前期收敛阶段，RLS算法的收敛速度要明显高于LMS算法的收敛速度。但RLS算法复杂度高，计算量比较大。

3.1 地形获取

航迹规划中最先需要考虑的就是地形获取问题，它对航迹质量有很大影响。地形获取一般通过卫星获得，目前常用的方法主要是构造数字地图数据库。2004年赵杰[10]在对数据地形的模拟中提出基于规则格网的数字高程模型的地形特征提取算法，对洼地、平坦地区等进行处理，有效地将主要的地形特征正确地提取出来。2006年巴海涛[11]采用数字地图信息融合原理建立等效数字地形图，把飞行区域内的已知地形、地物及威胁信息融合成一种综合的地形信息，生成等效数字地图；再经过对飞行数据的预处理，在一个类似于综合考虑了地形、威胁以及飞行器性能的等效地形曲面上进行搜索，对无人机的飞行航迹进行规划，达到了很好的规划效果。2015年唐晓东[12]采用栅格方法建立原始数字地图，并用双线性的插值方法对原始数字高程数据进行插值处理，把各类威胁等效为山峰模型，然后将原始数字高程数据与威胁处理后的数据进行融合，这种方法能更有效地得到航迹规划高程图。

Bagherian等[13]在使用进化算法的三维无人机轨迹规划中，采用数字地形模型DTM和地理信息系统GIS生成敌方位置信息，并在三维环境中显示。这种方法可以通过推导无人机的运动方程对问题进行建模。Liang等[14]为解决恶劣环境中的避障和安全飞行问题，采用了基于数字高程图(DEM)的导航模型，设计改进的A*算法获取初始路径，并结合了Bresenham画线算法画出初始路径，最后使用Bezier曲线将路径变平滑。这种与DEM结合的路径规划算法，随着DEM分辨率的提高，规划精度也更高。

3.2 威胁及代价建模

无人机威胁建模主要包括恶劣气候、地形障碍以及敌方武器等。为了得到期望航线并保证无人机安全，很多学者都对各种威胁及代价进行了建模，通过机载传感器获取各类威胁信息，以采取有效措施进行规避。Anderson等[15]根据性能数据对飞机威胁进行建模，采用参数识别或多维曲线拟合来简化模型的参数，直到建模威胁的性能与实际威胁的性能匹配，很大程度上减少了开发新的威胁模型所需的时间。Roberge等[16]通过将多个圆柱体并置来创建复杂区域，把危险区域输入为一系列圆柱形状，并仍用二维矩阵表示。李春华等[17]针对动态环境中预先未知威胁的情况，采用实时三维航迹规划方法稀疏D*搜索SDS算法，当检测到威胁时立即进行局部路径重新规划，有效地回避了各种突发威胁。张煜等[18]采用概率表示的方法对各种威胁进行建模，生成概率威胁地图，很容易地得出无人机沿某航段飞行所受的威胁概率。温乃峰[19]针对在线搜索提出直觉模糊集静态威胁区建模和动态威胁可达集估计的方法，可靠地评估了无人机所受的威胁，提高了航迹搜索速度并降低了航迹代价。

3.3 航迹规划算法

航迹规划算法是航迹规划的核心，传统的航迹规划算法包括单纯形法、匈牙利算法、人工势场法、A*算法等，然而鉴于航迹规划问题通常呈现出高维、非线性、离散连续变量混合、多目标等特性，传统算法很难有效应对。近些年，国内外学者结合计算智能方法，如遗传算法、蚁群算法和粒子群算法，提出了很多先进有效的航迹规划算法。本节重点介绍几类典型的航迹规划算法。

3.3.1 A*算法

A*算法是一种基于栅格的智能启发式搜索算法，它将搜索空间表示为网格的形式，以网格的中心点或顶点作为航迹点，通过搜索邻域内代价函数值最小的航迹点，从起始点逐步搜索到目标点，最后逆向回溯当前节点的父节点生成最优航迹，其中已被计算但待扩展的航迹节点存放在OPEN表中，已扩展的节点存放在CLOSE表中[20]。代价函数的表达式为

f(x)=g(x)+h(x)。

(1)

2000年，Szczerba等[21]提出的稀疏A*算法(sparse A*search，SAS)，是一种改进的A*算法，该算法结合航迹的约束条件，裁剪搜索空间的多余节点，缩短了搜索时间。Zammit等[22]提出一种A*纹波减少算法，衰减了因分辨率变化使路径长度产生的波纹效应，并通过对平滑算法的改进，缩短了路径长度。曹栋等[23]提出一种对规划点前后段航迹评估进行加权的改进A*算法，在航迹优化效果和计算时间之间得到平衡，提高了算法计算效率，又对OPEN表中插入删除节点的方式进行改进，采用双向OPEN链表的方法，不仅节省了计算时间，还提升了效率。刘群芳[24]使用改进型稀疏A*算法进行优化，在稀疏A*算法的基础上提取路径特征点后，再进行二次优化，通过稀疏A*算法和进化算法的结合对无人机静态航迹规划进行了设计，有效解决稀疏A*算法的绕径问题，规划出了具有较小航迹长度代价的航迹。李军华等[25]为了解决不确定环境下稀疏A*算法的绕径问题，提出改进稀疏A*算法与文化算法相结合的混合算法实现路径修径，首先采用改进稀疏A*算法剔除冗余特征点得到最优路径的特征点，然后采用进化算法对这些特征点进行进化，并将得到的最优个体定期传递给“信仰空间”，以进一步指导群体进化，该混合算法最大限度地优化了航迹。

3.3.2 遗传算法

遗传算法(genetic algorithm, GA)是1975年美国计算机专家John Holland教授根据达尔文进化论中的“适者生存，优胜劣汰”的理论提出的。该算法是一种基于自然生物进化的随机全局搜索算法，利用编码技术将某个问题的设计变量用称作染色体的数据串进行表示，其优点是具有适应性、全局优化性和隐含并行性，全局搜索能力非常强，缺点是收敛速度慢、容易过早陷入局部最优等，因此出现了很多对基本遗传算法的改进方法。

Dai等[26]在用遗传算法对无人机进行路径规划前，为感知几何复杂目标区域，提出了一种新的无人机覆盖和路径规划方案，采用基于遮挡感知的道路点生成算法得到了良好的时空分辨率，并设计最小化最大能量路径规划算法解决飞行器路径问题。结果表明，该方法具有更好的覆盖和更低的能耗。Arantes等[27]将启发式算法和遗传算法应用于紧急迫降的无人机路径规划问题中，使用遗传算法在合理的计算时间内得到更全质量的解决方案。Yan等[28]提出了一种基于遗传算法和Dubins曲线的固定翼无人机路径规划算法，采用新的编码方案将遗传算法用于二维环境中生成最短的威胁规避路径，并通过添加路径角度将2D Dubins路径转换为Dubins路径，最终在复杂三维环境下生成最短的威胁规避路径。吕文鹏等[29]为了解决基本遗传算法易过早局部收敛的问题并提高局部搜索能力，在无人机灾情巡查路径优化中引入多生境遗传算法，在适应值共享基础上，将排挤机制、间隔交叉两种方法分别引入选择和交叉算子中，并在种群中使用最相似个体中适应度最差的个体替换技术，提高了搜索种群的多样性，很大程度地避免了早熟问题。

3.3.3 蚁群算法

1996年Dorigo等[30]提出的蚁群算法(ACO)是一种用来在图中寻找优化路径的概率型技术，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。为了提高无人机作战任务的成功率，Dorigo等[30]提出了基于改进蚁群算法的适用于航迹规划的优化方法，该方法可以保证无人机以最小的被发现概率及可接受的航程到达目标点，保留算法的最优解、自适应状态转换规则和信息激素更新规则，能够有效提高算法收敛速度、搜索效率以及解的性能。

Konatowski等[31]采用蚁群算法与解决TSP(旅行商)问题类似的工作原理，很大程度上简化了对优化问题的表述，在各种任务参数中规划了无人机的路径。Daryanavard等[32]在地理区域无线物联网节点数据收集的无人机路径规划问题中，为找到传感器之间的最短路径，采用了蚁群算法和模拟退火算法两种优化方法进行三维建模对比，在传感器数量比较多的情况下，蚁群算法有更好的性能。王芳[33]在蚁群算法中融合了量子计算的量子特性，通过量子旋转门策略与最优路径的结合实现信息素的更新规则，不但延续了蚁群算法正反馈、易于分布式计算以及高鲁棒性等优点，而且继承了量子计算的并行性等高效机制，使算法的收敛效果更好，全局寻找最优解的能力也大大加强。刘蓉等[34]将混沌优化理论应用在蚁群算法的初始化阶段来设置初始信息素值，采用变尺度调节系数，先大范围粗略搜索，后逐步缩小范围，然后引入混沌扰动的信息素更新策略，使算法在解的双侧邻域内进行搜索，并对通过寻优得到的航路进行全局信息素更新，最终有效克服了局部最优的缺点，提高了搜索效率。

3.3.4 粒子群算法

1995年Kennedy等[35]提出的粒子群优化(particle swarm optimization, PSO)算法是一种新的进化优化算法，算法的运行机理是对生物群体的社会行为进行模拟，利用群智能建立简化的模型，最早启发于对鸟类搜寻食物行为的研究，同时，利用信息共享机制，使生物群体中的个体之间、个体与群体之间相互作用、相互影响，以促进整个群体的发展。

Patley等[36]采用正交设计的方法对粒子群算法进行改进，通过最小化预定目标函数来确定无人机在每个时间步长的最优位置，在获取3D航路点时使用倾斜平面策略并制定航路点排序策略，为每个无人机规划出最佳路径，同时又缩短了收敛时间。Vijayakumari等[37]采用滚动优化的PSO算法实现了基于感知与回避的碰撞避免，用动态约束和分散控制计算最佳控制输入，为多个无人机规划出了最优轨迹，这种方法是十分有效的防撞方法。宋宇等[38]采用模糊C均值算法与粒子群算法相结合的方法，通过调用模糊C均值算法得到停止分类后的隶属度矩阵，然后用轮盘赌算法确定粒子所属类别并进行下一步改进，使算法的全局寻优能力增强，寻优精度提高。Li等[39]在对多农用无人机飞行路线进行规划时，采用了可变邻域下降的增强型遗传粒子群优化算法，以最小的制造跨度优化了整个无人机组的飞行路径，该算法在离散PSO的基础上，结合GA算法对粒子位置进行了更新，有效地缩短了无人机群的飞行时间。梁静等[40]克服静态约束机制参数不好设置的缺陷，采用结合交叉策略和动态约束的动态多组群粒子群优化算法对路径进行优化，不仅找到有安全距离的路径并避免陷入局部最优。

3.4 航迹平滑处理

航迹平滑是无人机航迹规划的最后阶段，即对无人机航迹进行平滑处理，使无人机与威胁源保持一定距离并且满足可飞要求。初步规划的航迹往往具有一定的角度，由许多最短直线首尾连接而成，而无人机受飞行性能约束，转角有限不可能全都达到，因此需要对这些尖角进行平滑处理，使无人机沿满足飞行性能约束的曲线航迹飞到终点。目前航迹平滑研究方法有圆弧段串联法、地形光滑法、力平衡法、平滑算子法、滤波法、B样条曲线法和Dubins path法等[41]。而比较实用有效的一种航迹平滑算法是B样条曲线法，该算法不仅能对某个航迹段进行局部平滑，更能进行整体全局的平滑，平滑后的航迹在转折点前后曲率变化不大，能较好解决转折点处大角度控制的问题，因此所获得的航迹整体过渡自然，能满足无人机的机动性能约束，并且局部控制能力较强，不会出现突发反复转向操作。考虑到计算的复杂度及实际飞行效果，一般只要曲线曲率不小于无人机最小转弯半径，选择2次或3次B样条曲线进行平滑即可，更高次的没有太大实际意义。

Foo等[42]结合B样条曲线法和粒子群算法对无人机进行路径规划，其中将生成的备用路径用B样条曲线表示，最大限度地减少了计算量，并且将B样条曲线限制为3次，确保了生成的曲线尽量靠近控制点。Bai等[43]提出改进的人工势场方法对多UAV编队路径进行规划，其中引入了B样条插值方法对所规划的路径进行平滑处理，插补后的曲线路径更短更平滑，并且性能稳定、具有最小的均值误差。赵明[44]提出3次B样条曲线和反求控制点的3次B样条曲线相结合的方法，当关键路径点与最近威胁中心的距离较大时，采用3次B样条曲线法，得到比较平滑的航迹；距离较小时，采用反求控制点的B样条曲线法拟合，避免航迹接近威胁区。段彩萍等[45]在存在威胁的二维飞行环境中，采用3次非均匀B样条曲线插补的航迹平滑方法，对用蚁群算法所得到的航迹进行平滑处理，获得了较好的平滑效果。

4 存在的问题

尽管目前针对无人机航迹规划的研究已经取得了丰富的成果，然而，从实际使用需求出发，当前的研究还存在一定的不足，具体表现在如下几个方面。

(1)无人机规划模型构建方面：①二维模型多，三维模型少。无人机所处的真实环境是三维空间环境，为了模拟更真实的环境需要规划三维空间模型进行仿真，二维模型在平面上进行模拟，所建立的模型并不能反映真实的情况。②空气动力学考虑较少。对无人机动力学的约束考虑较少也较简单，造成所规划的路径实际并不可飞。③在线航迹规划模型的设计较少。大多数模型都是离线的，将威胁和障碍物简化为几何静态模型，使无人机按已经规划好的航迹飞行。而在线实时航迹规划中，环境数据会不断发生变化。④较少考虑规划过程中出现的不确定性因素。实际环境中不确定因素很多，一旦遇到突发情况，无人机便难以顺利完成任务。

(2)无人机航迹规划算法方面：①较少进行多重算法的融合。每种算法都有各自的优点，但单一算法多具有局限性，需要融合不同的算法形成混合智能算法，提高算法的适用性和寻优效率。②针对在线航迹规划算法的研究较少。在线航迹规划过程中当无人机获取到变化信息时需要对航迹进行局部调整，研究在线航迹规划算法能够提高无人机避碰避障的能力。③较少考虑针对不确定性环境下的规划算法研究。不确定性规划模型较少，导致不确定性环境下的规划算法研究偏少。静态环境的算法用在不确定环境中时，算法复杂度增大、性能差，因此需要对不确定性环境下的规划算法进行研究。

5 展望

随着对无人机航迹规划研究的深入，航迹规划的各种技术更加完善，成果也越来越多，但不确定环境下的研究和多机协同的研究还在发展阶段。从目前的研究动向来看，无人机航迹规划有以下发展趋势：①提高航迹规划的性能指标要求。航迹规划中对可达性、安全性和实时性等性能指标要求越来越高，无人机在动态的、不确定环境中飞行，环境信息瞬息万变，实时性差将会增加避碰避障的失败率。并且提高可达性、安全性可以保证无人机安全顺利到达目的地。②高效在线航迹规划算法的研究。可以使无人机在动态环境中边规划边飞行，遇到突发状况时能够更好完成局部路径调整。③多无人机协同航迹规划。随着任务要求越来越复杂，单个无人机很难完成规定任务，这就需要多个无人机之间进行协同工作，形成无人机网，协作完成任务。目前已经出现一些多无人机协同航迹规划的研究，但远远不够，需要继续研究多无人机的在线协同航迹规划。

6 结束语

在无人机航迹规划技术的研究中，已知环境下的静态航迹规划技术研究已经相对成熟，研究技术被广泛应用。然而，与此同时暴露出了一些新的问题，需要通过进一步的研究来解决，其中主要的问题是在不确定的、充满未知威胁信息的环境中对无人机航迹进行在线调整，规划时的实时性、精确性要求给规划方法及规划结果带来挑战。另外，目前的研究较少考虑动力学约束，对无人机自身状态等约束不能更好处理，所以航迹规划技术还需要不断地完善。