无人机航路规划研究

刁德权

摘 要：通过对无人机航路规划的研究，对无人机航路规划问题进行了概括和总结，介绍了无人机航路规划流程，分析了无人机航路规划的约束条件，阐述了目前国内外应用和研究的几种航路规划算法，并对无人机航路规划算法的发展趋势进行了展望。

关键词：无人机；航路规划；动态规划算法；启发式算法；遗传算法

1 无人机航路规划问题的描述

无人机航路规划是依据地形信息和执行任务环境条件信息，综合考虑无人机的性能、到达时间、耗能、威胁以及飞行区域等约束条件，为无人机规划出一条或多条自出发点到目标点的最优或可行的飞行航路，保证无人机高效、圆满地完成飞行任务，并安全返回基地[1]。其本质是多约束条件下最优或可行解的求解问题。无人机航路规划一般分两步：首先是飞行前预规划，即根据既定任务，结合环境限制与飞行约束条件，从整体上制定最优参考路径并装订特殊任务；其次是飞行过程中的重规划，即根据飞行过程中遇到的突发状况，如地形、气象变化、未知限飞禁飞因素等，局部动态的调整飞行路径或改变动作任务（如图1所示）。

从框图中可知，按照任务环境模型是否实时变化，即无人机飞行环境是否确定，航路规划可分为已知威胁信息环境下航路规划和未知威胁信息环境下航路规划。已知威胁信息环境下航路规划根据无人机飞行环境的确定信息，在无人机执行任务之前就可以进行规划设计，这一过程一般在无人机起飞前完成，实时性要求不高；未知威胁信息环境下航路规划通过无人机对环境变化更新后，在飞行中对航路进行重规划，实时性要求较高。

2 无人机航路规划约束条件

2.1 飞行环境限制

无人机在执行任务时，会受到如禁飞区、障碍物、险恶地形等复杂地理环境的限制，因此在航路规划时，应尽量避开这些区域，可将这些区域在地图上标识为禁飞区域，以提升无人机工作效率。此外，飞行区域内的气象因素也将影响任务效率，应充分考虑大风、雨雪等复杂气象下的气象预测与应对机制。

2.2 无人机物理限制

⑴最小转弯半径：由于无人机飞行转弯形成的弧度将受到自身飞行性能限制，它限制无人机只能在特定的转弯半径范围内转弯。⑵最大俯仰角：限制了航迹在垂直平面内上升和下滑的最大角度。⑶最小航路段长度：无人机飞行航路由若干个航点与相邻航点之间的航路段组成，在航路段飞行途中沿直线飞行，而到达某些航点时有可能根据任务的要求而改变飞行姿态，最小航路段长度是指限制无人机在开始改变飞行姿态前必须直飞的最短距离。⑷最低安全飞行高度：限制通过任务区域最低飞行高度，防止飞行高度过低而撞击地面而坠毁。

2.3 飞行任务要求

无人机具体执行的飞行任务主要包括到达时间和进入目标方向等，需满足如下要求：⑴航路距离约束：限制航路长度不大于一个预先设定的最大距离。⑵固定的目标进入方向：确保无人机从特定角度接近目标。

2.4 实时性要求

当预先具备完整精确的环境信息时，可一次性规划自起点到终点的最优航路。而实际情况是难以保证获得的环境信息不发生变换；另一方面，由于任务的不确定性，无人机常常需要临时改变飞行任务。在环境信息变化区域不大的情况下，可通过局部更新的方法进行航路的在线重规划；而当环境变化区域较大时，无人机航路规划系统则必须具备在线重规划功能。

3 无人机航路规划算法

由于无人机所处的战场环境异常复杂辽阔，规划约束条件众多，各因素之间又存在强耦合，再加上无人机自身独特的控制方式，航路规划在处理这些因素时面临极大挑战。Canny在1988年就已经证明航路规划是一个NP问题，对其直接求解往往导致组合爆炸。为了加速规划进程，近年来国内外学者已提出了许多不同的规划方法。下面对已有的规划方法加以概述。

3.1 动态规划算法

动态规划是分阶段决策过程的最优化方法。动态规划法是对于存在多个空中封锁和地面障碍等多约束的情况下，采用航路图分类法进行航路规划。无人机根据约束，在有限的探测和处理范围内，根据不同的滚转角度，得到下一时刻无人机可能到达的位置，并在新的飞行点上，计算再下一时刻的位置。以此类推，得到一棵航路树，比较树枝终点的性能指标并找到代价最小的节点，反向搜索其父节点，得到最优航路。

动态规划法模型简单，对地形要求不高，算法不依赖于威胁场的连续性，容易实现。但由于动态规划算法具有维数爆炸特性，如果在大范围内进行动态搜索，计算机无法处理大量信息，因此动态规划算法适于小范围内航路规划，对于范围较大的区域会出现组合爆炸。

3.2 启发式算法

启发式算法是指通过寻求一种能产生可行解的启发式规划，找到问题的一个最优解或近似最优解。启发式算法比较典型的是启发式A*搜索法，是利用问题拥有的启发信息来引导搜索，以达到减少搜索范围，降低问题复杂度的目的。启发式搜索首先定义以下代价函数：f（M）=g（M）+h（M）

式中：g（M）为启发式因子，表示从初始节点到当前节点M的真实代价；h（M）表示从当前节点M到目标节点的最小代价估计值；f（M）则表示从初始节点经M到目标节点的最小代价路径的估计值。搜索的原则是优先扩展f（M）小的节点，最终搜索得到最优航路（如图2所示）。

启发式算法由于提供了智能搜索，因此大幅度提高了搜索效率。用启发式A*搜索法进行航路搜索时，由于需要综合考虑各种因素，获得一条最优航路需要很长的收敛时间和极大的内存空间，因此不适于实时求解。为此，Robert J.Szczerba等人提出了一种用于二维规划的稀疏A*搜索算法。该算法结合航路约束有效地消减搜索空间，大大缩短了搜索时间，节省了内存空间，较好地满足了实时性要求。

3.3 遗传算法

遗传算法提供了一种求解复杂问题的通用框架，它仿效生物的遗传和进化机制，借助复制、杂交、变异等操作，使所要解决的问题从初始解一步步逼近最优解。其5个要素包括染色体编码、初始群体、适应度函数、遗传操作和控制参数。很多学者都将遗传算法用于飞行器的航路规划求解。

在角频率组固定的情况下，使用幅值组构造一条染色体，其基因位置表示对应的角频率，数值代表相应的幅值。应用该型染色体构造方法进行遗传搜索得到的优化航路（如图3所示）。

遗传算法计算速度快，得到的航路满足无人机机动性能，无须再进行平滑处理，所得航路能够严格经过起始点和目标点，但是容易产生早熟现象，不能得到最优解。Juris Vagners等人通过采用多种群并发计算，通过竞争机制优选的思想来解决遗传算法的早熟现象。Ioannis K.Nikolos等人采用更能符合实际的B样条曲线来表示航路，对无人机全局和局部航路进行规划，得到了较好的结果。

综上，无人机航路规划有多种算法，既有适于小范围的规划算法，可在无人机上进行动态修改；又有适于大范围的规划算法，可在已知信息下求得全局最优解；既能进行人为的智能规划，又能在一定范围内进行模型的自动求解。应在具体问题具体分析基础上，发展高效的无人机航路规划方法。

随着无人机所要执行的任务越来越复杂，加上环境的不确定性，对航路规划的要求也将越来越高。未知威胁信息环境下的实时航路规划将是未来研究的重点，高效的全局搜索方法和局部搜索方法，二者混合使用将是无人机航路规划的一种趋势。

[参考文献]

[1]J.F.Gilmore.Autonomous vehicle planning analysis methodology[J].In：The Proceeding of American Control Conference，Kluwer.Boston，MA，1991.

[2]C.Zheng， M.ding，C Zhou.Real-time route planning for unmanned air vehicle with an evolutionary algorithm[J].International Journal of Pattern Recognition and Artificial Intelligence，2003，17（1）：63-81.

[3]S.A.Bortoff. Path planning for UAVs[A].the Proceedings of the American Control Conference，Chicago，USA，2000：364-368.