面向大型工件的改进A*无碰路径规划

陈洁涛

广东工业大学 广东 广州 510006

0 引言

当今,机器人在工业、科研探索以及服务业等领域都有广泛的应用,其应用都离不开路径规划[1]。用于实体喷涂的机器人路径规划方法存在效率低、实用性差等问题,如何有效提高喷涂机器人无碰路径的安全性和实用性已成趋势[2-4]。

随着自动化技术等高速发展,A*、RRT等智能算法在无碰路径规划得到了广泛的研究和应用[5]。传统的A*算法是基于栅格地图的算法,而传统A*算法在规划过程中拓展的节点数多,存在冗余点多以及路径长的问题[6-8]。为解决面向大型工件的无碰路径规划时建图和寻路效率低的问题,本文对传统的A*算法进行改进,提高运算效率。

(一)改进A*算法无碰路径规划

本文改进的A*算法,其代价函数的启动置于从起点直线到终点的过程中碰到障碍物前启动,并且在其子节点离开障碍物时,关闭代价函数的建立,然后判断是否可直线到达终点,若不能直接到达,则到达下一个障碍物前,继续建立代价函数直到找到终点为止。

如图1所示,改进A*算法流程:

图1 传统A*和改进A*在工字钢的仿真情况(绿色线-传统A*路径,红色线-改进A*路径)

1首先确保起点S和终点E在三维栅格地图中是可到达的点,如果不是则退出寻路过程;

2首先判断起点S到终点E之间是否可直线通过,若是则返回空路径,若否则继续;

3对起点S开始,把S作为待检查方格,寻找起点S周围可达方格,检测是否有不可达的点,若是则将起点S和周围可达的点都放入OPEN开启列表,开启寻路操作,跳转至⑤;若不是则进行快速接近,跳转至④;

4在三维栅格地图中,以起点B到终点E的方向开始遍历,直到接近障碍物为止,将临近障碍物的P点作为新的起始点S,寻找周围可达的点,并放入到OPEN开启列表;

5计算每个周围方格的F值,F=G+H,其中G值表示从起点S移动至指定方格的实际距离,H值表示从指定方格移动至终点E的估计距离。

6从OPEN列表中选择F值最低的方格a,将其从OPEN列表中删除,放入到CLOSE列表中;

7检查方格a临近方格,若周围都是可达方格,则进行快速接近,否则继续,并只检测方格a临近且可到达的点;

a)障碍物和CLOSE列表中的不考虑;

b)若不在OPEN列表中,则加入到OPEN列表中,并计算F值,将父方格设置为方格a;

c)若某相邻方格c已在OPEN列表,计算新的路径从S经方格a到达方格c,判断新的G值是否更低,则修改父节点为方格a,重新计算F值,H值不变;而如果G值更高,值不做改变;

8继续在OPEN列表中找出F值最小的,从OPEN列表删除,添加至CLOSE列表,继续寻找周围可达的方格,如此循环;

a)直到OPEN列表中出现方块E则路径找到;

b)而若OPEN列表中无数据,则无合适路径。

(二)仿真测试

在Matlab上进行仿真,设定栅格大小10mm*10mm*10mm,在仿真过程中取若干组起始点和目标点分别用传统A*算法和改进的A*算法在H型钢工件所构成的三维栅格形地图进行验证,分析两者的路径、长度和时间。

对比传统A*与改进A*两种算法,改进的A*算法能快速找到无碰路径,并减少节点的拓展数,在长度方面与传统A*算法近似,而在计算时间方面会优于传统A*算法,能够提高无碰路径搜索的效率;且对于离障碍物较远的起始点和目标点,改进A*的效率尤为显著。

(三)结语

本文对于喷涂机器人全覆盖路径规划过程中出现的路径过渡问题以及对大型工件建图所带来的大量的数据,采用改进的A*算法,减少节点的拓展,减少搜索时间,提高喷涂机器人寻找无碰路径的效率。