收稿日期:2007-06-20基金项目:山东省优秀中青年科学家科研奖励基金项目(03BS149)作者简介:纪晴(1983-),女,山东德州人,山东建筑大学在读硕士,主要研究领域为嵌入式系统、无线传感网络等.文章编号:1673-7644(2007)04-0355-05移动机器人全覆盖路径规划算法综述纪晴,段培永,李连防,王海鹏(山东建筑大学信息与电气工程学院,山东济南250101)摘要:各种应用型移动机器人的设计是目前研究的焦点,它具有广阔的科研价值和市场前景,而路径规划技术是其中关键技术之一。本文系统总结了当前全覆盖路径规划算法的主要研究成果,并在覆盖效率、算法实现难易等指标方面进行比较剖析,探讨了各种算法的优势和不足。最后,提出进一步研究的方向。关键词:移动机器人;全覆盖路径规划;栅格;子区域中图分类号:TP24�����文献标识码:AOverviewofCCPPalgorithmsformobilerobotsJIQing,DUANPe-iyong,LILian-fang,etal.(SchoolofElectricalEngineering,ShandongJianzhuUniversity,Jinan250101,China)Abstract:Nowadays,manycountriesarefocusingontheresearchofvariouskindsofmobilerobotsbecauseoftheirrichvalueonscientificresearchandwideforegroundonmarket.Thepathplanningalgorithmisoneofthekeytechnologiesusedinmobilerobotdesign.Inthispaper,themainachievementsonthealgorithmresearcharesummarized,someanalysisandcomparisonisshowedinthecoverageefficiencyandthefeasibilitytoachievethealgorithms,andfinally,thefurtherresearchdirectionsarepointedout.Keywords:mobilerobots;completecoveragepathplanning(CCPP);grids;sub-regions0�引言��在欧美日等发达国家,移动机器人开发较早,近两年来已开发出多种面向市场的智能家用机器人。但总的来看,智能机器人的研究还刚刚起步,在自主能力和工作效率上还有待提高。而路径规划技术是目前发展较快、对移动机器人发展影响较大的关键技术之一。全覆盖路径规划技术有两层含义即要求机器人的运动具有遍历性和不重复性。它对清洁机器人、游泳池机器人、擦窗机器人、草坪修剪机、矿藏探测器、扫雷机器人等都具有重要意义。全覆盖路径规划可分为两类:无环境模型的规划和基于环境模型的规划。在此基础上移动机器人的全覆盖路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的方法主要有栅格表示法、可视图法(几何表示法)和拓扑图法(自由空间法)。下面根据这三种方法将目前主要路径搜索策略分类分析。1�基于栅格表示法的路径规划1.1�基于绕障的梳状规划让机器人先沿房间墙边走过一遍,记录房间特征及障碍物特征,将房间划分为大致与机器人等大的小栅格,每个栅格用一个累计值CV表示自方位障碍物的存在可能性(图1)。然后对整个房间梳状往复式遍历:机器人沿某一方向上覆盖,遇到障碍物第22卷第4期2007年8月���������山东建筑大学学报JOURNALOFSHANDONGJIANZHUUNIVERSITY���������Vol.22No.4Aug.2007时将进行邻域的搜索,若经过判断前方的障碍物为可绕障碍物,采用绕障算法,绕障后要保持在原来的方向上,直至到达边界或遇到不可绕障碍物后平移一个车距,以相反方向往回走(图2)。该方法虽然简单,但由于转弯次数较多,效率不高。而向内螺旋式行走路径更适合于完成全覆盖任务,但其用于障碍物复杂的情况下覆盖效率也会变低。图1�栅格地图图2�梳状遍历示意图1.2�基于生物激励的路径规划算法根据生物物理学家Hodgkin和Huxley提出的著名的神经细胞膜的电路模型和描述细胞膜的动力学模型(H-H模型)[1],Grossberg[2]提出了神经动力学网络模型,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是指当...
