Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (16): 204-210.DOI: 10.3778/j.issn.1002-8331.2001-0090

Previous Articles     Next Articles

Multi-AGV Path Planning Based on Improved Smooth A* Algorithm

HU Weimin, JIN Wenzhou   

  1. School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510461, China
  • Online:2020-08-15 Published:2020-08-11

改进平滑A*算法的多AGV路径规划

胡蔚旻,靳文舟   

  1. 华南理工大学 土木与交通学院,广州 510461

Abstract:

Advances in science and technology have prompted Automated Guided Vehicle(AGV) with many advantages to gradually replace manual handling, but the multi-AGV path planning and coordination problems have arisen at the historic moment. Aiming at the above problems, according to the driving characteristics of AGV, a Cartesian coordinate system environment is constructed, and the traditional A* algorithm is used as the basic model. By introducing 3 axes and 2 quadrants, the number of route turnings is used to eliminate invalid alternative points, and the driving path is smoothed. Minimize the time to formulate conflict judgment standards and coordination strategies for the goal to achieve the best system operating efficiency. Through example analysis, the improved A* algorithm single AGV line can reduce the maximum number of search points by 10.9% and the number of turns by 350%; the coordination strategy with the minimum time as the goal can effectively avoid the system from falling into a local optimal phenomenon due to the priority established by subjective factors.

Key words: Automated Guided Vehicle(AGV), improved A* algorithm, path planning, conflict coordination

摘要:

科技的进步促使拥有众多优势的自动导引车(Automated Guided Vehicle,AGV)逐步替代人工搬运,随之产生的多AGV路径规划、协调问题也应运而生。针对上述问题,依据AGV行驶特征,构建笛卡尔坐标系环境,以传统A*算法为基础模型,通过引入3轴-2象限、路线转向数来剔除无效备选点,平滑行驶路径;以系统总工作时长最小为目标制定冲突判断标准与协调策略,实现系统运行效率最佳的目标。通过实例分析,改进A*算法单AGV线路最多可减少10.9%搜索点数和350%转向数;以时间最小为目标的协调策略能够有效避免因主观因素制定的优先度而导致系统陷入局部最优的现象。

关键词: 自动导引车, 改进A*算法, 路径规划, 冲突协调