Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (12): 243-247.DOI: 10.3778/j.issn.1002-8331.2008-0099

Previous Articles     Next Articles

Application of Improved A* Algorithm in Path Planning

WANG Baojian, HU Dasha, JIANG Yuming   

  1. 1.College of Computer Science, Sichuan University, Chengdu 610065, China
    2.Big Data Analysis and Fusion Application Technology Engineering Laboratory of Sichuan Province, Chengdu 610065, China
  • Online:2021-06-15 Published:2021-06-10

改进A*算法在路径规划中的应用

王保剑,胡大裟,蒋玉明   

  1. 1.四川大学 计算机学院,成都 610065
    2.四川省大数据分析与融合应用技术工程实验室,成都 610065

Abstract:

Focusing on the application scenario of large-scale multi-AGV path planning, in order to solve the problem that the node preempting of multiple AGVs during path planning may result in excessive load on the node, cause local congestion, and reduce the operating efficiency of the entire system, this paper proposes an improved A* algorithm based on referring to the node load conditions. According to the algorithm, for the load of each node, starting from the initial value, the load of the node will be dynamically updated according to the corresponding dynamic load calculation formula. It introduces the load into the heuristic function of the A* algorithm to affect the AGV path selection through the node load and avoid high-load nodes. Through corresponding simulation experiments, it proves that the algorithm is conductive to effectively balance the load of each node and improve the efficiency of system operation.

Key words: AGV path planning, A* algorithm, load balancing, local congestion

摘要:

针对大规模多AGV路径规划的应用场景,为解决多个AGV在路径规划时因抢占节点,导致该节点负载过高,造成局部拥塞,致使整个系统的运行效率降低的问题。提出了一种结合节点负载情况的改进A*算法。各个节点的负载从初始值开始,根据相应的动态负载计算公式,动态更新该节点的负载。在A*算法的启发函数中引入负载,使节点负载影响AGV路径选择,避开高负载节点。通过相应的仿真模拟实验,证明了该算法能够有效地均衡各节点的负载,提高系统运行效率。

关键词: AGV路径规划, A*算法, 负载均衡, 局部拥塞