A*算法在移动机器人自学习中的使用*

张燕,徐一超,盛洲

(南京大学金陵学院,南京210089)

A*算法在移动机器人自学习中的使用*

张燕,徐一超,盛洲

(南京大学金陵学院,南京210089)

通过让移动机器人在未知环境下的自学习过程来得到环境地图,然后利用A*算法进行最优路径规划,并选取路径中的关键节点传给移动机器人,移动机器人就可以根据这些节点自主运行。通过移动机器人自主运行实验,可以看出其运行效果良好。

路径规划;A*算法;自学习;二维地图

引 言

自主移动机器人是一种通过传感器来感知和探测周围未知环境并在收到命令后进行自主移动的智能系统[1]。移动机器人能否进行高效率的导航移动即能否在环境中移动到目的地,是衡量机器人定位技术的关键[2]。移动机器人自学习需要以下几部分技术,首先需要获取未知环境下的障碍物地图,其次需要移动机器人知道自己的位置信息,最后需要使用路径规划算法进行路径规划。

目前常用的环境信息是通过传感器进行数据获取的,机器人避障和测距传感器主要有红外、超声波、激光及视觉传感器[3]。激光传感器和视觉传感器价格较贵,对控制器的要求较高[4],因而,在移动机器人系统中多采用红外及超声波传感器。因此本设计中采用超声红外传感器进行数据获取。目前移动机器人定位技术很多,常见的有内部传感器定位技术、主动传感器定位技术、视觉传感器定位技术、全球卫星定位技术[5]。综合考虑成本等因素,本设计使用内部传感器定位技术,采用里程计和陀螺仪进行位置定位。路径规划技术就是要机器人在障碍物环境中,寻找一条从出发点到目标点的合适路径,保证按照该路径行走时,不发生碰撞,并且满足一定的约束条件[6],根据周围环境信息是否已知,可分为全局路径规划技术和局部路径规划[7]。全局路径规划技术应用最普遍的是简单栅格法[8],并且由于周围的环境已知,故得出路径前,必须每次都要对全局环境进行处理。局部路径规划侧重于移动机器人当前周围环境的局部信息,并利用传感器来探测周围环境信息,然后进行实时路径规划。自学习功能需要在未知环境走一圈之后,根据获取的全局障碍进行路径规划,因此采用全局栅格地图的方式来实现。

1 系统组成和结构

对于移动机器人路径规划系统设计,硬件部分如图1所示,移动机器人下位机CPU是一个基于Cortex-M3内核的芯片,位置信息由里程计获取。超声红外传感器获取障碍物距离信息,九轴传感器中的陀螺仪用来获取角度信息。移动机器人的运动通过串口控制舵机运行,上位机通过无线模块进行数据通信。

2 移动机器人位姿和障碍信息获取

2.1 里程计

里程计即为用来测量移动机器人位移的霍尔传感器,本设计使用的是霍尔元件A3144,其能够感知磁钢信息。当磁钢靠近霍尔传感器时,传感器中的绿灯会亮,并输出低电平,用数字“0”表示输出低电平;当磁钢远离霍尔传感器时,传感器中的绿灯灭,又回到原来的高电平,用数字“1”表示输出高电平。当车轮转动时,固定在车轮上的每个磁钢会不断地靠近和远离霍尔开关传感器,这时就会在示波器上显示出方波。

图1 移动机器人路径规划结构框图

为了使测量的移动机器人行程信息更加准确,本设计在一个车轮轮彀上贴4个磁钢。如果只计算一个车轮转过的圈数,会因为车轮偶尔出现的打滑有较大的误差,因此在移动机器人对角线的两个车轮上分别安装4个磁钢,对两个车轮测得的位移取平均值,以此来减小一个车轮打滑所产生的误差。整体布局情况如图2所示。

图2 磁钢分布的位置

软件上采用GPIO中断的方式读取数据,每次CAP口捕捉到下降沿的时候,则计数一次,这样根据捕捉到的下降沿的个数,就可以知道磁钢和霍尔传感器相互感应的次数,再乘以每次感应的一个周期内车轮转过的距离,就可以得到机器人行走的距离。因为需要采集两个车轮的数据,采用两个GPIO中断获取数据,然后再去取平均值,以此来减小误差。

假设左前轮上里程计与磁钢感应的次数为n1,右后轮上的次数为n2,如图3所示,测得机器人车轮的周长L为20 cm,最后机器人中心点O行走经过的路程S为:

2.2 陀螺仪和电子罗盘

移动机器人获取角度信息可以采用陀螺仪或者电子罗盘,陀螺仪通过对角速度积分,便能得到角度值,但是时间较长会产生零漂。而电子罗盘可以直接获取角度信息,但是容易受周围磁场干扰。本设计考虑用两者进行数据融合获取角度信息。陀螺仪选用ITG3205,电子罗盘选用HMC5883L。为了减少一些电磁干扰,电子罗盘外加了屏蔽罩。两者与CPU的连接使用的是I2C接口,其I2C的软地址分别为0xd0和0x3c。硬件连接如图4所示。

图3 路程的测量

图4 角度传感器引脚连接

2.3 位姿获取

移动机器人位姿获取采用了航姿推算法计算机器人相对于初始位置的位移角度信息。

2.4 障碍物信息获取

为了得到机器人的周边环境信息,需要使用传感器。本文使用超声云台传感器和红外传感器结合起来获取障碍物信息。对于超声云台,通过I/O口控制超声传感器旋转,可以测量前方180度的障碍物信息,返回给CPU的是障碍物距离信息。其具体的流程如图5所示。首先根据移动机器人运动速度调整云台转速,让其很好地获取每一个角度的信息,而后依次获取前方5个点的信息,此时采样完成,由于超声传感器有时候由于镜面反射之类的原因,存在无判断,因此采用滤波算法进行处理,由于篇幅问题这里不再赘述。

图5 障碍物信息获取流程图

由于超声云台只能够获取前方障碍物信息,为了使移动机器人运行获取周围障碍物信息,设计采用4个红外传感器,分别布局在前方两个,左方一个,右方一个。通过探测4个方向近距离处是否有障碍物,来指导机器人运动,避免碰撞到障碍物,同时获取障碍物信息。

3 移动机器人路径规划研究

3.1 A*算法简介

A*算法是一种启发式搜索算法,即机器人对路径规划中所要搜索的点会预估其代价值,其代价值是猜测得到的,并不是实际测量的[11]。A*算法中最关键的公式是表示每一个节点代价值的预估代价函数F:

式中,G表示起始点到当前点的实际代价值,也即沿着路径移动到指定方格的移动耗费;H表示当前点到目标点的预估代价值[12]。为了简化计算,减小路径规划的时间复杂度,规定水平和垂直方向上的方格距离为10,对角线上距离为14。预估代价值H由曼哈顿函数计算得到[13],曼哈顿函数的计算方法就像在城市中从一个地方行走到另一个地方,在行走过程中是不能沿着对角线方向行走来穿过障碍物的,只可以通过直角转弯来绕过障碍物,而曼哈顿计算的就是从起点行走到终点所经过的街区数。因此预估代价值可以用数学表达式表示为:

其中(ax,ay)表示起点的坐标,(bx,by)表示终点的坐标。简言之,在计算预估代价值时,应忽略一切障碍物,只计算当前点坐标与终点坐标差的绝对值之和。进一步来说,预估代价值的计算是估算得到的,并不是通过测量计算得到的,这也是A*算法被称为启发式算法的原因。

A*算法实现过程中,需要建立两个列表[14]:open表和close表。open表中存放的是当前节点周围的可以访问到的节点,这些节点不仅包括水平和垂直方向上的,还包括对角线上的节点,最多就是该节点周围的8个节点,放在open表里的节点必须是非障碍物节点且不在open表或close表中的。close表则存放已经访问过的节点。

首先,寻路的第一步应该是简化搜索区域,即用一个二维数组来表示搜索区域,网格中的每一个方格可以用二维数组中的坐标来表示。其中方格用蓝色表示为不可通过,用黑色表示即为可通过,并且路径也可以被描述为从A到B所经历的方块的集合。其中的每一个格子会被当做节点对待,因为这样做有利于描述不规则的地图图形,节点能够被放置在地图中的任何位置,可以在格子的中心,也可以在格子的边界[15]。若直接用方格来描述,会比较麻烦,而且不够准确。

其次,将起点A作为待处理节点存放到open表中,由于open表中此时只有A节点,所以A节点即为当前点,然后把起始点A从open表中取出放入关闭列表中。判定A点周围可以通过的点并加入open表中,此时open表中会有8个节点,即为A节点周围的8个格子,将A点设置成这些可通过点的“父方格”。

每个加入开启列表里的方格都有一个F值,标注出了起始点周围8个节点对应的F、G、H的值。经过多次取出,open表里F值最小的方格加入close表中,并比较G值大小来决定是否改变当前点的父方格,最终就可以得到close表中的格子集合,即所要求得的最短路径。可以知道从起始点到目标点路径规划中所需要用到的点,及各个点对应的值的大小、指针指向等信息。如果从目标点开始沿着其指向父方格的指针开始寻找,最终能够到达起始点,这条路径就是通过A*算法来规划出的最优路径。

3.2 A*算法实现

具体实现流程图如图6所示。

图6 A*算法实现流程

4 上位机界面设计

4.1 串口通信界面设计

本设计使用Labwindows CVI进行上位机界面设计,首先编写串口通信界面,如图7所示。

图7界面左边几个复选按钮可以实现串口、波特率、校验位等选择,第一个文本框可以输入字符,通过串口发送到下位机,第二个串口可以接收下位机发过来的传感器数据。具体传感器数据格式如图8所示。

陀螺仪角度数据与超声传感器距离数据由分号隔开。第一部分的陀螺仪字符型数据被修改成整型数据,默认单位为度(°);第二部分为超声传感器发送的5个方向的距离数据,默认单位为厘米(cm),认为其可使用距离为30～ 100 cm;第三部分为里程计所获取数据,用“P”与红外测距传感器隔开,默认单位为厘米(cm);第四部分为红外测距传感器发送的4个方向(左右侧面各一个,正前方左右轮处各一个),默认单位为厘米(cm)。需要指出的是,根据实际测试,某一方向上红外传感器如果没有感知到障碍物,就发送“99”,因此,当收到“99”时认为距离足够远,这里是由于红外传感器测距方位在4～30 cm之间,不会达到99。

4.2 环境地图绘制界面设计

接下来编写环境地图绘制界面,要能够在界面上实时绘制地图,且在上位机利用获取的全局地图使用A*算法进行路径规划,如图9所示。

图9设计了环境网格地图,可以在移动机器人自学习的时候进行起始点和目标点的设置,进行路径规划,能够将A*算法计算的关键节点显示出来,同时显示关键节点的距离角度信息。该界面是串口通信界面的子界面,能够点击图7中的“打开地图”按钮进入,点击图9的“退出”按钮,退回到图7界面。

5 实验结果及分析

5.1 A*算法在上位机的仿真

为了验证A*算法的正确性,在上位机上对A*算法用VC做了仿真测试。分别选取U型图、Z型图来作为环境地图进行测试。实验结果如图10所示。

图9 环境地图界面

图10 A*算法验证

图10(a)是一个22×21的网格,设起始点为(0,3),目标点为(7,5)。其中白色圆圈表示的路径即为最短路径,白色矩形路径为其他路径,只需要证明白色圆圈走过的路径小于其他路径的距离,即可证明A*算法得出的路径即为最短路径。通过计算,可以得到白色圆圈经过的距离为10×23+14×12=398,白色矩形路径经过的距离为10× 25+14×11=404。很明显398小于404,并且在确定此起始点和目标点后,找不出有比白色圆圈路径更短的路径,因此在此环境中,A*算法得到的是最短路径。

图10(b)是一个23×24的网格,我们设起始点为(2,1),目标点为(19,19)。其中白色圆圈表示的路径仍为最短路径,白色矩形路径为其他路径。通过计算,可以得到白色圆圈经过的距离为10×31+14×12=478,白色矩形路径经过的距离为10×30+14×13=482。很明显478小于482,并且在确定此起始点和目标点后,找不出有比白色圆圈更短的路径,因此在此环境中,A*算法得到的是最短路径。

5.2 利用传感器绘制环境地图

为了验证移动机器人传感器获取的环境信息,在实验室搭建环境进行测试。图11(a)、(c)为实际环境,(b)、(d)为对应的传输到上位机的传感器数据经过解析之后绘制出来的地图,可见基本上障碍物信息能够绘制出来。地图中会存在一些数据的缺失,这是由于移动机器人运行时红外传感器探测过程中的误差导致,但是整体数据说明探测情况还是基本符合实际地图的。

图11 移动机器人环境地图绘制

5.3 A*算法进行路径规划

在上位机能够进行环境地图绘制的基础上使用A*算法进行路径规划,并且通过路径规划得到关键点指导移动机器人自学习。对于环境C进行A*算法处理,图12中节点1显示的是起始点,节点7为目标点,其中灰色曲线为算法规划的路径曲线,选取一些关键节点传输给移动机器人,让其进行自主运行。

从图12(a)、(b)两张图中可以看出,关键点-1即第一个关键点(图中节点2)与起点(图中节点1)的距离为200 cm,与其角度为0度,它们之间有9个格子,再加上关键点共10个格子,乘以20 cm的比例尺,得到200 cm是正确的结果,且关键点1与起始点在同一直线上,所以其间角度的确实为0度。图(b)中对于关键点0(图中节点3),即表示第二个关键点(图中节点3)与第一个关键点(图中节点2)的距离为28 cm,与其角度为45度,它们之间有1个格子,再加上特殊点共2个格子,但对角线的距离应是直角边的1.4倍,乘以14 cm的比例尺,得到28 cm是正确的结果。故在上位机得到的关于关键点间的距离和角度值是正确的。

图12 关键点角度和距离的测量曲线

结 语

本文设计了可以探测未知环境的移动机器人,能够通过传感器获取移动机器人的位姿信息,实现了下位机与上位机的无线通信,在此基础上,利用A*算法实现了移动机器人路径规划和指导移动机器人自主运行。搭建一些实验环境,通过移动机器人运行结果说明有一定的效果,当然还存在一些不足,譬如对于动态障碍物就无法实时更新地图进行重新规划,接下来会对于动态路径规划作进一步的研究。

[1]许亚.基于强化学习的移动机器人路径规划研究[D].济南:山东大学,2013:78-83.

[2]Kazuo Sugihara,Ichiro Suzuki.Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots [J].Journal of Robotic Systems,1996,13(3):127-139.

[3]张洪,钱胜,陈路.多传感器在确定智能小车安全区域中的应用[J].传感器与微系统,2013,32(12):145-147.

[4]韩保亮.基于多传感器的机器人环境建模与导航[D].南京:南京师范大学,2013:2-4.

[5]庄春华,赵治华,张益青,等.卫星导航定位技术综述[J]. 2014,3(2):34-36.

[6]Willms A R,Yang S X.An efficient dynamic system for realtime robot-path planning[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2006,36 (4):755-766.

[7]H R Everett.Sensors for Mobile Robots[M].New-York:Theory and Applications,1995:568-789.

[8]Ulrich I,Borenstdn J.VFH+:Reliable obstacle avoidance for fast mobile robots[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation,1998.

[9]王耀宾.超声导航移动机器人系统设计及模糊避障技术研究[D].青岛:中国海洋大学,2008:1-3.

[10]Tao Gao,Zhen Jing Yao.Sensors Network for Ultrasonic Ranging System[J].International Journal of Advanced Pervasive and Ubiquitous Computing(IJAPUC),2013,5(3): 47-59.

[11]刘军.基于改进蚁群算法的移动机器人路径规划研究[D].郑州:郑州大学,2010:92-95.

[12]Jin F,Hong B.Path planning for free-flying space robot using ant algorithm[J].Robot,2002,24(6):526-529.

[13]汪浩杰.多机器人系统中围捕策略的研究[D].武汉:华中科技大学,2007:37-43.

[14]Kazuo Sugihara,Ichiro Suzuki.Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots [J].Journal of Robotic Systems,1996,13(3):127-139.

[15]张前哨.基于A*算法的地图寻径的研究[D].武汉:武汉科技大学,2005.

张燕(讲师),主要从事嵌入式系统以及移动机器人的研究。

(责任编辑:薛士然 收修改稿日期:2016-05-24)

Usage of A*Algorithm in Self-learning of Mobile Robot

Zhang Yan,Xu Yichao,Sheng Zhou
(Jinling College of Nanjing University,Nanjing 210089,China)

The unknown environment is studied by the sensors to get the environment map,then A*algorithm is used to get the optimal path planning.The key nodes are choosed by the algorithm and then are passed to the mobile robot.The mobile robot can move autonomously according to these nodes in the same environment.The experiment results show that the robot can run well.

path planning;A*algorithm;self-learning;2D map

TP751.1

:A

省部级江苏省高校自然科学研究面上项目申报书(15KJB510013)。