移动机器人全覆盖路径规划算法综述.pdf

收稿日期:2007-06-20基金项目:山东省优秀中青年科学家科研奖励基金项目(03BS149)作者简介:纪晴(1983-),女,山东德州人,山东建筑大学在读硕士,主要研究领域为嵌入式系统、无线传感网络等.文章编号:1673-7644(2007)04-0355-05移动机器人全覆盖路径规划算法综述纪晴,段培永,李连防,王海鹏(山东建筑大学 信息与电气工程学院,山东 济南 250101)摘要:各种应用型移动机器人的设计是目前研究的焦点,它具有广阔的科研价值和市场前景,而路径规划技术是其中关键技术之一。本文系统总结了当前全覆盖路径规划算法的主要研究成果,并在覆盖效率、算法实现难易等指标方面进行比较剖析,探讨了各种算法的优势和不足。最后,提出进一步研究的方向。关键词:移动机器人;全覆盖路径规划;栅格;子区域中图分类号:TP24?文献标识码:AOverview of CCPP algorithms for mobile robotsJI Qing,DUAN Pe-i yong,LI Lian-fang,et al.(School of Electrical Engineering,Shandong JianzhuUniversity,Jinan 250101,China)Abstract:Nowadays,many countries are focusing on the research of various kinds of mobile robots because oftheir rich value on scientific research and wide foreground on market.The path planning algorithm is one of thekey technologies used in mobile robot design.In this paper,the main achievements on the algorithm researchare summarized,some analysis and comparison is showed in the coverage efficiency and the feasibility to achievethe algorithms,and finally,the further research directions are pointed out.Key words:mobile robots;complete coverage path planning(CCPP);grids;sub-regions0?引言?在欧美日等发达国家,移动机器人开发较早,近两年来已开发出多种面向市场的智能家用机器人。但总的来看,智能机器人的研究还刚刚起步,在自主能力和工作效率上还有待提高。而路径规划技术是目前发展较快、对移动机器人发展影响较大的关键技术之一。全覆盖路径规划技术有两层含义即要求机器人的运动具有遍历性和不重复性。它对清洁机器人、游泳池机器人、擦窗机器人、草坪修剪机、矿藏探测器、扫雷机器人等都具有重要意义。全覆盖路径规划可分为两类:无环境模型的规划和基于环境模型的规划。在此基础上移动机器人的全覆盖路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的方法主要有栅格表示法、可视图法(几何表示法)和拓扑图法(自由空间法)。下面根据这三种方法将目前主要路径搜索策略分类分析。1?基于栅格表示法的路径规划1.1?基于绕障的梳状规划让机器人先沿房间墙边走过一遍,记录房间特征及障碍物特征,将房间划分为大致与机器人等大的小栅格,每个栅格用一个累计值 CV 表示自方位障碍物的存在可能性(图 1)。然后对整个房间梳状往复式遍历:机器人沿某一方向上覆盖,遇到障碍物第 22 卷第 4期2007 年8月?山 东 建 筑 大 学 学 报JOURNALOFSHANDONG JIANZHU UNIVERSITY?Vol.22No.4Aug.2007时将进行邻域的搜索,若经过判断前方的障碍物为可绕障碍物,采用绕障算法,绕障后要保持在原来的方向上,直至到达边界或遇到不可绕障碍物后平移一个车距,以相反方向往回走(图 2)。该方法虽然简单,但由于转弯次数较多,效率不高。而向内螺旋式行走路径更适合于完成全覆盖任务,但其用于障碍物复杂的情况下覆盖效率也会变低。图 1?栅格地图图 2?梳状遍历示意图1.2?基于生物激励的路径规划算法根据生物物理学家Hodgkin 和 Huxley 提出的著名的神经细胞膜的电路模型和描述细胞膜的动力学模型(H-H 模型)1,Grossberg2提出了神经动力学网络模型,Yang 和 Meng 又将这种生物激励的神经网络应用于移动机器人运动的环境建模和路径规划 3-6。将房间划分成的小栅格作为一个神经元,通过生物激励神经网络模型的动力学激励公式来判断栅格的激励值大小:dxi?dt=-Axi+(B-xi)?Ii+?Wij Xj+-(D+Xi)Ii-,其中 Xi代表第i 个神经元的状态;A,B 和D 是非负常数,A代表衰减速率,B 和D 代表神经元状态的上下限;Ii为外部输入。下一个时刻位置是 Pn:Pn?Xpn=max Xj+Cyj,j=1,2,?,k,其中:C 是一个正常数;k 是邻域的神经元的总数;yj定义为yj=1-?j?,这里?j是指当前时刻和下个时刻的方向角改变的绝对值大小(图 3)。该方法考虑遍历最短的路径和转弯最少,能跳出死角和避开障碍物,达到完全遍历,但不足是重复率较高。在此基础上通过生物激励和启发式模板相结合的方法能够得到有很好的改善性能指标。图 3?当前神经元的邻域和路径规划示图意2?基于可视图法的路径规划?Neumann de Carvalho R 7等人在环境地图已知的前提下,在实际机器人平台上进行了基于行为模板的路径规划研究,将机器人的行为划分为多种固定的模板,根据实际位置选择合适的模板,最后实现路径的遍历(图 4)。该方法的不足是需要预先知道环境地图,改进是可以通过让机器人首先沿墙边行走完成对环境地图的大体构建,然后通过实时检测到的环境信息选择合适模板进行启发式行走,但此法的实现较困难。3?基于拓扑图的路径规划?子区域的分割方式如图 5 所示。(1)双线扫法。子区域分割采用适用于平行四356?山 东 建 筑 大 学 学 报?2007年?图 4?七个固定的行为模板示意图图 5?子区域分割示意图边形障碍物且其边大多平行于区域边沿的?双线扫法?。即用两根想象中的交叉长线分别?扫?过整个待覆盖的区域。又名 Boustrophedon Cellular Decom-position 法 8。HowieChoset 等人在梯形单元分解基础上提出一种左右来回运动分解法,将环境分成从左到右的单元切片,利用单元之间连接关系生成邻接图(图 6)。图 6?双线扫法示意图(2)Q-M 图法。采用 Quine 和 McCluskey(简称Q-M 法)7-9提出的用于电路上寻找最大素蕴含的方法,提取给定环境中所有基本矩形自由区域,并用这些自由区域作为节点构造连通图。3.1?基于旅行商问题(TSP)的路径规划9,10机器人沿首先沿墙边走后,记录环境特征。将房间按障碍物划分为若干子区域,将各个子区域缩成节点、子区域重心间距离缩成节点连线,建立起含障区域的全连通图?广义距离矩阵模型,然后对Hopfield 神经网络(CHNN)求解旅行商问题进行改进后,将其用于求该模型的最优有向连通图,即确定子区域衔接顺序。机器人按最优路径完成覆盖,即无重复的走过连通图中的所有节点(图 7)。该算法中广义距离阵数量级、系数等需要反复试探,且 CHNN算法本身容易收敛到局部极小,甚至发散。图 7?子区域分割图及对应的连通图3.2?基于图的遍历算法11图的遍历就是从图中任一顶点出发访遍途中其余顶点,且使每个顶点仅被访问一次的过程。图的遍历思想跟全覆盖路径规划有相似之处。遍历图的规则一般有两种:广度优先搜索和深度优先搜索两种盲目型搜索方式。同样地,先沿墙边走建立起环境模型,再把机器人工作区域分割成子区域后,将每个子区域视为一个结点。根据自区域之间的连接关系,可得到结点之间互连的网状图形结构。对房间的遍历即转化成图中的所有结点的遍历(图8)。结合子区域357?第 4期?纪晴等:移动机器人全覆盖路径规划算法综述?覆盖的顺序,当机器人有一个子区域进入下一个子区域时,搜索最短路径作为进入点。该种算法随着子区域的变大,不能保证搜索全覆盖距离最短。图 8?有向图表示3.3?基于二叉树的路径规划12,13四叉树表示方法就是递归地将整个工作平面分成四个子部分、子子部分,直到得到一些块,这些块内的元素要么全为 0(0 表示全部为可覆盖区域),要么全为 1(表示全部为障碍物区域)。由建立的环境模型先对房间进行四叉树的划分,然后对四叉树进行元素为 0(下图中用白色小方格表示)的节点搜索(图 9)。这种方法的优点是适用于障碍物较多的复杂环境中,但易出现死锁现象。3.4?基于标志点的路径规划14-16利用机器人超声波传感器识别环境中的标志,图 9?一个工作平面及其对应的四叉树表示如墙角(分为凹点和凸点),还有一般的障碍物。这些环境标志以及标志之间的连线构成拓扑图中的点和边,机器人在运动的过程中依据这些信息建立环境拓扑地图,利用深度优先搜索拓扑顶点,并不断更新地图。当搜索完环境中的所有标志点,机器人就覆盖了整个空间(图 10、11)。该算法通过神经网络分类器来识别真实环境标志,机器人通过搜索图可以实现房间的有效覆盖,但在实际情况下,如果没有直墙这类的环境边界作参考,离开一段距离后,机器人的运动路线会偏离水平基本运动,从而在子区域的覆盖面积将会减少。3.5?随机与局部规划相结合的混合路径规划17-19它最重要的思想是将随机方式和局部规划方式通过时钟或传感器信息决策循环切换,同时将错综复杂的环境信息模糊为几类情况,实时地监测机器人运行状态。具体为:首先进行环境学习,在随机覆盖过程中,一旦遇到障碍物,随机转过某一角度,若前方没有障碍,继续直进覆盖,直到遇到另一障碍物。当根据房间面积设定的随机覆盖时间达到或者认为当前覆盖位置处于角落时,脱离随机覆盖过程,图 10?基于标志点的环境表示转入局部规划方式的覆盖。首先选定覆盖方向,然后进行梳状覆盖,当遇到障碍不再采取绕障行为,而是平移一个车距后反方向继续覆盖,这样反复此过程,直到结束条件满足,重新返回随机覆盖过程(图12)。该算法比局部遍历的覆盖效率降低,但算法中的随机性保证了算法具有较低阶的期望复杂性。另外,该算法已成功用于浙江大学的 HSR2000 自主吸尘机器人中。358?山 东 建 筑 大 学 学 报?2007年?图 11?基于标志点的路径规划图 12?局部规划与随机覆盖相结合的路径规划4?展望?本文较为详细地分析介绍了目前主要的移动机器人全覆盖路径规划算法,虽然机器人的全覆盖路径规划算法研究取得了很大进步,但大多数算法离具体应用到实物中还有一定的距离,需要完善。而目前自主机器人在行为上大多还处于?低智能?阶段,环境感知能力有限,对路径的规划只是随机的方式或基于局部环境信息的方式 20,在复杂环境下,这种工作方式的效率会大大降低。因此,建立CCD 视觉系统,融合多种传感器进行定位和环境建模 21,从而实现移动机器人的全覆盖路径规划完全智能化将是今后一段时期一个重要的研究方向。参考文献:1?Hodgkin A L,Huxley A F.A quantitative description of membranecurrent and its application to conduction and excitation in nerve J.Phys Lond,1952,117(4):500-544.2?Grossberg S.Nonlinear neural networks:principles,mechanism,andarchitectures J.Neural Networks,1988,1(1):17-61.3?Yang S X,Meng M.Neural network approaches to dynamic collision-free trajectory generation J.IEEETransactionson Systems,manand-cybernetics-part:Cybernetics,2001,31(3):302-331.4?Yang S X,Meng M.An efficient neural network approach to dynamicrobot motionplanning J.Neural Networks,2000,13(2):143-148.5?Ni B,Chen X.New approach of neural network for robot path planningA.Man and Cybernetics,2004 IEEE International Conference onSystemsC.2004,1:735-739.6?Yang,S X,Luo C M.A neural network approach to complete cover-age path planning J.Systems,Man and Cybernetics,Part B:IEEETransactions,2004,34(1):718-724.7?Carvalho R N,Vidal H,Vieira P.Complete coverage path planningand guidance for cleaning robots A.Proceedings of the IEEE Interna-tional Symposium on Industrial Electronics C.1997,2:677-682.8?Choset H.Coverage of known spaces:the boustrophedon cellular de-composition J.IEEE Autonomous Robots,2000,9(3):247-253.9?Qiu X N,Song J T,Zhang X J,et al.Complete coverage path plan-ning methodformobile robot in uncertain environmentsA.IntelligentControl and Automation,WCICA 2006 C.2006,2:8892-8896.10?Chen H H,Du X,Gu W K.Path planning method based on neuralnetwork and genetic algorithm A.Proceedings of the 2004 Interna-tional Conference on Intelligent Mechatronics and Automation C.2004,1:667-671.11?Yao Z Y.Finding efficient robot path for the complete coverage of aknown space A.Intelligent Robots and Systems,2006 IEEE?RSJInternational Conference C.2006.3369-3374.12?Kristen S,Pamela JH,David W.Autonomy and common ground inhuman-robot interaction:a field study J.Intelligent Systems,2007,22(2):42-50.13?Petres C,Pailhas Y,Patron P,et al.Path planning for autonomousunderwater vehicles J.Robotics,2007,23(2):331-341.14?Amiram M,Gideon A.The extended concep-t based mult-i objectivepath planning and its a-life implications A .Artificial Life,ALIFE?07,IEEE Symposium C.2007.259-265.15?Chang S J,Dan B J.Free moving pattern?s online spanning tree cov-erage algorithm A.SICE-ICASE.International Joint Conference C.2006.2935-2938.16?Karras D A.Neural network models based on regularization tech-niques for off-line robot manipulator path planning A.NeuralNetworks,Proceedings,2004 IEEE International Joint Conference C.2004,1:25-29.17?Qiu X N,Liu S R,Yang S X.A rolling method for complete cover-age path planning in uncertain environments A.Robotics and Bio-mimetics,ROBIO 2004 IEEE International Conference C.2004.146-151.18?Luo C M,Yang S X,Stacey D A.Rea-l time path planning withdeadlock avoidance of multiple cleaning robots A.Robotics andAutomation,Proceedings,ICRA?03 IEEE International ConferenceC.2003,3:4080-4085.19?Stack J R,Smith C M.Combining random and data-driven coverageplanning for underwatermine detection A.OCEANS 2003Proceed-ings C.2003,5:2463-2468.20?华东东,李旭.车辆路径问题的改进遗传算法研究 J.山东建筑大学学报,2006,21(2):148-150.21?Acar E U,Choset H,Ji Y L.Sensor-based coverage with extendedrange detectors J.Robotics,2006,22(1):189-198.359?第 4期?纪晴等:移动机器人全覆盖路径规划算法综述?