无人机航迹规划常用算法综述
来源:尖兵之翼
|
作者: 王 琼 刘美万 任伟建 王天任
|
发布时间: 2021-03-10
|
39554 次浏览
|
分享到:
为促进航迹规划技术的发展, 对航迹规划常用算法进行综述。首先对航迹规划的规划思想和构成进行分析；其次将航迹规划算法分为传统经典算法和现代智能算法两大类, .....
无人机航迹规划一般由以下几个部分组成：描述规划空间, 选择航迹的表示形式, 分析约束条件, 确定代价函数, 选取航迹搜索算法和航迹平滑。无人机航迹规划一般由以下几个部分组成：描述规划空间, 选择航迹的表示形式, 分析约束条件, 确定代价函数, 选取航迹搜索算法和航迹平滑。其中下标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] 到达等, 这使四维航迹规划技术日益受到青睐, 且四维航迹规划较三维航迹规划具有更好的实时性。因此多无人机协同执行任务的四维航迹规划是今后无人机航迹规划技术发展的必然趋势, 而航迹规划算法作为技术的核心, 选取何种算法, 并针对四维多无人机协同航迹规划问题对算法进行改进是今后需要重点研究的内容。
