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

ｌ　匐　化　基于Ａ冰算法的ＡＧＶ路径规划的研究　Ｒｅｓｅａｒｃｈ　ｏｆ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｂａｓｅｄ　ｏｎ　Ａ　ａｌｇｏｒｉｔｈｍ　谢辉辉，胡江，班玉荣　×ｌＥ　ＨｕＩ．ｈｕｉ．ＨＵ　Ｊｉａｎｇ．ＢＡＮ　Ｙｕ．ｒｏｎｇ　（北京机械工业自动化研究所，北京１ＯＯｌ２０）　摘要：阐述了基于Ａ　算法的ＡＧＶ系统的路径规划算法，利用编程对一个简单实例做了具体的算法模　拟。　关键词：ＡＧＶ；路径规划　中图分类号：ＴＰ２７３　文献标识码：Ａ　文章编号：１　００９—０１　３４（２０１１）２（上）一０１１　３—０２　Ｄｏｉ：１　０．３９６９／ｉ．ｉｓｓｎ．１　００９－０１　３４．２０１１．２（上）．９６　０引言　随着生产技术和生产管理水平的进步，柔　性好，自动化程度高和智能化水平高的ＡＧＶＳ　（Ａｕｔｏｍａｔｅｄ　Ｇｕｉｄｅｄ　Ｖｅｈｉｃｌｅｓ　Ｓｙｓｔｅｍ，自动导向　一节点ｎ是搜索图中当前被扩展的节点　　一ｎ）是从初始状态经由节点Ｉ１到达目标节点的　ｇ（ｎ）是从初始节点到节点ｎ的最小代价ｇ　所有路径中最小路径大家ｐ（ｎ）的估计值　一一车）越来越多的应用于生产中间的过程物流输　送。而对于ＡＧＶＳ而言，选择正确而有效的路径，　可以提高运输效率，从而降低运输成本。本文将　着重论述ＡＧＶ运输系统的路径规划。　（ｎ）　一ｈ（ｎ）是从节点ｎ到达目标节点的最优路径代价　并且有如下限制：ｈ（ｎ）＜ｈ　（ｎ）　ｈ　（ｎ）的估计代价启发函数　Ａ　算法实现的步骤：　１）建立一个ＯＰＥＮ表和ＣＬＯＳＥ表，ＯＰＥＮ表　中放入刚生成的节点，ＣＬＯＳＥ表中放入已经扩展或　将要扩展的节点　２）将起点放入ＯＰＥＮ表中：　３）在图中搜索与起点相通的节点，判断其中　是否含有终点，如果有，则结束搜索，若没有，　则将与之相通的所有节点放入ＯＰＥＮ表中，将起点　放入ＣＬＯＳＥ表中　１概述　将ＡＧＶ运行涉及的区域用笛卡尔坐标系表　示，将ＡＧＶｚＪ，车可能停留的点和分叉路口的点作　为节点保存，那么ＡＧＶ４￣车从一点到达另一点的　路径规划就可以转换为图论搜索法。该方法现在　运用比较多的有Ｄｉｊｋｓｔｒａ算法、Ｆｌｏｙｄ算法和Ａ　算法　等，其中Ａ　算法因搜索过程效率较高而被较多使　用。下面具体介绍一下Ａ　算法的原理。　２　Ａ　算法原理　Ａ　算法是一种启发式搜索算法。之所以ⅡＬｆ启　发式算法，是因为该算法会在搜索过程中获得问　题自身的一些特性信息来指导搜索，这些特性信　息主要作用是对节点的重要性进行评估，通过这　个评估来实现对状态空间的可能位置进行排序，　得出最小代价的位置，在状态空问中对每一个节　点进行评估，得到最优的节点，再从这个节点出　发进行下一节点的搜索，直到寻找到目标节点。　评估函数：　ｎ）＝ｇ（ｎ）＋ｈ（ｎ）－－－一　（ｎ）＝ｇ　（ｎ）＋ｈ　（ｎ）　４）将ＯＰＥＮ表中的点按照估价函数ｆ（ｎ）的值　排序，选出最小值的节点，将其作为下一个扩展　结点，将该最小节点放入ＣＬＯＳＥ表中，重复步骤　４），直至ＯＰＥＮ表中出现终点　这样，ＣＬＯＳＥ表中所存储的点就是Ａ　算法得　出的路径。　３　Ａ　算法的实例　本文针对如下简单路径采用Ａ　算法进行了模　拟，将ＡＧＶ活动区域形成“地图”，并将ＡＧＶ可　能起始的点、到达的点与路口分叉点作为节点记　录到“地图”中，在ＡＧＶ接受任务时，只需输入　其中：　收稿日期：２０１０－１２－２２　作者简介：谢辉辉（１９８５一），女，湖北人，研究生，研究方向为工业自动化物流系统。　第３３卷第２期２０１１－２（上）　【１１３１　ｌ　起始目的节点，该系统就会算出路径。　訇　化　ＣＬＯＳＥ表　５）选择Ｄ的三个点Ｃ，Ｊ，Ｈ，Ｌ（Ｊ）＝１０，Ｌ（Ｈ）＝ＩＯ，比　较候选点Ｉ，Ｅ，Ａ，ｃ，Ｂ，Ｇ，Ｊ，Ｈ，从点Ｊ，Ｈ中任意选择一　点，如Ｈ　６）选择与Ｈ有关的点，发现存在目标节点　Ｅ　１１　Ｆ　１２　Ｇ　１３　Ｈ　１４　１４，搜索完毕　［［二二］［二］二二工　口　最后到达终点，路径为：ｌ—Ａ—Ｂ—Ｃ—Ｄ—　图１路径图　如图１所示，点ｌ到点ｌ０以及点１４为ＡＧＶ的加　载点，点１１到１３是ＡＧＶ的卸载点，点Ａ到点Ｊ是分　岔路点。在ＡＧＶ活动区域内建立笛卡尔坐标系，　把ＡＧＶ每一个可能停留点设置为节点表明它的坐　标，所有的节点记录为ＡＧＶ的活动地图。　点Ａ（１０，０）Ｂ（２０，０）Ｃ（３０，０）Ｄ（４０，０）Ｅ（１０，１０），Ｆ（　２０，１０），Ｇ（３０，ｌ０），Ｈ（４０，ｌｏ），Ｉ（０，Ｏ），Ｊ（５０，０）为交叉点；　点１（３，０），２（７，０），３（１３，０），４（１７，０），５　（２３，０），６（２７，０），７（３３，０），８（３７，０），　９（４３，０），１　０（４７，０），１　１（１　５，１　０），１　２　（２５，１０），１３（３５，１０），１４（５０，１０）为ＡＧＶ的　起始点或者终点。选取每一个节点到终点的直线　距离作为ｈ半（ｎ）函数，即　ｒ＿———————：—————————　ｈ　（ｎ）＝４（ｘ１。Ｘ２‘＋Ｙ１一Ｙ２）‘　在数据库中建立表格，把每个节点相邻节点　记录到表中，同时在另一张表中记录他们的坐标　位置，从起点开始计算每一个相邻节点到目标节　点的距离，即ｈ　（ｎ），选取其中最小值作为下一个　节点，然后再次计算距离，再次排序，直到到达　终点。例如选取节点ｉＮ节点ｌ４的路径，步骤为：　１）选择１的两个分叉点Ａ和Ｉ，距离　Ｌ（Ａ）＝４１．２３，Ｌ（Ｉ）＝５０．９９，选Ａ点，将点Ｉ计入ＣＬＯＳＥ　表；　２）选择Ａ的三个点Ｉ，Ｅ，Ｂ，Ｌ（Ｅ）＝４０，Ｌ（Ｂ）＝３　１．６２，　比较三点距离后，比较候选点Ｉ，Ｅ，Ｂ选择Ｂ点，将点　Ｅ计入ＣＬＯＳＥ表；　３）选择Ｂ的三个点Ａ，Ｆ，Ｃ，Ｌ（Ｆ）＝３０，Ｌ（Ｃ）＝２２．３６，　比较候选点Ｉ，Ｅ，Ａ，Ｆ，Ｃ选择ｃ点，将Ｆ计入ＣＬＯＳＥ　表；　４）选择Ｃ的三个点Ｂ，Ｇ，Ｄ，Ｌ（Ｇ）＝２０，Ｌ（Ｄ）＝１０，　比较候选点Ｉ，Ｅ，Ａ，Ｃ，Ｂ，Ｇ，Ｄ选择Ｄ点，将Ｇ点计入　［１１４１　第３３卷第２期２０１１－２（上）　Ｊ—ｌ４　图２是采用Ａ：．＝算法进行ＡＧＶ路径规划的应用　程序界面，在该应用程序中，只需在界面上输入　起始目的结点，点击“计算路径”按钮，就会输　出ＡＧＶ从起始点到目的节点所应经过的节点，然　后ＡＧＶ可根据这些点的坐标位置进行路径选择，　从而引导ＡＧＶ直到目标节点。　图２采用Ａ　算法进行ＡＧＶ路径规划的应用程序界面　４结论　从上例的模拟计算可以看出，可以很容易算　单台ＡＧＶ起点到终点的最终路径，并且该ｈ　（ｎ）　的选取保证了所选路段为距离最优的路段，比较　符合对ＡＧＶ路径规划的要求。但在实际的生产环　境中，会有多台ＡＧＶ同时运行，所选路径会涉及　到碰撞、死锁等问题，需要在路径规划的基础上　增加对这些问题的复杂运算。这些需要根据现场　的环境要求对ｈ　（ｎ）和　（ｎ）做综合的评估和选取，　以此来满足不同要求的路径。　参考文献：　【１］钟建琳．制造环境中ＡＧＶ运输子系统的路径规划【Ｊ】．机械　设计与制造，２０１０（２）：２３７—２３９．　【２］林尧瑞，马少平．人工智能导论【Ｍ】．北京：清华大学出版社．