Two-dimensional Global Path Planning Based on Potential Field Enhanced Fireworks Algorithm

doi:10.12382/bgxb.2023.0697

Abstract

Abstract:

High-quality path is an important prerequisite for future unmanned autonomous combat. A path planning method based on potential-field enhanced fireworks algorithm (PEFWA) is proposed for the path planning in complex obstacle environment. A planning space model and a dynamic dimension path description model are established, and an objective function including the feasibility factor and the length factor is set up to transform the path planning problem into an optimization problem. A dynamic dimension fireworks initialization strategy and a dimension adding and deleting strategy are designed to make the adjacent dimension individuals meet the distance constraint. An explosion amplitude calculation method and a continuous dimension selection method based on obstacle space information are proposed to generate the improved explosion sparks foe improving the global search ability. A potential field is generated to enhance the explosion spark by introducing the potential field guidance strategy, and the selected dimension is searched for many times in the direction of resultant force to improve the local optimization ability. The cross-combination strategy is used to generate the mutation sparks, and the dimensional individuals beyond the planning space are deleted to improve the efficient generation ability of diversity fireworks. A double-layer tournament selection strategy based on cosine similarity is proposed to improve the continuation ability of fireworks features. The same benchmark function is used to compare PEFWA with fireworks algorithm (FWA), particle swarm optimization (PSO) algorithm and genetic algorithm (GA). The results show that the optimization performance of PEFWA is stronger. Multiple path planning simulation experiments were carried out in the same complex obstacle environment to verify the effectiveness of each module in PEFWA. Compared with PSO, GA and A^* algorithms, PEFWA has the advantages in planning success rate, path length, path smoothness and robustness of results. PEFWA is effective for two-dimensional global path planning.

Key words: global path planning, fireworks algorithm, potential function, dynamic dimension, cross combination

CLC Number:

TP242.6

SUN Pengyao, HUANG Yanyan, WANG Kaisheng. Two-dimensional Global Path Planning Based on Potential Field Enhanced Fireworks Algorithm[J]. Acta Armamentarii, 2024, 45(10): 3499-3518.

Figures/Tables 25

References 22

[1]	李超, 王瑞星, 黄建忠, 等. 稀疏奖励下基于强化学习的无人集群自主决策与智能协同[J]. 兵工学报, 2023, 44(6): 1537-1546. doi: 10.12382/bgxb.2022.0177
	LI C, WANG R X, HUANG J Z, et al. Autonomous decision-making and intelligent collaboration of UAV swarms based on reinforcement learning with sparse rewards[J]. Acta Armamentarii, 2023, 44(6): 1537-1546. (in Chinese) doi: 10.12382/bgxb.2022.0177
[2]	张哲, 吴剑, 代冀阳, 等. 基于改进A^*算法的多无人机协同战术规划[J]. 兵工学报, 2020, 41(12): 2530-2539. doi: 10.3969/j.issn.1000-1093.2020.12.019
	ZHANG Z, WU J, DAI J Y, et al. Cooperative tactical planning for multi-UAVs based on improved A^* algorithm[J]. Acta Armamentarii, 2020, 41(12): 2530-2539. (in Chinese)
[3]	袁静妮, 杨林, 唐晓峰, 等. 基于改进RRT*与行驶轨迹优化的智能汽车运动规划[J]. 自动化学报, 2022, 48(12): 2941-2950.
	YUAN J N, YANG L, TANG X F, et al. Autonomous vehicle motion planning based on improved RRT* algorithm and trajectory optimization[J]. Acta Automatica Sinica, 2022, 48(12): 2941-2950. (in Chinese)
[4]	孙鹏耀, 黄炎焱, 潘尧. 基于改进势场法的移动机器人路径规划[J]. 兵工学报, 2020, 41(10): 2106-2121. doi: 10.3969/j.issn.1000-1093.2020.10.021
	SUN P Y, HUANG Y Y, PAN Y. Path planning of mobile robots based on improved potential field algorithm[J]. Acta Armamentarii, 2020, 41(10): 2106-2121. (in Chinese) doi: 10.3969/j.issn.1000-1093.2020.10.021
[5]	赵鹏程, 宋保维, 毛昭勇, 等. 基于改进的复合自适应遗传算法的UUV水下回收路径规划[J]. 兵工学报, 2022, 43(10): 2598-2608.
	ZHAO P C, SONG B W, MAO Z Y, et al. Path planning for UUV underwater recovery based on improved composite adaptive genetic algorithm[J]. Acta Armamentarii, 2022, 43(10): 2598-2608. (in Chinese) doi: 10.12382/bgxb.2021.0474
[6]	张瑜, 宋荆洲, 张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人, 2020, 42(5): 617-625. doi: 10.13973/j.cnki.robot.190649
	ZHANG Y, SONG J Z, ZHANG Q Q. Local path planning of outdoor cleaning robot based on an improved DWA[J]. Robot, 2020, 42(5): 617-625. (in Chinese) doi: 10.13973/j.cnki.robot.190649
[7]	高明, 唐洪, 张鹏. 机器人集群路径规划技术研究现状[J]. 国防科技大学学报, 2021, 43(1): 127-138.
	GAO M, TANG H, ZHANG P. Survey of path planning technologies for robots swarm[J]. Journal of National University of Defense Technology, 2021, 43(1): 127-138. (in Chinese)
[8]	李波, 杨志鹏, 贾卓然, 等. 一种无监督学习型神经网络的无人机全区域侦察路径规划[J]. 西北工业大学学报, 2021, 39(1): 77-84.
	LI B, YANG Z P, JIA Z R, et al. An unsupervised learning neural network for planning UAV full-area reconnaissance path[J]. Journal of Northwestern Polytechnical University, 2021, 39(1): 77-84. (in Chinese)
[9]	LUAN P G, THINH N T. Hybrid genetic algorithm based smooth global-path planning for a mobile robot[J]. Mechanics Based Design of Structures and Machines, 2023, 51(3): 1758-1774.
[10]	张震, 方群, 宋金丰, 等. 基于协同粒子群算法的航天器集群动态路径规划算法研究[J]. 西北工业大学学报, 2021, 39(6): 1222-1232.
	ZHANG Z, FANG Q, SONG J F, et al. Research on dynamic path planning algorithm of spacecraft cluster based on cooperative particle swarm algorithm[J]. Journal of Northwestern Polytechnical University, 2021, 39(6): 1222-1232. (in Chinese)
[11]	WU P F, LI T, SONG G F. UCAV path planning based on improved chaotic particle swarm optimization[C]// Proceedings of the 2020 Chinese Automation Congress. Shanghai, China: IEEE, 2020: 1069-1073.
[12]	TAN Y, ZHU Y C. Fireworks algorithm for optimization[C]// Proceedings of the International Conference on Advances in Swarm Intelligence. Beijing, China: Springer, 2010: 355-364.
[13]	余冬华, 郭茂祖, 刘晓燕, 等. 改进选择策略的烟花算法[J]. 控制与决策, 2020, 35(2): 389-395.
	YU D H, GUO M Z, LIU X Y, et al. An improved selection strategy of firework algorithm[J]. Control and Decision, 2020, 35(2): 389-395. (in Chinese)
[14]	滕志军, 李哲, 王幸幸, 等. 无线传感器网络中基于μ律爆炸算子的烟花虚拟力混合覆盖策略[J]. 控制理论与应用, 2023, 40(5): 817-824.
	TENG Z J, LI Z, WANG X X, et al. Fireworks virtual force mixture covering strategy based on μ-law explosion operator in wireless sensor networks[J]. Control Theory & Applications, 2023, 40(5): 817-824. (in Chinese)
[15]	邹适宇, 李复名, 谢爱平, 等. 基于改进烟花算法的资源分配[J]. 航空学报, 2021, 42(12): 324716. doi: 10.7527/S1000-6893.2020.24716
	ZOU S Y, LI F M, XIE A P, et al. Resource allocation based on improved fireworks algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(12): 324716. (in Chinese) doi: 10.7527/S1000-6893.2020.24716
[16]	余修武, 李佩, 刘永, 等. 基于烟花优化的WSN数据融合算法[J]. 华中科技大学学报, 2023, 51(5): 112-118.
	YU X W, LI P, LIU Y, et al. Data fusion of WSN based on fireworks algorithm optimization[J]. Journal of Huazhong University of Science and Technology, 2023, 51(5): 112-118. (in Chinese)
[17]	申晓宁, 许笛, 宋丽妍, 等. 采用离散烟花算法的移动群智感知异构任务分配[J]. 计算机工程与科学, 2023, 45(2): 321-331.
	SHEN X N, XU D, SONG L Y, et al. Heterogeneous task assignment of mobile crowdsensing based on a discrete fireworks algorithm[J]. Computer Engineering & Science, 2023, 45(2): 321-331. (in Chinese)
[18]	ZHAO H T, ZHANG C S, NING J X. A core firework updating information guided dynamic fireworks algorithm for global optimization[J]. Soft Computing, 2020, 24(2): 1185-1211.
[19]	YU J Y, GUO J S, ZHANG X F, et al. A Novel tent-levy fireworks algorithm for the UAV task allocation problem under uncertain environment[J]. IEEE Access, 2022, 10: 102373-102385.
[20]	薛裕颖, 张祥银, 张国梁, 等. 基于量子行为烟花算法的移动机器人路径规划及平滑[J]. 控制理论与应用, 2019, 36(9): 1398-1408.
	XUE Y Y, ZHANG X Y, ZHANG G L, et al. Path planning and smoothing based on quantum-behaved fireworks algorithm for mobile robot[J]. Control Theory & Applications, 2019, 36(9): 1398-1408. (in Chinese)
[21]	张玮, 马焱, 赵捍东, 等. 基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J]. 控制与决策, 2019, 34(2): 335-343.
	ZHANG W, MA Y, ZHAO H D, et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J]. Control and Decision, 2019, 34(2): 335-343. (in Chinese)
[22]	ZHANG X Y, XIA S, ZHANG T, et al. Hybrid FWPS cooperation algorithm based unmanned aerial vehicle constrained path planning[J]. Aerospace Science and Technology, 2021, 118: 107004.

函数	表达式	范围
Sphere	f(x)= $∑ i = 1 D x i 2$	[-100,100]
Rosenbrock	f(x)= $∑ i = 1 D - 1$ (100 $(x i + 1 - x i 2) 2$ + $(x i - 1) 2$ )	[-30,30]
Griewank	f(x)=1+ $∑ i = 1 D x i 2 4000$ + $∏ i = 1 D$ cos ( $x i i$ )	[-600,600]
Rastrigin	f(x)= $∑ i = 1 D$ ( $x i 2$ -10cos (2πx_i)+10)	[-5.12,5.12]
Ackley	f(x)= -20exp (-0.2 $1 D ∑ i = 1 D x i 2$ )- exp ( $1 D ∑ i = 1 D$ cos (2πx_i))+20+e	[-32,32]
Rotated hyper ellipsoid	f(x)= $∑ i = 1 D$ ( $∑ j = 1 i x j 2$ )²	[-65.536, 65.536]
Axis parallel hyper ellipsoid	f(x)= $∑ i = 1 D$ i $x i 2$	[-5.12,5.12]
Sphere_p	f(x)= $∑ i = 1 D x i 2$ +1000× $N \| x i \| ≤ 1$	[-100,100]

函数	表达式	范围
Sphere	f(x)= $∑ i = 1 D x i 2$	[-100,100]
Rosenbrock	f(x)= $∑ i = 1 D - 1$ (100 $(x i + 1 - x i 2) 2$ + $(x i - 1) 2$ )	[-30,30]
Griewank	f(x)=1+ $∑ i = 1 D x i 2 4000$ + $∏ i = 1 D$ cos ( $x i i$ )	[-600,600]
Rastrigin	f(x)= $∑ i = 1 D$ ( $x i 2$ -10cos (2πx_i)+10)	[-5.12,5.12]
Ackley	f(x)= -20exp (-0.2 $1 D ∑ i = 1 D x i 2$ )- exp ( $1 D ∑ i = 1 D$ cos (2πx_i))+20+e	[-32,32]
Rotated hyper ellipsoid	f(x)= $∑ i = 1 D$ ( $∑ j = 1 i x j 2$ )²	[-65.536, 65.536]
Axis parallel hyper ellipsoid	f(x)= $∑ i = 1 D$ i $x i 2$	[-5.12,5.12]
Sphere_p	f(x)= $∑ i = 1 D x i 2$ +1000× $N \| x i \| ≤ 1$	[-100,100]

函数	类别	PEFWA	FWA	PSO算法	GA
Sphere	平均值	6.16×10^-162	1.07×10^-157	2.10×10^-1	1.91×10^-4
	SD	1.79×10^-161	3.22×10^-157	1.28×10^-1	5.87×10^-5
Rosenbrock	平均值	0.0031	28.6666	347.9364	45.4041
	SD	0.0094	0.3433	410.7480	27.6569
Griewank	平均值	0.0027	0.0376	0.0642	0.6784
	SD	0.0007	0.0229	0.0193	0.3794
Rastrigin	平均值	0	0	63.8890	0.0427
	SD	0	0	12.2414	0.0220
Ackley	平均值	4.35×10^-15	4.44×10^-16	3.2212	0.0108
	SD	1.07×10^-15	0	0.5522	0.0021
Rotated hyper ellipsoid	平均值	1.72×10^-308	2.96×10^-323	1.3955	3.40×10^-7
	SD	0	0	0.6911	3.69×10^-7
Axis parallel hyper ellipsoid	平均值	5.78×10^-164	9.17×10^-160	0.3875	8.26×10^-4
	SD	0	2.75×10^-159	0.2871	2.74×10^-4
Sphere_p	平均值	30.0007	257.4851	153.4725	1.7347×10⁴
	SD	0.0008	110.5706	46.2182	2.5749×10³

函数	类别	PEFWA	FWA	PSO算法	GA
Sphere	平均值	6.16×10^-162	1.07×10^-157	2.10×10^-1	1.91×10^-4
	SD	1.79×10^-161	3.22×10^-157	1.28×10^-1	5.87×10^-5
Rosenbrock	平均值	0.0031	28.6666	347.9364	45.4041
	SD	0.0094	0.3433	410.7480	27.6569
Griewank	平均值	0.0027	0.0376	0.0642	0.6784
	SD	0.0007	0.0229	0.0193	0.3794
Rastrigin	平均值	0	0	63.8890	0.0427
	SD	0	0	12.2414	0.0220
Ackley	平均值	4.35×10^-15	4.44×10^-16	3.2212	0.0108
	SD	1.07×10^-15	0	0.5522	0.0021
Rotated hyper ellipsoid	平均值	1.72×10^-308	2.96×10^-323	1.3955	3.40×10^-7
	SD	0	0	0.6911	3.69×10^-7
Axis parallel hyper ellipsoid	平均值	5.78×10^-164	9.17×10^-160	0.3875	8.26×10^-4
	SD	0	2.75×10^-159	0.2871	2.74×10^-4
Sphere_p	平均值	30.0007	257.4851	153.4725	1.7347×10⁴
	SD	0.0008	110.5706	46.2182	2.5749×10³

参数	数值
规划空间范围/km	100×100
基地坐标/km	(0,0)
目标点坐标/km	(100,100)
各节点位置与威胁障碍范围(x,y,r)/km	(42,50,20); (15,12,10); (66,77,15); (40,15,12); (98,80,15); (15,85,18); (10,50,11); (80,10,10); (83,40,15);
最大循环次数T	500
惩罚算子F^penalty	500
烟花数量N^F	30
基础烟花算法爆炸参数	A^E=100,S^E=20,a=0.2, b=0.8, $S G i$ =3
基础烟花算法固定优化维数	30
相邻路径点距离约束 [l_min,l_max]	[1,2]
势场增强火花参数	S^θ=3,S^PF=3
交叉变异参数	S^C=50
改进选择策略参数	ρ^CH=0.99,N^U=10,N^FS=20, N^IS=10,b^CH=0.8