A~*算法的改进及其在AGV路径规划中的应用

作者：卫珊; 王凌; 王斌锐; 任海军; 杨永帅; 刘绪乐; 丁沣城

来源：自动化仪表, 2017, 38(11): 51-54.

DOI：10.16086/j.cnki.issn1000-0380.201711013

• AGV
• 路径规划
• 最短路径算法
• A~*算法
• 启发函数
• 曼哈顿距离

A~*算法是一种启发式搜索算法,被广泛应用于路径规划中。其中,启发函数的设计尤其重要。针对物流工厂中自主移动机器人AGV运行路径的特点,提出一种A~*算法中启发函数的设计方法,以提高路径搜索效率。首先,进行环境地图建模,使用拓扑建模法,将AGV运行地图转化为图论中的有向图,并以邻接表的形式存储有向图中节点信息和边信息;然后,研究不同启发函数的选择对A~*算法执行效率的影响;最后,对A~*算法进行改进,结合实际工厂中AGV路径特点,研究加权曼哈顿距离中权值的选择对算法执行效率的影响,并选取经验值进行试验。试验结果表明,与采用曼哈顿距离作为启发函数的A~*算法相比,采用改进的A~*算法平均路径规划效率提高了11.6%。改进A~*算法在AGV路径规划中可以有效提高路径搜索的效率,作为一种适用于工厂环境的AGV的路径规划算法,对A~*算法启发函数的设计有一定的参考价值。

• 单位
  中国计量大学; 机电工程学院