Liu Na, Ma Chiyue, Hu Zihang, Guo Pengfei, Ge Yun, Tian Min
College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China.
Math Biosci Eng. 2024 Jan 10;21(2):2137-2162. doi: 10.3934/mbe.2024094.
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.
本文提出了一种改进的A算法，旨在提高数字化生产车间中自动导引车（AGV）的物流路径质量，解决路径转弯过多和运输时间过长的问题。对传统A算法进行了内部和外部改进。在内部改进过程中，我们在A算法内部提出了一种改进的节点搜索方法，以避免生成无效路径；提供一种启发式函数，该函数使用对角距离而非传统启发式函数来减少路径中的转弯次数；并在A算法公式中添加转弯权重，进一步减少路径中的转弯次数并减少节点搜索次数。在外部改进过程中，通过改进的前向搜索优化算法和贝塞尔曲线方法对内部改进后的A算法的输出路径进行外部进一步优化，从而减少路径长度和转弯次数，创建转弯次数更少、距离更短的路径。实验结果表明，本研究提出的内部改进后的A算法与六种传统路径规划方法相比表现更好。基于内部改进后的A算法路径，完全改进后的A算法将转弯角度减少了约69%，路径缩短了约10%；基于仿真结果，本文改进后的A算法可减少AGV的运行时间，提高车间物流效率。具体而言，与传统A算法相比，AGV在改进后的A*算法路径上的行走时间减少了12秒。
