赵畅(1998-), 女, 硕士生, 从事无人机路径规划的研究, E-mail:
刘允刚(1970-), 男, 教授, 博士生导师, 从事非线性控制、自适应控制、智能无人系统先进技术等研究, E-mail:
陈琳(1990-), 女, 博士生, 从事智能无人系统先进理论与技术的研究, E-mail:
李峰忠(1988-), 男, 副研究员, 博士, 从事非线性控制与智能优化等研究, E-mail:
满永超(1988-), 男, 副研究员, 博士, 从事非线性控制与机电控制等研究, E-mail:
多无人机路径规划是一个复杂的多约束组合优化问题, 通过传统算法很难求得优良结果, 元启发式算法由于其快速高效而成为解决该类优化问题的有效手段. 首先, 针对多无人机路径规划的关键要素提出一种新的分类方法; 其次, 从算法改进方式入手, 对各项研究中所采用的元启发式算法进行分类梳理, 阐述它们的应用效果和优缺点, 并根据所提出的分类方法和研究特点归纳了当前的研究成果; 最后, 结合目前多无人机路径规划研究存在的问题对未来发展趋势进行展望.
Multi-UAV path planning is a complex multi-constraint combinatorial optimization problem, which is difficult to obtain good results through traditional algorithms. Recently, the metaheuristic algorithm has become an effective means to solve this kind of optimization problems because of its high efficiency. Firstly, a new classification method is proposed for the key elements of multi-UAV path planning. Then, we classify and discuss the improvement methods of metaheuristic algorithms used in the research results, elaborate the application performance, advantages and disadvantages of these algorithms, and summarize the current research results according to the proposed classification methods and research characteristics. Finally, the future development trend is prospected based on the existing problems in the current multi-UAV path planning research.
近年来, 无人机(unmanned aerial vehicle, UAV)由于其灵活度高、机动性强、安全风险系数小、成本低等特点, 被广泛应用于搜索巡逻[
路径规划是无人机执行任务的关键, 也是自主无人机在工程应用上的主要挑战, 吸引了国内外学者的广泛关注[
目前, 针对多无人机路径规划启发式算法的研究综述相对较少. 文献[
本文综述了近年来多无人机协同路径规划的研究成果. 主要工作如下: 1)对当前多无人机路径规划研究中的关键要素提出一种新颖的分类方式. 首先将所研究的问题根据其任务性质分为多旅行商(multiple travelling salesman problem, MTSP)问题、搜索问题、覆盖问题、避障及轨迹优化问题、其他问题; 其次, 针对所研究的环境维度和确定性对研究成果中的环境模型进行分类; 最后, 通过梳理和分析多无人机路径规划研究现状, 从模型层面和算法层面分析无人机间的协同关系. 2)对广泛应用于多无人机路径规划的元启发式算法从改进方式上进行分类梳理, 并讨论了各算法的应用效果、优势及缺陷. 另外, 结合上述分类方式及研究特点以表格的形式对当前研究成果进行归纳汇总, 协助读者快速、有针对性地获取该研究领域的相关信息. 3)结合当前多无人机路径规划研究的局限性, 从协同性、异构性、可扩展性、动态适应性、应用性5方面对存在的研究问题进行分析, 并展望了多无人机路径规划的未来发展趋势. 本文结构如
多无人机路径规划结构
通过梳理近年来多无人机路径规划研究, 本文从研究特点和规划要素角度对这些研究进行分类归纳, 并在第2节以表格形式给出分类结果. 本节的目的是介绍分类方式的同时结合规划要素分析目前的发展现状, 具体地, 本节将阐述多无人机路径规划研究的3方面关键要素, 分别为问题类型、环境模型、协同关系.
综合国内外研究发现, 多无人机协同路径规划问题可分为MTSP问题、搜索问题、覆盖问题、避障及轨迹优化问题与其他问题5大类. 具体分类方式定义如下.
1) MTSP问题.
在多无人机路径规划研究中, MTSP问题是最常见的问题模型. 建模时通常在地图中给定一系列目标点, 多个无人机共同去访问目标点, 由此求解无人机遍历所有目标点且最终返回起始点的最优路径.
2) 搜索问题.
无人机需要去访问的各目标位置事先未知, 需要通过建立概率图等方式搜索发现目标点位置, 并规划出一条到达目标位置的最优路径.
3) 覆盖问题.
当无人机执行搜救、侦察等任务时, 多架无人机需以最小代价高效覆盖整个任务区域, 规划出遍历任务区域的多无人机最优飞行路径. 需要注意的是, 文献[
4) 避障及轨迹优化问题.
在含障碍物的环境中, 对多无人机从起始点到目标点的航迹进行规划, 并考虑无人机的动力学模型对航迹进行优化处理, 使规划结果更高程度上满足实机飞行的要求, 从而提高规划算法的可行性.
5) 其他问题.
一些多无人机路径规划研究[
本文从维度、不确定性、应用3个角度对多无人机路径规划研究的环境模型进行分类和总结.
在多无人机路径规划中, 确定规划空间的维度是环境建模的关键. 任务简单、环境复杂度低的路径规划研究常采用2D环境模型, 假设无人机保持飞行高度不变或人为控制飞行高度, 规划时仅考虑无人机在某一平面的飞行. 此外, 在真实环境中存在相当多的结构约束和不确定性, 飞行任务也日益复杂化, 如森林救火、管道检修、电力巡检等. 为了满足飞行任务的要求, 越来越多的学者针对3D多无人机路径规划进行研究.
从不确定性角度出发, 环境可分为确定性环境和不确定性环境: 确定性环境指, 在规划之前障碍物大小、形状和位置精确已知, 且障碍物及其他环境因素不再发生未知的动态改变的环境; 不确定性环境指, 在规划系统中障碍物及其他环境因素未知或部分未知、障碍物突然出现或移动、环境中存在动态扰动等情况.
多无人机路径规划在军用和民用环境中均有广泛应用. 在军用领域, 多架无人机在作战要求、战场环境任务载荷等约束下, 通过相互配合规划出适宜的飞行路线. 近年来, 无人机应用从军用领域快速扩展到民用领域, 特别地, 小型多旋翼无人机在多样化的民用任务中取得了优良的应用效果, 如建筑检测、农业灌溉、航拍等. 多无人机路径规划的研究对提高任务执行效率和优化任务效果至关重要.
多无人机协同执行任务时, 需要各无人机相互配合、约束, 针对不同的研究问题和任务复杂度, 无人机相互配合方式和协同程度不一.根据目前多无人机路径规划研究成果分析, 无人机之间的协同关系在模型层面和算法层面均有体现, 具体如下.
无人机路径规划的目的是在满足约束条件下, 找到满足任务需求或某种性能指标的最优飞行路径. 多无人机路径规划需要在单无人机路径规划模型基础上, 进一步考虑无人机的任务分配、无人机间复杂的约束条件、共同的优化目标, 下面是基于这3方面的无人机协同关系介绍.
1) 任务分配.
路径规划是多无人机执行任务的关键, 一些研究将路径规划建立在明确的任务需求上, 如多无人机协同侦察、数据收集等. 为了提高任务执行效率, 在路径规划前, 总任务被分为若干个子任务分配给相应的无人机, 无人机通过执行各自的任务实现总任务目标, 一定程度上体现了多无人机之间的协同关系. 例如, 文献[
2) 约束条件.
无人机路径规划的约束通常包括飞行速度、飞行高度等自身的飞行性能约束以及地形、气象等环境因素约束. 相比于单无人机路径规划, 多无人机路径规划需要考虑更多的约束, 如多无人机之间的避碰约束、任务耦合约束、通信距离约束等. 一些研究通过增加无人机之间协同要求的约束条件来提高多无人机间的协同性和协同路径规划的可行性, 例如, 文献[
3) 优化目标.
无人机路径规划对不同的优化目标具有不同的任务需求, 一般包括最小飞行时间、飞行距离、威胁代价、最大覆盖面等. 在大多数研究中, 多无人机路径规划的优化目标也体现一定的协同性, 如最小总飞行时间、最短总飞行距离、最小能耗、协同最优覆盖等. 研究人员通过构造代价函数形成优化目标, 结合约束条件建立多无人机协同路径规划模型, 然后采用规划算法对模型进行求解. 例如, 文献[
针对无人机间的协同, 一些协同算法被应用于多无人机路径规划问题中, 如协同共进化遗传算法[
当前, 多无人机路径规划研究的协同关系主要表现于上述一方面或几方面的结合, 具体归纳见第2小节表格.
本节从改进方式上对近年来应用于多无人机路径规划问题的启发式算法进行综述, 并采用第1节的分类方式, 从多方面、多维度归纳相关研究的特点.
遗传算法(genetic algorithm, GA)[
近年来, 遗传算法被广泛应用于多无人机路径规划问题中. 文献[
遗传算法存在一些缺陷, 例如容易过早收敛、计算效率低等. 为了提高遗传算法在多无人机路径规划中的应用性能, 研究者对算法进行了改进, 并通过仿真实验验证了相应算法的性能. 本文根据算法的改进特点将改进方式分类为3方面: 在遗传算法各进化阶段上的改进、遗传算法与其他算法结合、协同共进化遗传算法的应用及改进.
基于遗传算法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
大规模; 最小时间 | 2D | 确定性 | - | √ | ||||||
[ |
最小能耗 | 2D | 确定性 | 民用 | √ | ||||||
[ |
传感器部署 | 2D | 确定性 | - | √ | ||||||
[ |
高效率侦察; 最短路径 | 2D | 确定性 | - | √ | √ | |||||
[ |
多目标监视 | 2D | 确定性 | - | √ | ||||||
[ |
最大信息量收集 | 3D | 确定性 | - | √ | √ | |||||
[ |
路径生成; 避障 | 2D | 确定性 | - | √ | √ | |||||
[ |
收集信息; 最短时间 | MTSP问题 | 2D | 确定性 | 民用 | √ | √ | √ | |||
[ |
最小无人机数等 | 2D | 确定性 | 民用 | √ | √ | |||||
[ |
最小无人机数量 | 覆盖问题 | 3D | 确定性 | - | √ | √ | ||||
[ |
搜索信息; 生成路径 | 搜索问题 | 2D | 不确定性 | 军用 | √ | |||||
[ |
高效率搜索; 避障 | 2D | 不确定性 | 军用 | √ | ||||||
[ |
协同装配; 轨迹优化 | 避障及轨迹优化问题 | 3D | 确定性 | - | √ | √ | ||||
[ |
侦察; 最短时间 | 其他问题 | 2D | 确定性 | 军用 | √ | √ | ||||
[ |
复杂任务规划及优化 | 2D | 确定性 | - | √ | √ | √ |
1) 在遗传算法各进化阶段上的改进.
遗传算法的求解过程包括染色体编码和种群初始化、计算适应度、基于适应度函数选择、交叉和变异等基本阶段.
在染色体编码阶段的改进. 文献[
在计算适应度及选择阶段的改进. 文献[
在交叉和变异阶段的改进. 文献[
2) 协同共进化遗传算法的应用及改进.
针对多无人机间的协同工作, 一些研究者对遗传算法进行了研究和改进. 文献[
3) 遗传算法与其他算法结合.
一些研究者将遗传算法与其他算法相结合以获得更好的优化效果. 文献[
蚁群优化算法(ant colony optimization, ACO)[
近年来, 很多学者基于蚁群优化算法对多无人机的协同路径规划问题进行研究, 并从多个方面改进蚁群优化算法. 本文从信息素改进、分布式蚁群算法研究与改进、不确定性环境下的应用与改进、蚁群算法与其他算法结合4个方面对相关研究成果进行分析讨论.
基于蚁群算法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
覆盖; 最小时间 | MTSP问题 | 2D | 确定性 | - | √ | √ | √ | |||
[ |
最小总路径 | 2D | 确定性 | - | √ | √ | |||||
[ |
搜索攻击; 在线避障 | 2D | 不确定性 | 军用 | √ | √ | √ | ||||
[ |
最小时间搜索 | 搜索问题 | 2D | 确定性 | - | √ | |||||
[ |
最短时间; 避碰 | 2D | 不确定性 | 军用 | √ | √ | |||||
[ |
未知动态环境 | 2D | 不确定性 | - | √ | ||||||
[ |
最优覆盖率及时间 | 覆盖问题 | 3D | 确定性 | - | √ | √ | √ | |||
[ |
最小时间搜索 | 2D | 确定性 | - | √ | √ | √ | ||||
[ |
多威胁源环境 | 避障及轨迹 | 2D | 确定性 | 军用 | √ | |||||
[ |
动态环境; 避障 | 优化问题 | 3D | 不确定性 | - | √ | √ |
1) 信息素改进.
信息素的编码方式和更新机制是蚁群算法的关键部分. 文献[
2) 分布式蚁群算法研究与改进.
考虑到多无人机路径规划任务中单个无人机的自主性, 很多学者对分布式蚁群算法进行了研究. 文献[
3) 不确定性环境下的应用与改进.
一些研究者针对蚁群优化算法在不确定性环境中的应用进行了改进. 文献[
4) 蚁群算法与其他算法结合.
由于多无人机路径规划问题的复杂性, 蚁群优化算法通常与其他算法相结合来提高解的质量. 文献[
粒子群算法(particle swarm optimization algorithm, PSO)[
近年来, 研究者多将粒子群算法应用于多无人机路径规划上. 文献[
传统的粒子群算法存在精度较低、容易陷入局部最优等缺陷. 为了提高算法性能, 优化多无人机协同路径规划性能, 研究人员在不同层面上对粒子群算法进行了改进, 本文从分布式粒子群算法研究与改进、粒子群算法与其他算法结合、粒子群算法各步骤的综合改进3方面对此展开分析.
基于粒子群算法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
最优覆盖 | MTSP问题 | 2D | 确定性 | - | √ | √ | ||||
[ |
侦察集群目标 | 搜索问题 | 2D | 不确定性 | - | √ | |||||
[ |
搜索运动目标 | 2D | 不确定性 | - | √ | √ | |||||
[ |
最短时间 | 覆盖问题 | 2D | 确定性 | 民用 | √ | √ | √ | |||
[ |
规划效果和速度 | 3D | 确定性 | - | √ | √ | |||||
[ |
避障 | 2D | 确定性 | 民用 | √ | √ | |||||
[ |
编队重组; 最短时间 | 避障及 | 2D | 不确定性 | - | √ | √ | ||||
[ |
考虑时间变量 | 轨迹优 | 3D | 确定性 | - | √ | √ | ||||
[ |
动力学约束; 避碰 | 化问题 | 3D | 确定性 | - | √ | √ | √ | |||
[ |
规划效果和速度 | 3D | 确定性 | - | √ | √ | |||||
[ |
最优路径规划 | 3D | 确定性 | - | √ | √ | |||||
[ |
动态环境重规划 | 其他问题 | 2D | 不确定性 | - | √ | √ | √ |
1) 粒子群算法计算阶段的改进.
粒子群算法的几个关键计算阶段有: 初始化粒子位置、计算目标函数、粒子位置与速度更新、满足终止条件跳出循环. 一些研究者针对多个计算阶段对粒子群算法进行了改进. 文献[
2) 分布式粒子群算法研究与改进.
为了提高整个协同系统的鲁棒性和自适应性, 分布式粒子群算法被广泛应用于多无人机路径规划. 文献[
3) 粒子群算法与其他算法结合.
为了提高算法性能, 粒子群算法通常与其他算法相融合来求解多无人机路径规划问题. 文献[
人工神经网络(artificial neural network, ANN)是近年来人工智能领域的研究热点, 将神经网络应用于多无人机路径规划研究, 可以显著提高多无人机系统自主性和自适应性. 此外, 神经网络算法在复杂动态环境下的规划问题中也有出色表现.
文献[
针对动态环境, 文献[
基于神经网络算法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
快速路径规划 | 3D | 确定性 | 军用 | √ | √ | √ | ||||
[ |
强化学习; 动态环境 | 避障及轨迹 | 3D | 不确定性 | - | √ | |||||
[ |
动态环境 | 优化问题 | 2D | 不确定性 | - | √ | √ | ||||
[ |
风扰动; 避障 | 2D | 不确定性 | 民用 | √ | ||||||
[ |
收集数据; 避障 | 搜索问题 | 2D | 不确定性 | 民用 | √ | √ | √ |
模拟退火法(simulated annealing, SA)[
文献[
基于模拟退火法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
提高计算效率 | MTSP问题 | 2D | 确定性 | - | √ | √ | ||||
[ |
兴趣点类型匹配 | 2D | 确定性 | 民用 | √ | √ | |||||
[ |
任务平衡 | 3D | 确定性 | 民用 | √ | √ | √ | ||||
[ |
提高UAV生存能力 | 2D | 确定性 | 军用 | √ | √ | √ | ||||
[ |
搜索问题 | 3D | 确定性 | 民用 | √ |
受生物行为启发, 人工蜂群算法、鸽群算法、果蝇算法、灰狼算法等仿生算法由于其独特优势在多无人机路径规划研究上成为学者们日益关注的焦点.
基于其他仿生算法的多无人机路径规划研究对比
文献 | 研究特点 | 问题类型 | 环境模型 | 协同关系 | |||||||
模型层面 | 算法层面 | ||||||||||
维度 | 确定/不确定 | 军用/民用 | 任务分配 | 约束条件 | 优化目标 | 规划算法 | |||||
[ |
双向规划搜索 | 3D | 确定性 | - | √ | ||||||
[ |
简化协调成本 | 避障及 | 3D | 确定性 | - | √ | √ | √ | |||
[ |
油田检测; 任务变化 | 轨迹优 | 3D | 确定性 | 民用 | √ | √ | ||||
[ |
避障; 收敛速度快 | 化问题 | 3D | 确定性 | - | √ | |||||
[ |
复杂环境 | 3D | 确定性 | 军用 | √ | √ |
人工蜂群算法(artificial bee colony, ABC)[
鸽群优化算法(pigeon-inspired optimization, PIO)[
果蝇优化算法(fruit fly optimization algorithm, FOA)[
灰狼优化算法(grey wolf optimization, GWO)[
多无人机协同路径规划是近几年的研究热点, 该领域研究人员在算法优化和技术方面已经进行了大量工作, 但仍有很多问题需要进一步研究. 本文从以下5个方面提出多无人机协同路径规划目前存在的问题, 并针对这些问题对未来发展趋势进行展望.
1) 协同性. 为了实现特定任务中无人机时间与空间的协同, 当前的研究通常在任务执行之前对无人机进行任务分配, 针对无人机航迹距离、安全性、任务要求等施加约束条件. 当无人机数量较多、任务较复杂、系统较为庞大时, 求解数学模型面临相当大的计算量, 从而无法满足系统的实时性要求, 解的质量也无法得到保证. 此外, 多无人机执行任务时仍需一定程度的人为规划, 自主协同的程度不够深入. 未来的多无人机系统将趋向于大规模、层次化、网络化, 实现更加复杂的任务. 无人机作为系统中的个体, 为了提高与其他各层次中个体的协同性, 分布式网络结构[
2) 异构性. 陆空机器人、多异构无人机等协同是完成复杂任务并提高系统自主性的关键, 尤其在军用领域, 异构无人机集群技术将会颠覆性地改变当前的作战模式. 根据不同的任务需求, 军用无人机存在战斗机、轰炸机、自杀式无人机等多种类型, 多异构无人机路径规划问题的研究对整个作战系统至关重要. 值得注意的是, 异构无人机在结构尺寸、通信协议、负载能力、感知系统、功能实现等各方面存在一定的差异, 很大程度上增加了路径规划的复杂性. 如何设计合理的协同控制架构, 增加更精确全面的约束条件以及如何进一步改进优化算法, 是当前异构无人机路径规划亟待解决的问题.
3) 可扩展性. 针对不同的任务、规模、环境等研究背景, 不同的多无人机路径规划模型和算法相继涌现. 由于约束耦合性强、算法复杂度高等限制, 多数研究只适用于该研究当下的研究背景, 不能或很难实现其他任务、更多无人机协同、不确定环境下的扩展. 鉴于此, 未来研究应在解耦多约束条件、建立简单的规划模型的同时降低算法的复杂度, 对适用度高的规划模块进行集成化处理, 从而实现灵活性高、可扩展性强的规划系统, 进一步推动多无人机协同研究的发展.
4) 动态适应性. 现有的大部分优化算法难以在动态环境下对多无人机进行高效的路径规划. 事实上, 在实际飞行任务中, 通常会出现无法预测的障碍物、扰动以及其他突发状况, 尤其在作战任务中, 战场态势复杂多变, 存在很多快速变化的动态干扰和突发情况. 遇到这类问题时, 需要及时对环境信息进行更新, 并针对新的信息进行航迹重规划. 目前, 航迹重规划研究多见于单无人机中, 多无人机航迹重规划问题复杂度高, 求解难度大, 在短时间内生成轨迹是一个难点. 在未来发展中, 应注重无人机航迹的快速生成, 例如用合理的空间表示方法降低环境复杂度、提高算法的收敛速度等, 另外, 应降低规划目标的优化程度, 重心放在可行性上. 此外, 针对动态环境问题, 深度学习和强化学习算法在众多算法中脱颖而出, 虽然目前对基于深度学习和强化学习的多无人机路径规划研究很多, 但仍有很大的发展空间.
5) 应用性. 目前, 国内外很多学者对多无人机路径规划问题进行了广泛的研究, 但通过实机飞行实验来验证算法的研究[
启发式算法的改进与应用是多无人机协同路径规划研究中的关键部分. 本文的目的是让读者了解近年来多无人机路径规划的研究现状和发展趋势, 并协助读者针对不同研究问题快速获取目前多无人机路径规划问题的研究方法和特点. 具体地, 本文首先整理并分析了多无人机路径规划的研究问题、环境模型和协同性表现, 提出了一种全新的分类方法; 其次, 着重对当前元启发式算法在多无人机路径规划的应用成果进行举例分析, 从多角度、多维度地分析其应用背景、应用特点以及效果优劣, 全面地梳理了相关研究脉络; 最后, 结合当前研究的局限性, 从协同性、异构性、可扩展性、动态适应性、应用性5方面对存在的问题进行分析, 并展望了多无人机路径规划的重点研究方向.
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.
杜云, 贾慧敏, 邵士凯, 等. 面向多目标侦察任务的无人机航线规划[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.
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.
Song B D, Park K, Kim J. Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J]. Computers & Industrial Engineering, 2018, 120: 418-428.
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.
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.
Aggarwal S, Kumar N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges[J]. Computer Communications, 2020, 149: 270-299.
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.
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.
Tarjan R. Depth-first search and linear graph algorithms[J]. SIAM Journal on Computing, 1972, 1(2): 146-160.
Zhou R, Hansen E A. Breadth-first heuristic search[J]. Artificial Intelligence, 2006, 170(4/5): 385-408.
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.
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.
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.
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.
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.
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.
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.
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.
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.
杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[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.
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.
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.
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.
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.
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.
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.
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.
张莹莹, 周德云, 夏欢. 不确定环境下多无人机协同搜索算法研究[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.
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.
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.
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.
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.
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.
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.
刘畅, 谢文俊, 张鹏, 等. 多目标群多基地多无人机协同任务规划[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.
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.
Ergezer H, Leblebicioğlu K. 3D path planning for multiple UAVs for maximum information collection[J]. Journal of Intelligent & Robotic Systems, 2014, 73(1/2/3/4): 737-762.
肖春晖, 邹媛媛, 李少远. 有障碍区域的多无人机多目标点路径规划[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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
10.1177/0020294020915727.]]>
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.
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.
Kennedy J, Eberhart R. Particle swarm optimization[C]. Proceedings of ICNN'95 — International Conference on Neural Networks. Perth, 1995: 1942-1948.
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.
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.
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.
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.
10.5028/jatm.v12.1169.]]>
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680.
Č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.
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.
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.
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.
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.
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.
夏瑞, 赵磊, 吴书宇, 等. 基于人工蜂群算法的无人机协同路径规划[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.
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.
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.
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.
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.
Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Erciyes University, 2005: 1-10.
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.
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.
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
邵壮, 祝小平, 周洲, 等. 三维动态环境下多无人机编队分布式保持控制[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.