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

Improvement of A~* Algorithm and Its Application in AGV Path Planning

作　　者：卫珊 王凌 王斌锐 任海军 杨永帅 刘绪乐 丁沣城 WEI Shan;WANG Ling;WANG Binrui;REN Haijun;YANG Yongshuai;LIU Xule;DING Fengcheng(College of Mechanical and Electrical Engineering,China Jiliang University,Hangzhou 310018,China;Hangzhou SIASUN Robot & Automation Co., Ltd., Hangzhou 311200, China)

机构地区：[1]中国计量大学机电工程学院,浙江杭州310018 [2]杭州新松机器人自动化有限公司,浙江杭州311200

出　　处：《自动化仪表》2017年第11期51-54,共4页Process Automation Instrumentation

基　　金：国家自然科学基金资助项目(51575530)

摘　　要：A~*算法是一种启发式搜索算法,被广泛应用于路径规划中。其中,启发函数的设计尤其重要。针对物流工厂中自主移动机器人AGV运行路径的特点,提出一种A~*算法中启发函数的设计方法,以提高路径搜索效率。首先,进行环境地图建模,使用拓扑建模法,将AGV运行地图转化为图论中的有向图,并以邻接表的形式存储有向图中节点信息和边信息;然后,研究不同启发函数的选择对A~*算法执行效率的影响;最后,对A~*算法进行改进,结合实际工厂中AGV路径特点,研究加权曼哈顿距离中权值的选择对算法执行效率的影响,并选取经验值进行试验。试验结果表明,与采用曼哈顿距离作为启发函数的A~*算法相比,采用改进的A~*算法平均路径规划效率提高了11.6%。改进A~*算法在AGV路径规划中可以有效提高路径搜索的效率,作为一种适用于工厂环境的AGV的路径规划算法,对A~*算法启发函数的设计有一定的参考价值。A*algorithm is a heuristic search algorithm widely used in path planning,in which the design of the heuristic function is particularly important.Considering the features of the operation path of automated guided vehicle(AGV)in logistics factories,a design method of heuristic function in A*algorithm is proposed to improve the efficiency of path search.Firstly,the model of environment map is established using the topological modeling method,and the AGV operation map is transformed into the directed graph in graph theory,and the information of the nodes and edges in the directed graph are stored in the form of adjacency tables.Then,the different heuristic functions in A*algorithm are selected to analyze their impacts to the execution efficiency of A*algorithm.Finally,based on the features of AGV path in the actual factories,the influence of the weighting of the weighted Manhattan distanceon the efficiency of the algorithm is studied to improve the A*algorithm;and the empirical value is selected for the experiment.The experimental results show that compared with the A*algorithm using the Manhattan distance as the heuristic function,the improved A*algorithm increases the efficiency of the average path planning by11.6%.The improved A*algorithm can effectively improve the efficiency of path search in AGV path planning and is suitable for the path planning of AGV in factory environment.The improved A*algorithm can effectively improve the efficiency of path search in AGV path planning.It is suitable for the path planning of AGV factory environment and has certain reference value for the design of A*algorithm heuristic function.

关 键 词：AGV 路径规划 最短路径算法 A*算法 启发函数 曼哈顿距离 

分 类 号：TH-39[机械工程] TP24[自动化与计算机技术—检测技术与自动化装置]