室内移动机器人的动态路径规划

At h e s i ss u b m i t t e dt o Z h e n g z h o uU n i v e r s i t y f o rt h ed e g r e eo fM a s t e r D y n a m i cP a t hP l a n n i n gf o rI n d o o rM o b i l eR o b o t B yJ i n g k u nL i u S u p e r v i s o r ：V i c e P r o f J i n gL i a n g C o n t r o lE n g i n e e r i n g S c h o o lo fE l e c t r i c a lE n g i n e e r i n g M a y ，2 0 1 4 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均己在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者： 、 刮徽 日期：弘年( 月 学位论文使用授权声明 扣日 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 靴敝艏：刁州 日期：V 、毕年岁月h 摘要 摘要 随着计算机技术的发展，机器人研究成为一个热点，目前机器人已经被应 用于社会多个领域。而人口的老龄化和家居服务的智能化需求使得家居服务机 器入的研究关注度越来越高，已经逐渐发展成机器人研究的一个重要方向。移 动机器人的导航是机器人一个基本功能，包含了环境感知、定位和路径规划等 问题。本文主要研究了在室内环境下，基于全局视觉和启发式搜索A 木算法的路 径规划系统。 论文首先介绍了与机器人路径规划相关的环境地图构建、机器人定位技术， 并概述了常用的路径规划算法，从整体上完成了基于视觉的路径规划系统方案 设计。为了校正摄像机的图像畸变，分别对摄像机的线性模型和非线性模型进 行了描述，并使用平面棋盘法标定摄像机。在环境地图构建方面，根据摄像机 采集的环境全局图像，在经过图像的预处理后，采用基于C a n n y 边缘轮廓的方 法提取障碍物的外部轮廓，分割出障碍物区域。为了提高路径规划算法效率， 对环境图像进行栅格化处理，构建环境全局栅格地图。在机器人的跟踪定位方 面，为了能够适应室内环境光照度等因素的干扰，使用基于c o d e b o o k 背景图像 检测出移动机器人区域。在机器人移动过程中，将检测到的机器人区域作为初 始搜索窗口，利用C a m S h i f t 算法跟踪定位机器人位置，在定位的准确性和实时 性方面能够满足系统需要。 最后，在栅格地图上采用启发式搜索A 掌算法进行路径规划。为了应对环境 中的未知障碍物，提出了动态路径规划方法，根据环境障碍物的变化更新环境 地图。利用Q t c r e a t o r 环境和O p e n C V 库构建了仿真界面，测试路径规划效果。 关键词：路径规划摄像机标定地图构建视觉定位A 半算法 A b s t r a c t A b s t r a c t W R ht h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , r e s e a r c h e sa b o u tr o b o t sh a v e b e c o m eah o ts p o t R o b o t sh a v ea l r e a d yb e e na p p l i e dt om a n ys o c i a lf i e l d s B e s i d e s ， t h ea g i n go ft h ep o p u l a t i o na n dt h ed e m a n do fi n t e l l i g e n th o u s e h o l ds e r v i c er o b o t s m a k ep e o p l ep a ym o r ea n dm o r ea t t e n t i o nt ot h er e s e a r c ho fh o u s e h o l dr o b o t sw h i c h h a sb e c o m ea ni m p o r t a n td i r e c t i o no fr o b o tr e s e a r c h e s N a v i g a t i o ni sab a s i c f u n c t i o no ft h er o b o t sw h i c hc o n t a i n st h ep e r c e p t i o no fe n v i r o n m e n t , l o c a l i z a t i o no f t h er o b o ta n dp a t hp l a n n i n ga l g o r i t h m s T h i sp a p e rm a i n l yf o c u s e so nt h ep a t hp l a n s y s t e mo ft h ei n d o o rr o b o tb a s e do nt h eg l o b a lv i s i o na n dt h eh e u r i s t i cs e a r c hA 木 a l g o r i t h m T h i s p a p e rf i r s t l y i n t r o d u c e st h e t e c h n o l o g i e s o fe n v i r o n m e n t a l m a p c o n s t r u c t i o na n dr o b o tl o c a l i z a t i o n ，w h i c ha r er e l a t e dt or o b o tp a t hp l a n n i n g A f t e r t h eo v e r v i e wo ft h ee x i s t i n gc o m l l l o n l yu s e dp a t hp l a n n i n ga l g o r i t h m s ，t h eo v e r a l l d e s i g no ft h ep a t hp l a n n i n gs y s t e mb a s e do nt h ev i s i o ni sd e t e r m i n e d I no r d e rt o r e v i s et h ei m a g ed i s t o r t i o no ft h ec a m e r a , t h el i n e a rm o d e la n dn o n l i n e a rm o d e lo f c a l n e r ai m a g i n ga r ed e s c r i b e d P l a n a rc h e s s b o a r di su s e df o rc a m e r ac a l i b r a t i o n I n t e r m so fe n v i r o n m e n t a lm a pc o n s t r u c t i o n ，a c c o r d i n gt ot h eg l o b a lv i s i o ni m a g e s a c q u i r e db yt h ec a m e r a , m e t h o db a s e do nC a n n ye d g ec o n t o u ri sa d o p t e dt ot h e i m a g e sa f t e rt h ep r e t r e a t m e n t o ft h ei m a g e s T h r o u g he x t e r n a lc o n t o u r so ft h e o b s t a c l e s ，a r e a so fo b s t a c l e sa r es p i l to u t 筋mt h ei m a g e s T oi m p r o v et h ee f f i c i e n c y o ft h ep a t hp l a n n i n ga l g o r i t h m , t h ee n v i r o n m e n t a li m a g e sa r er a s t e r i z e dt ob u i l dt h e g l o b a lg r i dm a po f t h ee n v i r o n m e n t A sf o r t h et r a c k i n ga n dl o c a l i z a t i o no f t h er o b o t , t h eb a c k g r o u n di m a g eb a s e do nc o d e b o o km o d e li su s e df o rr o b o ta r e ad e t e c t i o nt o a d a p tt ot h ei n t e r f e r e n c eo fa m b i e n tl i g h t I nt h ep r o c e s so ft h er o b o tm o v i n g ，t h i s p a p e ru s e sC a m s h i f la l g o r i t h mt ot r a c kt h ep o s i t i o no ft h er o b o t T h ea c c u r a c ya n d r e a l t i m ep e r f o r m a n c eo f t h el o c a l i z a t i o nm e e tt h en e e d so f t h es y s t e m A tl a s t , h e u r i s t i cs e a r c hA 率a l g o r i t h mi sa d o p t e dt og i r dm a pf o rp a t hp l a n n i n g I no r d e rt oa d a p tt ot h e1 o k n o w le n v i r o n m e n t a lo b s t a c l e s ，ad y n a m i cA 拳s e a r c h I I A b s t r a c t m e t h o di sp u tf o r w a r d ，w h i c hc a nu p d a t et h ee n v i r o n m e n tg r i dm a p B a s e do n Q t c r e a t o ra n dO p e n c vl i b r a r y , a ni n t e r f a c ef o rs i m u l a t i o ni sb u i l tt ot e s tt h er e s u l t so f t h ep a t hp l a n n i n ga l g o r i t h m K e y - w o r d s ：P a t hp l a n n i n gC a m e r ac a l i b r a t i o nM 印b u i l d i n gV i s u a ll o c a l i z a t i o n A 幸a l g o r i t h m I I I 目录 目录 摘要。：I A b s t r a c t I I 目录I V 图和附表清单V I I 1绪 仑一1 1 1 课题研究背景及意义一l 1 2 移动机器人发展现状一2 1 2 1 国外发展现状2 1 2 2 国内发展现状3 1 3 本文的主要内容4 2 路径规划相关技术及整体方案6 2 1 路径规划相关技术6 2 1 1 环境地图构建6 2 1 2 定位技术7 2 1 3 路径规划方法8 2 2 路径规划系统整体设计1 0 2 4 1 路径规划系统设计思路1 0 2 4 2 路径规划系统的硬件组成一1 1 2 4 3 基于图像处理的路径规划算法设计1 2 2 3 本章小结1 3 3 摄像机参数标定设计1 4 I V 目录 3 1 摄像机成像模型1 4 3 1 1线性情况下摄像机模型1 4 3 1 - 2 非线性情况下摄像机模型1 6 3 2 摄像机标定实现1 7 3 3 标定结果及分析1 9 3 4 本章小节2 1 4 环境地图构建2 2 4 1全局图像预处理2 2 4 1 1 滤波一2 2 4 1 2 形态学处理2 2 4 2 可行区域的提取2 3 4 2 1 边缘提取算法原理2 3 4 2 2 自适应阂值选取2 5 4 2 3 障碍物区域分割实现2 6 4 3 栅格地图构建2 7 4 4 本章小结2 9 5 移动机器人的视觉定位3 0 5 1 机器人检测算法的设计3 0 5 1 1 常见目标检测方法3 0 5 1 2 基于c o d e b o o k 的背景模型建立3 2 5 1 3 机器人区域检测实现。3 3 5 2 移动机器人跟踪定位算法的设计3 6 5 2 1 目标区域的分割3 6 5 2 2 目标跟踪算法原理3 6 5 2 3 机器人跟踪定位的实现3 9 5 3 本章小结4 1 6 移动机器人路径规划算法设计4 2 V 目录 6 1 启发式搜索技术4 2 6 1 1 估价函数4 2 6 1 2 最好优先搜索4 2 6 2A 木算法的路径规划4 5 6 2 1A + 算法原理4 5 6 2 2 估价函数的选择。4 5 6 2 3 路径规划算法实现4 6 6 3 动态环境路径规划策略4 8 6 4 路径规划系统仿真界面5 0 6 4 1仿真平台的搭建5 0 6 4 2 路径规划仿真结果5 l 6 5 本章小结5 3 7 总结与展望5 4 参考文献5 5 致谢5 7 个人简介5 8 V I 图和附表清单 图和附表清单 图1 1国外机器人研究成果一2 图1 2 国内机器人研究成果一4 图2 1路径规划系统整体方案1 1 图2 2 路径规划系统硬件框图1 2 图2 3 路径规划系统工作流程1 2 图3 1 摄像机成像模型1 4 图3 2 摄像机径向畸变1 6 图3 3 摄像机切向畸变1 7 图3 4 摄像机标定过程1 8 图3 5 标定棋盘图像缩略图1 9 图3 。6 棋盘角点连线2 0 图3 7 畸变校正前后图像2 1 图4 1 边缘提取原图像2 4 图4 2C a n n y 图像边缘提取效果2 5 图4 3 自适应C a n n y 算法流程图2 6 图4 4 自适应C a n n y 边缘检测结果2 7 图4 5 障碍物轮廓2 7 图5 1 帧间查分法原理图3 0 图5 2 背景减除法流程图3 1 图5 3c o d e b o o k 原理示意图3 2 图5 4c o d e b o o k 背景学习流程3 5 图5 5M e a n S h i f t 算法过程3 7 图5 6C a m S h i f l 算法目标定位3 9 图5 7 机器人直方图反向投影图4 0 图5 8 机器人运动跟踪定位效果4 1 图6 I最好优先搜索算流程图4 4 图6 2 路径规划常用估价函数示意图4 6 图6 。3A t 算法的两种寻路方式4 7 图6 4 动态路径规划流程5 0 图6 5O t c r e a t o r 下O p e n C V 配置5l 图6 6Q t c r e a t o r 环境的界面设计窗口5 1 图6 7 路径仿真界面5 2 图6 8 读取环境栅格地图5 2 图6 9A + 算法路径规划结果5 3 表3 1 标定结果2 0 V I I 1 绪论 1 绪论 1 1 课题研究背景及意义 从2 0 世纪6 0 年代第一台机器人的诞生开始，伴随着电子技术、计算机技 术等技术的发展，机器人技术在短短的几十年内取得了飞速的发展。机器人已 经在社会的各个领域有着广泛的应用，极大的提高了社会的生产效率，正在逐 渐改变人们的日常生活。根据用途的不同，可以将机器人分为用于生产制造的 工业机器人和用于非制造业的智能服务机器人。国际机器人联合会 ( I n t e r n a t i o n a lF e d e r a t i o no f R o b o t i c s ，I F 鼬对服务机器人有一个初步的定义，服 务机器人是为了完成对人类有益的服务工作，但不用于生产的是一种半自主或 全自主机器人1 1 I 。 智能服务机器人可划分为在特殊环境下作、止的专用服务机器人和用于服务 人的家用服务机器人 2 1 。据国外权威预测【3 】，到2 0 1 3 年全球个人或者家用机器 人的市场规模将由2 0 0 9 年的8 7 0 万台上升到1 1 4 0 万台，而服务机器人的产值 到2 0 2 5 年将达到5 1 7 亿美元。同时，我国是世界上人口第一大国，人口老龄化 趋势加快，到2 0 1 5 年我国6 0 岁以上的人口将由2 0 0 9 年的1 6 7 亿到底2 亿。 对服务机器人有着更多的需求。而且随着生活水平的提高，中国的车辆也日渐 增多，随之而来的交通事故也越来越多，残疾人数量在不断增加，己成为不可 忽略的群体。这将造成对护理人员的强大需求，家庭服务机器人可以在一定程 度上帮助照顾残疾人的日常生活，减少对医护人员的要求。智能服务机器人的 强大市场需求，加上机器人功能的智能化水平提高，未来将有可能出现机器人 作为日常生活的一部分，替代人力完成一些任务。因此家用的室内服务机器人 的研究，是很有必要和发展前景的。 移动机器人不管是执行简单的搬运任务，还是复杂的医疗探测、抢险救灾 等任务，都需要选择一条安全可行的路径，避免与工作空间的障碍物碰撞，即 机器人路径规划。路径规划是移动机器人的关键技术之，涉及到了环境地图 构建、机器人定位等问题，是现代机器人研究的一个重要方向。 图像处理技术的发展促进了计算机视觉在各领域应用发展。计算机视觉主 要通过视觉传感器获取环境信息，通过图像处理，提取需要的有用信息。由于 绪论 视觉传感器是被动式传感器，它们的采样过程不会对环境产生污染，相互之间 不会产生干扰。目前计算机视觉被广泛应用于机械制造、汽车电子等工、世部门 以及医学、军事领域，在机器人领域的应用主要集中在日标检测与跟踪、视觉 导航等方面。 在移动机器人的研究中。室内环境由于其结构化环境成为研究的首选背景， 基于室内环境的机器人研究可以作为其他环境的参考。本文主要研究基于室内 环境全局视觉的地图构建及机器人定位方法，并在满足实时性的前提下，使用 启发式搜索A + 算法进行路径规划，为室内家居服务机器人的其他应用提供基础 具有较好的发展前景和意义。 1 2 移动机器人发展现状 l2 l 国外发展现状 国外在机器人研究方面起步比较早，在欧美等发达国家对机器人的研究 已经取得了很大的发展，并且已经开始应用到家政、大型超市等日常生活环境 中I 。 在2 0 0 4 年，美国运输研宄会( T R C ) 研制了一种室内环境的助行机器人 H e l p M a t e ，该机器人能够在医院内自主定位与导航，帮助医护人员传递医学诊 断书、为病人送饭等任务。H e l p M a t e 采用建筑物模型识别匹配和测距传感器相 结合的方式实现定位，提高了定位的准确性。美国W O W W E E 公司开发了 R O V I O 机器人，这是- 个具有W i f i 控制功能的巡航机器人。R O V I O 可以通过 内置的摄像机实时观看所在环境的视频及音频，并可以利用W i f i 网络在个人电 脑年1 j 智能设各上对机器人进行远程遥控。 r a ) R O V I O 机器人 ( b ) i R o b i 家用机器人( c ) P a P e R o 机器人 圈1l 国外机器人研咒成果 2 1 绪论 韩国Y u j i n 公司开发了“i R o b i ”家用机器人【5 】，该机器人可以在房间自由 的走动，躲避房间内障碍物。在家中无人时，能够监测煤气是否关闭等。在家 长外出时，可以通过内置的摄像头，观察家中环境。德国西门子公司研发了 “S c h r o b b i e ”商场服务机器人，该机器人采用S i n a s 导航系统，通过内嵌的激 光传感器以路标的形式构建周围环境地图，并配合超声测距、陀螺仪进行导航， 实现避障功能。该机器人可以在超市内自主移动，完成擦洗地板、播放音乐和 提供商品咨询服务，并能有效避开顾客。 日本对机器人研究也很重视，早在1 9 9 9 年日本本田公司就研发了仿人双足 机器人A S I M O 6 1 ，到2 0 11 年，该机器人的行走速度就达到9 k m h ，能够单足、 双足弹跳，并且实现了自主避障和语音识别功能。日本N E C 公司开发的P a P e R o 机器人，使用C C D 摄像头进行图像识别和侦测与物体问的距离，在屋内可以 安全的移动，不发生危险。此外，它能够进行声音辨识和人脸识别，能够与人 做日常的沟通。 1 2 2 国内发展现状 国内机器人的研究起步较晚，但近些年取得了快速的发展。从1 9 8 6 年我国 将智能机器人的研究与开发列入国家8 6 3 高科技发展中，在8 6 3 计划的支持下， 国内对机器人的研究热度逐渐提高，不少科研机构已经在这方面研究取得了一 定成果。 中科院自动化研究所在2 0 0 0 年研发了机器人轮椅i W h e e l c h a i r ，该轮椅安 装有多个超声传感器，可以根据与前方物体之间的距离，自动调节速度，避免 出现碰撞或因急停而对用户产生的伤害，达到自主避障、绕障功能，并采用高 性能控制杆作为人机接口，具有电量显示、速度显示及多模式报警功能。 在2 0 0 9 年，中国科技大学自主研制了“可佳”服务机器人，能够实现环境 建模、路径规划、动态避障等功能，在动态环境中可以完成打扫房间、端茶倒 水等任务。该机器人还可以入机对话，并跟据对话信息，获取因果知识，利用 知识避免有害行为，是目前国际上智能化程度较高的机器人之一。 3 缔论 ( a ) 中科大可佳机器人( b ) 哈工夫保安机器人 图I2 国内机器人研究成果 哈尔滨工、世大学研制的家庭安保机器人可以在室内环境巡视观察室内环 境的变化，并及时把探测到的信息用无线网络通信的方式通知主人，达到监测 家中是否漏水、着火、煤气泄漏等。该机器人使用轮式行走结构，通过超声波 等传感装置，探测和识别障碍物并测距，避免碰撞家具和人，及时避开障碍物， 还可通过自带的摄像头拍摄室内环境图像，并通过因特网对机器人进行远程控 制。哈工大同时研发了家庭清扫机器人，在清扫过程中，能够自动寻找未覆盖 区域路径，提高清扫效率，避免重复清扫，并且在自主寻路回到充电站充电。 1 3 本文的主要内容 在室内移动机器人的路径规划问题中，涉及到了环境地图模型建立、机器 人定位方法、路径规划算法选择等问题。本文提出了基于视觉的环境地图构建 和机器人定位方法，采用斛算法进行路径规划，井构建仿真平台测试算法。论 文的主业内容如下： 第一章主要介绍了本课题的提出背景及意义，井简要概述了国内外机器人 的研究现状。 第：章主要介绍了移动机器人路径规划相关技术的常用方法，简要分析了 各种方法的优缺点并完成了本文路径规划系统的整体设计。 第三章主要介绍了摄像机的成像模型，分析了摄像机图像畸变的来源，并 使用平面棋盘进行了标定。 第四章主要介绍了利用摄像机采集的全局环境图像，分割图像中的障碍物 区域，构建出环境的栅格地图模型。 4 1 绪论 第五章主要介绍了机器入的初始位置的检测，及移动过程中机器人位置的 视觉跟踪定位方法。 第六章主要介绍了在基于启发式搜索胁算法的路径规划，并构建了基于 Q t c r e a t o r 和O p e n c v 仿真平台测试算法路径规划效果。 5 2 路径规划相关技术 2 路径规划相关技术及整体方案 在路径规划问题中，如何有效利用环境信息，选择一条适当的避障路径， 移动机器人需要解决以下三个问题：( 1 ) “我现在在哪里? ”；( 2 ) “我要去哪 里? ”；( 3 ) “怎么到该处去? ”。第一个问题是机器人的跟踪和定位问题，第 二个问题涉及到机器人的路径规划，即为规划一条可以到目标点的安全路径。 为了实现机器人的定位与路径规划，必须知道机器人所处环境信息，因此需要 解决第三个问题即环境地图的创建，将环境分为可行区域和障碍物区域。本章 首先分析了路径规划相关技术的常用方法，并简要介绍了本路径规划系统的整 体方案。 2 1 路径规划相关技术 2 1 1 环境地图构建 环境地图是移动机器人创建的用来描述周围环境的地图或者模型。典型的 地图构建方法有拓扑地图法、几何特征图法、栅格地图法等。 ( 1 ) 拓扑地图法 拓扑地图 7 1 是用一些特定点和点之间的连线来表示环境，没有一个明显的 尺度。拓扑图是可以看作一个图表，其中的节点代表环境中的重要位置，这些 节点可以通过路径或者边相互连接。两个节点间的边只有在路径是可以通行时 才会被创建，例如，机器人能够从一个节点移动另外的节点的情况。该方法忽 略了环境内物体的几何特征信息，图像抽象，表示方便。但该方法需要机器人 能够准确识别各个节点，要求节点具有明显可区分性的地标，而且一旦环境中 出现新的节点，需要重新建立所有拓扑，一般用于静态的结构化环境。 ( 2 ) 几何特征地图 几何特征地图r 7 】是用环境中的可计量信息和地标来描述环境。环境构建的 基础是物体和物体之间的距离信息。这种表示方法是基于全局参考框架的，所 有物体( 包括机器人) 的位置和方向都是在全局框架下建立起来的。大量的传 感器被用来计算机器人到物体的距离和角度，因此这种地图构建方法依赖于传 感器感知的准确度，一个错误的传感数据可能导致构建的几何地图的错误。几 6 2 路径规划相关技术 何特征地图构建适用于环境中包含可参数化路标特征的结构化环境，该方法定 位准确，但该方法对传感器噪声比较敏感，对传感设备要求较高。 ( 3 ) 栅格地图法 栅格法是由E l f e s 和M a r a v e c l 8 】在1 9 7 6 年提出的，主要思想是将环境划分 成网状结构，每个栅格代表一部分环境，用每个栅格被占领的概率值来表示环 境信息。栅格分为障碍物栅格和自由栅格。栅格地图对环境描述的精确度取决 于选取的栅格大小，栅格越小，则图像的栅格数越多，地图精确度越高，会占 用大量的存储空间，路径搜索算法效率降低。栅格太大时，环境描述精确度降 低，路径规划算法运算量小，但会造成规划路径的不准确。因此需要根据实际 应用环境和系统任务的要求，选择合适的栅格尺寸。栅格法由于计算简单，利 于编程实现，被广泛应用于游戏中的人物路径规划。 2 1 。2 定位技术 在路径规划问题中，只有知道了机器人当前的位置，目标点才有意义。在 室外定位方法中，G P S 已经以其卓越性能得到广泛应用。在室内环境中，由于 定位精度要求比室外高，且G P S 在室内覆盖效果不好，目前还没有一种通用的 定位系统。移动机器人的定位方法可分为相对定位和绝对定位。 ( 1 ) 相当定位 相对定位是在机器人的初始位置和方向己知的情况下，根据当前机器人相 对于初始位置的距离和偏向角，推算出当前位置。相对定位方法的一个直接应 用是航迹推算法 9 1 。 航迹推算定位不需要对外界环境的进行感知就可以进行定位，在机器入定 位中得到广泛应用。该方法的关键在于机器人单位时间问隔行走路径和机器人 航向角变化的测量。根据使用传感器的不同，航迹推算法可以分为基于惯性传 感器的惯性导航法和基于编码器的测距法。 惯性导航法常用的传感器有陀螺仪、加速度计，而基于编码器的航迹推算 法常用传感器为码盘，这两种方法都具有成本低，无需外部参考的优点。尽管 航迹推算法已经达到较高的定位精度，但误差随着机器人行走路径的增长而累 加，在机器人行走路程较长时，造成定位误差可能会很大，因此常将该方法作 为其他定位方法的辅助。 ( 2 ) 绝对定位 7 2 路径规划相关技术 绝对定位是确定机器人在全局环境中的位置的一种方法，目前较成熟的绝 对定位技术有：地图匹配定位【Io 】和基于信标定位技术。 基于信标定位是建立在环境中一系列已知的特征作为信标，利用移动机器 人安装的传感器观测信标，计算机器人与信标的位置关系进而得到当前觉得位 置的方法。信标定位常用的传感器有超声波传感器、激光传感器、视觉传感器 等。目前应用较多的信标定位方式有三边测量和三角测量。三边测量是通过测 量机器人与周围的三个信标的距离，确定机器人位置的方法。而三角测量则是 通过移动机器人与信标问的角度来实现定位的。信标定位要求环境中至少有三 个以上信标，虽然定位速度快，精确度高，但安装和维护成本高。 基于地图匹配的定位是机器人利用传感器感知构造出局部环境地图，与己 知的全局地图进行匹配，确定机器人当前位置。在进行定位前，需要构建全局 地图，全局地图的构建方法不同，得到的定位精确度也不同。在局部地图与全 局地图进行匹配时，采用数据关联的方法寻找局部环境特征与全局地图特征之 间的联系。地图匹配定位相比信标定位，不需要改变室内工作环境，成本低， 但该方法的运算速度慢，实时性差，特别是对于有未知障碍物情况，定位效果 不佳。 2 1 3 路径规划方法 机器人的路径规划是为了在有障碍物的空间，寻找一条合适且不会发生碰 撞的路线，使得机器人从起点移动到目标点。根据对环境信息掌握程度的不同， 路径规划可分为全局路径规划和局部路径规划。在环境信息完全已知的情况下， 路径规划是在整体布局基础上的全局路径规划，因此又称为静态路径规划。全 局路径规划精确度高，但是对环境的突发改变很难做出反应。而局部路径规划 是在环境信息部分未知或者完全不知的情况下，机器人通过传感器实时探测环 境信息，并根据环境变化修改路径，避免与障碍物碰撞，又称动态路径规划。 全局路径规划的算法在某些情况下可以用于局部路径规划，而局部路径规划的 算法一般也可以用于全局路径规划。 ( 1 ) 全局路径规划 全局路径规划方面的研究较为普遍，在环境信息已知的情况下，首先建立 环境模型，然后在该模型上应用算法搜索最优路径。在全局路径规划方法中， 常用的有可视图法、蚁群算法和栅格法等。 8 2 路径规划相关技术 可视图法【川的实质是将机器人、目标点、多边形障碍物在连线不能穿过障 碍物的情况下，把各顶点通过连线进行连接，各顶点连线通过排列组合的方式， 查找得到一条由机器人节点到达目标点的可行最优路径。该方法将最优路径的 选择转化为了在可视图中搜索从起始点到目标点的最短路径连线组合。运用优 化算法可以删除可视图构建过程中的一些不必要的连线，缩短搜索时间。可视 图法虽然能够找到最短路径，但是忽略了机器人的尺寸，很容易造成机器人与 障碍物距离太近或者直接接触，且搜索时间较长。 蚁群算法是由M a r c oD o r i g o 1 2 】提出的，灵感来自于蚂蚁在搜寻食物过程中 会通过释放一种挥发性分泌物来引导其他蚂蚁过来。在不知道食物源的情况下， 蚂蚁随机选择一条路径进行搜索，当有一只蚂蚁找到食物源后，会释放信息素， 其他蚂蚁会沿着信息素很快找到食物源，这样通过信息素的引导，慢慢靠近最 优的路径。蚁群算法具有很强鲁棒性，且搜索过程不需要人工的干预，但该算 法的计算量大，容易陷入局部最优解，实时性不高。 栅格法是在构建的环境全局栅格地图上，按照一定的规则搜索出一条最优 路径的方法。栅格法中常用的有A 士算法、D i j k s t r a 算法等，算法的效率与栅格 的大小有关系。栅格过大，环境信息存储量变小，环境分辨率降低，路径搜索 算法的消耗时间减少，但当处于障碍物密集的环境时，机器人可能无法发现某 些路径；栅格过小，环境信息存储量变大，虽然发现路径能力变强，但路径搜 索算法的搜索消耗增多，实时性变差。因此，选择合理的栅格大小，是路径算 法实时性的关键问题。 ( 2 ) 局部路径规划 对于局部路径规划，常用的方法有人工势场法、遗传算法、模糊逻辑法等。 由K h a t i b 提出来的人工势场法 1 3 1 是一种虚拟力法，它的基本思想是把机器 入看作带有单一磁性的个体，而障碍物对机器人产生排斥，目标点对机器入产 生引力，机器人在未知环境的运动视为在人工虚拟的力场中运动，其实质是在 斥力和引力的共同影响下，使机器人向着预期的目标进行运动。势场法进行路 径规划，计算量小，规划出的路径光滑，实时性好，适用于机器人的底层控制， 但当机器人处在陷阱区域或者相似障碍物群中时，机器人容易陷入局部最优而 不能达到目标点【1 4 l 。 遗传算法是【1 5 】类似于自然进化的随机搜索算法，问题的可能解被编码成染 色体，这些染色体组成一个种群。每个个体用适应度函数来评价，采用适应度 9 2 路径规划相关技术 函数作为个体和种群的选择机制。适应度值高的个体有更高的可能性被选择通 过交叉变异等遗传变换产生后代。种群一代代的演化，在经过许多代后，种群 收敛到较好的解，种群中的最优个体有大可能是全局最优解或者附近解。遗传 算法有很好的全局寻优能力，已经被应用于机器人的路径规划中。但该算法通 常计算量大，运行效率不高，限制了其在实时性要求较高的系统中的应用。 模糊逻辑法1 16 J 是在模糊集合的基础上发展而来的，参考了人在躲避碰撞时 并不是通过精确的计算，而是依据经验来做出反应实现的。在路径规划中，将 经验知识形成规则存储起来，利用传感器检测的环境数据，查询规则表得到规 划信息，实现局部路径规划。该方法计算量小，能够做到边规划边跟踪，实时 性很好，但也存在固有缺陷，如人的经验的完备性，输入数据较多时，推理规 则库的急剧膨胀，影响规划结果。 2 2 路径规划系统整体设计 2 4 1 路径规划系统设计思路 当前计算机图像处理能力和技术飞速发展，数字图像处理设备的性价比的 逐渐提高，计算机视觉也越来越受到人们的重视。本文将视觉信息作为环境信 息采集的主要途径，构建环境地图和机器人的跟踪定位。利用摄像机采集环境 障碍物信息，相对于雷达、超声波、激光、红外等传感器【1 7 】，具有以下特点： 1 图像信息量丰富，不仅包含了环境内的物体的距离信息，而且包含了物体的 颜色及形状等信息；2 计算机视觉是被动测量，不会对环境产生污染；3 采样速 度一般比较快。 由于机器人的局部视野范围有限，获取的信息量少，且不能从全局角度观 察环境，因此本课题将摄像机安装在室内天花板上，与机器人相分离，实时拍 摄室内环境的俯视图。由于图像传感器与机器人分离，减少了车载处理器的计 算量。利用俯视视觉获取室内环境的环境障碍物分布信息，方便构建环境的全 局地图，并且机器人始终在视野内活动，也便于设计机器人的定位算法。路径 规划系统的整体方案如图2 1 所示。 1 0 2 路径规划相关技术 图2 1 路径规划系统整体方案 利用摄像头获取室内环境的全局图像，传输给计算机进行图像处理。P c 机 构建出环境栅格地图，同时可以检测机器人在栅格地图中的位置。在下达任务 目标点后，调用路径规划算法规划为机器人选择一条到达目的地的蛀短路径， 并利用无线通信模块将机器人的控制信息传输给机器人，控制机器人行为。 2 42 路径规划系统的硬件组成 本文路径规划系统的硬件搭建使用的是轮式机器人作为移动平台。路径规 划系统包含了图像处理模块、机器人车体系统和无线通讯模块。图像处理模块 采用是C C D 摄像头采集环境的全局图像并传送。机器人车体系统包含了超声 测距模块、电机驱动模块、处f j 。器模块、机器人车体和外围接口等，实现对机 器人电机的控制。无线通讯模块实现上位机路径规划系统中P c 机与机器人车 体系统之间的通讯交流。 一蜷繇 2 路径规划相关技术 超声测距模块 j 立 。广1l ；甬佶掉- 1 ； 叫无线模块 一 N矿I 处理器 j F 7 ； P c 机 电机驱动模块 么二、 菲 图像采集模 机器人车体 块 移动机器人 ，一： 图2 2 路径规划系统硬件框图 2 4 3 基于图像处理的路径规划算法设计 在本课题的路径规划系统中，P C 机是整体的核心部分，负责处理摄像机传 输的图像。路径规划系统的实现流程如图2 2 。 图2 3 路径规划系统工作流程 1 2 2 路径规划相关技术 本课题路