无人机航迹规划常用算法综述
来源:尖兵之翼
|
作者: 王 琼 刘美万 任伟建 王天任
|
发布时间: 1883天前
|
56406 次浏览
|
🔊 点击朗读正文
❚❚
▶
|
分享到:
为促进航迹规划技术的发展, 对航迹规划常用算法进行综述。首先对航迹规划的规划思想和构成进行分析；其次将航迹规划算法分为传统经典算法和现代智能算法两大类, .....
遗传算法的基本思想是模拟生物遗传进化过程, 根据“适者生存”、 “优胜劣汰”的原则, 借助选择、 交叉、 变异等操作, 使所要解决的问题从初始解一步步逼近最优解。在航迹规划中, 遗传算法每条染色体(个体)代表无人机的一条航迹, 基因的编码方式也就是航迹节点的编码方式, 适应度函数由代价函数变化而来。遗传算法的优点是不要求优化函数具备连续、 可导和单峰等条件, 具有较强的鲁棒性, 是一种高效、 并行、 全局的搜索方法, 适用于三维全局航迹规划。缺点是种群失去多样性而导致早熟收敛, 寻优时间长, 局部搜索能力差等。针对该问题, 学者们提出了不同的改进方法, 如引入量子、 自适应等因子, 但这些改进方法仍然存在较多不足。文献[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问题, 要得到最优航迹需要极大的计算量和内存需求, 这将要消耗大量的时间, 而实际应用往往要求航迹规划系统能快速响应, 远远超出规定时间得到的航迹即便再优也不具有任何意义。因此, 保证在规定时间内规划出可行且尽量接近理论最优航迹的规划方法更具有现实意义。而实现这一规划方法最有效的算法无疑是现代智能算法。由于遗传算法、 蚁群算法等常用现代智能算法应用时间长、 应用范围广, 针对算法自身缺陷的改进方法也已经较为完善。在航迹规划这一应用中, 学者们不应再仅仅针对算法本身的缺陷去改进, 而应该结合航迹规划的特性, 将研究重心放在如何提高算法在航迹规划应用中的搜索效率和搜索精度。例如改进初始化方法, 从而改善随机初始化方法造成的存储空间和搜索时间上的浪费；改进编码方式, 使得算法更容易处理无人机的各种角度约束, 缩减不必要的搜索空间。这样才能使改进后的算法更适用于航迹规划, 实现以更快的速度得到更优的航迹, 并实现航迹真正意义上的可飞。
