基于改进多目标进化算法的栅格地图路径规划

doi:10.16183/j.cnki.jsjtu.2024.032

上海交通大学学报 ›› 2025, Vol. 59 ›› Issue (10): 1558-1567.doi: 10.16183/j.cnki.jsjtu.2024.032

基于改进多目标进化算法的栅格地图路径规划

董德金¹^,², 王常成³, 蔡云泽¹^,²()

¹ 上海交通大学自动化系, 上海 200240
² 上海交通大学系统控制与信息处理教育部重点实验室, 上海 200240
³ 航空工业沈阳飞机设计研究所, 沈阳 110035

收稿日期:2024-01-22 修回日期:2024-03-01 接受日期:2024-03-07 出版日期:2025-10-28 发布日期:2025-10-24
通讯作者: 蔡云泽,教授,博士生导师;E-mail:yzcai@sjtu.edu.cn.
作者简介:董德金(2000—),硕士生,主要从事智能体路径规划研究.
基金资助:
航空科学基金(20220001057001)

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

DONG Dejin¹^,², WANG Changcheng³, CAI Yunze¹^,²()

¹ Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China
² Key Laboratory of System Control and Information Processing of the Ministry of Education, Shanghai Jiao Tong University, Shanghai 200240, China
³ Shenyang Aircraft Design and Research Institute, Shenyang 110035, China

Received:2024-01-22 Revised:2024-03-01 Accepted:2024-03-07 Online:2025-10-28 Published:2025-10-24

摘要/Abstract

摘要：

大范围栅格地图的多目标路径规划具有节点规模大、目标数量多的特征,现有算法难以平衡求解帕累托前沿(PF)的速度与质量,因此研究面向PF的高效优化算法具有重要的理论意义.首先,提出一种基于代价向量的加权图建模方法,并在此基础上研究适用于大规模问题的优化算法,相比传统图搜索算法显著降低了时间成本.其次,针对PF求解质量不足的问题,提出一种改进的多目标进化算法并包含新的初始化策略,以及基于角度和偏移密度的思想设计个体和环境选择策略.该改进措施综合考虑种群多样性和收敛性,从而提升了求解效率.最后,通过仿真实验对比,验证了所提改进算法的有效性.

关键词: 栅格地图, 多目标路径规划, 多目标进化算法, 帕累托前沿

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)

中图分类号:

TP242
TP18

董德金, 王常成, 蔡云泽. 基于改进多目标进化算法的栅格地图路径规划[J]. 上海交通大学学报, 2025, 59(10): 1558-1567.

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.

图/表 18

图1

图2

图3

图4

图5

图6

图7

表1

表2

表3

表4

图8

图9

表5

图10

表6

表7

图11

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

基于改进多目标进化算法的栅格地图路径规划

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 23

相关文章 3

编辑推荐

Metrics

本文评价

场景	AD-MOEA 平均解个数	AD-MOEA 平均时间/s	精确解个数
Benchmark1	8.0	0.49	7.0
Benchmark2	4.1	1.08	4.0
Benchmark3	2.7	1.77	5.0

[1]	杜海阔1,2, 郭正玉3,4, 章露露1,2, 蔡云泽1,2. 基于多目标松散同步搜索的多目标多智能体异步路径规划[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 667-677.
[2]	苗镇华1, 黄文焘2, 张依恋3, 范勤勤1. 基于深度强化学习的多模态多目标多机器人任务分配算法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 377-387.
[3]	. 基于栅格图特征点提取下的蚁群算法路径规划[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99.