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

doi:10.11772/j.issn.1001-9081.2022111763

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (12): 3816-3823.DOI: 10.11772/j.issn.1001-9081.2022111763

Special Issue: 先进计算

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP391.9

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.

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

Figures/Tables 16

Fig.1 Structure of UAV swarm route planning model

Fig.2 Schematic diagram of receding horizon control strategy

Fig.3 Particle motion comparison of PSO and DCPSO algorithms

Fig.4 Path planning flow of UAV swarm based on 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

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

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

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

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

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

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

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

Fig. 6 Artificial potential field diagram

Fig. 7 Route planning of DCPSO algorithm

Fig.8 Convergence curve of DCPSO algorithm

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

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

References 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]	Peigen GAO, Bin SUO. Experimental design and staged PSO-Kriging modeling based on weighted hesitant fuzzy set [J]. Journal of Computer Applications, 2024, 44(7): 2144-2150.
[2]	Xiaoxin DU, Wei ZHOU, Hao WANG, Tianru HAO, Zhenfei WANG, Mei JIN, Jianfei ZHANG. Survey of subgroup optimization strategies for intelligent algorithms [J]. Journal of Computer Applications, 2024, 44(3): 819-830.
[3]	Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios [J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
[4]	Jun LIANG, Zehong HONG, Songsen YU. Image segmentation model based on improved particle swarm optimization algorithm and genetic mutation [J]. Journal of Computer Applications, 2023, 43(6): 1743-1749.
[5]	Zhihui GAO, Meng HAN, Shujuan LIU, Ang LI, Dongliang MU. Survey of high utility itemset mining methods based on intelligent optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1676-1686.
[6]	Zhenhua YU, Zhengqi LIU, Ying LIU, Cheng GUO. Feature selection method based on self-adaptive hybrid particle swarm optimization for software defect prediction [J]. Journal of Computer Applications, 2023, 43(4): 1206-1213.
[7]	Feng XIANG, Zhongzhi LI, Xi XIONG, Binyong LI. Inverse distance weight interpolation algorithm based on particle swarm local optimization [J]. Journal of Computer Applications, 2023, 43(2): 385-390.
[8]	Xuesen MA, Xuemei XU, Gonghui JIANG, Yan QIAO, Tianbao ZHOU. Hybrid adaptive particle swarm optimization algorithm for workflow scheduling [J]. Journal of Computer Applications, 2023, 43(2): 474-483.
[9]	Chunfeng LIU, Zheng LI, Jufeng WANG. Multi-objective optimization of minicells in distributed factories [J]. Journal of Computer Applications, 2023, 43(12): 3824-3832.
[10]	Bing GAO, Ya ZHENG, Jing QIN, Qijie ZOU, Zumin WANG. Network intrusion detection algorithm based on sparrow search algorithm and improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2022, 42(4): 1201-1206.
[11]	Fangxin NIE, Yujia WANG, Xin JIA. Teaching and learning information interactive particle swarm optimization algorithm [J]. Journal of Computer Applications, 2022, 42(3): 874-882.
[12]	Jing ZHANG, Aihong ZHU. Optimization method of automatic train operation speed curve based on genetic algorithm and particle swarm optimization [J]. Journal of Computer Applications, 2022, 42(2): 599-605.
[13]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[14]	ZHANG Meng, GUO Jianquan. Channel structure choice of closed-loop supply chain under uncertain demand and recovery [J]. Journal of Computer Applications, 2021, 41(7): 2100-2107.
[15]	TANG Yanqiang, LI Chenghai, SONG Yafei. Network security situation prediction based on improved particle swarm optimization and extreme learning machine [J]. Journal of Computer Applications, 2021, 41(3): 768-773.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 16

Related Articles 15

Recommended Articles

Metrics