Welcome to Francis Academic Press

Academic Journal of Computing & Information Science, 2023, 6(2); doi: 10.25236/AJCIS.2023.060205.

A new multi-objective point path planning algorithm for mobile robots


Zeping Yang, Xiangguo Sun

Corresponding Author:
Zeping Yang

College of Mechanical Engineering, Sichuan University of Science & Engineering, Sichuan, China


Aiming at the path planning problem of mobile robot passing through multiple target points with the shortest path under two-dimensional raster map, this paper proposes a method combining an improved A* algorithm with an annealing genetic algorithm. For the problem that A* algorithm will search adjacent nodes in turn, Jump Point Search (JPS) algorithm is introduced to avoid the search of surrounding nodes by searching the jump point of the current node and reduce the calculation time. In view of the prematurity problem of genetic algorithm, the simulated annealing algorithm is introduced to make the simulated annealing algorithm and genetic algorithm complement each other and overcome the prematurity problem of genetic algorithm effectively. By using TSPLIB dataset, the path planning of the improved genetic algorithm is obviously better than that of the original genetic algorithm. Finally, the feasibility and effectiveness of the method are verified by simulation, and the shortest safe path can be found quickly in the process of optimization.


path planning; A* algorithm; multi-objective point; genetic algorithm

Cite This Paper

Zeping Yang, Xiangguo Sun. A new multi-objective point path planning algorithm for mobile robots. Academic Journal of Computing & Information Science (2023), Vol. 6, Issue 2: 28-35. https://doi.org/10.25236/AJCIS.2023.060205.


[1] Mengxi Li, Boxia He, Yu Zhou. Multi-objective path planning method for mobile robot based on A~* and ant colony algorithm [J]. Machinery & electronics,2021,39(06):61-65+69. https://kns.cnki.net/ kcms/detail/detail.aspx?FileName=JXYD202106013&DbName=CJFQ2021

[2] Yi Lu, Yongping Gao, Jiangteng Long. Research on Path Planning of Mobile Robot Based on A~* Algorithm [J]. Journal of Hubei Normal University (Natural Science),202 ,42(02):59-65. DOI: 10.3969/j.issn.2096-3149.2022.02.009

[3] Jin Li, Chunlong Fu. Genetic Algorithm and ant colony algorithm based on the TSP problem study [J]. Computer Programming Skills & Maintenance, 2021(9):17-18+66. DOI: 10.16184/j.cnki.com. prg. 2021.09.007

[4] Fan Yang, Yachong Xue, Jing Li. Path planning for ergodic multi-task target robot under static obstacles [J]. Journal of Tiangong University, 2018, 37(04): 65-71. DOI: 103969/j.issn.1671-024x.2018.04.012

[5] Zhong, X., Tian, J., Hu, H. et al. Hybrid Path Planning Based on Safe A* Algorithm and Adaptive Window Approach for Mobile Robot in Large-Scale Dynamic Environment. J Intell Robot Syst 99, 65–77 (2020). https://doi.org/10.1007/s10846-019-01112-z

[6] Jiacheng CAI, Keqiang Bai, Xuchun Li, Zhengliang Huang, Zhigui Liu. Improved Path Planning Algorithm for Mobile Robot Based on JPS [J/OL]. Application Research of Computers:1-8[2022-07-20]. DOI: 10.19734/j.issn.1001-3695.2021.0671

[7] Jianmeng Huang, Yuxiong Wu, Xiezhao Lin. Smooth JPS path planning and trajectory optimization method for mobile robot [J]. Transactions of the Chinese Society for Agricultural Machinery,2021,52(02):21-29+121. DOI: 10.6041/j.issn.1000-1298.2021.02.002

[8] Shuangquan Tang, Bofeng Zhang, Sen Mu, Zixi Chen, Haoming Feng, Jing Xu. Optimal path planning problem based on Floyd algorithm [J]. Scientific and Technological Innovation,2021(24):16-17. https://kns.cnki.net/kcms/detail/detail.aspx?FileName=HLKX202124007&DbName=CJFQ2021

[9] Ou, J., Hong, S.H., Ziehl, P. et al. GPU-based Global Path Planning Using Genetic Algorithm with Near Corner Initialization. J Intell Robot Syst 104, 34 (2022). https://doi.org/10.1007/s10846-022-01576-6

[10] Jidai Wang, Xindong Wang, Qunhong Tian, Aiqin Sun, Xinchao Zhang, Liang Yuan. Path planning of mobile robot based on improved fuzzy adaptive Genetic Algorithm [J]. Machine tool & Hydraulics, 2021, 49(23):18-23. DOI: 10.3969 /j. issn. 1001-3881. 2021. 23. 004

[11] Kesheng Chen, Sidong Xian, Peng Guo. Adaptive temperature Simulated Annealing algorithm for traveling salesman problem [J]. Control theory & applications, 2021, 38(02):245-254. DOI:  10.7641/ CTA. 2020.00090

[12] Jian Sun, Songzuo Liu, Xiaoxiao Wu, Simin Wu. Parallel Simulated Annealing algorithm to solve TSP based on Spark [J]. Electronic Measurement Technology, 2022, (4): 53-58, DOI: 10.19651 / j.carol carroll nki emt. 2108429.

[13] Jin Zhang, Guotong Bi, Lili Li. A discrete bat algorithm for solving TSP problem [J]. Computer Engineering & Science, 2018, 40(11):2085-2091. DOI: 10.3969/j.issn.1007-130X.2017.11.024

[14] Y. Wu, W. Song, Z. Cao, J. Zhang and A. Lim, "Learning Improvement Heuristics for Solving Routing Problems," in IEEE Transactions on Neural Networks and Learning Systems, DOI: 10.1109/TNNLS. 2021.3068828.

[15] Juan Li, Xiaoming You, Sheng Liu, Jia Chen. Adaptive fuzzy ant colony system [J]. Computer Engineering and Applications, 2019, 55(15): 75-81. DOI: 10.3778/j.issn.1002-8331.1811-0349

[16] GÜNDÜZ, MESUT; KIRAN, MUSTAFA SERVET; and ÖZCEYLAN, EREN (2015) "A hierarchic approach based on swarm intelligence to solve the traveling salesman problem," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 23: No. 1, Article 9.https://doi.org/10.39 06/elk-1210-147

[17] Eneko Osaba, Xin-She Yang, Fernando Diaz, Pedro Lopez-Garcia, Roberto Carballedo, An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems, Engineering Applications of Artificial Intelligence, Volume 48,2016, Pages 59-71, ISSN 0952-1976. https://doi.org/10.1016/j.engappai.2015.10.006