Workshop AGV path planning based on improved A* algorithm

Na Liu; Chiyue Ma; Zihang Hu; Pengfei Guo; Yun Ge; Min Tian; Na Liu; Chiyue Ma; Zihang Hu; Pengfei Guo; Yun Ge; Min Tian

doi:10.3934/mbe.2024094

Mathematical Biosciences and Engineering

2024, Volume 21, Issue 2: 2137-2162. doi: 10.3934/mbe.2024094

Previous Article Next Article

Research article

Workshop AGV path planning based on improved A* algorithm

College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China

Academic Editor: Alessandro Ruggiero

Received: 25 October 2023 Revised: 03 December 2023 Accepted: 22 December 2023 Published: 10 January 2024

This article proposes an improved A* algorithm aimed at improving the logistics path quality of automated guided vehicles (AGVs) in digital production workshops, solving the problems of excessive path turns and long transportation time. The traditional A* algorithm is improved internally and externally. In the internal improvement process, we propose an improved node search method within the A* algorithm to avoid generating invalid paths; offer a heuristic function which uses diagonal distance instead of traditional heuristic functions to reduce the number of turns in the path; and add turning weights in the A* algorithm formula, further reducing the number of turns in the path and reducing the number of node searches. In the process of external improvement, the output path of the internally improved A* algorithm is further optimized externally by the improved forward search optimization algorithm and the Bessel curve method, which reduces path length and turns and creates a path with fewer turns and a shorter distance. The experimental results demonstrate that the internally modified A* algorithm suggested in this research performs better when compared to six conventional path planning methods. Based on the internally improved A* algorithm path, the full improved A* algorithm reduces the turning angle by approximately 69% and shortens the path by approximately 10%; based on the simulation results, the improved A* algorithm in this paper can reduce the running time of AGV and improve the logistics efficiency in the workshop. Specifically, the walking time of AGV on the improved A* algorithm path is reduced by 12s compared to the traditional A* algorithm.
- improved A* algorithm,
- AGV,
- path planning,
- bezier curve,
- path optimization
Citation: Na Liu, Chiyue Ma, Zihang Hu, Pengfei Guo, Yun Ge, Min Tian. Workshop AGV path planning based on improved A* algorithm[J]. Mathematical Biosciences and Engineering, 2024, 21(2): 2137-2162. doi: 10.3934/mbe.2024094

Related Papers:

Abstract

This article proposes an improved A* algorithm aimed at improving the logistics path quality of automated guided vehicles (AGVs) in digital production workshops, solving the problems of excessive path turns and long transportation time. The traditional A* algorithm is improved internally and externally. In the internal improvement process, we propose an improved node search method within the A* algorithm to avoid generating invalid paths; offer a heuristic function which uses diagonal distance instead of traditional heuristic functions to reduce the number of turns in the path; and add turning weights in the A* algorithm formula, further reducing the number of turns in the path and reducing the number of node searches. In the process of external improvement, the output path of the internally improved A* algorithm is further optimized externally by the improved forward search optimization algorithm and the Bessel curve method, which reduces path length and turns and creates a path with fewer turns and a shorter distance. The experimental results demonstrate that the internally modified A* algorithm suggested in this research performs better when compared to six conventional path planning methods. Based on the internally improved A* algorithm path, the full improved A* algorithm reduces the turning angle by approximately 69% and shortens the path by approximately 10%; based on the simulation results, the improved A* algorithm in this paper can reduce the running time of AGV and improve the logistics efficiency in the workshop. Specifically, the walking time of AGV on the improved A* algorithm path is reduced by 12s compared to the traditional A* algorithm.

References

[1]	Z. C. Qin, Research on intelligent selection algorithm of ship logistics optimal route, Ship Sci. Technol., 46 (2018), 75–86.
[2]	X. L. Zhao, L. W. Zhong, Optimization simulation and transport path analysis of intelligent warehouse based on flexsim, Software Guide, 21 (2018), 55–73.
[3]	M. Luo, X. R. Hou, J. Yang, Surface optimal path planning using an extended Dijkstra algorithm, IEEE Access, 8 (2020), 147827–147838. https://doi.org/10.1109/access.2020.3015976 doi: 10.1109/access.2020.3015976
[4]	Y. L. Zhou, N. N. Huang, Airport AGV path optimization model based on ant colony algorithm to optimize Dijkstra algorithm in urban systems, Sustainable Comput. Inf. Syst., 35 (2022), 100716. https://doi.org/10.1016/j.suscom.2022.100716 doi: 10.1016/j.suscom.2022.100716
[5]	Z. B. He, C. G. Liu, X. M. Chu, R. R. Negenborn, Q. Wu, Dynamic anti-collision A-star algorithm for multi-ship encounter situations, Appl. Ocean Res., 118 (2022), 102995. https://doi.org/10.1016/j.apor.2021.102995 doi: 10.1016/j.apor.2021.102995
[6]	Y. W. Gu, Z. T. Zhu, J. D. Lv, L. Shi, Z. J. Hou, S. K. Xu, DM-DQN: Dueling Munchausen deep Q network for robot path planning, Complex Intell. Syst., 9 (2023), 1–14. https://doi.org/10.1007/s40747-022-00948-7 doi: 10.1007/s40747-022-00948-7
[7]	C. W. Miao, G. Z. Chen, C. L. Yan, Y. Y. Wu, Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm, Comput. Ind. Eng., 156 (2021), 107230. https://doi.org/10.1016/j.cie.2021.107230 doi: 10.1016/j.cie.2021.107230
[8]	S. Y. Guo, X. G. Zhang, Y. Q. Du, Y. S. Zheng, Z. Y. Cao, Path planning of coastal ships based on optimized DQN reward function, J. Mar. Sci. Eng., 9 (2021), 210. https://doi.org/10.3390/jmse9020210 doi: 10.3390/jmse9020210
[9]	T. Wang, Z. L. Xue, X. Q. Dong, S. L. Xie, Autonomous intelligent planning method for welding path of complex ship components, Robotica, 39 (2021), 428–437. https://doi.org/10.1017/s0263574720000454 doi: 10.1017/s0263574720000454
[10]	Z. H. Han, S. G. Liu, F. Yu, X. D. Zhang, G. X. Zhang, A 3D measuring path planning strategy for intelligent CMMs based on an improved ant colony algorithm, Int. J. Adv. Manuf. Technol., 93 (2017), 1487–1497. https://doi.org/10.1007/s00170-017-0503-y doi: 10.1007/s00170-017-0503-y
[11]	N. Saito, T. Oda, A. Hirata, Y. Nagai, M. Hirota, K. Katayama, et al., A Tabu list strategy based DQN for AAV mobility in indoor single-path environment: implementation and performance evaluation, Internet Things, 14 (2021), 100394. https://doi.org/10.1016/j.iot.2021.100394
[12]	W. J. Meng, Q. Zheng, L. Yang, P. F. Li, G. Pan, Qualitative measurements of policy discrepancy for return-based deep q-network, IEEE Trans. Neural Networks Learn. Syst., 31 (2019), 4374–4380. https://doi.org/10.1109/tnnls.2019.2948892 doi: 10.1109/tnnls.2019.2948892
[13]	S. BiBi, M. Y. Misro, M. Abbas, Smooth path planning via cubic GHT-Bézier spiral curves based on shortest distance, bending energy and curvature variation energy, AIMS Math., 6 (2021), 8625–8641. https://doi.org/10.3934/math.2021501 doi: 10.3934/math.2021501
[14]	Z. Durakli, V. Nabiyev, A new approach based on Bezier curves to solve path planning problems for mobile robots, J. Comput. Sci., 58 (2022), 101540. https://doi.org/10.1016/j.jocs.2021.101540 doi: 10.1016/j.jocs.2021.101540
[15]	B. Y. Song, Z. D. Wang, L. Zou, L. Xu, F. E. Alsaadi, A new approach to smooth global path planning of mobile robots with kinematic constraints, Int. J. Mach. Learn. Cybern., 10 (2019), 107–119. https://doi.org/10.1007/s13042-017-0703-7 doi: 10.1007/s13042-017-0703-7
[16]	X. Li, L. Wang, Application of improved ant colony optimization in mobile robot trajectory planning, Math. Biosci. Eng., 17 (2020), 6756–6774. https://doi.org/10.3934/mbe.2020352 doi: 10.3934/mbe.2020352
[17]	K. Fransen, J. van Eekelen, Efficient path planning for automated guided vehicles using A* (Astar) algorithm incorporating turning costs in search heuristic, Int. J. Prod. Res., 61 (2023), 707–725. https://doi.org/10.1080/00207543.2021.2015806
[18]	B. Wu, X. N. Chi, C. C. Zhao, W. Zhang, Y. Lu, D. Jiang, Dynamic path planning for forklift AGV based on smoothing A* and improved DWA hybrid algorithm, Sensors, 22 (2022), 7079. https://doi.org/10.3390/s22187079 doi: 10.3390/s22187079
[19]	P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 4 (1968), 100–107. https://doi.org/10.1109/tssc.1968.300136 doi: 10.1109/tssc.1968.300136
[20]	A. K. Guruji, H. Agarwal, D. K. Parsediya, Time-efficient A* algorithm for robot path planning, Procedia Technol., 23 (2016), 144–149. https://doi.org/10.1016/j.protcy.2016.03.010 doi: 10.1016/j.protcy.2016.03.010
[21]	X. D. Wang, H. W. Zhang, S. Liu, J. L.Wang, Y. H. Wang, D. H. Shangguan, Path planning of scenic spots based on improved A* algorithm, Sci. Rep., 12 (2022), 1320. https://doi.org/10.1038/s41598-022-05386-6 doi: 10.1038/s41598-022-05386-6
[22]	X. L. Tong, S. E. Yu, G. Y. Liu, X. D. Niu, C. J. Xia, J. K. Chen, A hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm in the 2D random environments, Adv. Eng. Inf., 54(2022), 101755. https://doi.org/10.1016/j.aei.2022.101755 doi: 10.1016/j.aei.2022.101755
[23]	C. G. Li, X. Huang, J. Ding, K. Song, S. Q. Lu, Global path planning based on a bidirectional alternating search A* algorithm for mobile robots, Comput. Ind. Eng., 168 (2022), 108123. https://doi.org/10.1016/j.cie.2022.108123 doi: 10.1016/j.cie.2022.108123
[24]	C. W. Miao, G. Z. Chen, C. L. Yan, Y. Y. Wu, Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm, Comput. Ind. Eng., 156 (2021), 107230. https://doi.org/10.1016/j.cie.2021.107230 doi: 10.1016/j.cie.2021.107230
[25]	H. D. Li, T. Zhao, S. Dian, Forward search optimization and subgoal-based hybrid path planning to shorten and smooth global path for mobile robots, Knowl.-Based Syst., 258 (2022), 110034. https://doi.org/10.1016/j.knosys.2022.110034 doi: 10.1016/j.knosys.2022.110034

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)