[doc] 一种动态未知环境中自主机器人的导航方法

1、一种动态未知环境中自主机器人的导航方法计算机研究与发展journalofcomputerresearchanddevelopmentissnl000一l239/cnlll777/tp42(9):1538l543,2005一种动态未知环境中自主机器人的导航方法孟伟黄庆成韩学东洪炳镕(哈尔滨工业大学计算机科学与技术学院哈尔滨150001)(mengw)amethodofautonomousrobotnavigationindynamicunknownenvironmentmengwei,huangqingcheng,hanxuedong,andhongbingrong(schoolofcomput

2、erscienceandtecbnoloky,harbininstituteoftechnology,harbin150001)abstractanautonomousnavigationmethodofrobotindynamicunknownenvironmentispresented.humansassistanceisusedinsteadofparticulardescriptionofmap.therearetwophasesinthismethod,whicharehumansguidingphaseandautonomousnavigationphase.inphaseofhu

3、mansguiding,aroughpolarcoordinatemapoflocalenvironmentisobtainedbymultisensorinformationfusionandthroughittheglobalmapisobtained.themethodofeliminatingsensordataerrorisalsogivenhere.accordingtomapobtainedinguidingphase,arobotmovesindynamicenvironmentinthephaseofautonomousnavigation.constraintconditi

4、onofrobotsmotioncontrolanddynamicobstacleavoidingmethodarealsopresented.robotcandisposeofemergentobstaclesinthismethod,andoptimizationofpathisalsoattained.experimentresultsshowtheeffectivenessofthismethod.keywordsautonomousrobot;sensorfusion;obstacleavoiding摘要提出一种动态未知环境中机器人自主导航方法,利用少量的人类辅助避免了繁琐的地图描述

5、.该方法分两个阶段:用户引导阶段和自主导航阶段.在用户引导阶段,利用多种传感器信息融合生成局部环境的粗略的极坐标地图,利用它可以得到全局地图,还给出了消除传感器数据误差的方法;在自主导航阶段,利用引导阶段得到的地图在动态环境中进行运动,并给出了运动控制的约束条件以及动态避障的方法.机器人利用该方法可以处理突发的障碍物,还能对路径进行优化,实验结果证明了其有效性.关键词自主机器人;传感器融合;避障中图法分类号tp181引言近年来,自主导航已成为机器人领域中的一个热点问题.根据机器人对环境的了解程度,可以分为两种类型:环境信息完全已知的全局导航和环境信息完全未知或部分未知的局部导航.对于环境信息完

6、全已知的情况已经有许多解决方法,例如可视顶点图法和voronoi图法等,但这些方法需要大量的计算时间来建立和搜索数据结构,因此不适用于存在运动障碍物的在线自主导航.为了获得实时性能,khatib_l提出了一种基于势场的方法,这种方法计算简单,易于实现,因而受到了极大关注.然而,人工势场法固有的缺点经常导致规划的失败.对于环境信息完全未知的情况,由于无法得到整个环境的地图,因此,主要采取了基于传感器的导航方法,例如滚动窗口法【,但该方法对障碍物的大小和形状具有一定的限制.收稿日期:20040317;修回日期:20050314基金项目:国家”八六三”高技术研究发展计划基金项目(2001aa4222

7、70);国家自然科学基金项目(69985002)孟伟等:一种动态未知环境中自主机器人的导航方法1539在实际应用中,机器人的工作环境大多处于两种极端情况之间的,即环境信息部分未知,环境的整体布局已知且环境中存在着不可预知的障碍物.本文主要研究在这种动态环境中移动机器人的自主导航问题.针对部分未知环境中的导航问题,一些研究人员采用了路标的方法.例如,maeyama等人l3j提出一种室外机器人导航的方法,用户选择特定物体作为路标(如树和灌木),但除了指定的路标外机器人不能识别其他物体,而且地图中只记录路标的信息,机器人只能沿路标引导的路径前进,无法处理突发事件.taylor等人l4提出了一种基于可

8、视路标的边界位置图法,但是该方法对于路标的设置限制条件较高.为了让机器人得到一些关于环境的先验知识,kidono等人j提出了一种通过人类引导的机器人导航方法,但仅利用了视觉信息,无法保证所产生地图的准确性,地图一旦生成将不再改变,当环境发生变化时,机器人无法躲避新出现的障碍物.matsumoto等人l6j提出利用引导过程中获得的图像序列进行导航,但机器人必须按照引导的路径前进,而且该方法很容易受到光照条件的影响.本文提出了一种未知环境中移动机器人的导航方法,整个导航分为两个阶段:用户引导阶段和自主导航阶段.在用户引导阶段,用户引导机器人从起始位置到达目标位置,在此过程中,机器人利用多种传感器对

9、环境进行探测,并生成周围环境的一个简单地图,同时记录行走路线.在自主导航阶段,机器人根据引导阶段获得的路径和地图信息自主运动.该导航方法利用人类的少量协助代替了繁琐的地图构建工作,可以应对不可预知的障碍,同时考虑了机器人的形状对于避障效果的影响.2地图的生成在环境动态变化的情况下,由操作人员为机器人生成环境地图和指明路标是非常繁琐的,而仅靠机器人自身来生成地图,则要对机器人的智能程度提出更高的要求.为此,本文在生成初始地图时,由操作人员引导机器人朝目标点运动,在运动过程中,机器人记录走过的路径,同时获取周围的环境信息,生成周围环境的一个简单地图,为自主导航阶段提供参考.2.1环境信息的获取与表

10、示本文中,机器人比较容易获得障碍物的距离和角度信息,因而采用极坐标地图来表示环境信息.极坐标地图是以机器人为中心对当前环境的描述,如图1所示.在极坐标地图中,用数字i(=0,“)表示根据障碍物的分布划分的区域,对于同一障碍物用同一数字表示,规定机器人正方向所在区域为0.若区域内存在障碍物,则该区域标记为丁,否则标记为f.若多个障碍物重叠在一起,可以看做一个障碍物.定义五元组z表示机器人对于某个点的感知信息,z=(,.v,r,0),其中(,.y)为机器人的当前位置;为机器人的当前偏转角,为该点与机器人的距离;p为该点相对于机器人正方向的角度.20fig.1polarcoordinatesmap.

11、图1极坐标地图在用户引导阶段,用户通过遥控设备引导机器人从起点到达目标点,在前进的过程中,机器人通过ccd和声纳等传感器感知环境,并生成地图.在进行信息融合前,需要对机器人的位置信息进行估计,由于里程计会导致误差积累,所以仅凭里程计信息和航迹推算很难准确地获得机器人的位置信息,为此采用了机器人运动的非确定模型和再定位的方法来克服累计误差.在引导过程中,机器人的各传感器同时对环境进行探测,ccd摄像机可进行俯仰或摇摆来观察周围环境,获得物体的距离和角度信息.围绕机器人的声纳采用基于栅格概率模型的方法来进行环境信息探测:=2/l”o”唧)./(1)在栅格模型中,利用贝叶斯模型来消除不确定性:p(s

12、(志+1)l2(志+1)=1540计算机研究与发展2005,42(9)p(2(k十1)ls(k)p(s(k)l2(k)(k+1)1si(k)p(k)1(k)(2)2.2多传感器信息融合为了保证所得数据的可靠性,首先利用分段校正法调整数据,然后利用自适应加权融合算法得到环境信息.设传感器实际输出为u实=f(),期望输出为u校=k2.按照数据的分布密度情况,将f()划分为段,当段足够大时,每一小段可看做是直线.u实=u+k(),其中u为该段的初始值;k,为第段直线的斜率;相应的校正直线方程为u校=(u一a)+k2().设第组传感器在某点校正后的数据为dd2,d,则其算术平均值可表示为_fj=d(3

13、)可能会出现多个点表示同一障碍物的现象,为了去除冗余信息,可利用下面的算法生成地图.step1.将所有障碍点放入集合a,i:=0,:=0;step2.i:=i+1,当前障碍集b,:=,取出a中的点p放入b,;step3.对于yp.b,若sp,a且lp一p.ik,将点p,放入b,;step4.若b不发生变化,则转step5;否则,转step3;step5.r=maxdis(p,p,f),计算b中心点p,南;step6.若a,转step2;否则,转step7;step7.j:=j+1,若bj=,结束;否则,转step8;step8.在地图中以0.表示障碍物,转step7.该算法简单实用,若机器人在

14、环境中多次行走,可以得到更为精确的地图.相应的标准误差为=.in1薯(dp.(4)3蛀导航设此前结果的方差=o.,则()=0.根据分批估计理论,融合后的方差为+:(一)一-十h一-h一-:,(5)l)+2)其中,h=(11)为测量方程的系数矩阵,r为测量噪声的协方差,且r=e1,1,=ee=0.1eu(i)u(2)e2)jl2)j(6)由分批估计导出的距离数据融合值d为d=(一)一d一十+hr一d=+hd.(7)将上述几式相结合,可得到融合后的数据值为西+:11盯l)+2)1一01)一10_=_盯2)+希2.3障碍物位置信息的合成机器人对同一障碍物可能进行多次探测,因而通过用户的引导,机器人不

15、仅得到了环境的粗略地图,还得到了一条到达目标点的路径(称为引导路径),并记录了该路径以及在各点观测的环境的信息.根据得到的环境地图,机器人可以规划出一条路径(称为规划路径),若规划路径优于引导路径,则在自主导航阶段将规划路径作为参考路径,否则将引导路径作为参考路径.为了便于说明给出以下几个概念.(1)保护区area:表示机器人周围一个半径为rpr0的范围,rpru=rb0+r.ll.,r.b0为机器人的半径,r.为避碰半径.保护区内的物体很容易与机器人发生碰撞.(2)探测区areadei:表示area.之外所有传感器均能准确探测的区域,半径记为.(3)可视区areaview:表示atea之外部

16、分传感器仍能探测到的区域,半径记为r.(4)子目标点subg:参考路径上均匀分布的离散点为机器人期望的位置点.机器人可以利用它知道正在跟踪哪段路径,在避开障碍物后应返回哪里.由于机器人采用多种传感器进行数据采集,各传感器的性能不同,其准确探测的范围也不同,为了能充分地利用各种传感器的性能,给出了3种区域:保护区,探测区和可视区,它们的半径满足r.<l,一dd.l孟伟等:一种动态未知环境中自主机器人的导航方法r<r,如图1所示.保护区使得机器人不会与障碍物发生碰撞,探测区可以保证各个传感器能够比较准确地探测到障碍物的信息,而对于可视区内的障碍物,只有部分传感器可以准确地探测到,但这些

17、传感器提供的信息可以使得机器人对环境进行预测,这样可以提高导航的效率,导航一般是在探测区内进行的.探测区与可视区的半径要综合考虑各个传感器的精确探测范围和最大探测范围以及机器人自身的因素.3.1运动约束机器人在自主导航的过程中,机器人可以按照参考路径向目标点运动,并进行路径的优化.在运动中,机器人除了要绕开已知障碍,还要能避免与突现的障碍物发生碰撞,同时以尽可能短的路径到达目标点.因此,机器人既要安全地在各个障碍物之间穿行,还要保持运动速度和平稳性,需要进行一定的限制条件,这里采用约束函数l8j对机器人的运动的5个方面进行评价,分别是运动平稳性,目标吸引性,安全性,不无限扩散性和快速运动性.3

18、.2动态避障在引导阶段,机器人得到了到达目标点的参考路径,然而,由于机器人的运动空间是动态变化的,所以引导路径上随时可能出现障碍物或其他意外情况,因此,机器人应当具有动态避障的能力.为了减少不必要的绕行,这里障碍物指在局部路径或机器人期望运动方向上距离较近的物体.若在探测区内路径上当前子目标点subg一.没有被障碍物隐藏,但其前面相邻的子目标点subg一.被障碍物隐藏,则物体处于该路径上.为简单起见,本文利用可视边缘到达路径的距离来作为参考.避障过程中机器人需要记住当前障碍物,以免丢失目标或者无休止的绕行,当绕过或移开当前障碍物后避障即可结束.fig.2exampleofreferencepo

19、int.图2参考点示例避障的过程中可设置参考点来引导机器人.为了提高可靠性,可选择同一障碍物上的多个点作为参考点.参考点方向是相对较好的可能路径的一个方向.参考点p是如下确定的:设机器人的当前位置为r,机器人正方向与障碍物的外边缘切线角度为a0,切点为a.以ar的中心点为圆心,ar为直径做圆0l,以a为圆心,dp=rr【)l1.+d为半径做圆02,0l与02交于p点,pr与机器人正方向形成的方向角为a,若a>a,则点p为所求参考点(如图2所示).因为机器人的探测范围大,因而可以很早发现障碍,并得到其边缘信息,利用参考点绕过障碍,而无需走近障碍物后再沿其边缘绕过障碍.3.3速度计算及行为优

20、化由于环境中障碍物的存在以及机器人的旋转速度,需要不断地调整机器人的线速度.在保护区内若存在障碍物,则机器人很可能与之发生碰撞,机器人应当停止运动.假定保护区内有,z个障碍物,障碍物0与机器人的距离为,一,则机器人的线速度可通过下式得到:va=(v一v.)堡r.一r.b.t+v.(9)机器人的线速度v,为v(i=1,)的最小值,若存在障碍物距离机器人小于,则机器人停止运动.机器人在运动过程中,并非只是沿着参考路径前进.除了可以躲避障碍物,还可以对路径进行优化.机器人既可以保证能够到达终点,而且还可以缩短运动的距离和时间,提高效率.4实验与分析为了验证本文所提导航方法的有效性,在轮式移动机器人上

21、进行了实验.利用声纳和ccd摄像机获取环境信息.从实验结果可以看出,机器人通过多个传感器的数据融合可以获得较为准确的环境信息,与实际数据误差较小,可以作为导航的依据.实验1.机器人定点间运动(如图3所示).机器人从起点出发,依次经过abcd点到达终点,在该过程中要绕过灰色的障碍物.虚线部分为人引导机器人走过各点并到达终点的路径.在引导路径上放置了新的障碍物(图中的黑色障碍物),机器人实际的运动路线如实线所示.从图中可以看出,突发障碍物和路径不够优化是路径变化的主要原因,若机器人的运动环境没有发生变化,实际路径通常会优于引导路径,这也证明了该方法的有效性.实验2.机器人在走廊内依次按abcd的顺

22、序到这4个房间内传送物品(如图4所示).1542计算机研究与发展2005,42(9)机器人实际的运动路线如图4中实线所示,虚线部分表示引导路线.从图4可以看出,机器人不仅完成了到达各个房间的任务,而且所走过的路径要优于引导路径.3fig.3experimentresultofnavigation图3导航实验结果fig.4experimentresultofnavigation图4导航实验结果5结论本文给出了一种在动态未知环境中利用少许人类辅助的移动机器人导航方法.该方法利用多传感器融合生成环境地图,并利用极坐标地图的导航方式运动,可以缩短机器人的运动时间和距离,处理出现的突发障碍物,还能够对路

23、径进行优化,避障效果良好.参考文献1o.khatib.realtimeobstacleavoidanceformanipulatorsandmobilerobots.internationaljournalofroboticsresearch.1986.5(1):90982zhangchungang,xiyugeng.rollingpathplanningofmobile4678robotinglobalunknownenvironment.scienceinchina(seriese),2001,31(1):5158(inchinese)(张纯刚,席裕庚.全局环境未知时基于滚动窗口的机器人路

24、径规划.中国科学(e辑),2001,31(1):5158)s.maeyama,a.ohya,s.yuta.nonstopoutdoornavigationofamobilerobot.in:proc.1995ieee/rsjintlconf.intelligentroboticsandsystems.losalamitos,(,a:ieeecomputersocietypress.1995.130135camillo.j.taylor,dj.kriegman.visionbasedmotionplanningandexplorationalgorithmsformobilerobots.iee

25、etrans.roboticsandautomation,1998.14(3):417427k.kidono,j.mjura,y.shirai.autonomousvisualnavigationofamobilerobotusingahumanguidedexperience.roboticsandautonomoussystems,2002,40(2):12113oy.matsumoto.m.inaba,h.inoue.visualnavigationusingviewsequencedrouterepresentation.in:proc.ieeeintlconf.roboticsand

26、automation.losalamitos.ca:ieeecomputersocietypress.1996.8388tengzhaosheng,luolongfu,tongtiaosheng,autonomousdetectionsystemanddatafusion.beijing:mechanicalindustrialpress,1999(inchinese)(滕召胜,罗隆福,童调生,智能检测系统与数据融合北京:机械工业出版社,1999)jingxin西jan,wangyuechao,tandalong.cooperativemotionbehaviorsusingbiologymo

27、delingbehaviordecisionmakingrules.controltheoryandapplications,2003,20(3):407410(inchinese)(景兴建,王越超,谈大龙.基于仿生行为决策规则的协调运动行为.控制理论与应用,2003,20(3):407410)智能机器人,多智能体系统,机器学习孟伟等:一种动态未知环境中自主机器人的导航方法l543hongbingrong,bornin1937.heisprofessoranddoctoralsupervisorincomputerapplication.hiscurrentresearchareasareintelligentrobot,multiagentsystem,andvirtualreality.洪炳镕,1937年生,教授,博士生导师,主要研究方向为智能机器人,多智能体系统,虚拟现实researchbackgroundthisresearchissupportedbythenationalhightechnologydevelopmentprogramofchinaundergrantno.2001aa422270andthenationalnaturalsciencefoundationofc:hinaundergrantno.699