基于改进A*算法的AGV路径规划

陈晓冬王福威
辽宁石油化工大学信息与控制工程学院

运路径规划是AGV(automatedguidedvehicle)技一参数的指数(如工作一代的最小值,选择最短的路径,最短的操作时间等)[1],AGV在仓库的众多可以行术发展的关键技术之一.AGV的路径规划技术是指某驶的路线中选择一个最优的路径,该路径可以连接起始点和目标点,并且同时躲避道路上的障碍物[2].它的本质就是AGV在进行路径规划的时候会受到很多个外界条件的干扰,在此干扰的条件下寻找到最优路径或者可行解.AGV经过全局路径规划得到的路径的好坏会直接影响AGV完成货物分拣任务的进度[3].

常用的全局路径规划的方法有蚁群算法[4,5]、人工鱼群算法[6–8]、概率路图法[9]、粒子群算法[10–13]及A算法[12–14]等.也有一些应用于局部路径规划的算法,包括人工势场法[15–17]和动态窗口法[18–21]等.A算法作为典型节点搜索式算法,在不同场合具有很强实用性.

目前,A算法是一种常见的AGV路径规划方法,文献[22]提出采用自适应系数对评价系数进行加权,在搜索前期,希望能快速找到方向,该方法虽然提高了搜索速度,但是生成的路径不是最优路径;文献[23]提出将传统的A算法的8邻域搜索进行扩展至32邻域,该方法虽然扩大了搜索范围,但是存在AGV在运作的过程中存在穿墙的可能性;文献[24]提出将人工势场法与蚁群算法结合,机器人能够很好地局部避障,但路径轨迹平滑度不高.

针对以上的不足之处, 考虑通过使用动态加权, 改变搜索邻域的方法对传统的 A算法提出改进, 最后使用高阶贝塞尔曲线对 A算法规划出来的路径进行平滑处理.

1 传统的 A算法 A算法经典的启发式算法之一,与传统的快速扩展随机树算法不同的是,A算法为了使路径规划在搜索时搜索的方向更加清晰,它在自己的搜索领域里面加入了启发函数[25].A算法的核心是,确定起始点与目标点后,按照起始点周围上下左右,左上,右上,左下,右下这8个方向进行搜索和评估,并计算这8个点的估价函数值最小的点,并把这个点放入open列表中,再从这个点的周围上下左右,左上,右上,左下,右下8个方向进行搜索和评价,重复上述过程,直到搜索到目标节点.经过多次的搜索与评估最终找到一条从起始点到目标点的最短路径.

A*算法的代价函数定义如下:
f(n)=g(n)+h(n)(1)

其中,g(n)代表AGV在路径规划的途中从当前移动到的节点到起始节点所消耗的实际代价,h(n)代表AGV在路径规划的途中从当前运动到的节点到目标节点所消耗的估计代价,也就是A算法的启发函数.g(n)是已知的,所以A算法的优势主要体现在它的启发函数上,h(n)代表了A算法搜索的启发信息.换句话说,g(n)体现了A算法的广度优先趋势.如果h(n)=0,那么只有g(n)实际上是有用的,这时A*算法退化成迪杰斯特拉算法,它能保证一定可以找到一条最优路径,但是它浪费了时间去探索那些没有前途的方向.

A*算法的优劣就体现启发函数的选取上,目前常用的启发函数有欧几里得距离,曼哈顿距离和对角线距离.为了提高AGV的搜索效率,也就是让AGV的实际成本大于估计成本,本文使用欧几里得距离作为启发函数进行评估.
h(n)的欧氏距离计算公式如下: