【doc】智能割草机的区域全覆盖算法设计与仿真

【doc】智能割草机的区域全覆盖算法与仿真 智能割草机的区域全覆盖算法设计与仿真 第29卷第3期 2012年3月 机电 JournalofMechanical&ElectricalEngineering Vo1.29No.3 Mar.2012 智能割草机的区域全覆盖算法设计与仿真 许兴军 (浙江大学电气自动化研究所,浙江杭州310027) 摘要:为解决无导航功能的智能割草机割草区域最佳覆盖的问,提出了"单元分解目标区域,并逐一覆盖"的区域全覆盖算法.首 先介绍了区域全覆盖的总体策略,接着基于特定割草机硬件,采用了单元分解法作为全区域覆盖算法的整体策略,对每个子区域则 选择往复式行走方式进行逐一覆盖.然后具体提出了无障碍物区域和两障碍物区域的离线全覆盖算法,并对有障碍区域的算法加以 了改进和推广.随后基于Matlab软件,对有两圆形障碍物的圆形区域进行了全区域覆盖算法的仿真实验.实验结果表明,所提出的区 域全覆盖算法可以实现割草区域的最优覆盖. 关键词:智能割草机;区域全覆盖;电子篱笆;全覆盖仿真;Madab 中图分类号:TP391;TH69;TP242文献标志码:A文章编号:1001—4551(2012)03—302—05 Desiffandsimulationongionalall-o~veredalgprithmOeslRnansimulation0nre,tonalaover eclal~orithm ofintelligentmower XVXing-jan (InstituteofElectricalAutomation,ZhejiangUniversity,Hangzhou310027,China) Abstract:Inordertosolvetheproblemofcoveringthelawnareabytheintelligentmowerwithnofunctionofnavigation,aregionalall— coveredalgorithmbydecomposingthetargetareaandcoveringonebyonewaspresented.Firstlytheregionalall—coveredstrategywas introduced,thenthecelldecompositionalgorithmwasselectedasaregion-widecoverageoftheoverallstrategybasedonthehardware conditionsofthemower,andthewalkingwayofbackandforthwasusedforeachsub— area.Adetaileddescriptionoftheoff-linealgorithm forfullcoveragewaspresentedtotheregionwithnoobstacleandtwoobstacles,andthealgorithmforregionwithobstacleswaspromoted andimpmved.Theregionalal1一 coveredalgorithmforacircularareawithtwocircularobstacleswastestedbasedonMatlab.The experimentalresultsshowthattheregionalall-coveredalgorithmpresentedcanachievethebestcoverageofthetargetlawnarea. Keywords:intelligentmower;regionalall-covered;electronicfence;all— coveredsimulation;Matlab 0引言. 对于移动机器人而言,传统的路径规划指点到点 的最优路径规划,其目标是寻求一条从起始点到终点 的无碰撞的最优路径,该路径大多是点到点的线段序 列.割草机器人的路径规划是基于全区域覆盖运行的 路径规划(CompleteCoveragePathPlanning,CCPP),所 谓全区域覆盖是指移动机器人的运行轨迹要能够无 遗漏覆盖整个工作区域.因此全区域覆盖的路径规划 目标是产生一条有效路径来覆盖工作环境的每块可 达区域.除了割草机器人外,基于CCPP的移动机器人 有很多应用场合,如清洁机器人,喷漆机器人,地表探 测机器人等,因此CCPP的研究越来越受到关注H_7]. 割草机器人的工作环境一般比较复杂,基于已知 环境模型的精确路径规划在实践上一般较难实现,且 对定位系统的分辨率要求较高,从而增加了系统的成 本和实现的难度.市面上多数智能割草机出于成本考 虑,硬件配置有限,所以本研究从智能割草机的实际 出发设计区域全覆盖策略. 1智能割草机控制原理 本研究通过对市场上现有智能割草机的,可 收稿日期:2011-10—08 作者简介:许兴军(1986一),男,浙江萧山人,主要从事智能控制器,工业生产智能化 方面的研究.E-mail:xuxin~un@gmail.conl 第3期许兴军:智能割草机的区域全覆盖算法设计与仿真?303? 获得智能割草机控制框架图如图1所示. 图1智能割草机控制结构图 智能割草机控制原理的分析内容主要包括:电 源,传感器系统,控制系统,割草系统以及行走系统5 个方面,具体分析如下: (1)电源.24V的蓄电池可直接为割草系统和行 走系统提供电源,经变压器降压后才能为传感器系统 和控制系统提供电源. (2)传感器系统:红外传感器,具有避障的作用. 当割草机靠近障碍物时,红外传感器能帮助识别障碍 物,并将这一信息传送给控制系统以避开障碍物. 雨滴传感器,具有避雨的作用.在下雨的环境下, 落到割草机上的雨滴能被雨滴传感器识别,控制系统 获得信号后将驱动割草机到无雨区避雨. 角度传感器,具有保证人身安全的作用.当割草 机遇到斜坡翻转或被小孩提起成一定角度时,角度传 感器能将这一信号传送给控制系统,控制系统会立即 关闭割草电机,保证人身安全. 碰撞传感器,既能保证人的安全也能保证小车的 安全.一旦小车受到一定强度碰撞,控制系统会关闭 小车所有电机.这样可以避免小车受损,如果被撞的 物体是人,也就保障了人的安全. 电子篱笆传感器,它一方面可以保证割草机始终 在电子篱笆所围的范围内割草,另一方面是割草机返 回充电所依据的路线. (3)控制系统.控制系统的核心是CPU,它一方面 接收传感器系统,割草系统和行走系统的信号,并根据 这些信号通过相应的运算得到结果,再根据结果来控 制电机驱动器以实现对割草系统和行走系统的控制. 另一方面它还能接收无线模块的信号以实现人工控制 割草机运行. (4)割草系统.控制系统中的割草电机驱动器能 驱动割草电机,从而带动刀片的转动,以实现割草功 能.该系统中的电流传感器用于保护割草电机,因为 当刀片意外卡住时,电路中的电路会立刻变大而烧坏 电机.但电流传感器能将电流值反馈到控制系统,一 旦出现过流,控制系统就会立刻关闭割草电机以防止 烧坏. (5)行走系统.行走系统中有两个直流电机,分别 控制割草机的两个轮子.直流电机先作用于齿轮,由 齿轮来带动轮子转动,以实现割草机的前进和后退. 它也由控制系统控制,此处的电流传感器所起的作用 与割草系统中电流传感器所起的作用一样,都起保护 电机的作用. 2区域全覆盖策略选择 2.1智能割草机约束条件 (1)智能割草机具有两对相互垂直的电子篱笆传 感器,具体结构如图2所示.电子篱笆信号与传感器 和篱笆线的距离以及两者之间所成的角度有直接关 系,一般来说,传感器与篱笆线的距离越远,角度越 大,电子篱笆信号就越弱.所以图中传感器1,2此时 能检测到很强的电子篱笆1的信号,却几乎检测不到 电子篱笆2的信号.同样传感器3,4此时能检测到很 强的电子篱笆2的信号,却几乎检测不到电子篱笆1 的信号.因此,本研究通过传感器的信号状况可以判 断电子篱笆的位置. 电子篱笆1 电 子 篱 笆 2 图2电子篱笆传感器结构 (2)直线行走和转弯.经实验表明,本研究的割草 机在平地上能实现直线行走,转弯的半径也能得控制. (3)无法定位.即割草机运行时的位置信息未知. 因为本研究的割草机是一个商业化产品,鉴于成本的 考虑,在割草机上没有装备用于定位的硬件. (4)无记忆路径功能.因为本研究无法记录已行走 的路径,故无法判断现在所处的位置是否已经覆盖过. 2.2覆盖选择 由于移动机器人的全区域覆盖在现实生活中具 有广泛的应用,近年来,国内外许多学者进行了大量 ? 304?机电工程第29卷 的研究,出现了很多覆盖方法,如随机覆盖策略,单元 分解法,基于模板的方法,基于传感器的覆盖方法等, 各种方法都具有一定的适用场合和优缺点. 随机覆盖策略是指机器人无法直行时就随机地 转个角度继续前进,该策略对机器人的感知和计算能 力要求不高,无需定位传感器且算法简单,但不能保 证完全覆盖整个区域,重复覆盖率高,效率很低.本研 究中割草机的硬件条件虽然比较符合该方法,但由于 不能保证完全覆盖,使得割草机完成不了任务,故不 采用该方法. 单元分解法可保证区域的完全覆盖,是目前全区 域覆盖算法中运用最广的方法之一.它以障碍物为边 界,将空闲区域分解为一些互不重叠的单元,由于单 元中不包含任何障碍物,机器人可用简单的往返运动 实现单元覆盖,区域的全覆盖就转变为从一个单元到 另一个单元的运动规划.该方法最关键的问题就是区 域划分和实现单元衔接,若能解决这两个问题就能实 现全区域覆盖,这是一个可选择的方法. 基于模板的方法是根据已覆盖区域所获取的先 前信息,将当前环境信息与各个模板进行匹配;重复 地预测新区域并执行区域覆盖,从而整个覆盖路径就 转换成执行一系列不同的模板.该方法需要记忆一些 模板,本研究的割草机无法达到此要求,故该方法对 本研究不适用. 基于传感器的全区域覆盖是指在未知环境中利 用传感器的信息寻找一条路径,使机器人或机器人的 传感器遍历所有区域并执行相应任务.该方法对传感 器要求很高,对本研究也不适用. 因此,单元分解法比较适合本研究的智能割草 机,本研究也将采用该方法. 2.3单元行走方式选择 首先,本研究考虑无障碍时能充满整个区域割草 机的行走方式.其规划过程应遵循如下原则:?保证 区域全覆盖;?规划出的路径便于控制,易于实现;? 割草时间尽量短,消耗能量尽量少.从能耗方面来说, 割草机直线行走消耗的能量相对来说比较少,当割草 机曲线行走时,所消耗的能量就比较大.对于控制系统 来说,直线行走比较容易控制,曲线行走就很难控制, 所以割草机应尽可能选择直线段作为主要运动轨迹. 通常割草机以直线运动方式充满整个工作区的 路径类型有:随机方式,往复方式及螺旋方式(包括内 螺旋和外螺旋).如采用不同的行走路径,割草机的覆 盖区域效率和效益上都会不一样,在割草机消耗的时 间和能量上也会不一样,行走路径越长,转弯次数越 多则割草机消耗的能量和时间也就越多.随机方式不 管是在区域覆盖率还是消耗时间上都是不理想的,所 以这里不予考虑.当区域边界为曲线时,采用螺旋的 方式就会导致割草机曲线行走,那样不但消耗能量大 而且难于控制.若强制要求割草机直线螺旋,则边界 地区的覆盖就会出现问题. 当区域内有障碍物时,本研究就需要对区域进行 分割,然后让割草机在各子区域内分别完成完全覆 盖.由于本研究的割草机没有自导航功能,割草机对 自身的位置并不明确.如果采用内螺旋方式,它在子 区域内最后停留的地方大致在子区域重心,这时让它 自主地从该子区域精确的行走到另一个子区域,在没 有导航的情况下基本上是不可能实现的.同样的道 理,若采用向外螺旋,那么起点的位置就很难定位. 综上所述,本研究选择往复式行走路径,在没有 障碍时它不但能实现完全覆盖,而且在边界是曲线的 情况下依旧能保证行走,这不但耗能少而且易于实 现.在有障碍的情况下,通过一定的方法划分子区域, 它也能保证直线行走,并且它在完成白区域覆盖后会 停留在子区域边界,这样在无导航的情况下,割草机 也能从这一子区域进入其相邻的未被覆盖的子区域 进行覆盖. 3区域全覆盖算法设计 智能割草机需覆盖的区域类型分为两种:基本 (无障碍)区域和有障碍区域.对于基本区域,由于没 有障碍,容易覆盖.有障碍区域又可分为简单有障碍 区域和复杂有障碍区域. 3.1基本区域的覆盖 基本区域是指具有任意闭合曲线边界且内部无 障碍物的区域,它是智能割草机全区域覆盖运行空间 的最基本的单元. 本研究选择水平方向作为割草机行走方向,并采 用反复式覆盖来覆盖这一区域,具体情况如图3(a)所 示.图中的实际边界指的是需要覆盖区域的边界;名 义边界指覆盖过程中到达实际边界后,需要进行转 向,其转向顶点组成的边界.名义边界比实际边界多 出一个转向半径.因为这样使得割草区域超出了边 界,后期笔者对此进行了改进,如图3(b)所示,主要是 (a)传统原理图(b)改进后原理图 图3基本区域覆盖原理图 第3期许兴军:智能割草机的区域全覆盖算法设计与仿真 让割草机提前开始转弯,不过这样造成的问题就是在 边界区域会有一部分草坪因为割草机转弯而被遗漏, 为了解决这一问题,在割草机覆盖完整个区域后,本 研究再让其沿着边界行走一圈,以实现真正的全覆 .一 J吐O 3.2有障碍区域的覆盖 有障碍区域是指由一条闭合曲线包围的,其内部 含有静止和运动障碍的区域.对于运动障碍物(如动 物和车辆等),割草机器人探测到后,控制系统驱动它 停止直至运动障碍离开它的运动轨迹,当超过预定等 待时间后,控制系统将其处理为静止障碍.对于静止 障碍物,如果是一般小型物体(如树木,标杆等),可直 接绕过,如果是大型的(如花坛,水池等),则在全局路 径规划中予以考虑. 有障碍区域可以按基本直线运动方向划分为若 干个无障碍物的基本区域,然后按一定的次序不重复 地分别覆盖各个基本区域.对于基本区域的确定,本 研究可以用障碍物在水平方向的切线作为边界对区 域进行划分,然后用从左到右或从右到左的割草方式 来进行整体区域的覆盖. 本研究考虑一个比较复杂的有障碍区域如图4(a) 所示,该草地区域边界是曲线的,内部还有两个曲线边 界的障碍区域.正如上面所说的,对于这样的区域,本研 究可以水平线去分割区域,以障碍物的切线为边界对区 域进行子区域的划分,运用从右到左的策略,对图4(a) 划分区域后,可以得到3个子区域,如图4(b)所示. (a)有障碍区域原图(b)划分子区域 图4有障碍区域划分子区域 对于划分后的子区域,本研究可以采用基本区域 的覆盖方式进行覆盖,具体如图5所示.智能割草机 的起点为A,随后割草机就水平向前行进对区域进行 覆盖,直到到达边界再转弯,其运行模式和基本区域 覆盖基本一样.当割草机对区域1覆盖完毕后,它就 会沿着障碍物的边界曲线C2行走到点B,再沿着边 界曲线c1回到点c,这是为了清除割草机转弯引起 的遗漏的地方.然后,割草机再次沿着障碍物的边界 曲线c2行走到点B,由此衔接到区域2,并作为区域 2覆盖的起点.对区域2的覆盖仍旧和基本区域覆盖 (a)对区域1的覆盖(b)对区域2的覆盖 (C)对区域3的覆盖(d)对全区域的覆盖 图5有障碍区域覆盖原理图 方式一样,当割草机完成区域2的覆盖后,它也会沿 着障碍物边界曲线c3,C4绕障碍物一圈后,再沿着 C4行走到点c,从而进入区域3,并且C作为区域3 覆盖的起点.同理完成区域3的覆盖,到达终点D.最 后,再由终点D让割草机沿着边界曲线绕一圈以清除 遗漏草坪,这样智能割草机也就完成了对整个有障碍 区域的完全覆盖. 3.3全覆盖策略的推广 上述研究讨论了两个障碍物的情况,若障碍物增 长到n个,可以将上述方法做如下推广: 如果障碍的数目为n,那么平行分割线的数目为 2n,被分割的基本区域为n+l,在这n+1个基本区域 内做局部路径搜索n次以产生2n个有向弧C( 1,...,2n一1).通过基本区域R(1,...,n一1)的覆盖操作和产生有向弧C(i=l一.,2n一1)的局部路径搜索操 作,智能割草机依次经过每个基本区域,有向弧也能 首尾相接.如果把启始点和结尾点连接起来,移动机 器人整个行走路径将是封闭的.整个区域覆盖过程是 连续,不间断的. 考虑到实际情况,本研究将割草机来回直线行走 间的距离调整为割草机宽度的一般,以获得50%的余 量来确保100%的覆盖. 4基于Matlab的区域全覆盖仿真 4.1系统建模 (1)智能割草机.在给出车体模型之前,假定如下: 轮式移动智能割草机和地面之间是纯滚动的;轮 ? 306?机电工程第29卷 式移动智能割草机在平面之上运行;轮式移动智能割 草机是后轮驱动,后轮差动转向;轮式移动智能割草 机不考虑侧倾对横向运动的影响. 再考虑到智能割草机头部和尾部都是圆弧型的, 本研究就用一个半径为0.2cm的圆表示.这样割草机 每次割草宽度为0.4cm,并以0.2cm作为其转弯半径. (2)边界和障碍物.仿真中的边界均用深灰色的 直线或曲线表示,它是一些坐标的集合体.障碍区用 深灰色填充区域表示,其边界也依旧用深灰色直线或 曲线表示. (3)草坪.浅灰色区域代表未被割草机覆盖的草 坪,黑色区域则代表已被覆盖的草坪. (4)电子篱笆信号.由于实际的电子篱笆信号与 传感器和篱笆线的距离以及两者之间所成的角度有 关系,距离越远信号越小,角度的余弦值越小信号越 小.由此,本研究采用如下公式来模拟电子篱笆信号: : ,/[nOW(N)-bod(x)]+【nD(y)一6od(y COS0=Inow(z)一bod(x)I?, S=L?cos0 式中:nOW(X)一割草机当前位置的坐标;o(,,)一割 草机当前位置的Y坐标;bod(x)一边界A点的坐标; bod(y)一边界A点的Y坐标;一割草机当前位置离 边界A点的距离;cos割草机当前位置与A点的连 线和割草机前进方向所成脚的余弦值的绝对值;5一 割草机接收到的某一小段A电子篱笆产生的信号. (5)信号搜索范围.当割草机和边界的距离大于 某个值后,割草机接收到的电子礼包信号几乎可以忽 略,所以在模拟割草机接收信号的时候本研究设定了 搜索范围,本研究的搜索范围是以割草机的质心为圆 心,以0.4cm为半径的圆形区域. 4.2区域全覆盖仿真 对应基本区域的仿真,由于不存在子区域间衔接 的问题,仿真相对比较简单,选定起点后进行往复式 覆盖后都能实现全覆盖目标.对于有障碍区域的仿真 关键在于两点:?区域的划分;?子区域间的衔接.然 后根据基本区域覆盖的仿真算法就能实现对单障碍 物区域,双障碍物区域的覆盖仿真. 本研究对复杂的圆形边界双圆形障碍物区域进 行了全覆盖仿真实验,具体如图6所示.本研究先把 整体区域分成3个子区域,从区域1开始覆盖,如图6 (a)所示.本研究按同样的方法进行往复式覆盖,完成 对区域1的覆盖,如图6(b)所示.接着再沿障碍物边 界绕行1圈半,一方面清除了因转弯而在障碍物边界 引起的遗漏草坪,另一方面也使得割草机进入区域2 进行覆盖,如图6(c)所示.本研究采用同样的方法就 可以完成对区域2,3的覆盖,最后沿草坪边界绕行一 圈以实现对整个区域的全覆盖. 圈圈围(a)开始(b)覆盖区域1(c)进入区域2 圈圉圈(d)覆盖区域2(e)覆盖区域3(f)完全覆盖 图6双障碍物区域全覆盖仿真 仿真结果表明,采用本研究的区域全覆盖算法, 理论上可以实现目标区域100%的覆盖. 5结束语 本研究通过仿真效果图证明了笔者提出的区域 全覆盖策略的可行性,但该方法仍有一定局限性:? 提出区域全覆盖策略是基于本研究的智能割草机特 定的硬件条件而设计的,虽然对于本研究的割草机是 最优的策略,但如果智能割草机的硬件条件提升,如 割草机能准确定位时,该策略将不再最优;?如果覆 盖区域或障碍物边界十分不规则,那么该算法的编程 工作量会很大,且实际覆盖效果也将受影响;?该算 法假设覆盖区域地面是平整的,故如果地面有坡度, 基于该算法将无法实现目标区域的完全覆盖. 参考文献(References): [1]李开生.通用擦窗机器人控制系统体系结构的研究和实现 [D].北京:北京工业大学机电学院,2001. [2]张毅刚,刘杰.单片机原理及应用[M].哈尔滨:哈尔滨 工业大学出版社,2004. [3]方建军,何广平.智能机器人[M].北京:北京化学工业出 版社,2004. [4]朱长宏.轮式可移动机器人的研究[D].南京:南京航空航 天大学机电学院,2001. [5]章小兵,乔茹,赵光兴.基于改进蚁群算法的移动机器人 全局路径规划[J].机电工程,2009,26(3):90—93. [6]刘松,李志蜀,李奇.机器人全覆盖最优路径规划的改 进遗传算法IJ1.计算机工程与应用,2009,45(31):245—248. [7]祖莉.割草机器人全区域覆盖运行的控制和动力学特性 研究[D].南京:南京理工大学机械工程学院,2005. [编辑:李辉]