无人机航迹规划常用算法综述
王 琼1a,1b, 刘美万1a,1b, 任伟建1a,1b, 王天任2
(1. 东北石油大学 a. 电气信息工程学院; b. 黑龙江省网络化与智能控制重点实验室, 黑龙江 大庆 163318;2. 中国石化集团 中石化新星(北京)新能源研究院有限公司, 北京 100083)
摘要： 为促进航迹规划技术的发展, 对航迹规划常用算法进行综述。首先对航迹规划的规划思想和构成进行分析；其次将航迹规划算法分为传统经典算法和现代智能算法两大类, 对其中几种常用算法进行分析总结；最后阐述现代智能算法在航迹规划应用中的改进、 多重算法的融合改进以及多无人机四维航迹规划算法研究3个研究热点及未来发展趋势。
关键词： 无人机；航迹规划；综述；传统经典算法；现代智能算法
0 引 言
随着航空技术日益发展, 越来越多的无人机被用于替代飞行员执行一些高危险、 高强度或大范围巡检、 搜救任务, 因此完善的任务规划系统是无人机顺利完成任务的重要保障。任务规划系统一般由航迹规划、 导航、 数据通信3大子系统组成, 而航迹规划则是任务规划系统的核心部分。
无人机航迹规划就是在综合考虑无人机到达时间、 油耗、 威胁以及飞行区域等因素的前提下, 为无人机规划出最优或满意的飞行航迹, 以保证圆满地完成飞行任务[1] 。无论是在军事还是民用领域, 好的航迹规划系统都是提高无人机安全性能, 保证无人机出色完成任务的重要手段。笔者将在对航迹规划问题进行分析的基础上, 对当前几种常用航迹规划算法进行分类总结, 最后指出目前研究热点及未来发展趋势。
1 航迹规划问题分析
在不考虑时间因素的情况下, 无人机航迹规划应该是在三维空间中进行的, 但在一些任务中, 无人机保持在固定高度飞行, 不需要考虑高度变化问题。因此在进行航迹规划时可以将三维空间中的物体投影到二维平面, 从而将三维航迹规划问题降至二维, 简化问题的复杂度。但在军事突防、 电力巡线、 山地救援等应用中, 二维航迹规划实用价值有限。笔者将从规划思想和构成两方面对航迹规划问题进行分析。
1.1 规划思想
航迹规划问题是一个包含多个优化目标和多个约束的非线性规划问题[2] , 其核心就是建立目标函数的数学模型和有效地处理各项约束。由于涉及约束条件较多, 目标函数复杂, 数学模型建立困难, 为降低问题复杂性, 目前大多数学者都采用分层规划的思想, 将航迹规划分为两步进行。首先根据已知的环境信息、 任务要求等在无人机起飞前为其规划出一条满足约束条件的全局最优参考航迹。无人机在按照此航迹飞行的过程中, 当出现未知或动态威胁信息时, 再进行局部航迹动态优化。由于全局参考航迹规划需要考虑整体的优化, 因此要在避免陷入局部最优的情况下尽量减少计算量。而局部航迹动态优化用于应对突发威胁, 因此要尽量缩短规划时间以确保实时性。
1.2 规划构成
无人机航迹规划一般由以下几个部分组成： 描述规划空间, 选择航迹的表示形式, 分析约束条件, 确定代价函数, 选取航迹搜索算法和航迹平滑。
1) 描述规划空间。其目的是建立一个便于计算机进行航迹规划所使用的环境模型, 即将实际的物理空间抽象成算法能处理的抽象空间, 实现相互间的映射。规划空间的表示是否合理直接影响规划的效率和结果的优劣性。一种好的规划空间表示法应能满足如下要求:
① 规划空间能合理且尽量完善地反映飞行环境中的各种信息(地形、 威胁、 障碍等), 以利于航迹搜索；
② 当飞行环境中的某些信息发生变化时能实时地进行更新, 以满足实时应用的要求；
③ 能满足无人机自身性能约束条件, 包括最大拐弯角、 最大爬升/俯冲角、 最大航迹距离、 最小航迹段长度和最低飞行高度等。
常用的规划空间表示方法有栅格法和图形法。栅格法将规划空间分解成为一些简单的单元,并为每个单元分配一个代价值, 对应于无人机经过空间相应区域的代价, 并判断这些单元之间是否存在可行路径, 找到包含起始点和目标点的单元, 从起始单元开始, 依次向栅格中代价最小的邻域移动, 最后到达目标单元[3] 。航迹搜索算法中的A*算法、 动态规划法等就是利用栅格描述规划空间。由于数字地图采用栅格的形式存储, 所以多数的航迹规划研究都是使用栅格法表示规划空间。图形法首先根据一定规则将规划空间表示成一个由一维线段构成的网络图, 然后采用某一搜索算法在该网络图上进行搜索。使用图形法必须表示出所有可能的路径, 否则就可能丢失最优解。图形法相比栅格法数据处理量少, 但是更新较困难。常用的图形法有Voronoi图法[4] 、 可视图法(Visibility Graph) [5] 、 随机路标图法(PRM：Probabilistic Road Map) [6] 等。
2) 航迹表示。其形式有两种：一种是基于无人机运动学、 动力学描述的连续平滑航迹, 采用此种表示方法可以省去最后的航迹平滑环节；另一种是用航迹点表示, 相邻航迹点之间用直线段连接几何折线航迹。第2种表示方法有如下优点：
① 可以通过调整航迹节点的数目达到所需要的精度；
② 将复杂的航迹规划问题分解为一组统一形式的小规模子问题, 对于每个子问题, 只需关心一个点的坐标, 从而将考察航迹是否可行变为仅考察一个点或一条直线段是否满足要求；
③ 便于实现并行、 分布式计算。
3) 分析约束条件。航迹规划问题需要考虑的约束条件包括环境约束、 任务约束和无人机自身性能约束。环境约束有威胁约束(如被敌方雷达发现概率、 敌方导弹高炮击落概率、 撞地概率等)、 禁飞区约束、 复杂气象区约束等；任务约束有任务完成时间、 起始点、 目标点、 固定航向角、 低空/超低空突防等；无人机自身性能约束有最大/最小平飞速度、 最大航程、 最高/最低飞行高度、 水平最小转弯半径、 最大爬升角/俯冲角、 最大纵向曲率、 最大法向过载等[7] 。若是进行二维航迹规划, 则不需要考虑无人机的爬升/俯冲角约束和飞行高度约束。
4) 确定代价函数。代价函数将算法与实际物理问题紧密联系在一起。对于无人机航迹规划, 代价函数是评价航迹优劣的标准, 代价值越小则表明航迹越优, 反之表明航迹越差。确定代价函数需要综合考虑影响航迹性能的各项因素, 对各个指标进行量化和计算。三维航迹规划的代价函数通常包含航迹长度代价、 威胁代价和高度代价, 表示为
J=ω1L+ω2T+ω3H(1)
ω1+ω2+ω3=1(2)
其中J为航迹总代价, L为航迹长度代价, 一些文献也称其为燃油代价, T为威胁代价, H为高度代价； ω1、ω2、ω3为相应的权系数, 根据任务需要设置其值。二维航迹规划则不需要考虑高度代价。
5) 选取搜索算法。根据任务需求选取合适的算法规划出满足约束条件、 规避障碍、 使代价函数获得最优值的航迹是航迹规划问题的核心部分。
6) 航迹平滑。通过相应算法搜索出的航迹对于无人机实际飞行而言并不一定可行, 例如规划出的航迹拐弯点较多, 而无人机在实际飞行中由于自身机动限制不能频繁转弯, 因此需要对规划出的航迹进行平滑处理, 消除不必要的拐弯点以利于无人机实际飞行。常用航迹平滑方法有三次样条插值法[8] 、 贝塞尔曲线(Bezier Curve)[9] 、 k-trajectory算法[10] 等。
2 常用航迹规划算法
无人机航迹规划的本质是路径规划, 即寻找适当的策略构成连接起点到终点位置的由序列点或曲线组成的路径, 因此用于航迹规划的算法实际上也就是路径规划算法。路径规划算法有很多, 每种算法都有其自身的优缺点和适用范围, 按照规划决策可以将算法分为传统经典算法和现代智能算法[11] 两类。
2.1 传统经典算法
近年来常用于航迹规划的传统经典算法有Dijkstra算法、 人工势场法(APF：Artificial Potential Field)和模拟退火算法(SAA: Simulated Annealing Algorithm)。Dijkstra算法是图论中求解最短路径的经典算法, 适用于每条边的权数为非负的情况, 能得到从指定顶点到其他任意顶点的最短路径。使用Dijkstra算法进行航迹规划, 构建的赋权图的顶点代表航迹点, 赋权图的边代表所有可行航迹, Dijkstra算法的作用就是在这些可行航迹里找到最优航迹。Dijkstra算法实现简单, 但其运算时间和所用内存与搜索空间中节点个数平方成正比, 在大范围高维空间中搜索时间长, 对内存要求也很高, 因此多用于二维静态航迹规划[12,13] 。由于航迹规划空间范围大, 对于Dijkstra算法在航迹规划中的应用, 如何选取有效航迹点, 减少航迹点数量, 缩短规划时间是问题的关键。文献[12] 在Voronoi图的基础上使用Dijkstra算法寻找最优航迹, 将威胁看作一个点, 选取各威胁点之间连线的中垂线的交点为航迹点。这种方法能保证航迹最大化避开各个威胁, 安全性高, 但航迹较长。并且没有考虑无人机最大转弯角约束, 航迹不一定可飞。文献[13] 在可视图的基础上使用Dijkstra算法寻找最短航迹, 将多边形障碍的各个顶点看作航迹点, 并建立转弯角约束机制。这种方法得到的航迹短, 满足无人机最大转弯角约束, 但由于航迹贴近障碍物, 安全性较低。此外, 可视图不能表达物体运动的方向性约束的缺陷导致Dijkstra算法在搜索时可能找不到路径。虽然Dijkstra算法多用于二维航迹规划, 但也有学者将其应用于三维航迹规划。文献[14] 将飞行空间映射到由若干个四面体组成的三维Delaunay三角网中, 四面体的顶点对应威胁的位置, 四面体内切球的中心作为航迹点, 所有相邻四面体内切球中心点的连线构成一个三维网络, 这个三维网络就是所有可行航迹。然后用Dijkstra算法在这个三维网络上寻找最短航迹。最后用人工势场法对初始航迹进行优化, 获得平滑可飞的航迹。该方法与Voronoi图法类似, 规划出的航迹能最大化避开威胁, 安全性高, 但航迹相对较长。目前使用Dijkstra算法进行航迹规划多是利用Voronoi图、 概率地图或可视图描述规划环境, 然后在此基础上利用Dijkstra算法寻找最短航迹, 但得到的航迹若安全性高则航迹长, 若航迹短则安全性低, 没有在航迹长度与安全性之间寻找到一个好的平衡。
人工势场法是一种模拟电势场分布的规划方法, 任务区域内的目标点产生引力场, 威胁源产生斥力场, 无人机在引力和斥力的共同作用下向目标点运动。传统人工势场法定义如下。
航迹点X的引力势函数和斥力势函数分别为
(3)
(4)
其中Katt和Krep分别为引力和斥力增益系数, 且均为正常数； ρ(X,XG)为航迹点X与目标点XG之间的距离； ρ(X,XO)为航迹点X与威胁源XO之间的距离； ρO为威胁源最大影响距离。
无人机在X处受到的引力和斥力分别是相应势函数的负梯度
Fatt=-Uatt(X)=-Kattρ(X,XG)(5)
Frep=-(6)
总势场力为目标点产生的引力和各个威胁源产生的斥力的矢量和
Ftotal=Fatt+∑Frep(7)
人工势场法的优点是算法简明、 实时性好、 规划速度快, 在局部规划和实时规划领域应用广泛。缺点是当无人机离目标点比较远, Fatt≫Frep时, 合力方向更趋近目标点方向, 无人机可能会进入威胁区；当目标点附近有威胁源时, 斥力将会非常大, 而引力相对较小, 无人机将很难到达目标点；在复杂环境中, 容易产生局部极小值, 使算法停滞或震动；在障碍物附近有抖动现象, 在狭窄通道间频繁摆动；在动态环境下规划效果减弱；计算势场负梯度的方法因为没有优化变量, 将航迹规划问题转换成了非优化问题, 因此缺乏评价指标衡量航迹的优劣, 势场的建立直接决定了航迹的质量, 相同的环境下, 不同的势场形式也可能得到不同的航迹。针对该问题, 学者们结合无人机航迹规划的特点提出了多种改进方法。文献[15] 在斥力势函数中加入无人机与目标点的距离, 减小斥力, 改善障碍物在目标附近时, 目标不可达的问题。设置引导点为无人机提供方向随机的势场力, 解决局部极小值和震荡问题。文献[16] 在人工势场法搜索陷入威胁区时, 构造惩罚势函数替代斥力势函数, 并使用模拟退火算法取代虚拟力引导的方法搜索逃离位置, 有效避免了局部极小值和抖动现象, 得到的航迹能成功避开威胁, 但增大了计算量, 降低了人工势场法的实时性。文献[17] 通过引入相对速度斥力势场和斥力增益模糊控制器实现人工势场法的动态避障, 避免局部极小值。文献[18] 通过增加高度调节引力势函数以增强人工势场法在三维航迹规划中对高度的控制, 同时引入飞行器的动力学约束条件, 使航迹更具可飞性, 并改善了人工势场法的局部极小值、 障碍物附近抖动、 狭窄通道间频繁摆动等缺点。然而文献[15-18] 中均未衡量航迹优劣的评价指标, 对此文献[19] 引入附加控制力作为优化变量, 通过优化出适当的附加控制力, 使无人机在满足各种物理约束的条件下, 规划出的航迹可使代价指标最优, 降低了势场建立的任意性对航迹结果的影响。但文献[19] 在考虑无人机动力学模型时将无人机看作质点, 与实际动力学模型有一定差异。总之, 对于极小值等问题, 前人提出的各种改进方法都在一定程度上弥补甚至消除了这些缺陷, 但对于障碍物附近抖动、 狭窄通道间频繁摆动这一缺陷的改善效果还有待提高。
模拟退火算法是基于蒙特卡罗迭代求解法的一种启发式随机搜索算法。它模拟固体物质的退火过程, 在某一初始温度下, 伴随温度控制参数按照降温函数不断下降, 结合概率的突跳特性在解空间中随机寻找目标函数的全局最优解, 即能概率性地跳出局部最优解并最终趋于全局最优解。退火过程由冷却进度表(Cooling Schedule)控制, 包括温度控制参数的初值t及其衰减因子Δ t、 每个t值时的迭代次数和终止条件。模拟退火算法的优点是算法求得的解与初始解状态无关, 具有渐近收敛性, 是一种以概率1收敛于全局最优解的全局优化算法。缺点是解的质量依赖于当前解产生新解的变换方法和冷却进度表的设计。在航迹规划中, 模拟退火算法的一个解代表一条航迹, 目标函数则是代价函数, 常用于求解二维航迹规划中的TSP问题[20] , 但该算法多数没有考虑无人机的机动性能约束, 得到的航迹可飞性不高。模拟退火算法也可与易陷入局部最优解的算法相结合帮助其跳出局部最优找到全局最优解, 如遗传模拟退火算法[21] , 在交叉和变异过程中使用Metropolis准则判断是否接受新解, 当然, 这会增大原算法的计算量。
2.2 现代智能算法
相较于传统经典算法, 现代智能算法的应用更为广泛。在航迹规划中常用的现代智能算法有A*算法、 遗传算法(GA：Genetic Algorithm)、 蚁群优化(ACO：Ant Colony Optimization)算法和粒子群优化(PSO：Particle Swarm Optimization)算法。
A*算法是一种智能启发式搜索算法, 它将搜索空间表示为网格的形式, 以网格的中心点或顶点作为航迹点, 通过搜索邻域内代价函数值最小的航迹点, 从起始点逐步搜索到目标点, 最后逆向回溯当前节点的父节点生成最优航迹, 其中待扩展航迹节点存放在OPEN表中, 已扩展节点存放在CLOSE表中。代价函数的表达式如下所示
f(x)=g(x)+h(x)(8)
其中g(x)表示从起始点到当前节点的实际代价, h(x)称为启发函数, 表示从当前节点到目标点的估算代价, 常用的启发函数可选用欧氏距离、 曼哈顿距离、 对角线距离等。启发函数是A*算法的核心, 它能在搜索效率和最优解之间权衡。若h(x)小于从当前节点到目标点的实际代价, 则搜索得到最优路径, 但这时搜索节点增多, 搜索效率降低；若h(x)一直等于从当前节点到目标点的实际代价, 此时A*严格按照最优路径搜索, 搜索效率最高；若h(x)大于从当前节点到目标点的实际代价, 则搜索结果可能不是最优路径, 但搜索效率会提高。此外, OPEN表的维护方式也会影响A*算法的搜索效率, 当路径很长时, 这种影响会更明显。总之, 启发函数的选择决定了A*算法是否能找到最优解, OPEN表的维护方式和搜索节点数量决定了A*算法的运行速度。随着搜索空间增大, A*算法的计算量会呈指数增长, 导致规划时间过长, 一般用于静态航迹规划。在航迹规划中, 如何提高A*算法的运行速度并得到最优航迹是学者们重点考虑的问题。文献[7] 采用结构体式最小二叉堆和三层嵌套的二叉堆技术分别维护管理OPEN表和CLOSE表, 相比较于传统的数组式最小二叉堆维护OPEN表和单向链表管理CLOSE表的方式, 提高了最优节点的提取速度, 克服了数组二叉堆的容量可能导致OPEN表溢出的问题, 有效解决了动态二叉树易出现的极度不平衡问题, 保证了节点查找的高效率, 较大幅度提高了A*算法的规划效率。文献[22] 提出使用2.5维网格模型描述三维规划空间, 每个网格点包含经度、 纬度和高程信息, 此方法计算效率要远大于三维网格划分方式。文献[23] 将三维航迹规划分解为二维规划和高度规划, 使用动态时间规整(DTW: Dynamic Time Warping)距离作为A*算法的启发函数进行二维规划, 再由二维航迹结合高程数字地图, 利用粒子沉降法赋予每个航迹点高度信息, 生成三维航迹。这种方法有效地将三维空间的搜索节点删减至二维, 大大减少了搜索节点数量, 缩短了规划时间。使用DTW距离作为启发函数得到的航迹也要优于常用的欧氏距离、 曼哈顿距离和对角线距离, 但仍不是最优航迹。由于航迹规划问题的复杂性, 虽然学者们通过各种改进方法提高了A*算法的搜索效率, 但仍没有找到值恒等于从当前节点到目标点真实代价的启发函数, 实现A*算法的高效最优搜索。
遗传算法的基本思想是模拟生物遗传进化过程, 根据“适者生存”、 “优胜劣汰”的原则, 借助选择、 交叉、 变异等操作, 使所要解决的问题从初始解一步步逼近最优解。在航迹规划中, 遗传算法每条染色体(个体)代表无人机的一条航迹, 基因的编码方式也就是航迹节点的编码方式, 适应度函数由代价函数变化而来。遗传算法的优点是不要求优化函数具备连续、 可导和单峰等条件, 具有较强的鲁棒性, 是一种高效、 并行、 全局的搜索方法, 适用于三维全局航迹规划。缺点是种群失去多样性而导致早熟收敛, 寻优时间长, 局部搜索能力差等。针对该问题, 学者们提出了不同的改进方法, 如引入量子、 自适应等因子, 但这些改进方法仍然存在较多不足。文献[24] 针对量子遗传算法初始种群的单一性, 引入关于概率划分的小生境协同进化策略, 并对各种群采用动态量子旋转角；采用精英选择机制, 保留每一代中的最优个体, 并借鉴狼群分配原则对种群进行更新。该方法提高了量子遗传算法的稳定性和寻优精度, 但在收敛速度上没有改善, 且没有考虑无人机自身性能约束。文献[25] 使用并行遗传算法结合概率地图实现多无人机协同航迹规划, 并行遗传算法很好地克服了遗传算法早熟的缺陷, 但文献同样没有考虑无人机自身性能约束。文献[26] 通过在遗传算法主种群上附加一个病毒种群的方法, 保证可行引导段的有效积累并维持种群多样性。采用定长实值和变长实值两种编码方式分别为染色体和病毒个体编码, 通过采用反转录和转导这两种病毒感染操作实现两个种群间模块的信息交换, 使进化信息在种群内迅速、 定向地传播, 消除了寻优过程的盲目性。该方法改善了遗传算法早熟和局部收敛慢的问题, 提高了收敛速度, 但对于搜索精度几乎没有提高。文献[27] 提出多频振动遗传算法, 在遗传操作中使用两次变异操作, 分别作用于整个种群和精英个体, 为种群提供全局多样性和局部多样性, 从而有效避免早熟, 提高搜索精度, 达到快速收敛的目的。
蚁群优化算法模拟蚂蚁在寻找食物过程中发现路径的行为特性, 利用信息素浓度进行后继行为。T时刻蚂蚁n从节点a转移到节点b的概率为
(9)
其中τab为节点b上的信息素浓度； ηab为节点a与节点b之间的能见度, 也叫启发函数, 它可以是距离开销, 也可以是距离开销与其它开销的组合, 如高度、 安全度等； α、β为τab与ηab的相对重要性的权值； 为节点a的所有相邻节点的集合。
信息素具有挥发性, 随着时间的增加其浓度会降低。信息素的更新分为局部更新和全局更新, 局部信息素更新是用在蚂蚁完成一个航迹点的选择时, 相应的减少该点的信息素, 降低此点对后来蚂蚁的吸引程度, 从而增加蚂蚁的探寻范围, 减小算法陷入停滞的概率。其更新公式为
τab(t+1)=ξτab(t)(10)
其中ξ为信息素减少因子, 用于控制信息素减少的大小。全局信息素更新是经过m时刻, 当蚂蚁完成寻路任务后对其经过的所有航迹点上的信息素进行更新, 通过这种方式增加这条航路上的信息素, 其表达式为
τab(t+m)=(1-ρ)τab(t)+ρΔ τab(11)
Δ τab=Q/J(12)
其中ρ为信息素挥发因子； J为这条航迹的性能指标； Q为性能指标对于信息素的更新的比例系数。
蚁群优化算法的优点是具有良好的并行性、 协作性和鲁棒性, 后期收敛速度快。缺点是前期搜索时间长, 参数多并且解的质量受参数影响大, 容易陷入局部最优解, 适用于三维全局航迹规划。由于信息素的分布情况、 挥发方式和蚂蚁选择前进方向的盲目性影响着解的质量和获得解的时间, 学者们也通常从这几个方面, 结合航迹规划的特性对蚁群算法进行改进。文献[28] 将蚂蚁按数量均匀分组, 并在信息素浓度更新过程中使用差分进化算法的交叉、 变异、 选择操作, 合理分配各路径上蚂蚁留下的信息素, 避免某条路径上信息素累积过多而导致陷入局部最优解, 从而引导蚂蚁找到最优路径。该混合算法在保证基本蚁群算法优点的同时提高了全局收敛的速度, 但得到的航迹过长。文献[29] 提出一种文化蚁群算法, 设计了由蚁群算法演化的群体空间和由群体空间最优解构成的信仰空间, 两个空间同时演化, 彼此促进。在群体空间中加入惩奖机制, 对到达终点的蚂蚁走过的路径, 提高其信息素浓度, 反之, 则降低, 从而提高了蚂蚁找到可行路径的概率。信仰空间利用选择、 交叉、 变异这3种遗传操作进行更新。此外, 文献在启发式函数中加入了航路点的方差, 计算待选节点和其前面n个点的方差, 使选出的节点与前面节点的波动相对较小, 从而获得更平滑的航迹。该方法的双层进化模型加快了航迹的搜索速度, 但惩奖机制的评判标准单一, 到达终点的蚂蚁走过的路径并不一定就好, 此机制可能会降低解的质量。文献[30] 首先限制信息素挥发因子的范围, 防止其过大或过小影响算法的全局搜索能力, 并在信息素调整规则中引入航迹评价指标, 提高解的质量。然后将起始点和目标点之间的连线这一最短航迹信息反馈到系统中作为搜索的指导信号, 将能见度改进为当前节点与待扩展节点的距离和待扩展节点到最短航线的垂直距离加权和的倒数, 降低算法寻找航迹的盲目性, 加快了搜索效率。最后在该能见度的基础上, 将转移概率与一个0～1之间的随机数相乘, 选择邻域中转移概率最大的节点扩展。该方法在保证基本蚁群算法优点的同时提高了解的质量, 大大缩短了搜索时间。
粒子群优化算法模拟鸟群飞行捕食行为, 把每个粒子看作优化问题的一个可行解, 并将其延伸到N维空间, 每个粒子主要通过跟踪两个位置决定自己下一步的飞行, 一个是粒子本身所找到的最优解Pbest, 即个体最好位置；另一个是种群中所有粒子当前找到的最优解Gbest, 即全局最好位置, 最终群体成员逐渐移入问题空间的更好区域。所有的粒子都有一个由被优化的函数决定的适应值, 每个粒子还有一个决定其飞行方向和距离的速度。粒子群算法的速度和位置更新方式分别为
vij(k+1)=ωvij(k)+c1r1(pij(k)-xij(k))+c2r2(gij(k)-xij(k))(13)
xij(k+1)=xij(k)+vij(k)(14)
其中下标i、j、k分别表示第i个粒子, 第j维空间, 第k代粒子； ω为惯性权重, 描述了粒子对之前速度的“继承”； c1、c2为常数, 称为学习因子, 体现了粒子向全局最优粒子学习的特性； r1、r2为(0,1)之间的随机数。
与其他进化算法相比, 粒子群算法具有两个显著的不同特点。一是没有“优胜劣汰”的机制, 所有的粒子在迭代过程中始终作为种群的成员保留；二是没有交叉、 变异等进化算子, 每个粒子通过追随当前搜索到的最优值寻找全局最优。粒子群算法的优点是具有较强的鲁棒性, 对种群大小敏感性不高, 参数少, 前期收敛速度快, 缺点是后期收敛速度慢, 容易早熟陷入局部最优解, 可用于三维全局航迹规划。在航迹规划中学者们对粒子群算法的改进也多是通过提高种群的多样性避免局部最优。文献[31] 在量子粒子群优化算法(QPSO：Quantum-behaved Particle Swarm Optimization)的基础上引入繁殖机制, 整个种群中粒子位置更新后不直接进入下一代, 而是以一定概率将粒子放入繁殖池, 种群中最优个体不参与繁殖操作, 以便保护其不被破坏。该方法与QPSO算法和PSO算法相比, 能找到更优的航迹, 但由于增加了繁殖机制, 每次迭代时间要比QPSO 算法多。文献[32] 在基本PSO算法中引入病毒种群, 以增强主群体粒子的多样性, 提高局部搜索能力, 解决基本PSO算法容易陷入局部最优、 收敛速度慢的问题。文献[33] 在PSO算法中引入潜在网格构造算子, 在整个种群中粒子位置更新后, 为每个粒子运用相应的算子, 以克服PSO算法易陷入局部最优和后期收敛速度慢的问题, 该方法能得到质量更好的航迹。
3 目前研究热点及发展趋势
3.1 现代智能算法的改进
航迹规划是一个NP-hard问题, 要得到最优航迹需要极大的计算量和内存需求, 这将要消耗大量的时间, 而实际应用往往要求航迹规划系统能快速响应, 远远超出规定时间得到的航迹即便再优也不具有任何意义。因此, 保证在规定时间内规划出可行且尽量接近理论最优航迹的规划方法更具有现实意义。而实现这一规划方法最有效的算法无疑是现代智能算法。由于遗传算法、 蚁群算法等常用现代智能算法应用时间长、 应用范围广, 针对算法自身缺陷的改进方法也已经较为完善。在航迹规划这一应用中, 学者们不应再仅仅针对算法本身的缺陷去改进, 而应该结合航迹规划的特性, 将研究重心放在如何提高算法在航迹规划应用中的搜索效率和搜索精度。例如改进初始化方法, 从而改善随机初始化方法造成的存储空间和搜索时间上的浪费；改进编码方式, 使得算法更容易处理无人机的各种角度约束, 缩减不必要的搜索空间。这样才能使改进后的算法更适用于航迹规划, 实现以更快的速度得到更优的航迹, 并实现航迹真正意义上的可飞。
3.2 多重算法的融合改进
在现有的航迹规划算法中, 每种算法都有自己的优缺点, 但由于航迹规划问题的复杂度高, 单一算法很难满足整个航迹规划的要求。例如A*算法全局性好, 但实时性差, 不适用于动态航迹规划；人工势场法实时性好, 但容易陷入局部极值, 不适用于全局航迹规划。因此在航迹规划算法的选取上, 很多学者都会针对不同的规划阶段选择不同的算法规划出满意的航迹。又或者是将两个或多个算法融合改进, 用一种算法的优点去弥补另一种算法的缺点, 从而使融合后的算法满足航迹规划的各项要求。但融合算法很可能增大计算量, 或是融合后的实际效果并不如理论效果好, 这就需要学者们在今后做进一步的研究, 以改善融合算法的性能。
3.3 多无人机四维航迹规划算法研究
随着无人机在军用和民用领域的广泛应用, 任务复杂度的提升, 单无人机的有效载荷和飞行能力有限, 一些复杂任务必须依靠多无人机协作才能完成, 并且多无人机协同执行任务具备更强的生存能力和更广的任务执行范围。多无人机在协同执行任务时, 不仅要在空间上飞抵指定的目标点, 还需要严格满足时间上的约束, 如同时到达, 按紧密/松散时间[34] 到达等, 这使四维航迹规划技术日益受到青睐, 且四维航迹规划较三维航迹规划具有更好的实时性。因此多无人机协同执行任务的四维航迹规划是今后无人机航迹规划技术发展的必然趋势, 而航迹规划算法作为技术的核心, 选取何种算法, 并针对四维多无人机协同航迹规划问题对算法进行改进是今后需要重点研究的内容。
4 结 语
在无人机航迹规划技术日益成熟的今天, 如何在现有技术的基础上不断改进完善, 扩大无人机的应用领域, 实现智能快速实时、 利于工程实现的高维空间航迹规划, 提高无人机的生存能力和完成任务的效率, 是广大学者们仍需要重点研究的问题。
参考文献：
[1] 郑昌文, 严平, 丁明跃, 等. 飞行器航迹规划研究现状与趋势 [J] . 宇航学报, 2007, 28(6): 7-12.
ZHENG Changwen, YAN Ping, DING Mingyue, et al. Research Status and Trend of Route Planning for Flying Vehicles [J] . Journal of Astronautics, 2007, 28(6): 7-12.
[2] 韩攀, 陈谋, 陈哨东, 等. 基于改进蚁群算法的无人机航迹规划 [J] . 吉林大学学报：信息科学版, 2013, 31(1): 66-72.
HAN Pan, CHEN Mou, CHEN Shaodong, et al. UAV Track Planning Based on Improved Ant Colony Algorithm [J] . Journal of Jilin University：Information Science Edition, 2013, 31(1): 66-72.
[3] 王维平, 刘娟. 无人飞行器航迹规划方法综述 [J] . 飞行力学, 2010, 28(2): 6-10.
WANG Weiping, LIU Juan. A Summary of UAV Track Planning Methods [J] . Flight Dynamics, 2010, 28(2): 6-10.
[4] 聂俊岚, 张庆杰, 王艳芬. 基于加权Voronoi图的无人飞行器航迹规划 [J] . 飞行力学, 2015, 33(4): 339-343.
NIE Junlan, ZHANG Qingjie, WANG Yanfen. Flight Path Planning of UAV Based on Weighted Voronoi Diagram [J] . Flight Dynamics, 2015, 33(4): 339-343.
[5] MEDEIROS F L L, SILVA J D S D. Computational Modeling for Automatic Path Planning Based on Evaluations of the Effects of Impacts of UAVs on the Ground [J] . Journal of Intelligent & Robotic Systems, 2011, 61(1): 181-202.
[6] YAN F, LIU Y S, XIAO J Z. Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method [J] . International Journal of Automation and Computing, 2013, 10(6): 525-533.
[7] 李世晓, 朱凡, 张健, 等. 改进A*算法的多约束航迹规划 [J] . 电光与控制, 2014, 21(7): 36-40.
LI Shixiao, ZHU Fan, ZHANG Jian, et al. Improved Multi-Constraint Track Planning for A* Algorithm [J] . Electro-Optics and Control, 2014, 21(7): 36-40.
[8] 程琪, 荆涛, 于志游. 利用三次样条改进蚁群算法的无人机航路规划 [J] . 计算机测量与控制, 2016, 24(8): 272-274.
CHENG Qi, JING Tao, YU Zhiyou. UAV Route Planning Using Cubic Spline Improved Ant Colony Algorithm [J] . Computer Measurement & Control, 2016, 24(8): 272-274.
[9] SAHINGOZ O K. Generation of Bezier Curve-Based Flyable Trajectories for Multi-UAV Systems with Parallel Genetic Algorithm [J] . Journal of Intelligent & Robotic Systems, 2014, 74(1/2): 499-511.
[10] HUANG L, QU H, JI P, et al. A Novel Coordinated Path Planning Method Using K-Degree Smoothing for Multi-UAVs [J] . Applied Soft Computing, 2016, 48: 182-192.
[11] 胡中华, 赵敏, 姚敏, 等. 无人机航迹规划技术研究及发展趋势 [J] . 航空电子技术, 2009, 40(2): 24-29.
HU Zhonghua, ZHAO Min, YAO Min, et al. Research and Development Trend of UAV Track Planning Technology [J] . Avionics Technology, 2009, 40(2): 24-29.
[12] DONG S, ZHU X, LONG G. Cooperative Planning Method For Swarm UAVs Based on Hierarchical Strategy [C] ∥International Conference on System Science, Engineering Design and Manufacturing Informatization. Pacific Grove, CA, USA: IEEE, 2012: 304-307.
[13] MAINI P, SUJIT P B. Path Planning for a UAV with Kinematic Constraints in the Presence of Polygonal Obstacles [C] ∥International Conference on Unmanned Aircraft Systems. Arlington, VA, USA: IEEE, 2016: 62-67.
[14] QU Y, ZHANG Y, ZHANG Y. Optimal Flight Path Planning for UAVs in 3-D Threat Environment [C] ∥International Conference on Unmanned Aircraft Systems. Orlando, FL, USA: IEEE, 2014: 149-155.
[15] CHEN X, ZHANG J. The Three-Dimension Path Planning of UAV Based on Improved Artificial Potential Field in Dynamic Environment [C] ∥International Conference on Intelligent Human-Machine Systems and Cybernetics. Tlemcen, Algeria: IEEE, 2013: 144-147.
[16] 王强, 张安, 吴忠杰. 改进人工势场法与模拟退火算法的无人机航路规划 [J] . 火力与指挥控制, 2014(8): 70-73.
WANG Qiang, ZHANG An, WU Zhongjie. UAV Route Planning Based on Improved Artificial Potential Field Method and Simulated Annealing Algorithm [J] . Fire Control & Command Control, 2014(8): 70-73.
[17] 姚远, 周兴社, 张凯龙, 等. 基于稀疏A*搜索和改进人工势场的无人机动态航迹规划 [J] . 控制理论与应用, 2010, 27(7): 953-959.
YAO Yuan, ZHOU Xingshe, ZHANG Kailong, et al. Dynamic Path Planning of Unmanned Aerial Vehicles Based on Sparse A* Search and Improved Artificial Potential Fields [J] . Control Theory and Applications, 2010, 27(7): 953-959.
[18] 王伟, 王华. 基于约束人工势场法的弹载飞行器实时避障航迹规划 [J] . 航空动力学报, 2014, 29(7): 1738-1743.
WANG Wei, WANG Hua. Real-Time Obstacle Avoidance Path Planning of Missile-Borne Vehicle Based on Constrained Artificial Potential Field Method [J] . Journal of Aerospace Power, 2014, 29(7): 1738-1743.
[19] 罗冠辰, 于剑桥, 张思宇, 等. 穿越恶劣天气区域的无人机航迹规划 [J] . 北京理工大学学报, 2014, 34(10): 1054-1059.
LUO Guanchen, YU Jianqiao, ZHANG Siyu, et al. Drone Path Planning through Bad Weather Areas [J] . Transaction of Beijing Institute of Technology, 2014, 34(10): 1054-1059.
[20] BEHNCK L P, DOERING D, PEREIRA C E, et al. A Modified Simulated Annealing Algorithm for SUAVs Path Planning [J] . IFAC Papersonline, 2015, 48(10): 63-68.
[21] 邱福生, 杨建平, 邵绪威. 基于遗传模拟退火算法的无人机航迹规划 [J] . 沈阳航空航天大学学报, 2014, 31(1): 16-19.
QIU Fusheng, YANG Jianping, SHAO Xuwei. Flight Path Planning of UAV Based on Genetic Simulated Annealing Algorithm [J] . Journal of Shenyang Institute of Aeronautical Engineering, 2014, 31(1): 16-19.
[22] 占伟伟, 王伟, 陈能成, 等. 一种利用改进A*算法的无人机航迹规划 [J] . 武汉大学学报：信息科学版, 2015, 40(3): 315-320.
ZHAN Weiwei, WANG Wei, CHEN Nengcheng, et al. UAV Track Planning Using Improved A* Algorithm [J] . Geomatics and Information Science of Wuhan University, 2015, 40(3): 315-320.
[23] 杨润洲, 丁勇, 张承果. 基于DTW的改进A*算法在航迹规划中的应用 [J] . 电光与控制, 2016, 23(6): 5-10.
YANG Runzhou, DING Yong, ZHANG Chengguo. Application of Improved A* Algorithm Based on DTW in Track Planning [J] . Electro-optics and Control, 2016, 23(6): 5-10.
[24] 鱼佳欣, 李刚, 李东涛, 等. 改进量子遗传算法在无人机航迹规划中的应用 [J] . 计算机仿真, 2015, 32(5): 106-109.
YU Jiaxin, LI Gang, LI Dongtao, et al. Application of Improved Quantum Genetic Algorithm in UAV Flight Path Planning [J] . Computer Simulation, 2015, 32(5): 106-109.
[25] HAMED S, MOJTABA V, BABAK I, et al. Optimal Cooperative Path Planning of Unmanned Aerial Vehicles by a Parallel Genetic Algorithm [J] . Robotica, 2016, 34(4): 823-836.
[26] 俞琪, 刘新, 周成平, 等. 基于病毒遗传算法的快速航迹规划方法 [J] . 宇航学报, 2011, 32(4): 756-761.
YU Qi, LIU Xin, ZHOU Chengping, et al. Fast Track Planning Method Based on Virus Genetic Algorithm [J] . Journal of Astronautics, 2011, 32(4): 756-761.
[27] PEHLIVANOGLU Y V. A New Vibrational Genetic Algorithm Enhanced with a Voronoi Diagram for Path Planning of Autonomous UAV [J] . Aerospace Science & Technology, 2012, 16(1): 47-55.
[28] DUAN H, YU Y, ZHANG X, et al. Three-Dimension Path Planning for UCAV Using Hybrid Meta-Heuristic ACO-DE Algorithm [J] . Simulation Modelling Practice & Theory, 2010, 18(8): 1104-1115.
[29] 刘振峰, 谢洪森, 危水根. 基于文化蚁群算法的三维飞行器航路规划 [J] . 计算机仿真, 2013, 30(5): 99-103.
LIU Zhenfeng, XIE Hongsen, WEI Shuigen. Route Planning of 3D Aircraft Based on Cultural Ant Colony Algorithm [J] . Computer Simulation, 2013, 30(5): 99-103.
[30] TAO J, WANG Y, YANG H, et al. Three-Dimensional Path Planning of Unmanned Aerial Vehicle under Complicated Environment [C] ∥Control and Decision Conference. Big Sky, MT, USA: IEEE, 2016: 6377-6382.
[31] 傅阳光, 周成平, 丁明跃. 基于混合量子粒子群优化算法的三维航迹规划 [J] . 宇航学报, 2010, 31(12): 2657-2664.
FU Yangguang, ZHOU Chengping, DING Mingyue. Three-Dimensional Path Planning Based on Hybrid Quantum Particle Swarm Optimization Algorithm [J] . Journal of Astronautics, 2010, 31(12): 2657-2664.
[32] 吴天爱, 吴云玉, 别晓峰. 采用病毒粒子群优化算法的飞行器航迹规划 [J] . 电光与控制, 2014, 21(8): 102-105.
WU Tianai, WU Yunyu, BIE Xiaofeng. Aircraft Path Planning Using Virus Particle Swarm Optimization Algorithm [J] . Electro-optics and Control, 2014, 21(8): 102-105.
[33] LIU Y, ZHAN G X, GUAN X, et al. Potential Odor Intensity Grid Based UAV Path Planning Algorithm with Particle Swarm Optimization Approach [J] . Mathematical Problems in Engineering, 2016, 2016(2): 1-16.
[34] 杨祖强. 生物启发的多无人机协同四维航迹规划方法研究 [D] . 杭州: 浙江大学航空航天学院, 2016.
YANG Zuqiang. Bio-inspired 4D Trajectory Generation for Multi-UAV Cooperation [D] . Hangzhou: School of Aeronautics and Astronautics, Zhejiang University, 2016.
Overview of Common Algorithms for UAV Path Planning
WANG Qiong1a,1b, LIU Meiwan1a,1b, REN Weijian1a,1b, WANG Tianren2
(1a. School of Electrical Information and Engineering; 1b. Heilongjiang Provincial Key Laboratory of Networking and Intelligent Control, Northeast Petroleum University, Daqing 163318, China; 2. Sinopec Star (Beijing) New Energy Research Institute Company Limited, Sinopec Star Petroleum Company, Beijing 100083, China)
Abstract: In order to promote the development of path planning technology, the planning ideas and forms of path planning are analyzed. The path planning algorithms are divided into the traditional classical algorithms and modern intelligent algorithms in two categories, and some commonly used algorithms are analyzed and summarized. And the current research hotspots and future development trends are pointed out from the three aspects of improving the application of modern intelligent algorithms in path planning, amalgamation of multiple algorithms and the research of four-dimensional path planning algorithms for multiple UAVs.
Key words: unmanned aerial vehicle (UAV); path planning; review; traditional classical algorithms; modern intelligent algorithms
中图分类号： TP39
文献标识码：A
收稿日期： 2018-04-17
基金项目： 国家自然科学基金优秀青年科学基金资助项目(61422301)
作者简介： 王琼(1969— ), 女, 黑龙江大庆人, 东北石油大学教授, 博士研究生, 主要从事智能控制理论、 人工智能算法研究, (Tel)86-13836955000(E-mail)[email protected]；