An Improved Multi-Objective Evolutionary Algorithm for Grid Map Path Planning

doi:10.16183/j.cnki.jsjtu.2024.032

Abstract

Abstract:

Multi-objective path planning on large-scale grid maps is characterized by a large number of nodes and multiple targets. Existing algorithms struggle to balance the speed and quality of solving the Pareto front (PF). Therefore, studying efficient optimization algorithms based on the PF has certain theoretical significance. First, a weighted graph modeling method based on cost vector is proposed, and optimization algorithms for solving large-scale problems are studied accordingly, which significantly saves time and costs compared with graph search algorithms. Then, to address the issue of low quality of the PF solutions, an improved multi-objective evolutionary algorithm is proposed, which includes a new initialization strategy. Individual and environment selection strategies are designed based on the concepts of angle and shift-based density. These improvements take both population diversity and convergence into account, thereby improving the solving efficiency. Finally, comparative simulation experiments are conducted to verify the effectiveness of the improved algorithm.

Key words: grid map, multi-objective path planning, multi-objective evolutionary algorithm, Pareto front (PF)

CLC Number:

TP242
TP18

DONG Dejin, WANG Changcheng, CAI Yunze. An Improved Multi-Objective Evolutionary Algorithm for Grid Map Path Planning[J]. Journal of Shanghai Jiao Tong University, 2025, 59(10): 1558-1567.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Tab.1

Tab.2

Tab.3

Tab.4

Fig.8

Fig.9

Tab.5

Fig.10

Tab.6

Tab.7

Fig.11

References 23

[1]	裘柯钧, 鲍中凯, 陈璐. 民用客机总装车间自动引导车任务分配及路径规划[J]. 上海交通大学学报, 2023, 57(1): 93-102. doi: 10.16183/j.cnki.jsjtu.2021.223
	QIU Kejun, BAO Zhongkai, CHEN Lu. Task assignment and path planning for automatic guided vehicles in aircraft assembly workshop[J]. Journal of Shanghai Jiao Tong University, 2023, 57(1): 93-102.
[2]	ABED B M, JASIM W M. Multi objective optimization algorithms for mobile robot path planning: A survey[J]. International Journal of Online & Biomedical Engineering, 2022, 18(15): 160-177.
[3]	OU Y Q, FAN Y X, ZHANG X L, et al. Improved A^* path planning method based on the grid map[J]. Sensors, 2022, 22(16): 6198.
[4]	ZHANG D, LUO R, YIN Y B, et al. Multi-objective path planning for mobile robot in nuclear accident environment based on improved ant colony optimization with modified A^[J]. Nuclear Engineering and Technology*, 2023, 55(5): 1838-1854.
[5]	DUAN P, SANG H Y, LI J Q, et al. Solving multi-objective path planning for service robot by a pareto-based optimization algorithm[C]// 2018 Chinese Control and Decision Conference. Shenyang, China: IEEE, 2018: 3416-3420
[6]	HOHMANN N, BUJNY M, ADAMY J, et al. Hybrid evolutionary approach to multi-objective path planning for UAVs[C]// 2021 IEEE Symposium Series on Computational Intelligence. Orlando, USA: IEEE, 2021: 9660187.
[7]	STEWART B S, WHITE C C. Multiobjective A^[J]. Journal of the ACM*, 1991, 38(4): 775-814.
[8]	MANDOW L, DE LA CRUZ J L P. Multiobjective A^* search with consistent heuristics[J]. Journal of the ACM, 2008, 57(5): 1-25.
[9]	Ulloa C H, Yeoh W, Baier J, et al. A simple and fast bi-objective search algorithm[C]// Proceedings of the International Conference on Automated Planning and Scheduling. Nancy, France: AAAI, 2020, 30: 143-151.
[10]	REN Z Q, ZHAN R, RATHINAM S, et al. Enhanced multi-objective A^* using balanced binary search trees[C]// Proceedings of the International Symposium on Combinatorial Search. Vienna, Austria: AAAI, 2022: 162-170.
[11]	HU X B, GU S H, ZHANG C, et al. Finding all Pareto optimal paths by simulating ripple relay race in multi-objective networks[J]. Swarm and Evolutionary Computation, 2021, 64: 100908.
[12]	JIN B. Multi-objective A^* algorithm for the multimodal multi-objective path planning optimization[C]// 2021 IEEE Congress on Evolutionary Computation. Kraków, Poland: IEEE, 2021: 1704-1711.
[13]	AHN C W, RAMAKRISHNA R S. A genetic algorithm for shortest path routing problem and the sizing of populations[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 566-579.
[14]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[15]	LI K, FIALHO A, KWONG S, et al. Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(1): 114-130.
[16]	REN Q, YAO Y, YANG G, et al. Multi-objective path planning for UAV in the urban environment based on CDNSGA-II[C]// 2019 IEEE International Conference on Service-Oriented System Engineering. San Francisco, USA: IEEE, 2019: 350-3505.
[17]	YAO X Y, LI W H, PAN X G, et al. Multimodal multi-objective evolutionary algorithm for multiple path planning[J]. Computers & Industrial Engineering, 2022, 169: 108145.
[18]	ZHENG S H, ZHENG C R, LI W. Research on multi-objective shortest path based on genetic algorithm[C]// 2022 2nd International Conference on Computer Science and Blockchain. Wuhan, China: IEEE, 2022: 127-130.
[19]	TIAN Y, ZHENG X T, ZHANG X Y, et al. Efficient large-scale multiobjective optimization based on a competitive swarm optimizer[J]. IEEE Transactions on Cybernetics, 2020, 50(8): 3696-3708. doi: 10.1109/TCYB.2019.2906383 pmid: 30951490
[20]	CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791.
[21]	DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.
[22]	TIAN Y, CHENG R, ZHANG X Y, et al. An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(4): 609-622.
[23]	LIU Z Z, WANG Y, HUANG P Q. AnD: A many-objective evolutionary algorithm with angle-based selection and shift-based density estimation[J]. Information Sciences, 2020, 509: 400-419.

场景	节点个数	目标个数	设置种群数量	设置迭代轮次
P1	400 (20×20)	2	20	20
P2	400 (20×20)	5	70	70
P3	1600 (40×40)	2	20	20
P4	1600 (40×40)	3	40	40

场景	平均求解数目
场景	AD-MOEA	NAMOA^*	NSGA-III	NSGA-II	MOEA/D	AR-MOEA	LMOCSO
P1	8.2	10	1.9	1.5	1.2	11.8	1.1
P2	30.4	65	5.7	3.8	timeout	8.9	1.7
P3	10.0	15	1.7	1.7	1.3	13.7	1.2
P4	18.9	28	1.9	3.2	1.9	19.3	1.1

场景	平均求解时间/s
场景	AD-MOEA	NAMOA^*	NSGA-III	NSGA-II	MOEA/D	AR-MOEA	LMOCSO
P1	0.32	0.29	2.20	0.46	0.39	2.19	0.17
P2	8.77	14.93	25.38	5.56	timeout	25.54	0.57
P3	0.70	3.80	17.58	4.80	5.40	18.25	3.27
P4	3.26	13.33	61.85	12.47	74.94	59.97	6.42

算法	平均内存占有率
算法	P1	P2	P3	P4
AD-MOEA	0.518	0.496	0.482	0.492
NAMOA^*	0.519	0.495	0.501	0.494
NSGA-III	0.518	0.495	0.483	0.489
NSGA-II	0.517	0.500	0.489	0.485
MOEA/D	0.518	timeout	0.487	0.483
AR-MOEA	0.516	0.502	0.484	0.487
LMOCSO	0.519	0.505	0.483	0.492

算法	HV	IGD	算法	HV	IGD
AD-MOEA	35111	12.06	MOEA/D	1650	202.70
NSGA-III	4740	164.18	AR-MOEA	61	248.70
NSGA-II	2252	195.44	LMOCSO	180	240.88