无人机集群——航迹规划你不知道的各种算法优缺点

我们都知道无人机(UAV )因具有可探测性低、造价低廉、不惧伤亡、起降简单、操作灵活、系统配置多样化、自动控制智能化等特点，因而在未来一体化联合作战中扮演越来越重要的角色。然而早期的无人机都是按照地面任务规划中心预先计算并设定好的航迹飞行，但是随着无人机所承担的任务越来越复杂，其飞行环境的不确定性，对航迹规划的要求也将越来越高。

无人机航迹规划的主要根据任务目标规划满足约束条件的飞行轨迹，是无人机先进任务规划系统的关键组成部分。航迹规划的目的是根据预设数字地图，通过GPS/INS组合导航系统，在适当时间内计算出最优或次最优的飞行轨迹。考虑到数字地图误差及随机环境的影响( 如随机风场等)，要求无人机在飞行过程中具有动态修正轨迹的能力，能回避敌方威胁环境，安全地完成预定任务。无人机航迹规划。主要包括环境信息( 如随机风场、敌方雷达扫描半径范围、及导弹高炮打击威胁区、地形因素)、无人机系统约束、航迹规划器、无人机自动驾驶仪等。航迹规划总框架图如图1所示：

航迹总框图如图1所示

再者，根据执行任务”飞机性能的不同，航迹规划可以分为攻击无人机航迹规划及侦察无人机航迹规划；根据规模的不同，可以分为单机及多机协同编队航迹规划；根据飞行过程的不同，可以分为爬升航迹规划、着陆航迹规划、及巡航航迹规划；根据飞行环境的不同，可以分为确定环境及不确定环境航迹规划。此外，按照实现功能可以划分为离线静态航迹预规划及在线动态实时航迹规划。其算法可分可行性方向算法、通用动态算法及实时优化算法。根据规划范围可分为全局规划算法及局部寻优算法。如Dynapath算法是一种前向链动态规划技术，在大的任务区域内进行航线规划是典型的大范围优化问题，Dynapath 算法可以得到问题的全局最优解。但该算法具有维数爆炸特性的缺陷。

航迹规划按照步骤可以分为两个层次：第一层是整体参考航迹规划;第二层是局部航迹动态优化。整体参考航迹规划是飞行前在地面上进行的。参考航迹的优劣依据预先确定的性能指标，一般根据无人机飞行的任务要求、安全要求、飞行时间和其他战略、战术考虑等因素组合确定，以此最优性能为标准，通过动态路径规划算法生成一条最优参考航迹。有了参考航迹之后，无人机受环境及自身约束条件如最小转弯半径、滚转角等限制，在实际飞行中并非严格沿着参考航迹来飞，而是对参考航迹进行局部动态优化，最后生成最优航迹。按照几何学的观点可以分为基于图形和基于栅格的规划方案。一般来说，前者较为精确，但需要较长的收敛时间;此外按照规划决策可以分为传统规划算法及智能规划算法。

接下来，来分享一下关于无人机航迹规划算法方面的相关内容：

航迹规划算法可以分为传统经典算法和现代智能算法两大类。其中，前者主要包括动态规划法、导数相关法、最优控制法；后者主要包括启发式寻优搜索、遗传算法、人工神经网络(ANN)，群体智能(SA: Swarm Intelligence,主要包括蚁群算法(ACO)、粒子群算法(PSO)蜂群算法(ABC))等。

传统规划算法

（1）动态规划算法

动态规划算法是解决多级决策最优化问题的常见算法。该算法应用于无人机航迹规划中，要求模型相对简单，不要求威胁场连续性，可以获得全局最优解，但缺陷是随着规划区域的扩大，受状态空间的限制，会出现组合爆炸，只能应用于小范围内的搜索(如在无人机高空作业并且威胁单一的情况下可取得良好的效果)，不易应用于三维空间。因此，必须降维简化计算，以提高速度，如将三维航迹分解为水平方向和垂直方向两个二维航迹并分别进行计算，或通过数字地图预处理技术，将三维最优航迹规划转化为安全曲面上的二维航迹规划。

（2）导数相关法

采用导数相关法，主要有最速下降法、牛顿法、共轭梯度法、拟牛顿法、信赖域方法和最小二乘法，其中最速下降法目前使用比较多。最速下降法是S.J.Asseo于1982年提出的，它应用最速下降法求解地形跟踪(TF: Terrain Following) 及地形规避(TA: Terrain Avoiding)问题。该方法相对较简单，收敛速度较快，需要地形一阶编导连续，相对最优控制法对地形要求不高:但由于算法是建立在目标函数梯度基础上,要求导函数连续、迭代运算量大，且易陷入局部最优解。通常，该算法中关于威胁的考虑过于简单，仅以飞行方向同威胁方向的夹角作为威胁大小的计算依据。将威胁场迭加于地形之上，相当于通过增加地形的高度来实现对威胁场的处理，因此，不能反映地形对威胁的遮蔽作用。

（3）最优控制方法

最优控制算法在火箭、卫星轨道规划中有广泛的应用。该算法对地形要求较严，一般要求地形的二阶偏导函数连续；模型及其参数相对复杂，在复杂地形下可能出现死锁，容易发散，规划时间长。因此,在处理TF/TA问题时,一般将问题进行分解。TF主要考虑垂直面内的运动，TA则是水平面的运动，不同的平面内分别进行规划。直升飞机的地形跟踪三维路线直接生成法以速度方向与地形的切平面坐标轴间的夹角作为控制量，飞机的位置坐标作为状态变量，将路线规划问题化为一起点固定、终端自由、时间自由的最优控制问题，通过不断地改变初始航向的方法，使路线的终点接近目标点。这种方法的优点在于将两端固定的问题简化为一端固定、一端自由的问题，从而大大简化了伴随向量的求解。

传统方法存在着共同的缺点，未考虑启发因素，不具备智能搜索功能，容易陷入局部最优，算法通过大规模的反复迭代以弥补智能导向能力的缺乏。因此，算法计算时间长。

智能规划算法

（1）启发式寻优搜索

启发式搜索是在状态空间中的搜索，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标，省略大量的搜索路径，提高效率。A*算法是一种经典的启发式搜索算法，该算法一般应用于基于栅格的数字地图中，多用于解决静态规划的问题。在应用过程中，一般取距离代价和威胁代价等方面的加权和来表示实际代价。A*算法同样存在随搜索区间的增大，内部存储数据增加，搜索时间过长，实时性无法保证的问题，一般应用于二维空间的搜索。通常对基本A*算法进行改进，使之能应用于实时规划。如三维稀疏A*算法(SAS)通过准确有效的剪除不符合要求的状态来使规划快速收敛。采用栅格的形式构造飞行环境，运用一种改进的A*算法搜索，将距离代价、威胁代价以及机动性代价三者的加权和作为路径代价，并运用模糊技术为三者的权值进行分配，针对环境的变化可以调整权系数，对动态环境有较高的适应性。采用各栅格代价值(MCarray)作为输入产生各栅格到目标节点的最小代价值(BCarray)作为启发式项,取得了良好效果。传统的A*算法存在搜索速度慢和耗内存空间大的缺陷。为了加快搜索过程和节省内存空间,通过分区搜索并结合飞行约束削减搜索节点,提出了稀疏A*算法。通过创建Cheap表及降低搜索空间的方法，改进A*算法，解决了算法进行大空间搜索时，耗时急剧增加的问题，因此提高了算法的效率。仿真结果表明，该方法计算速度快，易于实现。

（2）遗传算法

遗传算法(GA)是可用于复杂系统优化的具有鲁棒性的搜索算法。该算法通过染色体的复制、交叉、变异得到新的个体,并对个体性能进行评估，从而得到最优的符合要求的个体。与传统的优化算法相比，主要有以下特点: (1) GA以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身，而遗传算法以它的某种编码形式。(2) GA直接以适应度作为搜索信息，无需导数等其它辅助信息。(3) GA使用多个点的搜索信息，具有隐含并行性。(4) GA使用概率搜索技术，而非确定性规则。但是由于无人机航迹规划存在时间上和计算机资源的约束，GA会出现早熟现象,得不到全局的最优解。

利用极坐标描述威胁位置和航迹点，将路径编码由二维缩减至一维，通过降低搜索空间来提高优化效率。采用遗传算法并以侦察效率指标评估的计算方法，解决了航迹规划中的侦察效率量化问题，通过该方法得到的侦察航迹可以有效地提高无人机的侦察效率"。遗传算法的关键在于对群体的编码，经过大量的实验表明，使用浮点数编码比二进制编码在CPU计算时间上更加有效。初始群体的选取应具有多样性，使得规划空间的每一个体都有机会参与进化。利用导航点的坐标信息以及一位校验位对航迹进行实值编码，结合航迹的约束条件以及评价函数对航迹群体进行分析，然后采用自设定的几种遗传算子对群体进行操作。采用更能符合实际的B样条曲线来表示航迹，对无人机全局和局部航迹进行规划。遗传算法良好群体搜索性能，固有的并行计算能力等优点都使得此算法在航迹规划中被广泛应用。但遗传算法进行路径规划存在费时的问题，一般将其应用于参考航迹的规划过程，很难应用于实时规划。从算法结构上进行改造，将变异操作从交叉操作中分离出来，成为独立的并列于交叉的遗传寻优操作；在交叉操作中，以“门当户对”原则进行个体的配对，利用混沌序列确定交叉点，实行单点交叉,以确保算法收敛精度；在变异操作中，利用混沌序列对染色体中多个基因进行变异，避免了算法早熟。

（3）神经网络方法

由于Hopfield网络引入了“能量函数”的概念，在达到稳定时网络的能量最小，所以很自然地可以用其特殊的非线性动态结构来解决优化之类的技术问题。一种基于Hopfield神经网络的无人机地形跟随(TF)/地形回避(TA)的航迹规划方法将地形信息反映到算法参数连接权中，利用扩展的Hopfield模型结合无人机约束条件实现航迹安全、合理的规划。使用基于距离变换的串行模拟构建数值势场, 加速了数值势场的传播。在学习过程中，通过调整连接权系数改变局部势场分布。试验表明，算法在单处理器上可以进行有效的快速航迹规划，该方法具有较高的效率和环境适应性。

蚁群算法

蚁群算法( ACO)是一种用来在图中寻找优化路径的机率型技术，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。为提高无人机作战任务的成功率，提出了基于蚁群算法的适用于航迹规划的优化方法，该方法可以保证无人机能够以最小的被发现概率及可接受的航程到达目标点。保留最优解、自适应状态转换规则和自适应信息激素更新规则，有效地提高了算法收敛速度和解的性能"。基于改进蚁群算法的无人机三维航迹规划方法，则以保证在敌方防御区域内以最小的被发现概率以及可接受的航程到达目标点。首先对无人机三维航迹规划模型进行分析，在此基础上采用蚁群算法对三维航迹进行优化。其次，将最短路径的信息反馈到系统中作为搜索的指导信号，并改进节点选择方法，以提高应用蚁群算法搜索无人机三维航迹的效率。最后，将所研究的方法应用于无人机的三维航迹规划。仿真结果表明，本文提出的方法是有效的。改进蚁群算法的初始信息素强度与启发因子，并以岛屿进攻战役这一特定作战任务为例，就实现了侦察多目标时的航迹规划问题。在每次循环结束，保留其最佳结果及改进蚂蚁状态转换规则,对基本蚁群算法提出了改进，提供了一种新的有效的航迹优化算法。仿真结果表明，改进的算法克服了原算法的收敛速度慢、易于过早陷入局部最优的缺点。针对传统蚁群算法在搜索过程中出现停滞现象，还研究出一种Q-学习的自适应蚁群算法的无人机航迹规划方法，仿真结果表明，该方法也是一种有效的航迹规划方法。

综上所述，各种智能优化算法都有其自身特点，编程的复杂程度也不一样，启发式寻优搜索对动态环境有较高的适应性，可应用于实时规划，但存在搜索速度慢和耗内存空间大的缺陷。蚁群算法在概念上较为接近航迹规划问题，编程相对比较容易，但随着问题规模的扩大,需要较大的存储空间；遗传算法目前使用比较广泛，但是由于航迹长度的不确定，导致编码长度动态修改，增加了编程的复杂度；神经网络法适用于TF/ TA的航迹规划，而对于具有雷达、导弹及高炮等威胁因素未作考虑。此外，为有效利用算法各自的优势，混合算法将成为航迹规划算法的发展趋势。

无人机实时航迹规划是当今无人机集群配合,集群战术再规划，集群战术目标再制定等高级自主飞行的技术基础，也是提高无人机的生存概率的一种最有效的手段。如果你想更系统，更快速的推进无人机集群项目研究，可以在已经开发好的无人机集群平台上开展项目实验及科研。

现在已经开发好的无人机集群科研平台，可用于无人系统的动态建模和控制研究、运动规划、避障控制、多信息融合、编队控制、多智能体协调控制、无人系统自主控制等研究方向。

可进行的多机编队飞行实验非常全面及具有实用性：

❉多无人机协同搜索区域分割与覆盖算法仿真

❉多无人机任务分配策略实验

❉多机编队队形设计、保持、变换和防撞实验；

❉多无人机任务航迹规划实验

❉多无人机通信组网实验

在无人机编队飞行方面，可提供无人机编队飞圆形、空间8字、空间螺旋，队形变换，从跟随、空地协同等无人机编队例程。这些例程完全开源。多种视频教程由浅入深地为用户讲解实验的原理、步骤、目标等，并附有相应的配套例程代码，方便用户快速掌握、理解。

而且平台开放性高，接口丰富。可以很方便地进行二次开发。还可根据用户的实际需求定制整个系统平台，并提供相应的技术支撑和详细的例程及说明书指导。满足用户的个性化和差异化需求，使平台更加契合用户的使用特点和习惯，提升体验感和交互率，减少用户熟悉平台的时间成本，大大提高用户的开发效率和体验。

重要的是，集群研发平台所有的例程都可以在仿真平台中模拟仿真。可以软件在环仿真，硬件在环仿真，实现仿真和实物开发有机结合。可以在实测之前通过仿真测试验证算法的可靠性和有效性，然后无缝切换到本集群研发平台。大大提高研发效率。

平台接口不仅丰富、而且开放性强，用户不需要掌握太多的底层编程技术即可完成算法的修改和验证。支持C、C++、Python、ROS、Matlab/Simulink等多种编程环境，提供完善的二次开发接口。

兼容的定位系统也覆盖全面，目前涵盖主流的室内外定位方式。可提供光学定位系统、UWB定位系统、激光定位系统、GPS、RTK等多种定位平台，定位系统覆盖面积可根据客户要求定制。

在通信方面：支持WIFI、数传、等多种集群通讯方式。

随着对无人机航迹规划要求的越来越高，未来无人机航迹规划在算法方面的发展方向及研究重点主要有: (1)不确定环境下的实时航迹规划。对多传感信息运用不确定性理论进行综合处理，以便合理有效利用各种信息，对战场态势进行评估，真正实现在无人干预的情况下，根据探测结果自动修改航迹; (2)战术级的强实时的航迹规划问题; (3)高效的全局搜索方法和局部搜索方法的混合使用;(4) 多任务目标(如低空突防、目标搜索营救、信息侦察等任务)综合的规划算法: (5) 多机协同规划算法。要求执行任务时，整体代价达到最优:(6)针对地形、敌情信息处理方法的研究算法。此项研究直接决定了规划路径的质量。