基于动态簇粒子群优化的无人机集群路径规划方法

doi:10.11772/j.issn.1001-9081.2022111763

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (12): 3816-3823.DOI: 10.11772/j.issn.1001-9081.2022111763

基于动态簇粒子群优化的无人机集群路径规划方法

王龙宝¹^,², 栾茵琪¹, 徐亮³, 曾昕³, 张帅⁴, 徐淑芳¹^,²()

^1.河海大学计算机与信息学院, 南京 211000
^2.水利部水利大数据技术重点实验室(河海大学), 南京 211000
^3.长江生态环保集团有限公司, 武汉 430014
^4.中国电建集团昆明勘测设计研究院有限公司, 昆明 650051

收稿日期:2022-11-28 修回日期:2023-03-26 接受日期:2023-03-30 发布日期:2023-05-08 出版日期:2023-12-10
通讯作者: 徐淑芳
作者简介:王龙宝（1977—），男，江苏盐城人，高级工程师，博士，CCF会员，主要研究方向：领域软件、智能计算
栾茵琪（2000—），女，山东菏泽人，硕士研究生，主要研究方向：智能计算
徐亮（1980—），男，江西九江人，高级工程师，主要研究方向：生态环保工程建设管理
曾昕（1990—），男，湖北十堰人，工程师，主要研究方向：生态环保工程建设管理
张帅（1988—），男，云南昆明人，高级工程师，主要研究方向：信息融合；
徐淑芳（1981—），女，安徽青阳人，副教授，博士，主要研究方向：无线通信网络、信息融合。Email：xushufang@hhu.edu.cn
基金资助:
云南省科技厅重大科技专项计划项目(202202AF080003);长江生态环保集团有限公司科研项目(HBZB2022005)

Route planning method of UAV swarm based on dynamic cluster particle swarm optimization

Longbao WANG¹^,², Yinqi LUAN¹, Liang XU³, Xin ZENG³, Shuai ZHANG⁴, Shufang XU¹^,²()

^1.College of Computer and Information，Hohai University，Nanjing Jiangsu 211100，China
^2.Key Laboratory of Water Big Data Technology of Ministry of Water Resources （Hohai University），Nanjing Jiangsu 211100，China
^3.Yangtze Ecology and Environment Company Limited，Wuhan Hubei 430014，China
^4.Power China Kunming Engineering Corporation Limited，Kunming Yunnan 650051，China

Received:2022-11-28 Revised:2023-03-26 Accepted:2023-03-30 Online:2023-05-08 Published:2023-12-10
Contact: Shufang XU
About author:WANG Longbao， born in 1977， Ph. D.， senior engineer. His research interests include domain software， intelligent computing.
LUAN Yinqi， born in 2000， M. S. candidate. Her research interests include intelligent computing.
XU Liang， born in 1980， senior engineer. His research interests include construction management of ecological and environmental protection projects.
ZENG Xin， born in 1990， engineer. His research interests include construction and management of ecological and environmental protection projects.
ZHANG Shuai， born in 1988， senior engineer. His research interests include information fusion.
Supported by:
Major Science and Technology Special Program of Yunnan Province Science and Technology Department(202202AF080003);Scientific Research Project of Yangtze Ecology and Environment Company Limited(HBZB2022005)

摘要/Abstract

摘要：

路径规划对于无人机（UAV）集群的任务执行十分重要，而且高维场景中的计算通常很复杂。群体智能为解决该问题提供了较好的解决思路。粒子群优化（PSO）算法具有参数少、收敛速度快、操作简单等优点，尤其适用于路径规划问题，但它在应用时存在全局搜索能力差、容易陷入局部最优的问题。为了解决上述问题以提升无人机集群路径规划的效果，提出了动态簇粒子群优化（DCPSO）算法。首先，利用人工势场法和滚动时域控制原理建模UAV集群路径规划问题的任务场景；其次，引入Tent混沌映射和动态簇机制进一步提升全局搜索能力和搜索精度；最后，使用DCPSO算法优化模型的目标函数，以获得UAV集群的每个轨迹点的选择。在单峰/多峰、低维/高维不同组合的10种基准测试函数下的仿真实验结果表明，与PSO、鸽子启发优化（PIO）、麻雀搜索算法（SSA）和混沌扰动鸽群优化（CDPIO）算法相比，DCPSO算法具有更好的计算最优值、均值和方差，搜索精度更佳，稳定性更强。此外，UAV集群路径规划应用实例仿真结果也验证了DCPSO算法的性能与效果。

关键词: 粒子群优化, 动态簇机制, 无人机集群, 路径规划, 滚动时域控制

Abstract:

Route planning is very important for the task execution of Unmanned Aerial Vehicle （UAV） swarm， and the computation is usually complex in high dimensional scenarios. Swarm intelligence has provided a good solution for this problem. Particle Swarm Optimization （PSO） algorithm is especially suitable for route planning problem because of its advantages such as few parameters， fast convergence and simple operation. However， PSO algorithm has poor global search ability and is easy to fall into local optimum when applied to route planning. In order to solve the problems above and improve the effect of UAV swarm route planning， a Dynamic Cluster Particle Swarm Optimization （DCPSO） algorithm was proposed. Firstly， artificial potential field method and receding horizon control principle were used to model the task scenario of route planning problem of UAV swarm. Secondly， Tent chaotic map and dynamic cluster mechanism were introduced to further improve the global search ability and search accuracy. Finally， DCPSO algorithm was used to optimize the objective function of the model to obtain each trajectory point selection of UAV swarm. On 10 benchmark functions with different combinations of unimodal/multimodal and low-dimension/high-dimension， simulation experiments were carried out. The results show that compared with PSO algorithm， Pigeon-Inspired Optimization （PIO）， Sparrow Search Algorithm （SSA） and Chaotic Disturbance Pigeon-Inspired Optimization （CDPIO） algorithm， DCPSO algorithm has better optimal value， mean value and variance， better search accuracy and stronger stability. Besides， the performance and effect of DCPSO algorithm were demonstrated in the route planning application instances of UAV swarm simulation experiments.

Key words: Particle Swarm Optimization (PSO), dynamic cluster mechanism, Unmanned Aerial Vehicle (UAV) swarm, route planning, receding horizon control

中图分类号:

TP391.9

王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 计算机应用, 2023, 43(12): 3816-3823.

Longbao WANG, Yinqi LUAN, Liang XU, Xin ZENG, Shuai ZHANG, Shufang XU. Route planning method of UAV swarm based on dynamic cluster particle swarm optimization[J]. Journal of Computer Applications, 2023, 43(12): 3816-3823.

图/表 16

图1 无人机集群路径规划模型的结构

Fig.1 Structure of UAV swarm route planning model

图2 滚动时域控制策略示意图

Fig.2 Schematic diagram of receding horizon control strategy

图3 PSO和DCPSO算法的粒子运动对比

Fig.3 Particle motion comparison of PSO and DCPSO algorithms

图4 基于DCPSO的无人机集群路径规划流程

Fig.4 Path planning flow of UAV swarm based on DCPSO

表1 PSO、PIO、SSA和DCPSO算法的参数

Tab.1 Parameters for PSO， PIO， SSA and DCPSO algorithms

算法	参数	描述	值
PSO	N	种群数量	50
	$c 1$	学习因子（认知部分）	2
	$c 2$	学习因子（社会部分）	2
	$w$	惯性权重因子	1
PIO	$N$	种群数量	50
PIO	$R$	地图和指南针影响因子	0.3
SSA	$N$	种群数量	50
	$P D / %$	发现者	20
	$S D / %$	警觉者	10
DCPSO	$N$	种群数量	50
	$c 1$	学习因子（认知部分）	2
	$c 2$	学习因子（社会部分）	2
	$w$	惯性权重因子	1

表1 PSO、PIO、SSA和DCPSO算法的参数

Tab.1 Parameters for PSO， PIO， SSA and DCPSO algorithms

算法	参数	描述	值
PSO	N	种群数量	50
	$c 1$	学习因子（认知部分）	2
	$c 2$	学习因子（社会部分）	2
	$w$	惯性权重因子	1
PIO	$N$	种群数量	50
PIO	$R$	地图和指南针影响因子	0.3
SSA	$N$	种群数量	50
	$P D / %$	发现者	20
	$S D / %$	警觉者	10
DCPSO	$N$	种群数量	50
	$c 1$	学习因子（认知部分）	2
	$c 2$	学习因子（社会部分）	2
	$w$	惯性权重因子	1

表2 单峰低维函数的测试结果

Tab.2 Test results of unimodal low-dimensional functions

函数名	算法	最优值	平均值	方差	耗时/s
Easom	PSO	-4.286 4×10^-5	-6.061 5×10^-6	1.302 8×10^-5	1.651 6
	PIO	-1.0	-0.999 9	7.266 9×10^-6	6.731 4
	SSA	-0.999 9	-0.999 9	3.888 6×10^-7	2.064 8
	CDPIO	-1.0	-0.999 9	2.879 7×10^-17	—
	DCPSO	-2.675 2×10^-9	-2.675 2×10^-9	0	13.093 3
Matyas	PSO	0.015 0	0.229 2	0.269 8	1.360 0
	PIO	9.498 9×10^-63	3.321 0×10^-30	2.266 6×10^-29	6.790 1
	SSA	0	2.391 7×10^-17	1.242 0×10^-16	2.043 6
	CDPIO	1.046 7×10^-101	2.986 7×10^-95	2.376 5×10^-188	—
	DCPSO	0	0	0	12.866 3

表3 单峰高维函数的测试结果

Tab.3 Test results of unimodal high-dimensional functions

函数名	算法	最优值	平均值	方差	耗时/s
Sumsquares	PSO	6.675 7×10^-6	6.892 1×10^-6	6.67×10^-6	5.425 6
	PIO	1.926 6×10^-17	6.055 5×10^-14	3.777 3×10^-13	9.477 7
	SSA	0	4.495 0×10^-10	1.361 6×10^-9	3.857 2
	DCPSO	0	0	0	16.247 0
Sphere	PSO	9.144 3×10^-4	2.483 7×10^-2	9.12×10^-4	14.595 4
	PIO	3.147 7×10^-24	3.644 5×10^-21	2.820 6×10^-20	12.703 2
	SSA	0	7.332 8×10^-8	3.411 3×10^-7	3.310 4
	DCPSO	0	0	0	15.566 5

表4 多峰低维函数的测试结果

Tab.4 Test results of multimodal low-dimensional functions

函数名	算法	最优值	平均值	方差	耗时/s
Bohachevs-ky1	PSO	2.124 7×10^-11	1.297 5×10^-8	2.293 5×10^-8	5.343 8
	PIO	0	0	0	9.163 6
	SSA	0	1.811 7×10^-17	5.499 4×10^-17	3.582 6
	CDPIO	0	0	0	—
	DCPSO	0	0	0	12.871 4
Eggcrate	PSO	7.468 4×10^-12	3.484 2×10^-8	4.367 4×10^-8	6.234 7
	PIO	9.961 7×10^-61	3.902 3×10^-13	3.875 3×10^-12	8.345 3
	SSA	9.375 7×10^-9	5.087 9×10^-7	5.915 2×10^-7	2.092 5
	DCPSO	0	0	0	12.851 3
Schaffer	PSO	3.215 4×10^-11	5.369 7×10^-7	6.324 7×10^-9	7.267 4
	PIO	0	1.811 7×10^-14	5.337 2×10^-14	9.655 0
	SSA	0	1.690 1×10^-13	9.099 3×10^-13	2.114 9
	CDPIO	0	0	0	—
	DCPSO	0	0	0	12.904 8
Bohachevs-ky3	PSO	1.514 8×10^-11	4.398 2×10^-9	7.269 4×10^-9	5.639 8
	PIO	0	4.440 8×10^-18	3.222 3×10^-17	8.161 9
	SSA	0	8.173 7×10^-11	4.400 4×10^-10	2.190 1
	CDPIO	0	0	0	—
	DCPSO	0	0	0	13.133 4

表5 多峰高维函数的测试结果

Tab.5 Test results of multimodal high-dimensional functions

函数名	算法	最优值	平均值	方差	耗时/s
Rastrigin	PSO	63.489 1	74.234 6	9.116 8	24.284 6
	PIO	0	1.225 6×10^-13	1.231 9×10^-14	20.417 8
	SSA	0	6.296 3×10^-5	0.000 2	15.781 6
	CDPIO	-3.005 4	-3.005 4	0	—
	DCPSO	0	0	0	43.357 3
Ackley	PSO	2.389 4	16.081 6	8.514 4	70.364 0
	PIO	1.325 4×10^-10	6.737 3×10^-10	1.060 7×10^-9	46.840 7
	SSA	4.440 8×10^-16	1.961 9×10^-5	0.000 1	31.933 4
	DCPSO	4.440 8×10^-16	4.440 8×10^-16	0	116.100 0

表6 实验参数设置

Tab.6 Experimental parameter setting

参数	描述	值
L_area/km	飞行区域长度	100
W_area/km	飞行区域宽度	100
H_area/km	飞行区域高度	20
Num×Num	网格数	100×100
UAVS=［uav₁，uav₂，uav₃，uav₄］	无人机集群初始坐标	（10，20，15）
		（20，10，15）
		（10，10，15）
		（10，15，15）
Obs=［obs₁，obs₂］	障碍物中心位置	（35，40，15）
Obs=［obs₁，obs₂］	障碍物中心位置	（50，50，15）
Obj	目标点坐标	（85，80，15）
φ /（°）	无人机最大航向角	45

图5 无人机集群、障碍物和轨迹终点分布图

Fig.5 Distribution map of UAV swarm， obstacles and trajectory end point

图6 人工势场图

Fig. 6 Artificial potential field diagram

图7 DCPSO算法的路径规划

Fig. 7 Route planning of DCPSO algorithm

图8 DCPSO算法的收敛曲线

Fig.8 Convergence curve of DCPSO algorithm

图9 多障碍环境下DCPSO算法的路径规划

Fig. 9 Route planning of DCPSO algorithm in multi-obstacle environment

表7 DCPSO算法进行30次独立重复实验的结果

Tab. 7 Results of using DCPSO algorithm to conduct 30 independent repeated experiments

序号	轨迹长度/km	序号	轨迹长度/km	序号	轨迹长度/km
1	108.784 7	11	109.477 1	21	108.752 3
2	108.888 3	12	108.441 6	22	108.923 8
3	108.577 6	13	109.027 4	23	109.027 4
4	109.613 2	14	108.338 0	24	108.545 2
5	109.406 1	15	109.855 8	25	108.820 3
6	108.888 3	16	109.234 5	26	108.234 5
7	109.406 1	17	109.027 4	27	109.130 9
8	109.406 1	18	109.130 9	28	108.902 5
9	109.234 5	19	109.441 6	29	108.652 5
10	108.820 3	20	108.545 2	30	109.006 0

参考文献 16

1	LYU H， YIN Y. Fast path planning for autonomous ships in restricted waters［J］. Applied Sciences， 2018， 8（12）： No.2592. 10.3390/app8122592
2	VOLKAN PEHLIVANOGLU Y. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV［J］. Aerospace Science and Technology， 2012， 16（1）： 47-55. 10.1016/j.ast.2011.02.006
3	XUE J， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm［J］. Systems Science and Control Engineering， 2020， 8（1）： 22-34. 10.1080/21642583.2019.1708830
4	DUAN H， QIAO P. 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. 10.1108/ijicc-02-2014-0005
5	BHARNE P K， GULHANE V S， YEWALE S K. Data clustering algorithms based on swarm intelligence［C］// Proceedings of the 3rd International Conference on Electronics Computer Technology. Piscataway： IEEE， 2011： 407-411. 10.1109/icectech.2011.5941931
6	KENNEDY J， EBERHART R. Particle swarm optimization［C］// Proceedings of the 1995 International Conference on Neural Networks — Volume 4. Piscataway： IEEE， 1995： 1942-1948.
7	鲁亮亮，代冀阳，应进，等. 基于APSODE-MS算法的无人机航迹规划［J］. 控制与决策， 2022， 37（7）：1695-1704.
	LU L L， DAI J Y， YING J， et al. UAV trajectory planning based on APSODE-MS algorithm［J］. Control and Decision， 2022， 37（7）： 1695-1704.
8	NAYEEM G M， FAN M， AKHTER Y. A time-varying adaptive inertia weight based modified PSO algorithm for UAV path planning［C］// Proceedings of the 2nd International Conference on Robotics， Electrical and Signal Processing Techniques. Piscataway： IEEE， 2021： 573-576. 10.1109/icrest51555.2021.9331101
9	LI X， ZHAO Y， ZHANG J， et al. A hybrid PSO algorithm based flight path optimization for multiple agricultural UAVs［C］// Proceedings of the IEEE 28th International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2016： 691-697. 10.1109/ictai.2016.0110
10	田兴华，张纪会，李阳. 基于混沌映射的自适应退火型粒子群算法［J］. 复杂系统与复杂性科学， 2020， 17（1）：45-54.
	TIAN X H， ZHANG J H， LI Y. An adaptive annealing particle swarm optimization based on chaotic mapping ［J］. Complex Systems and Complexity Science， 2020， 17（1）： 45-54.
11	ZHANG R， SUN M， PAN C. Micro-nano satellite resource allocation algorithm based on chaos-filled PSO ［C］// Proceedings of the 6th International Symposium on Computer and Information Processing Technology. Piscataway： IEEE， 2021： 204-208. 10.1109/iscipt53667.2021.00048
12	KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots ［J］. The International Journal of Robotics Research， 1986， 5（1）： 90-98. 10.1177/027836498600500106
13	段海滨，杨之元. 基于柯西变异鸽群优化的大型民用飞机滚动时域控制［J］. 中国科学：技术科学， 2018， 48（3）：277-288. 10.1360/n092017-00211
	DUAN H B， ZHANG Z Y. Large civil aircraft receding horizon control based on Cauthy mutation pigeon inspired optimization ［J］. SCIENTIA SINICA Technologica， 2018， 48（3）： 277-288. 10.1360/n092017-00211
14	LIANG X， WANG D， HUANG M. Improved grey wolf optimizer and their applications［C］// Proceedings of the IEEE 7th International Conference on Computer Science and Network Technology. Piscataway： IEEE， 2019： 107-110. 10.1109/iccsnt47585.2019.8962504
15	XU S， XU D， MAO Y， et al. A cooperative dynamic cluster in multitasking mobile networks ［J］. Intelligent Automation and Soft Computing， 2017， 23（4）： 567-572. 10.1080/10798587.2017.1316079
16	LI L， XU S， NIE H， et al. Collaborative target search algorithm for UAV based on chaotic disturbance pigeon-inspired optimization［J］. Applied Sciences， 2021， 11（16）： No.7358. 10.3390/app11167358

[1]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[2]	梁军, 洪泽泓, 余松森. 基于改进粒子群优化算法和遗传变异的图像分割模型[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1743-1749.
[3]	于振华, 刘争气, 刘颖, 郭城. 基于自适应混合粒子群优化的软件缺陷预测特征选择方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1206-1213.
[4]	马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 474-483.
[5]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[6]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[7]	柳春锋, 李峥, 王居凤. 分布式工厂中微型制造单元多目标优化[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3824-3832.
[8]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[9]	盖荣丽, 高守传, 李明霞. 粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2177-2183.
[10]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[11]	高兵, 郑雅, 秦静, 邹启杰, 汪祖民. 基于麻雀搜索算法和改进粒子群优化算法的网络入侵检测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1201-1206.
[12]	聂方鑫, 王宇嘉, 贾欣. 教与学信息交互粒子群优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 874-882.
[13]	张京, 朱爱红. 基于遗传算法和粒子群优化的列车自动驾驶速度曲线优化方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[14]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.
[15]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.

基于动态簇粒子群优化的无人机集群路径规划方法

Route planning method of UAV swarm based on dynamic cluster particle swarm optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 16

相关文章 15

编辑推荐

Metrics