（机械电子工程专业论文）吸尘机器人非结构环境下自主路径规划方法的研究.pdf

浙江大学坝l 学位论文 1b 石u l z 3 全文摘要 吸尘机器人遍历路径规划足实现机器人智能的一个关键部分，本文主要以吸尘 机器人在非结构化环境中的自主路径规划殴计为中心，通过对吸尘机器人的一些关 键技术一智能控制技术、路径规划技术等的研究，提出一种适应性较强的路径规划 方法，以达到最终实现吸尘机器人家居环境中自主、独立工作的f 1 的。 本文共由五章组成：第一章首先概述了吸尘机器人技术, f h , p t l d l 人路径规划的主 要算法。第二章则介绍了遍历路径规划实现的两种方案，以此作为后续研究的指导。 第三章针对环境中障碍静止且室内环境局部已知的情况，提出一种将环境边界确定 性考虑在内的遍历路径规划方法，并且对算法进行仿真卉：且给出模拟非结构化环境 中的实验结果。第四章针对第二章提出算法的缺点，排l 山不确定伯感器信息的影响， 试验一种随机规划与局部路径舰划相结合的混合路径规划方法。该算法不考虑全局 定位，只利用局部有效定位信息，对复杂环境的适应性增强。同时，遍历路径规划 过程中也考虑运动障碍的影响，设7 , 4 。相应“逃离”算法。另外，在遍历规划结束后， 设计同归充电座的路径规划方法，并目论证各种定位误筹下晌回归必然性。最后， 给m 各个算法的实验结果并给j 弘分析。 关键词：吸尘机器人，路径舰划，逊障，遍历，智能控制，甲片机，非结构环境 浙江大学硕 j 学位论文 a b s t r a c t c o v e r a g ep a t hp l a n n i n g 1 sap i v o t a l p r o b l e m f o r c l e a n i n g r o b o tt oa c h i e v e i n t e l l i g e n c e i nt h i sd i s s e r t a t i o n ，t h ea u t o n o m o u sp a t hp l a n n i n g i nu n s t r u c 协r e de n v i r o n m e n t i sd e s c r i b e d ，a l o n gw i t ht h er e l a t e dk e yt e c h n i q u e ss u c ha s i n t e l l i g e n tc o n t r o la n dp a t h p l a n n i n ge t c a ni d e a a b o u t c o v e r a g ep a t hp l a n n i n gi sp u tf o r w a r dt oa c c l i m a t ea l lk i n d so f c o m p l e x c o n d i t i o n si no r d e rt oi m p r o v et h e a p p l i c a t i o no f c l e a n i n gr o b o t i nt h e f a m i l y l i f e f i r s t ，c h a p t e r1g i v e sas u r v e yo fa l g o r i t h m sa b o u ti n t e l l i g e n tr o b o ta n d p a t hp l a n n i n g t e c h n i q u e s - c h a p t e r2d e s c r i b e st h ea i ma n dd e t a i l e dc o n t e n t so ft h i sr e s e a r c hp r o j e c t ，a n d f i n a l l yt h ei m p l e m e n t a t i o n so f a l g o r i t h m sa r ea l s ot h e o r e t i c a l l ys u m m a r i z e di nt h i sc h a p t e r c h a p t e r3 ，b a s e do nt h ea c t i o n l e s so b s t a c l ea n dk n o w ni n d o o re n v i r o n m e n t ，aw a yo f c o v e r a g ep a t hp l a n n i n gi sg i v e nc o n s i d e r i n gc o n f i r m a b i l i t yo f e n v i r o n m e n t b o r d e r l i n e ，t h e n t h e a l g o r i t h mi se m u l a t e da n dt h et e s tr e s u l ta r ea l s op r o v i d e d c h a p t e r 4 ，a c c o r d i n gt ot h e s h o r t a g e o ft h e a l g o r i t h mp r o v i d e d i nt h e c h a p t e r3 a n dr e m o v i n gt h ei n f l u e n c eo f u n s u r e n e s ss e n s o r si n f o r m a t i o n ，af e a s i b l em i x e d a p p r o a c ho fp a t hp l a n n i n gi sd i s c u s s e d t h i sa l g o r i t h mm i x e st h ea d v a n t a g e so f r a n d o mp l a n n i n ga n d p a r t i a lp a t hp l a n n i n g ，a n d u s e st h ev a l i di n f o r m a t i o no fl o c a t i o n i no r d e rt o i m p r o v et h ea p p l i c a b i l i t yi nt h e ”s t r u c t u r e dr o o me n v i r o n m e n t a tt h es a m e t i m e ，i nv i e wo f t h e m o v i n go b s t a c l e 。ae s c a p e 剐g o r i t t u ni sd i s c u s s e d t h e nap a t hp l a n n i n gm e t h o dt or e t n r nt oc h a r g e ri sg i v e n a n dt h e w a y b a c k i n e v i t a b i l i t yi sp r o v e dt a k i n gi n t oa c c o u n td i f f e r e n tl o c a t i o n se r r o r s a t l a s t t i l et e s t r e s u l t so f a l g o r i t h ma r e p r o v i d e da n da n a l y z e d k 州。出c l 。撕n gr o b o t ，p a t hp l a n n i n g ，o b s t a c l ea v o i d a n c e ，c o v e r a g e ，i n t e l l i g e n t c o n t r o l ，m i c r o p r o c e s s o gu n s l r u c t u r e de n v i r o n m e n t 塑垩查堂堡圭堂些丝塞 一一 致谢 几个月的辛苦以后，我的学位论文终于完成，同时也标志着我的研究生学习即 将结束。在此，向所有的关怀和帮助我的老师、同学和亲人表示由衷的感谢。 我要衷心感谢我的导师朱世强教授，在课题的进行过程中，始终 导到他的热情 关怀。随着课题的深入，导师科学有效的思维方式往往使我们受益，而目，他严谨 踏实的治学态度、工作生活中的细致入微、对我们的严格要求都使我体会到老师为 人师表的风范。 我要衷心感谢我的老师盒波副教授。作为课题的指导老师，他为研究课题的实 现、找们的成长付出了很大的心血，老师缜密的思维、勤恳的念度更是值得我们钦 佩。 我十分感谢同一课题组的龚华锋同学、刘瑜博士、庞作伟同学、刘松国同学和 葛耀铮老师以及已经毕业的吴海彬博士。作为一个团体，我的研究同大家的配合和 支持息息相关，平日里热烈的讨论、技术上的细心讲解无不使我茅塞顿开，受益匪 浅。同时，感谢合作公司t e k 的老师和同事们，两年来我们度过了愉快的时光，一 起为吸尘机器人的产业化进程而努力。我也要感谢同一实验室的徐振贤同学，他对 技术的敏感和学习知识的热情都值得我学习。 最后，我要感谢我的家人。虽然离家干旱，但是他们在精神上给予我极大的支 持和鼓励，让我一如既往的不断向前，这也是我若干年求学的最坚强后盾。 冯申i 申 二零零四年春 浙礼：大学硕- 上学位论文 第一章绪论 【本章提要】本章在介绍服务机器人研究现状的基础上，进一步对应用较广的吸尘 机器人的关键技术和研究现状给予了说明。同时也介绍了课题涉及的吸尘机器人路 径规划技术的研究内容和现状。 1 1 服务机器人的发展 服务机器人主要是指“以半自主或全自主方式运行、提供并完成服务的机器人， 它有益于人类的生活和设备的运行与维护”。服务机器人与人类工作在同的工作空 间内，具有人机接口和部分非结构化环境中的高度自主能力等1 1 1 2 1 。以往的服务机 器人的研究和开发主要在大学和研究所中进行，目前，越来越受到企业和商业界的 重视，这主要是其所具有的广大市场和巨大利润所至。服务机器人的出现主要有两 个原因：一是劳动力成本的上升；另一个是人们想摆脱令人烦恼枯燥的工作，如清 洁、家务劳动、照料病人和建筑施工等等。另外，福利事业，特别是老年人数比例 的上升也为服务机器人创造了一个广大的市场。 1 日 舛 咖i 妊 n2 d o o 束数量 - 2 叩1 2 0 叫计划安装数量 j | | | | | | | | | | 。 ：广 ：i m - ， 翻 。“ = = j _ ：一h ，v 豫疆j - 。，、 目刊譬黼塑弊 粼女_ m 熬! _ l 溢i _ m _ 塑堑查兰堡圭兰垡丝苎 目前在欧美、日本等西方发达国家，服务机器人己广泛应用于五大领域：医疗 福利服务、商场超市服务、餐厅旅馆服务、维修清洗服务和家庭服务。图i - i “ 展 示了近年来服务机器人在各个应用领域的发展情况对比，其中清洁机器人在 2 0 0 1 2 0 0 4 年的数量已经达到了1 4 1 5 0 台。 服务机器入的服务对象可以分为人、设备以及其他对象。图1 - 2 ( a ) 是一个用 于飞机的车载式清洗服务机器人s k y w a s h ，它能节省人工清洗一半以上的时间。 s k y w a s h 集成先进机器人系统的所有特点：通过c a d 一飞行器模型实现动作过程的 预先规划，基于3 d 传感器的目标定位，触觉传感器控制动作，1 1 个自由度的运动机 械手安装在支架支持的卡车上，完全的安全特点保障了最大的可靠性。s k y w a s h 在人 的监督下，从人为设定的机身位置开始工作。图( b ) 是在1 9 9 3 年投入使用的用于 医院的运输机器人，它沿着走廊运送食品、药物、文件等。考虑到技术性以及使用 者的利益，简单明了的人机界面，不知疲倦的自动导航以及在远程控制下的开门和 操作电梯的能力都使其成为服务机器人行业的先驱。图c o ) 展示的医疗操作器是以 人类为服务对象的，它包括个六自由度机械臂重平衡控制器，计算机控制器、图 形工作站。机械臂的运动路径可以预先编程、通过六自由度的“空间鼠标”手动驱 动或者通过声音驱动0 川 1 2 l i l 。 ( a ) ( b ) ( c ) 图1 - 2 形形色色的服务机器人 国内服务机器人的研究主要体现在清洁机器人的开发工作。哈尔滨工业大学于 9 0 年代丌始致力于这方面的研究，先后承担了国家8 6 3 高科技计划资助项目高 楼壁面清洗爬壁机器人和玻璃幕墙壁面清洗爬壁机器人的研究工作，成功地完成了 2 浙汀大学硬士学位论文 样机的研制工作。另外，还与香港中文大学合作研制了全方位移动地面清扫机器人。 目前，正努力实现科研成果的产业化工作。我们实验室也一直致力于智能吸尘机器 人的籼关研究，至今已有六年，实现五代样机。现在，已经初步实现无人操作情况 下的自主作业，并且形成了产品化的雏形。 1 2 吸尘机器人的研究现状 1 2 1 吸尘机器人的特点 清洁足服务机器人应用最广的领域之一。目前，三个主要的应用领域是家用吸 坐机器人、公共建筑地扳清洗机和火型建筑物的擦窗机器a 和外墙清洗机器人。我 们所研究的主要是家用吸尘机器人。它有其自身的一些特点： 1 、从任务要求的角度，家用吸尘机器人是依靠真空吸力来吸除地板的灰尘、纸屑等 种小脏物，因此需要较大的能量。为了能够工作在床底下或椅子、桌子下面，吸 尘机器人本身的尺寸电不能太大。 2 、从工作环境的角度来说，最常见的工作环境是部分非结构化环境。在实际应用中， 主要是办公室、公共建筑、超级市场、家庭居室等。这些场所的共同特征是平整 的地板、垂直的墙壁、规范的门厅和走廊，以及可咀人为控制调甘的温度和湿度。 在这种环境中，机器人和人类经常要发生互动作用。家俱可以挪动，人也可以来 回走动。此时，机器人必须设法使它自己穿梭于各种物体之中，有较高的智能和 适应件。 3 、在机械结构方向，必须考虑电线、微小凸台等情况，提高它的越障能力。 1 2 2 吸尘机器人的研究现状 吸尘机器人系统通常由4 个部分组成：移动机构、感知系统、控制系统和吸尘 系统。移动机构是吸尘机器人的主体，决定了吸尘器的运动空间， 一般采用轮式机 构c 感知系统一般采用超声波担i 距仪、接触和接近传感器、视觉传感器、红外线传 浙江火学顼l 学位论文 感器和c c d 摄像机等。随着近年来计算机技术、人工智能技术、传感技术以及移动 机器人技术的迅速发展，吸尘机器人控制系统的研究和开发已具备了坚实的基础和 良好的发展前景。目前发展较快、对吸尘机器人发展影响较大的关键技术是：传感 技术、智能控制技术、路径规划技术、吸尘技术、电源技术等。 图1 3 ( a ) 和( b ) 所示分别是德国和我国研制的大型清扫机器人，可以实现火 车站、机场、大厅等大面积环境的清洁。对于图( b ) 的机器人具有如下的特点： ( 1 ) 采用全方位轮实现任意方向的移动，使得机器人可执行对狭窄区域的清扫任务。 ( 2 ) 采用开放式机器人控制结构，实现硬件可扩展，软件可移植、可貅承。停栅熊 图1 - 3 大型地面清扫机器人 人作为服务载体具有更好的功能适应性。 ( 3 ) 机器人具有在拥挤环境下的实时避障功能，能适应不断变化的清扫工作环境。 ( 4 ) 具有遥控操作和自主运动两种运行方式。 ( 5 ) 吸尘机构可实现吸尘腔路的自动转换，提高了吸尘效率。 ( 6 ) 具有智能电源管理功能，延长了运行时间，提高了对有限的移动动力资源的利 用率。 图1 4 实验室开发的吸尘机器人 图】4 是我所在实验室的研究成果，比较第一代样机与最新样机，已经实现了几 折江大学硕i 学位论文 点突破： ( i ) 步进电机驱动到直流i u 机驱动，实现了机器人的平滑运动； ( 2 ) 超声视觉传感器的布局优化进一步开发了超卢视觉功能； ( 3 ) 简单避障功能到完全自主作业的智能完善： ( 4 ) 友好的人机接口功能的实现： ( 5 ) 自动充电对接方式的调整，使得对接成功率大大提高： 吲1 5 中展示了现有的一些进入市场的家用吸尘机器人。( a ) 是伊莱克斯生产的 “三叶虫”( b ) 是三星的最新产品，( c ) 则是产品化的典范“r o o m b a ”。比较之下， 它们各具特点，三叶虫和三星的产品功能更加完善、智能化程度较高，综合了各粪 感检测、控制技术，但是相对过高的成本也使其价格较昂贵，r o o m b a 实现了简中 功能的低成本实现，在市场上大获成功。 ( a )( b ) ( c ) 图卜5 家用吸尘机器人 1 3 吸尘机器人路径规划技术综述 吸尘机器人的路径舰划就是根据机器人所感知到的工作环境信息，按照某种优 化指标，在起始点和目标点规划出一条与环境障碍无碰撞的路径，并且实现所需清 扫区域的合理完全路往覆盖。机器人路径规划研究开始于2 0 世纪7 0 年代，目前对 这一问题研究仍旧i 一分活跃。其主要研究内容按机器人工作环境不同可分为静态结 构化环境、动态已知环境和动态不确定环境，按机器人获取环境信息的方式不同可 以分为基于模型的路径规划和基于传感器的路径规划1 1 4 具体说来，包括如下几个 浙江大学硕：l 学位论文 方f l i ：i ： ( 一) 遍历规划算法 对运动规划问题，目前有具体的解析算法，但由于解析算法牵涉到复杂的积分 问题，实现起来依然具有相当的难度，尤其对于吸尘机器人的路径规划更是如此。 吸尘机器人的作用既然是替代人进行清洁工作，那么它的工作环境往往复杂多变， 机器人对环境信息知道的程度不同，它所采取的方式也会有所区别。包括信息完全 已知情况下采取的全局路径规划，环境信息完全未知或部分来知，通过传感器在线 地对机器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局部 路径规划。目前的遍历路径规划方法主要有基于环境地图的遍历方法、基于传感器 信息的遍历方法。 ( 1 ) 基于环境地图的遍历算法 这类算法均是在预先获得环境地图的基础上实现。主要包括模板法( t e m p l a t e b a s e da p p r o a c h ) 等。模板法嘶m 7 1 使用五个预先定义的模板t m ( t o w a r d sm a r k e r ) 、 u t ( u t u r n ) 、s s ( s i d es h i f t ) 、u 1 1 ( u t u r n i n t e r l a c e d ) 、b t ( b a c k t r a c k e r ) 控制路径 规划动作，以低成本的方式实现了尽可能大的环境覆盖率。 ( 2 ) 基于传感器信息的遍历算法 顾名思义，此类算法不需要预先的环境建模过程，依靠自身携带的传感器获得 的环境信息实现路径规划。其中比较典型的应用包括c g 算法、基于m o r s e f u n c t i o n s 的e x a c tc e l l u l a rd e c o m p o s i t i o n s 2 4 1 ”m 1 。这些算法通过传感器信息 和定义函数或者获得c r i t i c a lp o i n t s 信息，或者获得动作控制规则，从而决策路径规 划。此种方式对环境的变化适应性好，但是复杂环境下决策路径的质量下降。 ( 二) 环境建模与识别 在路径规划问题研究过程中，必然遇到环境建模与识别的问题。迄今，环境建 模的主要方法4 1 有：可视图法( v i s i b i l 时g r a p h ) 、自由空间法( f b es p a c eg r a p h ) 、栅 格法( g r i d ) 、人工势场法等。 6 浙江人学礁1 e 学位论文 ( 1 ) 可视图法就是在c 空间( c o n f i g u r a t i o ns p a c e ) ，运动物体缩小为一点，障碍 物边界相应地向外扩展为c 一空间障碍。在二维青况下，扩展的障碍物边界可有多个 多边形表示，用直线将物体运动的起点s 和所有c 一空间障碍物的定点以及目标点c 连接，并保证这些直线段不与c 一空问障碍物相交，就形成了一张图，称之为可视图 ( v i s i b i l i t yg r a p h ) 。由于任意两直线的顶点都是可见的，显然从起点s 沿着这些直线 到达目标点的所有路径均是运动物体的无碰撞路径。对图搜索就可以找到最短无碰 撞安全运动路径。 ( 2 )自由空间法为了简化问题，通常采用“结构空间”来描述机器人及其周围的 环境。它的基本思想是采用预先定义的基本形状( 如广义锥形，凸多边形等) 构造自 由空间，并将自由空间表示为连通图，然后通过对图的搜索来规划路径，其算法的 复杂度往往与障碍物的个数成正比。自由空间法的优点是比较灵活，机器人的起始 点和目标点的改变不会造成连通图的重新构造，缺点为不是任何时候都可以获得最 短路径。 ( 3 ) 栅格法就是将机器人规划空间分解成一系列的具有二值信息的网络单元，工 作空间分解成单元后则使用启发式算法在单元中搜索安全路径。搜索过程多采用四 叉树或八叉树表示工作空间。 ( 4 ) 传统的人工势场法把移动机器人在环境中的运动视为一种在抽象的人造受力 场中的运动，目标点对移动机器人产生“引力”，障碍物对移动机器人产生“斥力”， 最后通过求合力来控制移动机器人的运动。但是，由于势场法把所有信息压缩为单 个合力，这样就存在把有关障碍物分布的有价值的信息抛弃的缺陷，且易陷入局部 最小值。 现在，将神经网络、遗传算法、模糊控制等应用于移动机器人路径规划已经为 越来越多的人所采用，并且在地图识别、路径搜索效率以及路径优化方面有了很大 的改善。 ( 三) 吸尘机器人工作模式选择 吸尘机器人实际上是一个多任务处理系统，在自主路径规划的过程中不仅要执 1 塑垩查堂堡主兰垡笙茎一 行规划任务，同r 十需要处理各种事件，例如各种传感器信号。产生各类信号的环境 虽然不同，但是火部分的决策仍然是建立在传感器信号基础上，并由此驱动吸尘器 的动作。因此，在算法应用过程中必须考虑吸尘机器人的算法设计结构、传感器逻 辑层和工作模式选择。 1 4 本学位论文的主要研究内容 本学位论文主要以吸尘机器人在非结构化环境中的自主路径规划设计为中心， 详细介绍了在定位系统基础上的具有遍历特性的路径规划方法。以具体的应用为基 础，通过对趿尘机器人的一些关键技术一智能控制技术、路径规划技术等的研究，实 现一种适应性较强的路径规划方法。整个论文主要阐述了以下几方面内容： ( i )基于栅格法的环境建模与遍历路径规划方法研究。 ( i i ) 在对智能吸尘机器人工作环境和工作任务加以分析的基础上，提出不同方案， 比较其优缺点。在此基础上，对于一种随机与规划相结合的方案给予具体实 施，针对实验过程中的问题做进一步的研究。 ( i i i ) 吸尘机器人基于绕障的自动回归充电座算法设计与应用。 1 5 本章小结 本章介绍了服务机器人当前强劲的发展势头，进一步对应用较广的吸尘机器人 f 由特点和研究现状作以介绍，从中可以发现服务机器人领域研究的意义不仅在于挑 战人类的技术高峰，同时也可以将人类从各种劳动中解脱出来，真正的将技术应用 于我们的f i 常生活。 塑望奎竺堡兰兰笪兰兰一 第二章研发平台和方案介绍 【本章提要】本章简要介绍了自主设计的研究平台h s r 2 0 0 0 和它的软哽件性能。 2 1研发平台的软硬件结构 图2 ，1 展示了我们自主开发的研究平台，外形采用圆形结构，两轮驱动，一个万 向轮起到支撑作用，以便于灵活转动；前端为整体式接触传感器，提供三个方向的 碰撞信号；l l 对超声波传感器分布在平台四周，覆盖了前后左右的范围，构成环境 感知系统，进行障碍物检测和辅助定位：两个增量式编码器安装在驱动结构上，提 供系统的定位数据。核心控制部分采用双c p u 体系，主从c p u 进行分布计算，保证 实时性要求。 圉2 - 1 研发平台 将控制系统硬件模块化设计，可以分为主c p u 控制模块、驱动模块、从c p u 定 位模块、人机界面模块、时钟模块、超声波发射接收模块以及充电对接模块、电源 模块等。整个控制系统的软件结构分为三层，即核心控制层( 决策层) 、姿态控制和 数掘融合层、驱动和传感器信息收集层( 图2 2 ) 。要做到吸尘器的完全自主的动作， 如自主规划吸尘、电源电压不足时返回充电座充电，吸尘器的位置和方向信息是尤 其必要的。这样就涉及到定位的问题。所谓定位就是确定移动物体在固定坐标系中 的位置及其本身的姿态a 定位技术可以分为绝对定位技术和相对定位技术。在本课 题中，选用光电编码器进行信号的采样，定位方式上属于相对定位技术。这样在工 作过程中不可避免的具有累积误差，特别是长时间的运行或长距离的运动会使累积 9 坚壁型堂堕l 一 误差超 h 设定要求，造成定位的不准确。一般情况下只采用一种相对定位技术并不 能足够的获取现实环境的所有相关特征，因此，我们对于定位数据的处理以及程序 的容错性能就提出了更高的要求，并且要尽可能利用其他的定位技术，其目的即是 尽量获得精确的位置信息，建立一个相对完备的环境模型，在此基础上进行吸尘机 1ll | 核心控制层 ：气人机界面 ln i姿态控制 数据融合 j 1 1 驱动系统ii 定位与视觉l 图2 - 2 系统功能框图 器人的路径规划。或者，当绝对定位信息并不能完全满足自主定位要求，相对定位 信息还是具备一定的精度和可靠性，有利于系统智能控制的砸确决策。因此，无论 从哪一个层面来考虑，定位模块的引入对于吸尘机器人的自主路径规划都是必须的。 2 2实验方案介绍 现有的遍历规划算法虽然很多，但是都处于实验阶段，真正应用的算法多采取 随机规划的方式，或者采用简单的基于传感器的方式。同时，路径规划的实验方案 主要依靠实验平台性能，主要是系统的硬件条件。对于本吸尘机器人来说，包括超 声波探测能力、定位精度分析、电机调速性能以及最大运行速度，主要参数见下表： 超声波探测范围最小2 c m 直径物体稳定探测距离1 2 c m 盲区i c m 红外传感器探测范围发射角度( 3 0 0 ，+ 3 0 。)探测距离1 0 c m 碰撞传感器行程8 m m i 乜移l 运行：佚况最大速发0 2 m s 坚壁壁塑塑一 袭2 - 1 实验平台性能参数 在上表列出韵硬件条件下，可以制定可行的路径规划方案，选择了两种方案a 方案一：一种局部环境模型下的“梳状”路径规划方式，可以用下面图示的过程实 现。 ( i )贴边学习； 当返凹充电座时构建地图： i i i ) 寻找边界，开始绕障方式的遍历清扫； ( i v )清扫完毕后以贴边方式回归充电座； ( a ) 贴边学习( b ) 绕障清扫( c ) 贴边方式同充电座 图2 - 3 方案一过程表示 方案二：具有局部规划清扫功能的路径规划方法。方案一能够精确执行的前提是定 位误差满足一定的精度要求，或者通过算法实时修正误差。但是，对于以智能实用 为目标，硬件的速度性能指标一定的情况下，复杂算法的处理是不可取的。因此， 提出一利i 对定位精度几乎没有任何要求的路径规划方法。此方法考虑随机规划与局 部梳状遍历规划的结合，不仅在清洁覆盖率上对比单一随机规划有所提高，而且有 了更高的智能自主性。 浙扫人学硕上学位论文 ( a ) 局部规划 ( b ) 局部规划+ 随机清扫 图2 - 4 方案二过程表示 2 3 本章小结 本章在大致介绍了研究平台的软硬结构的基础上，说明了两种用于吸尘机器人 的遍历路径规划方法。两种方法都具有一定的适应性和实用性，反映出吸尘机器人 自主智能的运动a 在下面两章中，就两种方案算法分别给予分析。 塑翌盔兰堡圭兰堕堕苎一 第三章基于栅格法的遍历路径规划方法研究 【本章提要】本章介绍了一种基于栅格法的局部环境建模方法，并在此基础上实现 遍历路径规划。同时，评价了环境模型的准确性以及在实验平台上的适用性。 3 1 建立环境模型 地图构建方法大致可以分为三类：栅格表示、几何信息表示和拓扑图表示”9 1 。 栅格表示方法将整个环境分为若干相同大小的栅格，对于每个栅格指出其中是否存 在障碍物。这种方法实现简单，对需要的传感器没有很赢的要求。但是当所要描述 的环境较大或者需要详细描述环境信息时，对于地图的创建和维护所占用的内存空 间和c p u 时间增大，不利于系统的设计和实时处理。 几何信息表示方法是将机器入提取的传感器信息抽象成几何表示，如直线、曲 线等，这种表示方法更为形象、紧凑，但是它提高了对传感器采集信息的要求，并 且需要利用一定的算法对这些传感器信息做额外的处理，如c c d 的图像处理。 拓扑图表示方法将环境化为一张具有拓扑意义的图。图中的节点对应于环境中 的一个特征状态( 如房间中的障碍物) ，如果环境特征状态间存在直接连接的路径，图 中对应的节点之间也以线相连。拓扑图通常不需要机器人准确的位置信息，对于机 器人的位置误差也有了更好的鲁棒性。但当环境中存在两个很相似的地方时，拓扑 图方法将很难确定这是否为同一节点。 对于自主吸尘机器人而言，它需要实现自定位以及自主路径规划，全局的地图 模型是必要的，同时它对位置、角度误差有一定的要求。对比以上提出的几种地图 构建方法，考虑系统硬件配置，我们采用了栅格表示方法来构造地图。在地图创建 过程中，主要进行了以下几方面的工作：( 1 ) 地图存储算法；( 2 ) 通过r t 学习，方 式建立环境地图；( 3 ) 地图的处理与优化。 塑垩查堂堕：! 兰垡堡苎一 3 1 1 通过“学习”导航方式构建局部环境模型 在第二章我们已经分析了系统硬件性能，考虑超声波的探测范围( 1 5 c m ) 阻及 房问环境的未知性，采用了一种贴边“学习”方式，即是让自主吸尘机器人从指定 位置沿墙壁及其靠墙壁的障碍物外缘按逆时针( 或顺时针) 方向绕房间行走一周， 行走过程中记录机器人中心点的位置坐标，这样就可以描绘出工作环境的轮廓及靠 墙壁障碍物的布置隋况。当两个墙壁障碍物距离很近以至吸尘器不能进入时，机器 人就会将二者看作一个障碍物进行处理。“学习”的目的在于建立环境边界的局部环 境模型。为了建立相对精确的地图，需要可靠的定位信息和尽量平滑的贴边运动轨 迹。采用这种学习方式的优点在于： ( 1 ) 降低了对超声波传感器的要求。我们并不需要很大的视觉探测范围，因此传感 器可以有较高的精度和速度，达到了传感器性能充分利用的目的。 ( 2 ) 在学习前，所有的区域都是未知的，任意选定方向获取信息就涉及到未知区域 以及空白区求解问题，边界以及梳吠遍历学习方式避免了这个问题。同时，边 界学习后建立的轮廓地图也为下一步的遍历学习提供了导航的作用。 ( 3 ) 学习的过程虽然以时间为代价，但是，它同时也是种清扫的过程，实现了吸 尘机器人的工作目的。 定位系统 目前，实验平台使用“车轮脉冲定位”方法，这种方法主要依赖车轮的运行脉 冲来计算小车的定位。在比较理想的工作环境下，基本可以达到使用的要求。但是， 如果工作环境过于复杂，其定位的精度会受到很大影响。我们先分析r 车轮脉冲定 位”的工作原理： 1 4 塑笙查堂堡主兰竺笙塞 v 图3 - 1 机器人运动分析 图3 - 1 中肛吸尘器两轮间距 肛_ 车1 的旋转半径 4 口棚器人围绕z 轴的旋转角度 吩一左右两轮的转动速度 根据实际情况，建立一个以地面为x y 平面，z 轴为垂直地面向上的固定参考坐标系 a 。同时为了描述吸尘器的位姿，在吸尘器上也建立直角坐标系b ，用来描述机器人 的实时方位。根据图3 一i 的几何关系可得： a j 母c o s z l 。 ( 3 1 ) 以y 2 姆s 1 7 a “ ( 3 2 ) 舅弘( w 2 + r ) c o s a 。 ( 3 3 ) 2 ad 十40 2 ” ( 3 4 ) a ：堕! 只 n i + 丁4 一j r 一 ( 3 5 ) 而斤： 坚坚 + 矿 v 2 t v 1 7 。 ： 型! ：墨：三 + n 2 + l + t n l + l + t 。 塑望奎兰堡主堂垡堡! 一 ：型! w ( 3 6 ) n 2 一n 1 式中肝一计算周期内光电编码器测得轮1 的脉冲数 卜计算周期内光电编码器测得轮2 的脉冲数 一为步进电机单位脉冲驱动轮子前进的距离 尹一运算周期 从上面的计算公式来看，所有的变量且y 以及角度均是轮距和轮径斤的函数。 从我们实际的试验过程中看，对于不同的地面状况( 地板、地毯) ，斤的变化不大， 可以满足要求。的变化非常大，对角度和坐标的影响起着绝对的作用。 超声数据的应用与电机控制 在局部环境建模的过程中，区别于已有的超声波数据使用方式，主要利用超声 波采集数据实现平滑贴边，运动过程中记录机器人当前位姿信息，将此信息作为电 子地图形成的原始数据。贴边的平滑程度不仅反映出对运动控制情况，而且也要精 确的跟踪障碍物的边界轮廓，保证地图构建的准确。利用超声信息实现平滑贴边的 原理如下： 两组超声波探头u 1 、u 2 ，它们的安装位置如图3 2 ( a ) 所示，假设平台侧边与障 碍边界需要保持距离d 。当平台刚好处于位置。0 。时，探头u l 实测与障碍边界 距离讲，u 2 实测与障碍边界距离曲( 以，西) 。这种测量结果与超声波测距的原理有 关，但是满足条件d ，m = 岛、以膨= 屯，于是，平滑贴边的条件为： 函( d 一埘，d + a d ) ( 3 - 7 ) 在实验过程中我们发现，采用单组探头测量值作为唯一的充要条件对于不规则形状 的障碍边界形状跟踪存在不适应性，因此又引入探头u 2 的测量值兄，条件为： 应2a ( 3 8 ) 式( 3 8 ) 的作用在于使平台y 方向坐标一直与前进方向的障碍边界保持近似的平 行，即卢一0 。，其中a 是系统允许的距离障碍边界最远距离。根据式( 3 - 7 ) 、( 3 8 ) 是甭成立的情况，将平台运动过程中探测范围分区( 图3 2 ) ，其中涂色部分表示 塑墅塑堂塑坚一 实验平台，符号- a - c 的含义分别为减速区、停止区、位姿调整区，这些标志主要用 幽3 五超声： 作示意削 于贴边实现过程中的方向导航。符号d - f 分别表示贴边过程中机器人质心同贴边障 碍的距离分区，它们的含义分别为距离过大、适中以及过于贴近。这里只讨论利用 左侧探头实现贴边情况，假设前方1 2 0 。范围内探澳4 障碍w l ，左侧1 2 0 。范【羽内探 测障碍、2 ，图示范围外的情况均视为巾，于是w 1 、w 2 有效组合与决策间对应关系 如表3 1 示，代码0 、1 、2 等表示超声波原始数据经过算法决策后的返回值，代表不 代码电机运行状态 可能的环境状态 0 两轮同速高速前进w i e 中1 3 如e 1 两轮同速低速前进w l au 、d u w 1 auw 2 e 2 两轮反向原地低速转动w i 中uw j d u w j b u w t cuw z 硅f 浙江大学硕士学位论文 3一轮静止为中心低速转动w l muw 2 中 u w 1 auw 2 o 4两轮差速低速前进w l auw 2 e f u w j cuw 2 f 表3 - 1电机状态与可能的环境表示 同的可能学习环境，同时，这些代码也相应的对应了电机状态控制指令。利用表3 1 所示的对应关系，我们很容易就可以实现障碍形状的跟踪，对于不规则形状障碍， 虽然轨迹比较凌乱，但是可以通过调整地图存储的栅格大小使得轨迹在地图上的映 射无重复性。 部分贴边实验结果显示及分析 我们知道，机器人沿墙周的过程中，必然涉及壁面交接、壁面与靠墙壁障碍 的交接处等，这些位置的壁面突变，从而使传感器在此处获得的信号也是突变的。 因此，我们将注意力集中于这些位置，并且将其称为凸壁问题和凹壁问题。在实验 平台尾部固定记录水笔，如图3 - 3 记录了环境情况分别为垂直规则面，规则凹壁以及 不规则凸壁情况下的贴边轨迹。可以看出，轨迹连续并且比较平滑，运动控制基本 可以实现障碍物形状的跟踪。下丽主要针对凸壁、凹壁情况就算法应用给予相关的 分析。 ( ) 凸壁障碍分析 在凸壁问题中，机器人就探测方向的信号会突然消失( 如图3 - 3 ( a ) ) ，此时面临 的最大问题在于信息量的不足。将图3 3 ( a ) 描绘的轨迹分段( 图3 4 ( a ) ) ，凸壁问题的 处理过程可以用连续轨迹状态i 状态2 一状态3 来描述。状态1 中，超声探头接收 正常信息，以轨迹1 贴边前进。机器人处于状态2 位置( 图3 4 黑色部分) ，机器人 接收不到任何障碍信息，由此，相应的设计了寻边过程，确保这一过程的实现。首 先假设机器人总是从充电座出发，同时依靠左侧及正面传感器完成贴边过程。根据 塑翌查兰竺兰些至兰一 假设可以得到结论，机器入所在平面坐标系的二、三象限必然存在障碍物，这样 ( a ) 凸壁障碍( b ) 凹壁障碍 ( c ) 规则障碍 图3 - 3 贴边轨迹显示 就确定了寻边的方向。 ( = ) 凹壁障碍分析 如图3 - 3 ( b ) ，墙壁的内转角处是典型的凹壁问题。在这样的位置，机器人会 ( a )c o ) 图3 - 4 凸壁问题处理过程 在两个测量方向上获得障碍物的距离信息，分别判断所属的障碍区域集合，执行对 应的预先定义的障碍处理决策。 3 1 2 一种基于栅格法的数据存贮算法 我们知道栅格法的弊端在于需要大量的存储空间，而对于吸尘机器人而言，清 扫环境空间大小的未知性更突出了栅格法的局限性。在研究过程中采用一种类似 于栅格法的数据存储方法矩形网格法来存储环境模型，形成电子地图。该算法 克服了栅格法的局限性，减少了所需的存储容量，使得空间利用率有了提高。 在研究中，我们利用11 对超声波传感器作为机器人的主视觉系统，引入接触传 塑垩茎兰型! 圭兰些：兰兰 感器增强获取信息的可靠，i 稳定性。通过这些传感器，我们获得了表征房间环境特 征的数据，并且以t r 电子地图”的形式表示，这样就可以通过不断填写“电子地图” 来获得完整而精确的房间环境1 5 7 1 。电子地图采用矩形网格的形式，其基本思想是将 整个房间网格化，也就是坐标的离散化，通过实际面积与网格面积的映射来实现房 f f j j 实际物理区域的离散化表示。在“电子地图”中，每一网格对应一个四位的状态 字。我们采用四维矢量的形式描述网格状态如下： vfi ，) = f af ，b ，c 口，d j 式中f ，表示实际房间中任意点的离散 坐标 疗。q 空 6 i 暂空 c 。当d 。2 q 时，l 表示处理后 的墙壁障碍，0 表示墙壁障 碍边界；当d 。= 1 时，1 表 y 凇 甲 - 4 。 -x ) - 一x al cl 图3 - 5 坐标系间位置映射关系 示为孤立障碍，0 表示为可清扫区域 d 。表示障碍物类型，o 代表是墙壁障碍类型；1 表示为孤立障碍或可清 扫区域 为了构建地图，需要在清扫环境中建立一个以地面为x 、y 平面，z 轴为垂直地 面向上的固定参考坐标系a ( x ，y ，0 ) ，同时为了描述自主吸尘机器人的位置姿态， 在机器人上也建立同样的坐标系b 。用二维笛卡儿矩形栅格分割地面所在的x 、y 平 面，建立地图坐标系c 。将机器人的起始运动位置定义为坐标系a 的原点，三个坐标 系之间的位置关系如图3 - 1 所示：机器人的车载坐标在环境坐标系中的位置由下位 机通过光电编码器获取信息计算得到，并传至上位机。车载坐标在地图坐标系中的 表示可以通过公式( 3 9 ) 获得。 誓一：_ ( 3 - 9 ) l 耳= r , o 。+ k 塑翌查兰堕兰兰垒笙壅一一 同时，地图坐标在内存中的存储地址可以通过映射关系( 3 1 0 ) 获得a j 爿d d 尺脚= ( j + j “一g r i d ) 7 2( 3 1 0 ) l o f f s e t = ( f + j “一g r i d ) 2 其中i ，可以通过公式( 3 ，“) 计算 jkxcl(3-11) 【j = 定义 i ，卜一房间中任意点的离散坐标 磁r f d 一房间网格化后x 方向形成的格点数 一d d 月e s 9 一离散坐标信息被存入的地址 叫巩螗卜离散坐标信息被存入后的高低字节偏移地址 二维矩形栅格的边长 通过以上的映射关系，我们可以看到，每个字节存储两个网格( 对应两个离散 坐标) 的状态信息。“电子地图”是我们进行路径规划的基础之一。定位信息越准确， 环境建模越精确，电子地图形成越完备，就更加容易找到最优的路径规划方案。 3 1 3 理想环境建模结果 经过上述贴边学习以及数据采集和处理后，进步就可以可以利用提出的矩形 网格法完成最终的环境建模。首先我们选择一个相对理想的环境模型进行试验，没 有铺设地毯的硬地面环境，机器人的最大行驶速度o , 2 m s 。环境中人为设置简单的贴 墙和孤立障碍物，其布局如图3 - 6 虚线所示，我们将存储器中记录的机器人边界学习 后记录的中心行走轨迹读至p c 机并显示，结果如图3 - 6 ( a ) 实线所示。这里的理想 环境必须满足以下条件： ( 1 ) 房间面积s 2 0 1 1 12 ： ( 2 ) 地面介质材料一致，且必须保证足够的摩擦系数防止打滑，同时不建议软质 材料，避免对轮距的不确定影响； ( 3 ) 非结构环境中障碍物形状比较规范，易于实现超声测距，不会失效： 塑坚查兰! 堕! 兰垡堡墨一 ( a ) ( b ) 图3 - 6 理想环境的环境建模 这样的规定主要是为了避免机器人的非系统误差，同时对于某些容易产生系统误差 的条件加以限制，最大程度的保证定位的精确。 在描绘了环境轮廓后，进一步的，我们将边界全部填充，以此表示完整的墙壁 障碍物( 见图3 - 6 0 ) ) ) ，这样，可以表示环境边界的局部环境模型构建完成。 3 2 基于局部环境模型的梳状遍历学习 在建立了局部环境的基础上，就可以进一步利用环境知识实现一种梳状遍历规 划。遍历规划方法是应用于具有遍历特性移动机器人的一种路径规划方法，不同于 通常所说的点到点规划方法。它是在满足某种性能评价指标最优的前提下寻找条 在设定