Academic Journal of Computing & Information Science, 2023, 6(2); doi: 10.25236/AJCIS.2023.060205.
Zeping Yang, Xiangguo Sun
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
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.
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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.
 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
 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.
 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
 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
 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