Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

2025 , Vol. 59 >Issue 10: 1558 - 1567

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2024.032

Electronic Information and Electrical Engineering

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

  • DONG Dejin ,
  • WANG Changcheng ,
  • CAI Yunze
Expand
  • 1 Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China
    2 Key Laboratory of System Control and Information Processing of the Ministry of Education, Shanghai Jiao Tong University, Shanghai 200240, China
    3 Shenyang Aircraft Design and Research Institute, Shenyang 110035, China

Received date: 2024-01-22

  Revised date: 2024-03-01

  Accepted date: 2024-03-07

  Online published: 2024-03-15

Fold

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)

Cite this article

DONG Dejin , WANG Changcheng , CAI Yunze . An Improved Multi-Objective Evolutionary Algorithm for Grid Map Path Planning[J]. Journal of Shanghai Jiaotong University, 2025 , 59(10) : 1558 -1567 . DOI: 10.16183/j.cnki.jsjtu.2024.032

References

[1] 裘柯钧, 鲍中凯, 陈璐. 民用客机总装车间自动引导车任务分配及路径规划[J]. 上海交通大学学报, 2023, 57(1): 93-102.
  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.
[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.
Options
Outlines

/

〈 〉