基于势场增强烟花算法的二维全局路径规划

doi:10.12382/bgxb.2023.0697

摘要/Abstract

摘要：

高质量路径是未来无人自主作战的重要前提,针对复杂障碍环境下路径规划问题,提出基于势场增强烟花算法(Potential-field Enhanced Fireworks Algorithm, PEFWA)的路径规划方法。建立规划空间模型与动态维数路径描述模型,设立包含可行性因素与长度因素的目标函数,将路径规划问题转化为最优化问题;设计动态维数烟花初始化与维度增删操作,使相邻维度个体满足距离约束;提出基于障碍空间信息的爆炸幅度计算方法和连续维度选择方法,生成改进爆炸火花,提高全局搜索能力;引入势场引导策略,生成势场增强爆炸火花,让所选维度在合力方向上多次搜索,提高局部优化能力;采用交叉组合策略生成变异火花,并对超出规划空间的维度个体进行删减操作,提高多样性烟花高效产生能力;提出基于余弦相似度的双层锦标赛选择策略,提高烟花特征延续能力。采用相同基准函数,将PEFWA与烟花算法(Fireworks Algorithm, FWA)、粒子群优化(Particle Swarm Optimization, PSO)算法、遗传算法(Genetic Algorithm, GA)进行对比。研究结果表明:PEFWA的优化性能更强;在相同复杂障碍环境下进行多次路径规划仿真实验,验证了PEFWA中各个模块的有效性,与PSO算法、GA、A^*算法相比,PEFWA在规划成功率、路径长度、路径光滑度、结果鲁棒性等方面均有优势;PEFWA在二维全局路径规划问题上具有有效性与优越性。

关键词: 全局路径规划, 烟花算法, 势函数, 动态维数, 交叉组合

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

中图分类号:

TP242.6

孙鹏耀, 黄炎焱, 王凯生. 基于势场增强烟花算法的二维全局路径规划[J]. 兵工学报, 2024, 45(10): 3499-3518.

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.

图/表 25

图1 势场增强烟花算法流程

Fig.1 Flowchart of PEFWA

表1 测试函数

Table 1 Testing functions

函数	表达式	范围
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]

表1 测试函数

Table 1 Testing functions

函数	表达式	范围
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]

表2 函数测试结果对比

Table 2 Comparison of function test results

函数	类别	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³

图2 平均适应度值变化曲线对比

Fig.2 Change curves of average fitness value

表3 改进模块验证实验参数

Table 3 Parameters of improved module validation experiments

参数	数值
规划空间范围/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

表3 改进模块验证实验参数

Table 3 Parameters of improved module validation experiments

参数	数值
规划空间范围/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

图3 实验1路径规划结果

Fig.3 Results of path planning in Experiment 1

图4 实验1收敛图

Fig.4 Convergence plot for Experiment 1

图5 实验2路径规划结果

Fig.5 Results of path planning in Experiment 2

图6 实验2收敛图

Fig.6 Convergence plot for Experiment 2

图7 实验3路径规划结果

Fig.7 Results of path planning in Experiment 3

图8 实验4路径规划结果

Fig.8 Results of path planning in Experiment 4

图9 与规划结果余弦相似度达到阈值的路径示意图

Fig.9 Schematic diagram of similar paths

图10 被选出的部分烟花示意图

Fig.10 Illustrations of part of the selected fireworks

图11 实验5路径规划结果

Fig.11 Results of path planning in Experiment 5

图12 被选出的部分烟花示意图

Fig.12 Illustrations of part of the selected fireworks

图13 实验6路径规划结果

Fig.13 Results of path planning in Experiment 6

图14 多次实验平均适应度变化情况对比

Fig.14 Comparison of the average fitness changes of multiple experiments

表4 模块验证实验数据统计结果

Table 4 Parameters of improved module validation experiments

序号	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
2	0
3	94	157.76	7.38	126.98	8134.64	0.958
4	100	155.80	0.65	40.3	295.43	0.960
5	100	152.74	0.27	8.04	4.42	0.992
6	100	151.58	0.10	6.68	1.80	0.998

表4 模块验证实验数据统计结果

Table 4 Parameters of improved module validation experiments

序号	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
2	0
3	94	157.76	7.38	126.98	8134.64	0.958
4	100	155.80	0.65	40.3	295.43	0.960
5	100	152.74	0.27	8.04	4.42	0.992
6	100	151.58	0.10	6.68	1.80	0.998

图15 不同算法最优路径结果对比

Fig.15 Comparison of optimal path results of different algorithms

图16 不同算法平均适应度变化情况对比

Fig.16 Comparison of average fitness changes of different algorithms

表5 算法对比数据统计结果

Table 5 Results of data statistics for multiple algorithms

算法	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
PSO算法	91	181.60	1758.47	46.68	5232.79	0.963
GA	97	176.74	125.47	46.28	2580.37	0.983
A^*算法	100	210.15	14.17			0.954
PEFWA	100	151.58	0.10	6.68	1.80	0.998

表5 算法对比数据统计结果

Table 5 Results of data statistics for multiple algorithms

算法	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
PSO算法	91	181.60	1758.47	46.68	5232.79	0.963
GA	97	176.74	125.47	46.28	2580.37	0.983
A^*算法	100	210.15	14.17			0.954
PEFWA	100	151.58	0.10	6.68	1.80	0.998

表6 复杂障碍环境参数

Table 6 Complex obstacle environment parameters

参数	设定值
规划空间范围/km	100×100
起点坐标/km	(0,0)
目标点坐标/km	(100,100)
各障碍空间范围 (x/km,y/km),q)	(61,100,1);(61,6,1);(69,6,1);(69,100,1); (41,79,2);(41,0,2);(49,0,2);(49,79,2); (6,26,3);(31,26,3);(31,6,3);(34,6,3); (34,29,3);(6,29,3);(6,79,4);(6,51,4); (34,51,4);(34,54,4);(9,54,4);(9,79,4); (76,11,5);(94,11,5);(94,39,5);(76,39,5); (76,46,6);(84,46,6);(84,100,6);(76,100,6)
T	500
F^penalty	500
N^F	30
爆炸参数	A^E=100,S^E=20,a=0.2,b=0.8,
相邻路径点距离约束	[l_min,l_max]=[1,2]
势场增强火花参数	S^θ=3,S^PF=3
S^C	50
改进选择策略参数	ρ^CH=0.99,N^U=10,N^FS=15, N^IS=5,b^CH=0.6

图17 复杂环境下路径规划最优结果对比

Fig.17 Comparison of optimal results of path planning in complex environments

图18 复杂环境下不同算法平均适应度变化情况对比

Fig.18 Comparison of average fitness changes of different algorithms in complex environments

表7 复杂环境下算法对比数据统计结果

Table 7 Results of data statistics for multiple algorithms in complex environment

算法	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
PEFWA	100	294.05	7.06	22.86	156.75	0.9976
A^*算法	100	389.34	35.83			0.9977

表7 复杂环境下算法对比数据统计结果

Table 7 Results of data statistics for multiple algorithms in complex environment

算法	RoS/%	$F ¯$	σ²( $F ¯$ )	$T ¯ f$	σ²(T_f)	$ρ ¯$
PEFWA	100	294.05	7.06	22.86	156.75	0.9976
A^*算法	100	389.34	35.83			0.9977

参考文献 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.