基于A*算法的AGV路径规划的研究

谢辉辉，胡 江，班玉荣

XIE Hui-hui，HU Jiang，BAN Yu-rong

（北京机械工业自动化研究所，北京 100120）

0 引言

随着生产技术和生产管理水平的进步，柔性好，自动化程度高和智能化水平高的AGVS（Automated Guided Vehicles System，自动导向车）越来越多的应用于生产中间的过程物流输送。而对于AGVS而言，选择正确而有效的路径，可以提高运输效率，从而降低运输成本。本文将着重论述AGV运输系统的路径规划。

1 概述

将AGV运行涉及的区域用笛卡尔坐标系表示，将AGV小车可能停留的点和分叉路口的点作为节点保存，那么AGV小车从一点到达另一点的路径规划就可以转换为图论搜索法。该方法现在运用比较多的有Dijkstra算法、Floyd算法和A*算法等，其中A*算法因搜索过程效率较高而被较多使用。下面具体介绍一下A*算法的原理。

2 A＊算法原理

A*算法是一种启发式搜索算法。之所以叫启发式算法，是因为该算法会在搜索过程中获得问题自身的一些特性信息来指导搜索，这些特性信息主要作用是对节点的重要性进行评估，通过这个评估来实现对状态空间的可能位置进行排序，得出最小代价的位置，在状态空间中对每一个节点进行评估，得到最优的节点，再从这个节点出发进行下一节点的搜索，直到寻找到目标节点。

评估函数：

f（n）=g（n）+h（n）----f*（n）=g*（n）+h*（n）

其中：

--节点n是搜索图中当前被扩展的节点

--f（n）是从初始状态经由节点n到达目标节点的所有路径中最小路径大家f*（n）的估计值

--g（n）是从初始节点到节点n的最小代价g*（n）

--h（n）是从节点n到达目标节点的最优路径代价h*（n）的估计代价启发函数

并且有如下限制：h（n）＜h*（n）

A*算法实现的步骤：

1）建立一个OPEN表和CLOSE表，OPEN表中放入刚生成的节点,CLOSE表中放入已经扩展或将要扩展的节点

2）将起点放入OPEN表中；

3）在图中搜索与起点相通的节点，判断其中是否含有终点，如果有，则结束搜索，若没有，则将与之相通的所有节点放入OPEN表中，将起点放入CLOSE表中

4）将OPEN表中的点按照估价函数f（n）的值排序，选出最小值的节点，将其作为下一个扩展结点，将该最小节点放入CLOSE表中，重复步骤4），直至OPEN表中出现终点

这样，CLOSE表中所存储的点就是A*算法得出的路径。

3 A＊算法的实例

本文针对如下简单路径采用A*算法进行了模拟，将AGV活动区域形成“地图”，并将AGV可能起始的点、到达的点与路口分叉点作为节点记录到“地图”中，在AGV接受任务时，只需输入起始目的节点，该系统就会算出路径。

图1 路径图

如图1所示，点1到点10以及点14为AGV的加载点，点11到13是AGV的卸载点，点A到点J是分岔路点。在AGV活动区域内建立笛卡尔坐标系，把AGV每一个可能停留点设置为节点表明它的坐标，所有的节点记录为AGV的活动地图。

点A（10,0）B（20,0）C（30,0）D（40,0）E（10,10）,F（20,10）,G（30,10）,H（40,10）,I（0,0）,J（50,0）为交叉点；点1（3,0），2（7,0），3（13,0），4（17,0），5（23，0），6（27,0），7（33,0），8（37,0），9（43,0），10（47,0），11（15,10），12（25,10），13（35,10），14（50,10）为AGV的起始点或者终点。选取每一个节点到终点的直线距离作为h*（n）函数，即

在数据库中建立表格，把每个节点相邻节点记录到表中，同时在另一张表中记录他们的坐标位置，从起点开始计算每一个相邻节点到目标节点的距离，即h*（n），选取其中最小值作为下一个节点，然后再次计算距离，再次排序，直到到达终点。例如选取节点1到节点14的路径，步骤为：

1）选择1的两个分叉点A和I,距离L（A）=41.23,L（I）=50.99,选A点，将点I计入CLOSE表；

2）选择A的三个点I,E,B,L（E）=40,L（B）=31.62,比较三点距离后，比较候选点I,E,B选择B点，将点E计入CLOSE表；

3）选择B的三个点A,F,C,L（F）=30,L（C）=22.36,比较候选点I,E,A,F,C选择C点，将F计入CLOSE表；

4）选择C的三个点B，G,D,L（G）=20,L（D）=10,比较候选点I,E,A,C,B,G,D选择D点，将G点计入CLOSE表

5）选择D的三个点C,J,H,L（J）=10,L（H）=10,比较候选点I,E,A,C,B,G,J,H,从点J，H中任意选择一点，如H

6）选择与H有关的点，发现存在目标节点14，搜索完毕

最后到达终点，路径为：1—A—B—C—D—J—14

图2是采用A*算法进行AGV路径规划的应用程序界面，在该应用程序中，只需在界面上输入起始目的结点，点击“计算路径”按钮，就会输出AGV从起始点到目的节点所应经过的节点，然后AGV可根据这些点的坐标位置进行路径选择，从而引导AGV直到目标节点。

图2 采用A*算法进行AGV路径规划的应用程序界面

4 结论

从上例的模拟计算可以看出，可以很容易算单台AGV起点到终点的最终路径，并且该h*（n）的选取保证了所选路段为距离最优的路段，比较符合对AGV路径规划的要求。但在实际的生产环境中，会有多台AGV同时运行，所选路径会涉及到碰撞、死锁等问题，需要在路径规划的基础上增加对这些问题的复杂运算。这些需要根据现场的环境要求对h*（n）和f*（n）做综合的评估和选取，以此来满足不同要求的路径。

[1]钟建琳.制造环境中AGV运输子系统的路径规划[J].机械设计与制造,2010（2）：237-239.

[2]林尧瑞,马少平.人工智能导论[M].北京：清华大学出版社.