基于改进A＊算法的AGV调度研究

冯鲁波

（四川大学计算机学院，成都610065）

0 引言

自动导引运输车（automated guided vehicle，AGV）是一种智能运输设备。AGV是目前无人工厂中的重要组成部分，在自动化流水线中可以取代人工完成搬运的任务。随着制造业的发展和人工成本的提高，自动化流水线也需要相应的AGV调度系统来满足日益增长的任务需求。基于以上背景，对多AGV路径规划算法的优化提出了更高要求[1]。

Rajotia等[2]提出了基于半动态时间窗约束的路径规划算法，经过实际验证后，证明该策略可以有效降低AGV运行过程中的拥堵概率，提高系统的运行效率。Fan[3]设计了一种基于动态串联回路的AGV路径设计方法，针对于降低AGV运行回路并建立数学模型，可以有效防止AGV冲突。梁承姬[4]提出了一种无冲突的AGV路径规划方法，通过计算每一段路径上的时间窗实现冲突规避，从而给出多AGV的无冲突路径规划。泰应鹏等[5]通过时间窗与A*算法的结合，提出了一种改进的A*算法，规划好的路径会通过计算时间窗进行避障。

本文通过设置拥堵阈值，改进传统A*算法的启发函数；并减少转弯次数和约束转向角度，以减少运行时间；设计基于时间窗的规避算法以解决冲突问题，分析多AGV的冲突问题以及常见的冲突类型，预测和规避可能发生的冲突，最终获得全局最优路径。

1 静态路径规划

1.1 传统A*算法

A*算法是一种启发式路径规划算法，通过建立合适的启发函数，对周围的环境进行求解，获得启发信息，利用这些信息选择最优的目标，从而搜索到最优路径[6]。……