欧洲冠军联赛四强

行业新闻

无人机航迹规划常用算法综述

(JIESHANGPIAN)

       人工势场法的优点是算法简明、 实时性好、 规划速度快, 在局部规划和实时规划领域应用广泛。缺点是当无人机离目标点比较远, 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的概率为

       其中τ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 结 语

     在无人机航迹规划技术日益成熟的今天, 如何在现有技术的基础上不断改进完善, 扩大无人机的应用领域, 实现智能快速实时、 利于工程实现的高维空间航迹规划, 提高无人机的生存能力和完成任务的效率, 是广大学者们仍需要重点研究的问题。


导航栏目



联系我们

LIANXIREN:CHENXIANSHENG

YOU XIANG:cj@swtjb.net.cn

GONG SI:ZHONGKEHUIJUKEJIYOUXIANGONGSI

DI ZHI:BEIJINGXICHENGQUPUTAOYUAN1HAOPANGUZHIKU1LOU


用手机扫描二维码关闭
二维码