2022, Vol. 37
近年来, 无人机(unmanned aerial vehicle, UAV)由于其灵活度高、机动性强、安全风险系数小、成本低等特点, 被广泛应用于搜索巡逻[1]、侦察监视[2]、抢险救灾[3]、物流配送[4]、电力巡检[5]、农业灌溉[6]等军用或民用任务. 与单架无人机相比, 多无人机协同工作具有鲁棒性好、容错性高等独特优势, 不仅能够完成单架无人机无法完成的复杂任务, 而且在部分无人机出现故障时, 只需重新规划剩余无人机即可继续执行任务, 从而达到优化任务执行效果和提高系统可靠性的目的.
路径规划是无人机执行任务的关键, 也是自主无人机在工程应用上的主要挑战, 吸引了国内外学者的广泛关注[7]. 现有的无人机路径规划算法主要分为经典算法和元启发式算法. 经典算法包括: 基于搜索的算法, 如
目前, 针对多无人机路径规划启发式算法的研究综述相对较少. 文献[20]从无人机群协同路径规划任务、环境和问题框架出发, 对相关研究进行分类、回顾与统计. 文献[21]总结了无人机群路径规划模型, 并归纳了相关智能优化算法. 但上述研究均没有从无人机协同关系的角度对目前相关研究成果进行总结归纳.
本文综述了近年来多无人机协同路径规划的研究成果. 主要工作如下: 1)对当前多无人机路径规划研究中的关键要素提出一种新颖的分类方式. 首先将所研究的问题根据其任务性质分为多旅行商(multiple travelling salesman problem, MTSP)问题、搜索问题、覆盖问题、避障及轨迹优化问题、其他问题; 其次, 针对所研究的环境维度和确定性对研究成果中的环境模型进行分类; 最后, 通过梳理和分析多无人机路径规划研究现状, 从模型层面和算法层面分析无人机间的协同关系. 2)对广泛应用于多无人机路径规划的元启发式算法从改进方式上进行分类梳理, 并讨论了各算法的应用效果、优势及缺陷. 另外, 结合上述分类方式及研究特点以表格的形式对当前研究成果进行归纳汇总, 协助读者快速、有针对性地获取该研究领域的相关信息. 3)结合当前多无人机路径规划研究的局限性, 从协同性、异构性、可扩展性、动态适应性、应用性5方面对存在的研究问题进行分析, 并展望了多无人机路径规划的未来发展趋势. 本文结构如图 1所示.
|
图 1 多无人机路径规划结构 |
通过梳理近年来多无人机路径规划研究, 本文从研究特点和规划要素角度对这些研究进行分类归纳, 并在第2节以表格形式给出分类结果. 本节的目的是介绍分类方式的同时结合规划要素分析目前的发展现状, 具体地, 本节将阐述多无人机路径规划研究的3方面关键要素, 分别为问题类型、环境模型、协同关系.
1.1 问题类型综合国内外研究发现, 多无人机协同路径规划问题可分为MTSP问题、搜索问题、覆盖问题、避障及轨迹优化问题与其他问题5大类. 具体分类方式定义如下.
1) MTSP问题.
在多无人机路径规划研究中, MTSP问题是最常见的问题模型. 建模时通常在地图中给定一系列目标点, 多个无人机共同去访问目标点, 由此求解无人机遍历所有目标点且最终返回起始点的最优路径.
2) 搜索问题.
无人机需要去访问的各目标位置事先未知, 需要通过建立概率图等方式搜索发现目标点位置, 并规划出一条到达目标位置的最优路径.
3) 覆盖问题.
当无人机执行搜救、侦察等任务时, 多架无人机需以最小代价高效覆盖整个任务区域, 规划出遍历任务区域的多无人机最优飞行路径. 需要注意的是, 文献[20-23]中将MTSP问题也称为覆盖问题, 为了方便分类, 本文将需要遍历已知目标点的覆盖问题归类为MTSP问题.
4) 避障及轨迹优化问题.
在含障碍物的环境中, 对多无人机从起始点到目标点的航迹进行规划, 并考虑无人机的动力学模型对航迹进行优化处理, 使规划结果更高程度上满足实机飞行的要求, 从而提高规划算法的可行性.
5) 其他问题.
一些多无人机路径规划研究[24-26]中的问题模型不符合上述各种类别, 本文将其归类于“其他问题”.
1.2 环境模型本文从维度、不确定性、应用3个角度对多无人机路径规划研究的环境模型进行分类和总结.
在多无人机路径规划中, 确定规划空间的维度是环境建模的关键. 任务简单、环境复杂度低的路径规划研究常采用2D环境模型, 假设无人机保持飞行高度不变或人为控制飞行高度, 规划时仅考虑无人机在某一平面的飞行. 此外, 在真实环境中存在相当多的结构约束和不确定性, 飞行任务也日益复杂化, 如森林救火、管道检修、电力巡检等. 为了满足飞行任务的要求, 越来越多的学者针对3D多无人机路径规划进行研究.
从不确定性角度出发, 环境可分为确定性环境和不确定性环境: 确定性环境指, 在规划之前障碍物大小、形状和位置精确已知, 且障碍物及其他环境因素不再发生未知的动态改变的环境; 不确定性环境指, 在规划系统中障碍物及其他环境因素未知或部分未知、障碍物突然出现或移动、环境中存在动态扰动等情况.
多无人机路径规划在军用和民用环境中均有广泛应用. 在军用领域, 多架无人机在作战要求、战场环境任务载荷等约束下, 通过相互配合规划出适宜的飞行路线. 近年来, 无人机应用从军用领域快速扩展到民用领域, 特别地, 小型多旋翼无人机在多样化的民用任务中取得了优良的应用效果, 如建筑检测、农业灌溉、航拍等. 多无人机路径规划的研究对提高任务执行效率和优化任务效果至关重要.
1.3 协同关系多无人机协同执行任务时, 需要各无人机相互配合、约束, 针对不同的研究问题和任务复杂度, 无人机相互配合方式和协同程度不一.根据目前多无人机路径规划研究成果分析, 无人机之间的协同关系在模型层面和算法层面均有体现, 具体如下.
1.3.1 模型层面无人机路径规划的目的是在满足约束条件下, 找到满足任务需求或某种性能指标的最优飞行路径. 多无人机路径规划需要在单无人机路径规划模型基础上, 进一步考虑无人机的任务分配、无人机间复杂的约束条件、共同的优化目标, 下面是基于这3方面的无人机协同关系介绍.
1) 任务分配.
路径规划是多无人机执行任务的关键, 一些研究将路径规划建立在明确的任务需求上, 如多无人机协同侦察、数据收集等. 为了提高任务执行效率, 在路径规划前, 总任务被分为若干个子任务分配给相应的无人机, 无人机通过执行各自的任务实现总任务目标, 一定程度上体现了多无人机之间的协同关系. 例如, 文献[22]针对多无人机对地面区域最小时间覆盖的问题, 先对区域进行划分, 在每个分区分配一架无人机; 再用并行遗传算法对每个分区的覆盖问题进行求解, 将多无人机路径规划问题转换为单无人机路径规划问题. 在该方法中, 无人机的协同关系仅体现于分配阶段, 协同程度较弱.
2) 约束条件.
无人机路径规划的约束通常包括飞行速度、飞行高度等自身的飞行性能约束以及地形、气象等环境因素约束. 相比于单无人机路径规划, 多无人机路径规划需要考虑更多的约束, 如多无人机之间的避碰约束、任务耦合约束、通信距离约束等. 一些研究通过增加无人机之间协同要求的约束条件来提高多无人机间的协同性和协同路径规划的可行性, 例如, 文献[27]在多无人机协同搜索攻击任务中, 除了对无人机进行任务规划外, 还考虑了无人机间的避碰约束.
3) 优化目标.
无人机路径规划对不同的优化目标具有不同的任务需求, 一般包括最小飞行时间、飞行距离、威胁代价、最大覆盖面等. 在大多数研究中, 多无人机路径规划的优化目标也体现一定的协同性, 如最小总飞行时间、最短总飞行距离、最小能耗、协同最优覆盖等. 研究人员通过构造代价函数形成优化目标, 结合约束条件建立多无人机协同路径规划模型, 然后采用规划算法对模型进行求解. 例如, 文献[28]以最小化所有无人机能量消耗之和为优化目标来求解多无人机路径规划问题.
1.3.2 算法层面针对无人机间的协同, 一些协同算法被应用于多无人机路径规划问题中, 如协同共进化遗传算法[29]、分布式协同粒子群算法[30]等, 这类算法将多无人机路径规划问题分解为若干组单无人机路径规划问题, 分组进行了优化, 且各组之间存在协同合作, 共同求解整个优化问题. 文献[31]针对多无人机传感器布局问题, 提出了一种基于协同共进化遗传算法的路径规划方法, 在算法中将每个无人机作为物种, 每种解决方案作为物种中的个体, 个体适应度由该解决方案与此刻其他物种中个体的性能表现来决定, 该研究通过协同进化算法实现无人机间的协同. 此外, 一些研究为了实现或提高无人机的协同性, 对现有的路径规划算法进行了改进, 如文献[32]在遗传算法中加入抗体元素, 通过在各无人机之间交换抗体信息排除无人机相互碰撞的路径. 文献[33]将免疫算法的相似性度量引入蚁群算法中以减少无人机的航迹重复率.
当前, 多无人机路径规划研究的协同关系主要表现于上述一方面或几方面的结合, 具体归纳见第2小节表格.
2 元启发式算法本节从改进方式上对近年来应用于多无人机路径规划问题的启发式算法进行综述, 并采用第1节的分类方式, 从多方面、多维度归纳相关研究的特点.
2.1 遗传算法遗传算法(genetic algorithm, GA)[34]是一种利用生物学、遗传学、进化学概念而提出的启发式随机搜索算法, 具有较强的自学习性、自适应性、全局搜索性和可扩展性, 已成为求解复杂组合优化问题的有力工具.
近年来, 遗传算法被广泛应用于多无人机路径规划问题中. 文献[35]在多无人机覆盖问题的局部规划阶段, 采用遗传算法获得多目标整数规划模型的最优解. 文献[28]提出一种以所有可能路径为种群的遗传算法, 通过减少无人机旋转次数来降低能耗.
遗传算法存在一些缺陷, 例如容易过早收敛、计算效率低等. 为了提高遗传算法在多无人机路径规划中的应用性能, 研究者对算法进行了改进, 并通过仿真实验验证了相应算法的性能. 本文根据算法的改进特点将改进方式分类为3方面: 在遗传算法各进化阶段上的改进、遗传算法与其他算法结合、协同共进化遗传算法的应用及改进. 表 1为基于遗传算法的多无人机路径规划研究对比.
|
表 1 基于遗传算法的多无人机路径规划研究对比 |
1) 在遗传算法各进化阶段上的改进.
遗传算法的求解过程包括染色体编码和种群初始化、计算适应度、基于适应度函数选择、交叉和变异等基本阶段.
在染色体编码阶段的改进. 文献[24]针对多基地多无人机协同侦察路径规划问题, 以目标、基地、无人机序号、任务、航向角为基因改进传统的遗传算法, 该算法对于侦察问题具有很强的实用价值, 但过多的约束条件和动态环境导致结果存在一定误差, 且提出的模型对于新动态因子不具有足够的适应性.
在计算适应度及选择阶段的改进. 文献[25]针对多无人机复杂的任务规划问题, 在所提出的多目标遗传算法中设计了一个混合适应度函数来寻找最优解. 文献[36]在多基地多无人机协同侦察路径规划问题中提出了一种周期性快速搜索遗传算法(periodic fast search genetic algorithm, PFSGA), 模仿自然界周期性往复“进化-退化”特点, 并将传统遗传算法中的选择算子改进设计为最优逆转序列算子和最优插入点算子, 使种群适应度增加或不变. 该算法收敛速度快、精度高、易于求得模型的最优解.
在交叉和变异阶段的改进. 文献[37]研究了无障碍物环境下无人机群对地面多目标进行监视的路径规划问题, 将基于近似梯度的局部搜索策略集成到遗传算法中, 设计交叉算子以产生后代, 构造了一种模因算法来生成高质量的Dubins路径. 该算法能以较低的计算成本找到高质量的解, 且易于扩展到多架无人机和多组目标场景. 文献[38]提出了应用遗传算法及两个新变异算子来解决三维环境下无人机路径规划问题, 收集信息量最大化的同时避免了无人机进入禁飞区域. 此外, 该算法利用模式搜索方法和求解MTSP问题生成一个智能播种的初始种群, 增加了算法整体达到全局最优解的概率. 文献[22]首先使用
2) 协同共进化遗传算法的应用及改进.
针对多无人机间的协同工作, 一些研究者对遗传算法进行了研究和改进. 文献[29]采用合作型协同进化遗传算法进行多无人机协同搜索路径规划, 基于滚动优化思想实现实时生成局部最优路径的功能, 该算法比一般遗传算法具有更高的搜索效能. 为了提高规划效率, 文献[31]对协同共进化遗传算法进行了改进: 针对任务执行时无人机数量增加或减少的需求, 提出了物种数量进化(物种的死亡和出生)的思想. 改进后的算法能有效地应用于多无人机传感器布局任务, 但在动态环境中, 难以实时自主跟随环境变化.
3) 遗传算法与其他算法结合.
一些研究者将遗传算法与其他算法相结合以获得更好的优化效果. 文献[42]在多架无人机协同装配任务的离线路径规划问题中, 将中心力优化算法(central force optimization, CFO)与遗传算法相结合, 提出了一种新型并行智能优化算法——中心力优化-遗传算法. 该算法引入并行计算思想, 提高算法对多智能体问题的计算效率, 加快了算法收敛速度. 文献[32]在遗传算法中引入启发式免疫算子, 提出了一种免疫遗传算法, 使其能够产生并保存优秀的抗体, 获得无人机的协同飞行搜索路径, 提高无人机在不确定环境下的搜索效率. 文献[41]提出了一种由遗传算法训练的深度学习算法(deep learning trained by genetic algorithm, DL-GA)用于多无人机数据采集, 解决了能量浪费和无人机数量问题. 该算法收敛速度快, 适用于复杂的优化问题.
2.2 蚁群算法蚁群优化算法(ant colony optimization, ACO)[43]是受蚁群觅食行为的启发而提出来的一种元启发式算法. 蚂蚁在路线上沉积一种叫信息素的物质, 其他蚂蚁感知信息素, 并倾向于寻找信息素浓度最高的路径, 因此, 蚂蚁能够以一种非常有效的方式找到巢穴和食物之间的最短路径. 蚁群优化算法具有信息正反馈、并行性高、优化能力强等优点, 通常用来解决大而复杂的组合优化问题.
近年来, 很多学者基于蚁群优化算法对多无人机的协同路径规划问题进行研究, 并从多个方面改进蚁群优化算法. 本文从信息素改进、分布式蚁群算法研究与改进、不确定性环境下的应用与改进、蚁群算法与其他算法结合4个方面对相关研究成果进行分析讨论. 表 2为基于蚁群算法的多无人机路径规划研究对比, 这些研究中算法的可行性均通过仿真实验得到验证.
|
|
表 2 基于蚁群算法的多无人机路径规划研究对比 |
1) 信息素改进.
信息素的编码方式和更新机制是蚁群算法的关键部分. 文献[49]针对多威胁源的复杂环境, 在多无人机初始路径规划阶段采用一种改进的蚁群优化算法, 该算法采用混合信息素更新方法, 限制了第一代最短路径信息素的更新, 从而降低陷入局部最优的概率, 加快了收敛速度, 但在动态和不确定性环境中存在一定的局限性. 文献[45]提出了一种基于蚁群优化来确定多无人机最小时间搜索路径的方法(minimum time search-ant colony optimization, MTS-ACO), 该方法提出了MTS-ACO的两种不同信息素表编码, 并设计出一种最小时间搜索启发式函数, 使蚁群优化算法在最初阶段生成高质量的解, 加速算法的收敛. 与其他算法相比, MTS-ACO方法能在更短的计算时间内获得更好或类似的解决方案. 但该方法只适用于沿直线段轨迹飞行的无人机, 且只对时间进行了优化, 忽略了其他优化目标. 文献[48]考虑到蚁群算法依赖信息素引导获得最优路径在密集目标群情况下的局限性, 引入一种双向简化搜索策略来生成区域访问顺序, 减小无人机的时间消耗.
2) 分布式蚁群算法研究与改进.
考虑到多无人机路径规划任务中单个无人机的自主性, 很多学者对分布式蚁群算法进行了研究. 文献[44]提出了一种高效的并行多蚁群算法, 通过并行计算平台CUDA来解决多无人机路径规划问题, 该算法中每只蚂蚁作为独立的个体执行任务, 没有中央控制机制, 蚁群之间共享信息素, 使得收敛结果更优. 算法实现复杂度低, 计算结果分配到多个集群中, 集群之间相互协作, 从而更好地解决多无人机路径规划问题. 文献[27]基于改进的分布式蚁群算法和Dubins曲线设计, 提出了一种智能自组织算法(intelligent self-organized algorithm, ISOA)以解决多无人机协同搜索攻击任务规划问题, 其中分布式蚁群算法用来生成航路点, 使每一架无人机都有自主优化决策的能力. 在算法中设计了一种新的状态转换规则, 使得状态转换不仅要考虑信息素浓度和启发式函数, 而且要考虑无人机的距离约束, 从而确保无人机能够在最大范围内返回初始点或特定目的地. 该算法采用自下而上的策略, 具有高实时性、可靠性和灵活性, 但在实际应用中可能会受到有效载荷约束的限制.
3) 不确定性环境下的应用与改进.
一些研究者针对蚁群优化算法在不确定性环境中的应用进行了改进. 文献[46]针对最小时间搜索(minimum time search, MTS)任务提出了一种基于实时编码域蚁群算法(ant colony optimization for real-coded domains, ACO
4) 蚁群算法与其他算法结合.
由于多无人机路径规划问题的复杂性, 蚁群优化算法通常与其他算法相结合来提高解的质量. 文献[51]用改进的蚁群算法优化多无人机的路径, 结合匈牙利算法对无人机编队进行多条件多参数下的协同任务分配. 所提出的蚁群算法将局部更新与全局动态更新相结合, 改进了信息素更新方法, 加快了收敛速度, 使迭代曲线更加稳定. 文献[33]针对山地地形中多无人机检测任务路径规划问题, 以最大覆盖率和最短任务时间为优化目标, 提出了改进的多种族蚁群算法, 同时引入免疫算法的相似性度量, 并结合协同进化算法的一些特点, 降低了无人机之间的航迹重复性, 该算法在个体覆盖率、总覆盖率和飞行时间上具有明显优势. 文献[50]在多无人机协同路径规划问题上, 针对高峰和山脉等动态环境, 提出了一种基于最大最小蚁群优化算法(maximum-minimum ant colony optimization, MMACO)和差分进化(differential evolution, DE)的元启发优化算法, 该算法解决了ACO和MMACO在信息过剩与全局优化之间的矛盾, 提高了系统鲁棒性, 加快了算法收敛速度. 另外, 文献[52]针对强风和龙卷风的动态环境, 又提出一种基于MMACO和柯西突变算子(Cauchy mutant, CM)的混合生物启发算法, 该算法比MMACO收敛速度快, 不易陷入局部最优, 鲁棒性强, 能够消除噪声和干扰, 在获得更优路径的同时, 避免了多个无人机之间的碰撞. 文献[23]在覆盖目标点路径规划问题中, 将蚁群算法与贪心策略相结合, 利用两层算法优化无人机的数量和任务时间.
2.3 粒子群算法粒子群算法(particle swarm optimization algorithm, PSO)[53-54]模拟鸟类个体(粒子)在多维搜索空间中的社会行为. 其中每个粒子代表一个点, 粒子通过适应度函数来评估位置, 并且与局部邻近的粒子共享最佳位置的信息, 同时使用这些信息来更新速度和位置, 通过迭代得到全局最优解. 粒子群算法被广泛应用于非线性、不可微、多峰值问题的优化过程.
近年来, 研究者多将粒子群算法应用于多无人机路径规划上. 文献[26]针对动态环境中的避碰问题提出了一种基于粒子群优化算法的多智能体系统路径规划算法, 在较快的计算速度下得到了高质量的解决方案. 传感器收集的信息在所有智能体之间共享, 每个智能体都有其他智能体的位置信息, 从而实现协同任务分配和路径规划. 文献[55]针对多无人机编队控制、目标跟踪、避碰避障前提下的路径规划问题, 提出了一种基于粒子群算法的分布式在线轨迹生成策略, 并在一台四旋翼飞行器上评估了轨迹生成算法的鲁棒性. 该策略适用于大型搜索区域, 鲁棒性强, 只依赖于轨迹生成部分, 不依赖于模型或无人机控制律, 具有较好的泛用性和实用性. 文献[56]研究了多无人机协同森林灭火任务分配与路径规划问题, 采用拍卖算法为每架无人机分配火点后, 使用粒子群优化算法及控制集成化与时间离散化算法(control parametrization and time discretization, CPTD), 在控制输入约束和碰撞约束下优化无人机到指定火点的路径. 文献[57]针对无人机编队重构情况下的路径规划问题, 提出了一种基于Dubins轨迹和粒子群优化算法的方法, 并通过仿真和固定翼飞行器飞行实验进行验证. 实验表明, 该方法能够及时生成无人机的可行路径, 保证了编队重构的快速性和有效性, 并对不同队形具有通用性, 实现了一致问题和高维问题的有效解决.
传统的粒子群算法存在精度较低、容易陷入局部最优等缺陷. 为了提高算法性能, 优化多无人机协同路径规划性能, 研究人员在不同层面上对粒子群算法进行了改进, 本文从分布式粒子群算法研究与改进、粒子群算法与其他算法结合、粒子群算法各步骤的综合改进3方面对此展开分析. 表 3为基于粒子群算法的多无人机路径规划研究对比, 这些研究中算法的可行性均通过仿真实验得到验证.
|
|
表 3 基于粒子群算法的多无人机路径规划研究对比 |
1) 粒子群算法计算阶段的改进.
粒子群算法的几个关键计算阶段有: 初始化粒子位置、计算目标函数、粒子位置与速度更新、满足终止条件跳出循环. 一些研究者针对多个计算阶段对粒子群算法进行了改进. 文献[30]针对无人机编队三维路径规划问题, 对粒子群优化算法进行了综合改进, 包括改进粒子初始分布、根据评估自适应调整参数以及用期望粒子代替不期望粒子的变异策略, 从而提高了收敛速度和解的最优性. 文献[62]研究复杂环境下多无人机集群执行任务时无人机的避碰问题, 针对粒子群优化算法过早收敛导致结果陷入局部极小值的缺陷, 提出了一种改进的粒子群算法. 该算法使用混沌逻辑映射初始化粒子, 发展了一种自适应突变策略来平衡局部与全局搜索, 通过用新的粒子替换不活跃的粒子将解推向全局最优化, 算法的收敛速度和解的最优性都得到了提高.
2) 分布式粒子群算法研究与改进.
为了提高整个协同系统的鲁棒性和自适应性, 分布式粒子群算法被广泛应用于多无人机路径规划. 文献[61]提出了一种具有协同机制的分布式协同粒子群优化(distributed cooperative particle swarm optimization, DCPSO)算法, 用于生成执行编队会合任务的多架无人机空间路径集, 与协同进化遗传算法相比, 该算法有更高的稳定性, 不易陷入局部最优, 搜索成功率高. 文献[59]提出了一种分布式粒子群优化(distributed particle swarm optimization, DPSO)算法来求解无人机集群侦察路径规划问题, 根据侦察任务不同, 提出了最大密度收敛DPSO算法(maximum density convergence DPSO algorithm, MDC-DPSO)、快速交叉DPSO算法(fast cross-over DPSO algorithm, FCO-DPSO)、精确覆盖勘探DPSO算法(accurate coverage exploration DPSO algorithm, ACE-DPSO), 同时为了避免陷入局部最优, 提出了跳出机制和重访机制.
3) 粒子群算法与其他算法结合.
为了提高算法性能, 粒子群算法通常与其他算法相融合来求解多无人机路径规划问题. 文献[60]对多无人机协同搜索运动目标进行研究, 引入权重因子对传统目标函数进行改进, 使目标发现概率最大化, 同时将遗传算法的交叉算子引入到粒子群优化算法中, 用混合粒子群优化算法(hybrid particle swarm optimization, HPSO)对路径规划优化模型进行求解, 增加了种群的多样性, 提高了算法的搜索效率. 文献[58]针对多无人机大范围最优覆盖路径规划问题, 以一个新的并行公式创建了一种粒子群优化与遗传算法相结合的混合算法(hybrid form of PSO-genetic algorithms, HPSOGA), 设计了变异算子、逆算子和交叉算子. 该方法简单, 可实时计算, 能在合理的计算时间内获得高质量的解. 文献[63]提出了一种基于时间变量的多无人机四维协调无碰撞路径规划算法, 并设计了一种改进的粒子群优化机制—–空间细化投票机制(spatial refined voting mechanism, SRVM), 克服了局部最优和收敛速度慢的缺陷, 同时构造了搜索空间的目标距离和求解边界, 提高了所有粒子的搜索精度和速度. 文献[64]采用时间戳分割(time stamp segmentation, TSS)技术构建多无人机协同路径规划模型, 提出了一种改进粒子群优化与改进共生有机体搜索(modified symbiotic organisms search, MSOS)结合的新方法, 提高了搜索任务的效率.
2.4 神经网络算法人工神经网络(artificial neural network, ANN)是近年来人工智能领域的研究热点, 将神经网络应用于多无人机路径规划研究, 可以显著提高多无人机系统自主性和自适应性. 此外, 神经网络算法在复杂动态环境下的规划问题中也有出色表现.
文献[65]针对多无人机三维路径规划提出了一种改进的神经网络算法, 根据威胁与无人机之间的距离用动态可调步长调整初始轨迹点, 结合改进的神经网络和自适应学习因子, 同时根据代价函数建立收益函数, 通过收益得到最优策略. 仿真结果表明该算法能安全绕过威胁, 获得更好的路径. 文献[66]针对多无人机在数据采集任务中的路径规划问题, 提出了一种多智能体深度强化学习的方法, 将路径规划问题转化为分散的部分可观测马尔可夫决策过程, 通过训练双深度Q网络(double deep Q-network, DDQN)来逼近最优无人机控制策略.
针对动态环境, 文献[67]提出了多无人机路径规划和避障的策略算法Deep-Sarsa, 将传统的Sarsa与神经网络相结合, 取代了Q表格来存储状态信息和预测最佳动作, 避免了Q表格因需存储信息太多而导致维数过大的问题. Deep-Sarsa算法使用深度神经网络来决定无人机需要采取何种行动, 对不同的情况具有较强的泛化能力, 可以处理复杂的状态组合, 能够在动态环境中为无人机提供可靠的路径, 算法有效性在ROS-Gazebo环境的仿真测试中得到了验证. 文献[68]则采用强化学习来应对动态环境下高实时性需求的规划问题, 具体地, 提出了一种基于多智能体深度确定性策略梯度(multi-agent deep deterministic policy gradient, MADDPG)算法的并行目标分配与路径规划方法, 将多无人机目标分配与路径规划问题整合到一个多智能体系统中, 根据相应的奖励措施在动态环境下通过改进的MADDPG对系统进行训练. 该系统简单且具有实时性, 为相关领域的研究者提供了一种新的思路. 文献[69]针对风扰动下大规模无人机自主路径规划问题提出了一种基于平均场博弈(mean-field game, MFG)理论的神经网络方法. 特别地, 通过在每个智能体上局部求解两个偏微分方程来实现MFG理论控制, 用机器学习解决多维无人机状态下计算量过大的问题. 在该研究中, 每个无人机都能以分布式的方式实时加速控制, 在低通信和可接受的计算量的情况下能够有效地避免碰撞.
表 4为上述基于神经网络算法的多无人机路径规划研究对比.
|
|
表 4 基于神经网络算法的多无人机路径规划研究对比 |
模拟退火法(simulated annealing, SA)[70-71]模仿冶金学中的加热冷却过程, 不易陷入局部最优解, 具有优良的鲁棒性.
文献[72]针对多无人机路径规划问题提出了一种GPU加速模拟退火算法, 该算法在并行计算平台CUDA上执行, 能显著提高飞行路线规划问题的求解效率. 文献[73]将小型多无人机路径规划视为旅行商问题, 提出了一种考虑多游客和城市性质的模拟退火方法, 使无人机与兴趣点的匹配最大化, 总行程距离最小化, 但该方法不适用于动态环境. 特别地, 算法的验证平台ArduCopter采用了符合某商用无人机通信标准的通信协议, 这使得研究成果更易于应用在实际场景中. 文献[74]为了平衡各无人机的任务, 提出一种基于交换-判定模拟退火(swap-and-judge simulated annealing, SJSA)的无人机任务分配与路径规划新策略. 具体地, 通过在原有的三维车辆路径问题(vehicle routing problem, VRP)模型上根据无人机数量增加虚拟节点, 更高效地生成可行解. 此外, 提出了通用距离矩阵的概念, 实现了无人机任务的均衡分配. 文献[75]针对复杂约束条件下多无人机多任务的路径规划问题, 结合
|
|
表 5 基于模拟退火法的多无人机路径规划研究对比 |
受生物行为启发, 人工蜂群算法、鸽群算法、果蝇算法、灰狼算法等仿生算法由于其独特优势在多无人机路径规划研究上成为学者们日益关注的焦点. 表 6为基于以上仿生算法的多无人机路径规划研究对比, 这些研究中算法的有效性均通过仿真实验得到了验证.
|
|
表 6 基于其他仿生算法的多无人机路径规划研究对比 |
人工蜂群算法(artificial bee colony, ABC)[82]是受蜜蜂采蜜行为的启发而提出来的一种元启发式算法. 文献[77]在多无人机协同路径规划问题中改进了传统人工蜂群算法的食物产生方式, 并采用非确定性规划方法和双向规划机制, 提高了航迹质量.
鸽群优化算法(pigeon-inspired optimization, PIO)[83]是一种模拟鸽子归巢行为的新型仿生算法, 能高效应用于无人机编队中. 文献[78]针对基于时间戳技术(TSS)的多无人机协同路径规划问题, 提出了社会等级鸽群优化算法(social-class pigeon-inspired optimization, SCPIO)来搜索TSS模型上的可行路径, 提高了传统鸽群优化算法的搜索能力.
果蝇优化算法(fruit fly optimization algorithm, FOA)[84]由于其原理简单、全局寻优快等优势在路径规划研究中得到了广泛应用. 针对多无人机任务变化的油田巡检路径规划问题, 文献[79]提出了一种基于最优参考点的改进果蝇优化算法(optimal reference point based fruit fly optimization algorithm, ORPFOA). ORPFOA结合成本距离矩阵, 能够快速逼近全局最优解, 保证优化结果的稳定性, 并且克服了传统果蝇优化算法在添加新任务时规划能力弱的缺陷.
灰狼优化算法(grey wolf optimization, GWO)[85]是近几年提出的另一种新型群智能优化算法, 具有简单易实现的优点. 文献[80]采用改进的灰狼优化算法来解决三维无人机的路径规划问题, 该算法收敛速度快, 计算成本低, 避免了局部最优. 文献[81]针对复杂对抗环境下多无人机协同路径规划问题, 在传统灰狼优化算法基础上从种群初始化、衰减因子更新和个体位置更新3个方面进行了改进, 能够以较低的计算成本和更快的收敛速度求解所建立的多约束目标优化模型.
3 面临的挑战和未来发展方向多无人机协同路径规划是近几年的研究热点, 该领域研究人员在算法优化和技术方面已经进行了大量工作, 但仍有很多问题需要进一步研究. 本文从以下5个方面提出多无人机协同路径规划目前存在的问题, 并针对这些问题对未来发展趋势进行展望.
1) 协同性. 为了实现特定任务中无人机时间与空间的协同, 当前的研究通常在任务执行之前对无人机进行任务分配, 针对无人机航迹距离、安全性、任务要求等施加约束条件. 当无人机数量较多、任务较复杂、系统较为庞大时, 求解数学模型面临相当大的计算量, 从而无法满足系统的实时性要求, 解的质量也无法得到保证. 此外, 多无人机执行任务时仍需一定程度的人为规划, 自主协同的程度不够深入. 未来的多无人机系统将趋向于大规模、层次化、网络化, 实现更加复杂的任务. 无人机作为系统中的个体, 为了提高与其他各层次中个体的协同性, 分布式网络结构[86]和自主学习类算法[68]应成为未来研究中的主流.
2) 异构性. 陆空机器人、多异构无人机等协同是完成复杂任务并提高系统自主性的关键, 尤其在军用领域, 异构无人机集群技术将会颠覆性地改变当前的作战模式. 根据不同的任务需求, 军用无人机存在战斗机、轰炸机、自杀式无人机等多种类型, 多异构无人机路径规划问题的研究对整个作战系统至关重要. 值得注意的是, 异构无人机在结构尺寸、通信协议、负载能力、感知系统、功能实现等各方面存在一定的差异, 很大程度上增加了路径规划的复杂性. 如何设计合理的协同控制架构, 增加更精确全面的约束条件以及如何进一步改进优化算法, 是当前异构无人机路径规划亟待解决的问题.
3) 可扩展性. 针对不同的任务、规模、环境等研究背景, 不同的多无人机路径规划模型和算法相继涌现. 由于约束耦合性强、算法复杂度高等限制, 多数研究只适用于该研究当下的研究背景, 不能或很难实现其他任务、更多无人机协同、不确定环境下的扩展. 鉴于此, 未来研究应在解耦多约束条件、建立简单的规划模型的同时降低算法的复杂度, 对适用度高的规划模块进行集成化处理, 从而实现灵活性高、可扩展性强的规划系统, 进一步推动多无人机协同研究的发展.
4) 动态适应性. 现有的大部分优化算法难以在动态环境下对多无人机进行高效的路径规划. 事实上, 在实际飞行任务中, 通常会出现无法预测的障碍物、扰动以及其他突发状况, 尤其在作战任务中, 战场态势复杂多变, 存在很多快速变化的动态干扰和突发情况. 遇到这类问题时, 需要及时对环境信息进行更新, 并针对新的信息进行航迹重规划. 目前, 航迹重规划研究多见于单无人机中, 多无人机航迹重规划问题复杂度高, 求解难度大, 在短时间内生成轨迹是一个难点. 在未来发展中, 应注重无人机航迹的快速生成, 例如用合理的空间表示方法降低环境复杂度、提高算法的收敛速度等, 另外, 应降低规划目标的优化程度, 重心放在可行性上. 此外, 针对动态环境问题, 深度学习和强化学习算法在众多算法中脱颖而出, 虽然目前对基于深度学习和强化学习的多无人机路径规划研究很多, 但仍有很大的发展空间.
5) 应用性. 目前, 国内外很多学者对多无人机路径规划问题进行了广泛的研究, 但通过实机飞行实验来验证算法的研究[57]很少, 研究成果仍停留在仿真阶段. 其中, 仿真方式包括将无人机视为质点的数值仿真[22]、考虑无人机动力学约束的仿真[61]、更接近实际飞行器的半实物仿真[73]等. 然而, 在实际应用中可能存在飞行航迹限制、通信延迟、能量约束、电磁干扰等问题, 使实机飞行效果与实验仿真结果存在一定程度的差距, 最小化该差距对研究至关重要. 未来的研究将趋向于增加更复杂的约束条件, 用更有效的优化算法和更接近实物的仿真模式, 更大程度上实现多无人机路径规划的可行性、实用性、智能性、自主性、自适应性. 此外, 规划算法应用于实机飞行时, 由于感知、定位的速度及准确度等限制, 无人机往往需要以非常低的速度飞行, 这可能无法满足任务效率需求, 因此, 多传感器融合的多维感知技术将对自主无人机系统的实质发展具有重要意义.
4 结语启发式算法的改进与应用是多无人机协同路径规划研究中的关键部分. 本文的目的是让读者了解近年来多无人机路径规划的研究现状和发展趋势, 并协助读者针对不同研究问题快速获取目前多无人机路径规划问题的研究方法和特点. 具体地, 本文首先整理并分析了多无人机路径规划的研究问题、环境模型和协同性表现, 提出了一种全新的分类方法; 其次, 着重对当前元启发式算法在多无人机路径规划的应用成果进行举例分析, 从多角度、多维度地分析其应用背景、应用特点以及效果优劣, 全面地梳理了相关研究脉络; 最后, 结合当前研究的局限性, 从协同性、异构性、可扩展性、动态适应性、应用性5方面对存在的问题进行分析, 并展望了多无人机路径规划的重点研究方向.
| [1] |
Lee K S, Ovinis M, Nagarajan T, et al. Autonomous patrol and surveillance system using unmanned aerial vehicles[C]. The 15th International Conference on Environment and Electrical Engineering (EEEIC). Rome, 2015: 1291-1297.
|
| [2] |
杜云, 贾慧敏, 邵士凯, 等. 面向多目标侦察任务的无人机航线规划[J]. 控制与决策, 2021, 36(5): 1191-1198. (Du Y, Jia H M, Shao S K, et al. UAV trajectory planning for multi-target reconnaissance missions[J]. Control and Decision, 2021, 36(5): 1191-1198.) |
| [3] |
Casbeer D W, Beard R W, McLain T W, et al. Forest fire monitoring with multiple small UAVs[C]. Proceedings of the 2005 American Control Conference. Portland, 2005: 3530-3535.
|
| [4] |
Song B D, Park K, Kim J. Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J]. Computers & Industrial Engineering, 2018, 120: 418-428. |
| [5] |
Deng C, Wang S W, Huang Z, et al. Unmanned aerial vehicles for power line inspection: A cooperative way in platforms and communications[J]. Journal of Communications, 2014, 9(9): 687-692. DOI:10.12720/jcm.9.9.687-692 |
| [6] |
Chao H Y, Baumann M, Jensen A, et al. Band- reconfigurable multi-UAV-based cooperative remote sensing for real-time water management and distributed irrigation control[J]. IFAC Proceedings Volumes, 2008, 41(2): 11744-11749. DOI:10.3182/20080706-5-KR-1001.01989 |
| [7] |
Aggarwal S, Kumar N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges[J]. Computer Communications, 2020, 149: 270-299. DOI:10.1016/j.comcom.2019.10.014 |
| [8] |
Vachtsevanos G, Kim W, Al-Hasan S, et al. Autonomous vehicles: From flight control to mission planning using fuzzy logic techniques[C]. Proceedings of 13th International Conference on Digital Signal Processing. Santorini, 1997: 977-981.
|
| [9] |
Stentz A. Optimal and efficient path planning for partially-known environments[C]. Proceedings of the 1994 IEEE International Conference on Robotics and Automation. San Diego, 1994: 3310-3317.
|
| [10] |
Tarjan R. Depth-first search and linear graph algorithms[J]. SIAM Journal on Computing, 1972, 1(2): 146-160. DOI:10.1137/0201010 |
| [11] |
Zhou R, Hansen E A. Breadth-first heuristic search[J]. Artificial Intelligence, 2006, 170(4/5): 385-408. |
| [12] |
Per O P, Patrick D. Probabilistic roadmap based path planning for an autonomous unmanned helicopter[J]. Journal of Intelligent & Fuzzy Systems, 2006, 17(4): 395-405. |
| [13] |
Yershova A, Jaillet L, Simeon T, et al. Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain[C]. Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Barcelona, 2005: 3856-3861.
|
| [14] |
Tseng F H, Liang T T, Lee C H, et al. A star search algorithm for civil UAV path planning with 3G communication[C]. The 10th International Conference on Intelligent Information Hiding and Multimedia Signal Processing. Kitakyushu, 2014: 942-945.
|
| [15] |
Chen X, Chen X M. The UAV dynamic path planning algorithm research based on Voronoi diagram[C]. The 26th Chinese Control and Decision Conference. Changsha, 2014: 1069-1071.
|
| [16] |
Kumar Debnath S, Omar R, Abdul Latip N B, et al. A review on graph search algorithms for optimal energy efficient path planning for an unmanned air vehicle[J]. Indonesian Journal of Electrical Engineering and Computer Science, 2019, 15(2): 743. DOI:10.11591/ijeecs.v15.i2.pp743-749 |
| [17] |
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. DOI:10.1007/s11633-013-0750-9 |
| [18] |
Meng L, Qing S, Jun Z Q. UAV path re-planning based on improved bidirectional RRT algorithm in dynamic environment[C]. The 3rd International Conference on Control, Automation and Robotics (ICCAR). Nagoya, 2017: 658-661.
|
| [19] |
Beheshti Z, Shamsuddin S M. A review of population-based meta-heuristic algorithm[J]. International Journal of Advances in Soft Computing and Its Applications, 2013, 5(1): 1-35. |
| [20] |
Zhang H, Xin B, Dou L H, et al. A review of cooperative path planning of an unmanned aerial vehicle group[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(12): 1671-1694. |
| [21] |
杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37(11): 2291-2302. (Yang X, Wang R, Zhang T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization[J]. Control Theory & Applications, 2020, 37(11): 2291-2302. DOI:10.7641/CTA.2020.00105) |
| [22] |
Cekmez U, Ozsiginan M, Sahingoz O K, et al. UAV path planning with parallel genetic algorithms on CUDA architecture[J]. Lecture Notes in Engineering and Computer Science, 2014(1): 551-557. |
| [23] |
Li J, Xiong Y H, She J H. An improved ant colony optimization for path planning with multiple UAVs[C]. IEEE International Conference on Mechatronics (ICM). Kashiwa, 2021: 1-5.
|
| [24] |
Cao Y, Wei W Y, Bai Y, et al. Multi-base multi- UAV cooperative reconnaissance path planning with genetic algorithm[J]. Cluster Computing, 2019, 22(3): 5175-5184. |
| [25] |
Ramirez-Atencia C, Bello-Orgaz G, R-Moreno M D, et al. Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms[J]. Soft Computing, 2017, 21(17): 4883-4900. DOI:10.1007/s00500-016-2376-7 |
| [26] |
Biswas S, Anavatti S G, Garratt M A. Particle swarm optimization based co-operative task assignment and path planning for multi-agent system[C]. IEEE Symposium Series on Computational Intelligence (SSCI). Honolulu, 2017: 1-6.
|
| [27] |
Zhen Z Y, Xing D J, Gao C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm[J]. Aerospace Science and Technology, 2018, 76: 402-411. DOI:10.1016/j.ast.2018.01.035 |
| [28] |
Shivgan R, Dong Z Q. Energy-efficient drone coverage path planning using genetic algorithm[C]. The 21st International Conference on High Performance Switching and Routing (HPSR). Newark, 2020: 1-6.
|
| [29] |
张莹莹, 周德云, 夏欢. 不确定环境下多无人机协同搜索算法研究[J]. 电光与控制, 2012, 19(2): 5-8. (Zhang Y Y, Zhou D Y, Xia H. Cooperative search algorithm for multi-UAV in uncertain environment[J]. Electronics Optics & Control, 2012, 19(2): 5-8. DOI:10.3969/j.issn.1671-637X.2012.02.002) |
| [30] |
Shao S K, Peng Y, He C L, et al. Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J]. ISA Transactions, 2020, 97: 415-430. DOI:10.1016/j.isatra.2019.08.018 |
| [31] |
Sørli J V, Graven O H, Bjerknes J D. Multi-UAV cooperative path planning for sensor placement using cooperative coevolving genetic strategy[C]. Advances in Swarm Intelligence. Berlin, 2017: 433-444.
|
| [32] |
Zhou Z W, Luo D L, Shao J, et al. Immune genetic algorithm based multi-UAV cooperative target search with event-triggered mechanism[J]. Physical Communication, 2020, 41: 101103. DOI:10.1016/j.phycom.2020.101103 |
| [33] |
Lin W, Zhu Y, Zeng W C, et al. Track planning model for multi-UAV based on new multiple ant colony algorithm[C]. 2018 Chinese Automation Congress (CAC). Xi'an, 2018: 3862-3867.
|
| [34] |
Nikolos I K, Valavanis K P, Tsourveloudis N C, et al. Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE Transactions on Systems, Man, and Cybernetics — Part B: Cybernetics, 2003, 33(6): 898-912. DOI:10.1109/TSMCB.2002.804370 |
| [35] |
Li J D, Li X Q, Yu L J. Multi-UAV cooperative coverage path planning in plateau and mountain environment[C]. The 33rd Youth Academic Annual Conference of Chinese Association of Automation (YAC). Nanjing, 2018: 820-824.
|
| [36] |
刘畅, 谢文俊, 张鹏, 等. 多目标群多基地多无人机协同任务规划[J]. 弹箭与制导学报, 2019, 39(1): 119-124. (Liu C, Xie W J, Zhang P, et al. Collaborative mission planning of multi-target group multi-base and multi-UAV[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2019, 39(1): 119-124.) |
| [37] |
Zhang X, Chen J, Xin B, et al. A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets[J]. Chinese Journal of Aeronautics, 2014, 27(3): 622-633. DOI:10.1016/j.cja.2014.04.024 |
| [38] |
Ergezer H, Leblebicioğlu K. 3D path planning for multiple UAVs for maximum information collection[J]. Journal of Intelligent & Robotic Systems, 2014, 73. |
| [39] |
肖春晖, 邹媛媛, 李少远. 有障碍区域的多无人机多目标点路径规划[J]. 空间控制技术与应用, 2019, 45(4): 46-52. (Xiao C H, Zou Y Y, Li S Y. Multi-UAV multi-target point path planning with obstacles[J]. Aerospace Control and Application, 2019, 45(4): 46-52. DOI:10.3969/j.issn.1674-1579.2019.04.006) |
| [40] |
Binol H, Bulut E, Akkaya K, et al. Time optimal multi-UAV path planning for gathering its data from roadside units[C]. The 88th Vehicular Technology Conference (VTC-Fall). Chicago, 2018: 1-5.
|
| [41] |
Pan Y W, Yang Y W, Li W Z. A deep learning trained by genetic algorithm to improve the efficiency of path planning for data collection with multi-UAV[J]. IEEE Access, 2021, 9: 7994-8005. DOI:10.1109/ACCESS.2021.3049892 |
| [42] |
Chen Y B, Yu J Q, Mei Y S, et al. Trajectory optimization of multiple quad-rotor UAVs in collaborative assembling task[J]. Chinese Journal of Aeronautics, 2016, 29(1): 184-201. DOI:10.1016/j.cja.2015.12.008 |
| [43] |
Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41. DOI:10.1109/3477.484436 |
| [44] |
Cekmez U, Ozsiginan M, Sahingoz O K. Multi-UAV path planning with multi colony ant optimization[C]. Intelligent Systems Design and Applications. Berlin, 2017: 407-417.
|
| [45] |
Perez-Carabaza S, Besada-Portas E, Lopez-Orozco J A, et al. Ant colony optimization for multi-UAV minimum time search in uncertain domains[J]. Applied Soft Computing, 2018, 62: 789-806. DOI:10.1016/j.asoc.2017.09.009 |
| [46] |
Perez-Carabaza S, Bermudez-Ortega J, Besada-Portas E, et al. A multi-UAV minimum time search planner based on ACO R[C]. Proceedings of the Genetic and Evolutionary Computation Conference. Berlin, 2017: 35-42.
|
| [47] |
Yang F, Ji X L, Yang C W, et al. Cooperative search of UAV swarm based on improved ant colony algorithm in uncertain environment[C]. IEEE International Conference on Unmanned Systems (ICUS). Beijing, 2017: 231-236.
|
| [48] |
Sun Y, Chen J C, Du C L. Path planning of UAVs based on improved ant colony system[C]. IEEE International Conference on Progress in Informatics and Computing (PIC). Shanghai, 2020: 396-400.
|
| [49] |
Huang L W, 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. DOI:10.1016/j.asoc.2016.06.046 |
| [50] |
Ali Z A, Han Z G, Di Z R. Path planning of multiple UAVs using MMACO and DE algorithm in dynamic environment[J]. Measurement and Control, DOI: 10.1177/0020294020915727.
|
| [51] |
Shi J, Wang Y K, Tian J F. Research on cooperative task assignment of UAV formation[J]. DEStech Transactions on Computer Science and Engineering, 2017, 489-496. |
| [52] |
Ali Z A, Han Z G, Hang W B. Cooperative path planning of multiple UAVs by using max-min ant colony optimization along with cauchy mutant operator[J]. Fluctuation and Noise Letters, 2021, 20(1): 2150002. DOI:10.1142/S0219477521500024 |
| [53] |
Kennedy J, Eberhart R. Particle swarm optimization[C]. Proceedings of ICNN'95 — International Conference on Neural Networks. Perth, 1995: 1942-1948.
|
| [54] |
Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]. Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya, 1995: 39-43.
|
| [55] |
Belkadi A, Abaunza H, Ciarletta L, et al. Distributed path planning for controlling a fleet of UAVs: Application to a team of quadrotors[J]. IFAC-PapersOnLine, 2017, 50(1): 15983-15989. DOI:10.1016/j.ifacol.2017.08.1908 |
| [56] |
Ghamry K A, Kamel M A, Zhang Y M. Multiple UAVs in forest fire fighting mission using particle swarm optimization[C]. International Conference on Unmanned Aircraft Systems (ICUAS). Miami, 2017: 1404-1409.
|
| [57] |
Chen Q Y, Lu Y F, Jia G W, et al. Path planning for UAVs formation reconfiguration based on Dubins trajectory[J]. Journal of Central South University, 2018, 25(11): 2664-2676. DOI:10.1007/s11771-018-3944-z |
| [58] |
Haghighi H, Sadati S H, Dehghan S M M, et al. Hybrid form of particle swarm optimization and genetic algorithm for optimal path planning in coverage mission by cooperated unmanned aerial vehicles[J]. Journal of Aerospace Technology and Management, DOI: 10.5028/jatm.v12.1169.
|
| [59] |
Wang Y B, Bai P, Liang X L, et al. Reconnaissance mission conducted by UAV swarms based on distributed PSO path planning algorithms[J]. IEEE Access, 2019, 7: 105086-105099. DOI:10.1109/ACCESS.2019.2932008 |
| [60] |
Hu X X, Liu Y H, Wang G Q. Optimal search for moving targets with sensing capabilities using multiple UAVs[J]. Journal of Systems Engineering and Electronics, 2017, 28(3): 526-535. DOI:10.21629/JSEE.2017.03.12 |
| [61] |
Shao Z, Yan F, Zhou Z, et al. Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization[J]. Applied Sciences, 2019, 9(13): 2621. DOI:10.3390/app9132621 |
| [62] |
Ahmed G, Sheltami T, Mahmoud A, et al. IoD swarms collision avoidance via improved particle swarm optimization[J]. Transportation Research Part A: Policy and Practice, 2020, 142: 260-278. DOI:10.1016/j.tra.2020.09.005 |
| [63] |
Liu Y, Zhang X J, Zhang Y, et al. Collision free 4D path planning for multiple UAVs based on spatial refined voting mechanism and PSO approach[J]. Chinese Journal of Aeronautics, 2019, 32(6): 1504-1519. DOI:10.1016/j.cja.2019.03.026 |
| [64] |
He W J, Qi X G, Liu L F. A novel hybrid particle swarm optimization for multi-UAV cooperate path planning[J]. Applied Intelligence, 2021, 51(10): 7350-7364. DOI:10.1007/s10489-020-02082-8 |
| [65] |
Chen X, Ai Y D. Multi-UAV path planning based on improved neural network[C]. Chinese Control and Decision Conference (CCDC). Shenyang, 2018: 354-359.
|
| [66] |
Bayerlein H, Theile M, Caccamo M, et al. Multi-UAV path planning for wireless data harvesting with deep reinforcement learning[J]. IEEE Open Journal of the Communications Society, 2021, 2: 1171-1187. DOI:10.1109/OJCOMS.2021.3081996 |
| [67] |
Luo W, Tang Q R, Fu C H, et al. Deep-sarsa based multi-UAV path planning and obstacle avoidance in a dynamic environment[C]. Advances in Swarm Intelligence. Berlin, 2018: 102-111.
|
| [68] |
Qie H, Shi D X, Shen T L, et al. Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning[J]. IEEE Access, 2019, 7: 146264-146272. DOI:10.1109/ACCESS.2019.2943253 |
| [69] |
Shiri H, Park J, Bennis M. Massive autonomous UAV path planning: A neural network based mean-field game theoretic approach[C]. IEEE Global Communications Conference (GLOBECOM). Waikoloa, 2019: 1-6.
|
| [70] |
Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680. DOI:10.1126/science.220.4598.671 |
| [71] |
Černý V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm[J]. Journal of Optimization Theory and Applications, 1985, 45(1): 41-51. DOI:10.1007/BF00940812 |
| [72] |
Turker T, Yilmaz G, Sahingoz O K. GPU-accelerated flight route planning for multi-UAV systems using simulated annealing[C]. Artificial Intelligence: Methodology, Systems, and Applications. Berlin, 2016: 279-288.
|
| [73] |
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. DOI:10.1016/j.ifacol.2015.08.109 |
| [74] |
Huo L S, Zhu J H, Wu G H, et al. A novel simulated annealing based strategy for balanced UAV task assignment and path planning[J]. Sensors, 2020, 20(17): 4769. DOI:10.3390/s20174769 |
| [75] |
Yue X, Zhang W. UAV path planning based on $K$-means algorithm and simulated annealing algorithm[C]. The 37th Chinese Control Conference (CCC). Wuhan, 2018: 582-587.
|
| [76] |
Ning Q, Tao G P, Chen B C, et al. Multi-UAVs trajectory and mission cooperative planning based on the Markov model[J]. Physical Communication, 2019, 35: 100717. DOI:10.1016/j.phycom.2019.100717 |
| [77] |
夏瑞, 赵磊, 吴书宇, 等. 基于人工蜂群算法的无人机协同路径规划[J]. 无线互联科技, 2018, 15(13): 13-21. (Xia R, Zhao L, Wu S Y, et al. Drone cooperative path planning based on artificial bee colony algorithm[J]. Wireless Internet Technology, 2018, 15(13): 13-21. DOI:10.3969/j.issn.1672-6944.2018.13.007) |
| [78] |
Zhang D F, Duan H B. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning[J]. Neurocomputing, 2018, 313: 229-246. DOI:10.1016/j.neucom.2018.06.032 |
| [79] |
Li K, Ge F W, Han Y, et al. Path planning of multiple UAVs with online changing tasks by an ORPFOA algorithm[J]. Engineering Applications of Artificial Intelligence, 2020, 94: 103807. DOI:10.1016/j.engappai.2020.103807 |
| [80] |
Dewangan R K, Shukla A, Godfrey W W. Three dimensional path planning using grey wolf optimizer for UAVs[J]. Applied Intelligence, 2019, 49(6): 2201-2217. DOI:10.1007/s10489-018-1384-y |
| [81] |
Xu C, Xu M, Yin C J. Optimized multi-UAV cooperative path planning under the complex confrontation environment[J]. Computer Communications, 2020, 162: 196-203. DOI:10.1016/j.comcom.2020.04.050 |
| [82] |
Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Erciyes University, 2005: 1-10.
|
| [83] |
Duan H B, Qiao P X. Pigeon-inspired optimization: A new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics, 2014, 7(1): 24-37. DOI:10.1108/IJICC-02-2014-0005 |
| [84] |
Pan W T. A new fruit fly optimization algorithm: Taking the financial distress model as an example[J]. Knowledge-Based Systems, 2012, 26: 69-74. DOI:10.1016/j.knosys.2011.07.001 |
| [85] |
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61. DOI:10.1016/j.advengsoft.2013.12.007 |
| [86] |
邵壮, 祝小平, 周洲, 等. 三维动态环境下多无人机编队分布式保持控制[J]. 控制与决策, 2016, 31(6): 1065-1072. (Shao Z, Zhu X P, Zhou Z, et al. Distributed formation keeping control of UAVs in 3-D dynamic environment[J]. Control and Decision, 2016, 31(6): 1065-1072.) |