（检测技术与自动化装置专业论文）移动机器人拓扑地图创建研究.pdf

山东大学硕士学位论文 摘要 随着科学技术的飞速发展，移动机器人在未知环境中自主完成任 务的应用领域越来越广泛，如工业、民用及军事等。对于大规模未知 环境，需要移动机器人能够自主完成环境探索、创建周围环境地图， 并利用地图进行导航或完成更复杂任务。创建未知空间的环境地图是 移动机器人控制与导航的关键，自主完成各种智能任务的前提，也体 现了机器人的感知能力和智能水平。本文主要研究移动机器人在未知 环境中自主进行拓扑地图创建的问题，主要工作如下t 首先，对本文的研究背景作了介绍，回顾了移动机器人环境地图 创建的研究现状，指出目前存在的问题，并简要介绍了本论文的主要 内容。 其次，采用模式识别图像处理问题中常用的细化算法创建环境的 拓扑地图，解决了v o r o n o i 图中易产生多余节点和路径信息的问题。首 先以栅格地图建模机器人工作环境，然后将环境的栅格地图进行细化， 提取出环境的有效拓扑信息。仿真实验表明，基于细化算法创建的环 境拓扑地图，清晰、简易且有效。相比于栅格地图，信息存储空间要 求较低，从而提高了移动机器人自主运行、导航和路径规划的能力。 第三，研究了多移动机器人拓扑地图融合的问题，实现了在机器 人的相对位置未知的情况下，多移动机器人系统的拓扑地图融合。把 拓扑地图融合问题看作图像匹配领域的扩展问题，利用拓扑地图的几 何结构，基于图像匹配和图像配准，确定两个地图间的最佳匹配。首 先，对于特殊环境中的拓扑地图，采用穷尽搜索优化算法，寻找最大 的公共子图，进行地图融合；其次，对于一般环境中的两个拓扑地图， 采用图像配准方法中经典的i c p ( i t e r a t i v ec l o s e s tp o i n t ) 算法，结合 奇异值分解算法( s v d ) ，进行地图融合。本章最后的仿真实验表明， 基于几何结构的图像配准结合穷尽搜索优化算法以及i c p 图像配准算 法应用于拓扑地图融合，均具有较高的可行性和有效性。 最后，对本文所做的工作加以总结，分析了可以进一步进行改进 的地方，并对未来的发展进行了展望。 山东大学硕士学位论文 关键词：拓扑地图创建；v o r o n o i 图；细化算法；地图融合；图像配准； i c p 算法 i i 山东大学硕士学位论文 a b s t r a c t w i t ht h ef a s td 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 ，m o b i l er o b o t s w h i c hc a na u t o n o m o u s l ya c c o m p l i s ht a s k si nu n k n o w ne n v i r o n m e n ta r e w i d e l yu s e di nm a n yf i e l d s ，s u c ha si n d u s t r y ，c i v i l i a nl i f ea n dm i l i t a r y e s p e c i a l l yi nu n k n o w nl a r g e s c a l ee n v i r o n m e n t s ，m o r ei n t e l l i g e n ta n d a u t o n o m o u sm o b i l er o b o t sa r ee x p e c t e dt oe x p l o r et h e i re n v i r o n m e n t s ， b u i l dm a p so fe n v i r o n m e n t s ，a n dt h e nu s et h em a p st o n a v i g a t ea n dd o o t h e rc o m p l i c a t e d w o r k m a pb u i l d i n g i st h e k e yt e c h n o l o g ya n d f u n d a m e n t a lp r o b l e mi nm o b i l er o b o t s a l s o ，t h i se m b o d i e st h ep e r c e p t i o n a b i li t ya n di n t e ll i g e n c eo fr o b o t s w ef o c u so nt h er e l a t e dp r o b l e m so f t o p o l o g i c a lm a pb u i l d i n gi nu n k n o w ne n v i r o n m e n t t h em a i ns t u d i e s u n d e r t a k e ni nt h i st h e s i sa r e1 i s t e da sf o l l o w s ： f i r s t l y ，t h e d i s s e r t a t i o nr e v i e w st h er e s e a r c h b a c k g r o u n d ，t h e r e s e a r c hs i t u a t i o na n dt h ep r e s e n tp r o b l e mo fm a pb u i l d i n go fm o b i l e r o b o t t h em a i nc o n t e n t so ft h i st h e s i sa r ed e s c r i b e db r i e f l y s e c o n d l y ，t o p o l o g i c a lm a pi s b u i l tb a s e do n t h i n n i n ga l g o r i t h m w h i c hi sc o m m o n l yu s e di ni m a g ep r o c e s s i n go fp a t t e r nr e c o g n i t i o n t h i s a v o i d s p r o d u c i n gu n n e c e s s a r yn o d e sa n dp a t h s t h ee n v i r o n m e n ti s m o d e l e di ng r i dm a p ，n e x tt h et h i n n i n ga l g o r i t h mi sa p p l i e di nt h em a p ， a n dt h e nt h ee f f e c t i v et o p o l o g i c a li n f o r m a t i o ni se x t r a c t e d s i m u l a t i o n r e s u l t ss h o wt h a tt h et o p o l o g i c a lm a pb a s e do nt h i n n i n gi sc l e a ra n d s u c c i n c t m o r e o v e rt h i st o p o l o g i c a l m a pr e d u c e s i n f o r m a t i o ns t o r a g e m e m o r y t h i s w i l l i m p r o v e t h e a b i l i t y o fa u t o n o m o u s o p e r a t i o n ， n a v i g a t i o na n dp a t hp l a n n i n gf u r t h e r t h i r d l y ，w eh a v ed o n es o m er e s e a r c hw o r k o n t o p o l o g i c a lm a p m e r g i n gf o rm u l t im o b i l er o b o t t h ep a p e ri m p l e m e n t st h et o p o l o g i c a l m a pm e r g i n gp r o c e s sf o rm o b i l er o b o t sw h e nt h er o b o t sd on o th a v ea c o m m o nr e f e r e n c ef r a m eo rg l o b a lp o s i t i o n i n g o u ra l g o r i t h mu s e st h e g e o m e t r i c s t r u c t u r eo f t o p o l o g i c a lm a p s t od e t e r m i n et h eb e s t c o r r e s p o n d e n c eb e t w e e nm a p sw i t ho v e r l a p p i n gr e g i o n s t h ea p p r o a c ht o 山东大学硕士学位论文 t h i s p r o b l e md r a w sf r o mt h ea r e a so fi m a g e r e g i s t r a t i o n i m a g e r e g i s t r a t i o nc o m b i n i n gw i t he x h a u s t i v es e a r c h i n gm e t h o di sa d o p t e dt o c o m p l e t er e g u l a rt o p o l o g i c a lm a pm e r g i n g i c pa l g o r i t h mw h i c hi s c l a s s i c a li n i m a g er e g i s t r a t i o nc o m b i n i n gw i t hs v di sa d o p t e dt o c o m p l e t eg e n e r a lt o p o l o g i c a lm a pm e r g i n g s e v e r a le x p e r i m e n t s d e m o n s t r a t et h ee f f i c a c yo fo u ra l g o r i t h m f i n a l l y ，c o n c l u s i o n s a r ep r o v i d e d o u t l o o ko ff u t u r er e s e a r c hi s a n a l y z e d k e y w o r d s ：t o p o l o g i c a lm a pb u i l d i n g ；v o r o n o ig r a p h ；t h i n n i n g a l g o r i t h m ；t o p o l o g i c a lm a pm e r g i n g ；i m a g er e g i s t r a t i o n ；i c pa l g o r i t h m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：j 上蔓牡 日 期：盈监i 互也 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：哔导师签名： 山东大学硕士学位论文 第一章绪论 1 1 论文研究背景及意义 随着计算机技术和人工智能技术的飞速发展，机器人技术受到各 国研究人员的普遍关注，机器人也应用到很多领域，如工农业、交通 运输、医疗卫生、军事等。将机器人应用于危险环境，代替人类完成 某些繁重工作，在近年的研究中取得了很多成果。具有自主感知和执 行功能的智能移动机器人也有着巨大的应用前景，例如矿井环境探测、 外太空及深海探险、自动搬运、服务机器人等。在许多应用场合中， 机器人工作空间的环境是事先未知的，创建未知空间的环境地图是机 器人控制与导航的关键，也是移动机器人自主完成各种智能任务的前 提。因此，建立工作空间的环境模型是移动机器人学的一个基本并且 具有挑战性的研究课题。 智能移动机器人导航定义为：通过传感器感知环境和自身状态， 实现在有障碍物的环境中面向目标的自主运动【。导航技术需要解决 三个方面的问题：环境建模、自定位和路径规划。环境建模指移动机 器人根据自身携带的传感器，获取周围工作环境信息，将障碍物、路 标等的空间位置进行准确描述，即创建地图( m a p p i n g ) 【2 j 。所以，环 境建模是导航研究的基础，也是移动机器人实现自主、完成给定任务 的重要条件之一。 移动机器人在未知环境中自主探索和地图创建的研究，能够提高 机器人的工作能力和应用范围。完全未知环境，即机器人对环境一无 所知，不存在任何先验信息，包括环境大小、形状、障碍物位置等等， 且环境中不存在诸如路标、灯塔等人为设定的参照物【3 l 。在这种未知 环境中，机器人要创建地图必须依赖于自身携带的传感器所获得的信 息。由于传感器自身的限制或噪声的影响，感知信息存在不同程度的 不确定性，因此通常需要对感知信息再处理，通过多感知信息的融合 获得较准确的环境信息，创建较准确的环境模型。 本论文主要进行未知环境中移动机器人拓扑地图创建的研究，包 括未知大规模环境下，单机器人拓扑地图创建和多机器人拓扑地图融 山东大学硕士学位论文 合等方面。本章主要介绍移动机器人系统环境地图创建的发展历程及 研究现状、常用传感器的原理和特性、多传感器信息的融合及多移动 机器人系统的地图融合，最后简要介绍本论文的主要工作。 1 2 移动机器人系统环境地图创建的发展历程及研究现状 工作空间环境建模一直是移动机器人领域的一个重要研究方向。 经过各国学者的努力，该领域的研究取得了丰硕的成果：在环境模型 描述方面，m o r a v e c 等提出了二维占有栅格的概念【4 l ；s e l f 等人提出移 动机器人同时定位与地图创建，称作s l a m ( s i m u l t a n e o u sl o c a l i z a t i o n a n dm a p p i n g ) 【5 】，由于其重要的理论与实用价值，被认为是实现真正 全自主移动机器人的关键【6 1 ；k o r t e n k a m p 等人设计的机器人携带声纳 和视觉传感器的组合，探测环境并创建环境的拓扑地图【_ 7 1 。在机器人 定位研究中，也提出了位姿跟踪、概率定位等方法。多机器人系统的 研究中，r e k l e i t i s 等探讨了地图探索中的多机器人之间的合作问题【8 1 。 机器人建立地图的过程，实际上就是机器人根据传感器获取的感 知信息对其工作空间建模的过程。地图创建包括三个需要解决的基本 问题【3j ：第一、地图的表示方法；第二、机器人的导航，机器人在环 境中运动，获取环境信息并记录；第三、不确定信息的描述和处理方 法，机器人将获取的环境信息进行描述并利用信息更新地图。 随着机器人工作任务复杂性的增加及应用领域的不断扩展，多机 器人系统的研究逐渐受到关注，国际上的研究已经取得很大成果，如 日本n a g o y a 大学的c e b o t 自重构机器人系统，美国o a kr i d g e 国家实验 室的协作机器人系统，以及机器人足球赛等【9 1 。在地图创建中，多个 移动机器人协同工作，互相交流信息，不仅提高了系统的工作效率， 也增强了环境地图的准确性和鲁棒性。 地图创建问题涉及到移动机器人研究的多个方面：地图的表示方 法、传感器、多传感器信息融合、多机器人协作、探索策略和路径规 划等。 1 2 1 环境的空间表示方法 环境的空间表示法，主要分为两大类：几何地图( g e o m e t r i c a lm a p ) 2 山东大学硕士学位论文 和拓扑地图( t o p o l o g i c a lm a p ) 。其中，几何地图又分为栅格地图 ( g r i d b a s e dm a p ) 和特征地图( l a n d m a r km a p ) 1 0 j 。每种地图表示 方法都有各自的优缺点： ( 1 ) 栅格地图 栅格地图表示法最早由m o r a v e c 和e l f e s 于19 8 5 年提出【4j ，其原理是 将环境分解成若干相同大小的栅格，每个栅格单元具有一个概率值， 表示它是否被障碍物占据。栅格地图易于创建、表示和维护，机器人 感知的每个栅格单元的信息直接与环境对应，使用声纳这样的低成本 传感器便可获得创建地图的信息。借助于栅格地图，机器人可以方便 地完成自定位、路径规划等。栅格地图表示法的缺点是：在表示大规 模环境或对环境划分比较详细时，栅格数量增大，地图维护所占用的 内存和c p u 计算时间迅速增长，使计算机的实时处理变得很困难。为 了提高实时处理能力，有的研究者对栅格地图表示法进行了改进，形 成了四叉树等模型。b u r g a r d 在导航机器人中使用神经网络学习感知数 据，然后映射到地图中j ，a n g e l o 提出基于反馈神经网络模型的栅格 概率计算方法【12 1 ，以减少传感器镜面反射、随机性误差等影响。r i b o 分析了b a y e s i a n 概率模型、d s 证据理论、模糊集三种算法更新栅格地 图模型的优缺点【1 3 】。 ( 2 ) 特征地图 特征地图由若干包含环境位置信息的特征组成，线段、角点、目 标边缘等均可作为地图特征，特征可以精确地存储在地图中，而这些 特征易于被机器人观测到，方便用于位置估计和目标识别。如a y a c h e 采用视觉传感器获取环境中的直线段信息f 1 4 l ，i p 等人从原始声纳测量 数据中提取线段特征【1 5j ，c h o s e t 等采用a t m 模型精确提取环境中的点 特征 16 1 。多传感器信息融合是提高特征检测能力的重要手段【17 1 ， c a s t e l l a n o s 对激光和摄像机数据进行特征级数据融合【1 8 】。特征地图缺 点是特征的提取需要对感知信息作额外的处理，需要一定数量的感知 数据才能得到结果，而且特征地图的更新比栅格地图复杂很多。 ( 3 ) 拓扑地图 拓扑地图，首先由k u i p e r s 在19 7 8 年提出，是一种紧凑的环境表示 方法，通常以图( g r a p h ) 的结构形式表现一个环境的连通性1 1 9 1 。拓扑 山东大学硕士学位论文 地图把室内环境表示为带节点和相关连接线的拓扑结构图，其中节点 表示环境中的重要位置点如拐角、门等，拓扑地图的边表示不同节点 之间的连接通道，如环境中的走廊等。拓扑地图不仅方便规划，适用 于基于行为的导航，而且可以直接使用很多成熟高效的图形搜索和推 理算法；它重在描述环境的拓扑结构，对环境没有精确的位置要求： 而且对存储空间和计算时间要求都比较低，所以，基于拓扑地图的计 算效率比较高1 2 0 】。尽管拓扑地图具有多个优点，但仍存在不利的方面， 它要求方便地观测到拓扑节点，对拓扑节点的定义是拓扑地图创建的 难点，环境的相似性将使系统陷入节点混淆的状态。节点定义方法大 致有三种类型：第一种是人为预定节点标志【2 l 】，第二是特定位置法， 即根据特定位置的环境信息定义节点。k u i p e r s 采用爬山法寻找局部唯 一特征点，利用外部传感器感知的信息定义节点 2 2 1 ，第三种是传感器 测量值相似的区域，n e h m z o w 直接根据栅格直方图信息进行节点定义 2 3 1 0 v o r o n o i 图是拓扑地图创建中一种常见的方法，但是由于噪声的影 响会产生多余的节点或路径。本文采用细化算法创建环境拓扑地图解 决了这一问题，环境的拓扑信息有效、简洁并清晰。 1 2 2 移动机器人常用传感器 要智能地完成指定任务，移动机器人必须根据外界环境来决策自 身的动作，因此，移动机器人需要具有对环境的感知能力。环境感知 是指机器人依靠自身携带的传感器系统来获取环境信息，实现对环境 的认识、理解和建模。移动机器人常用的传感器可分为两大类： 其中一类是内部传感器，用于感知机器人本身运动参数。常用的 有：电子罗盘、加速度仪、陀螺仪、编码器等。这类传感器通常与机 器人的运动模型一起用来实现机器人的位置估计，基于航位推算方法， 用于机器人的运动轨迹跟踪。但是由于内部传感器存在累积误差，所 以不能直接用于长期定位。 另一类是外部传感器，用于对机器人周围环境特征进行检测，是 创建地图的信息来源。主要包括声纳、红外传感器、激光测距仪、视 觉传感器等。其中声纳、红外、激光传感器均属于测距传感器，工作 4 山东大学硕士学位论文 原理大致相同：测量信号在空间传播后，遇到障碍物被反射回来，通 过测量发送和接收信号的时间差，已知信号的传播速度，便可求得障 碍物与机器人之间的距离。由于这种类型传感器简单、处理速度快， 在移动机器人导航和地图创建中，已经取得了广泛的应用。视觉传感 器可以获取更丰富的环境信息，如几何特征、颜色信息等，而且信号 测量范围广，但实时性相对较差。外部传感器存在系统误差但不会有 累积误差，可以用来修正机器人的位置误差。 1 2 3 移动机器人多传感器信息融合技术 由于噪声的影响或者传感器自身的限制，机器人携带的各种传感 器获得的环境信息都会带有不同程度的不确定性，感知信息的不确定 必然会导致环境模型的不确定。因此，地图创建过程中，需要对感知 信息再处理，通过多传感器信息的融合获得较准确的环境信息。 常用的多传感器信息融合方法有加权平均、贝叶斯估计、卡尔曼 滤波、d s 证据推理、人工神经网络等。 加权平均法简单直观，一般应用于动态低水平的数据处理，但最 终结果不是统计上的最优估计；贝叶斯估计一般用于融合静态环境中 多传感器低层数据，融合具有高斯白噪声的不确定传感器信息；卡尔 曼滤波一般应用于系统噪声和观测噪声为高斯白噪声的线性系统，目 前已应用在移动机器人的定位、地图创建以及导航等方面，而对于非 线性系统模型则采用扩展卡尔曼滤波( e k f ) ：d s 证据推理方法是贝 叶斯估计的扩展，将局部成立的前提与全局成立的前提分离，用于处 理前提条件不完整的信息融合；神经网络法根据系统要求和融合形式， 选择网络拓扑结构，通过网络学习确定连接权值，对各传感器的输入 信息进行融合，具有在有噪声情况下知识获取能力、自适应能力、容 错性等特点。 本文中拓扑地图的创建是从栅格地图中提取节点和连接路径，而 环境栅格地图的建立利用基于d s 证据理论的数据融合方法对声纳传 感器信息进行解释和融合。 山东大学硕士学位论文 1 2 4 多移动机器人系统的地图创建 目前，多机器人系统的研究已成为热点，它是从单个机器人系统 的研究扩展来的，但与单机器人相比，多机器人系统具有很多优点【2 4 j ： 第一，多个机器人可以在工作空间的不同区域同时探索，探索速 度比单个机器人快； 第二，功能不同的多个机器人可以协同工作，增加了系统的冗余 度，使容错性和鲁棒性更强； 第三，多个机器人可以具备相同的知识或不同的知识，通过通讯 联系，协作机器人之间共享信息，使得多机器人系统的定位及环境地 图的精度更高。 多移动机器人系统协同工作，提高了系统完成任务的效率，增强 了系统的容错性、鲁棒性和灵活性，提高了环境地图的精度，因此应 加以充分利用，尽量发挥多机器人系统的优势，从而在复杂环境中高 效、可靠地完成任务。 在地图创建中需要解决多机器人地图融合问题。早期的拓扑地图 融合研究中，多假设各机器人相对位置已知，通过融合各自建立的局 部地图而得到全局地图，这会降低融合的实时性。本文借鉴h u a n g 提出 的图像配准算法，实现了机器人相对位置未知的情况下，拓扑地图的 融合。只要两个拓扑地图包含有意义的相同区域( 通常大于两个顶点) ， 那么最后就会得到融合后的正确的全局地图，扩大了拓扑地图融合的 应用范围。 采用分散式结构的多机器人系统，实现了信息共享、自主决策， 但是各机器人之间的协作没有得到体现，可能会出现多个机器入同时 探索同一区域的情况，机器人也可能将其他运动的机器人当成动态干 扰。y a s u o 通过对机器人群体行为的分析，提出了一种基于观测的协作 框架结构【25 1 。k i m 设计的多机器人系统中每个机器入的控制算法互不 相同，实现了地图创建中在线的进化学习【2 6 1 。d e d e o g l u 解决的问题是 融合基于路标的地图，机器人不在同一坐标系下，初始时刻不知道对 方的相对位置，运用两个地图间的单顶点匹配，估计一种平面转换， 然后匹配其他的顶点，产生一个统一的全局地图【27 1 。但是，多机器人 6 山东大学硕士学位论文 协作创建地图仍然没有得到一个完整的总体解决方案。 1 3 本文的主要工作 本文以移动机器人环境建模任务为背景，探讨了拓扑地图创建及 相关问题，研究了单机器人拓扑地图的创建方法和多机器人拓扑地图 融合问题。主要工作包括： ( 1 ) 回顾了移动机器人地图创建的研究现状，地图创建的主要问 题包括：环境空间表示法，多传感器信息融合以及多机器人地图融合。 本文研究了拓扑地图创建中常用的v o r o n o i 图，建立了移动机器人环境 建模仿真平台，对基于平面点集的v o r o n o i 图和二维平面中的广义 v o r o n o i 图g v d 分别进行了实验验证。 ( 2 ) 采用模式识别图像处理问题中常用的细化算法创建环境的拓 扑地图，简易且有效。首先以栅格地图建模机器人环境，然后将环境 的栅格地图进行细化，提取出环境的有效拓扑信息。仿真实验表明， 基于细化算法创建的环境拓扑地图，清晰、简洁，相比于v o r o n o i 图 不会产生多余的节点和路径信息；相比于栅格地图，信息存储空间明 显减少，从而提高了移动机器入自主运行、导航的能力。 ( 3 ) 研究了多移动机器人拓扑地图融合问题，实现了机器人相对 位置未知的情况下，多机器入系统的拓扑地图融合。借鉴h u a n g 等人 提出的图像匹配和图像配准方法，将拓扑地图融合问题看作图像匹配 领域的扩展问题，基于拓扑地图的几何结构，搜索地图的最大重叠区 域，完成地图融合。首先，对于特殊环境中的两个拓扑地图，采用图 像配准结合穷尽搜索优化算法，寻技最大的公共子图，进行地图融合； 其次，对于一般的两个拓扑地图，采用图像配准方法中经典的i c p 算 法，结合奇异值分解算法( s v d ) ，进行地图融合。最后，进行了仿真 实验，分别在简单环境和复杂环境下进行了实验。实验结果表明，基 于几何结构的图像配准算法以及i c p 图像配准算法应用于拓扑地图融 合，均具有较大的可行性和较高的效率。 ( 4 ) 最后，文章分析了下一步可以进行改进的地方并对未来发展 进行了展望。 7 山东大学硕士学位论文 1 4 论文结构 本文结合山东省科技发展计划项目“多移动机器人协同环境探索 系统研究”，以未知环境下移动机器人的环境建模为研究背景，对机 器人在未知环境下拓扑地图的建立和多移动机器人拓扑地图融合算法 进行了探讨研究，并进行了仿真实验。文章结构主要分为以下几个部 分： 第一章绪论，综述了本文的研究背景，移动机器人环境地图创建 现状以及涉及到的主要问题。 第二章单移动机器人拓扑地图的创建。采用模式识别图像处理问 题中常用的细化算法创建环境的拓扑地图，解决了v o r o n o i 图中易产生 多余节点和路径信息的问题。首先以栅格地图建模机器人环境，然后 将环境的栅格地图进行细化，提取出环境的有效拓扑信息。仿真实验 表明，基于细化算法创建的环境拓扑地图，清晰、简洁且有效，而且 信息存储空间减少。 第三章多移动机器人的拓扑地图融合。将拓扑地图融合问题看作 图像匹配领域的扩展问题，基于拓扑地图的几何结构，利用图像配准 方法搜索最大的相同区域，确定两个地图间的最佳匹配。首先，对于 特殊环境中的两个拓扑地图，采用穷尽搜索优化算法，寻找最大的公 共子图，进行地图融合；其次，对于一般的两个拓扑地图，采用图像 配准方法中经典的i c p 算法，结合奇异值分解算法( s v d ) ，进行地图 融合。分别在简单仿真环境和模拟的复杂实际环境进行了仿真实验， 结果表明了基于几何结构的图像配准以及i c p 图像配准算法在拓扑地 图融合中的应用效果良好。 第四章针对移动机器人创建环境拓扑地图和多移动机器人的拓 扑地图融合问题，本章给出了全文的结论和对未来发展方向的展望。 8 山东大学硕士学位论文 第二章基于细化算法的移动机器人拓扑地图创建 拓扑地图，由k u i p e r s 首次提出，以图( g r a p h ) 的结构形式表现一 个环境的连通性，重在描述环境的拓扑结构【l9 1 。相比于栅格地图，信 息存储空间和计算量明显减少，是一种简洁有效的环境表示方法。拓 扑地图由两个基本要素组成，g = ( v ，e ) ，v 表示地图中的节点，e 表示 地图中节点之间的连接路径。 拓扑地图的创建有两种方式，一种是直接根据传感器信息和机器 人运动模型创建，如r y b s k i 设计的机器人携带一个全景的摄像机，在 探索过程中，通过识别环境图像数据的特征创建拓扑地图【2 引，节点表 示环境中的重要位置点，如走廊交叉点，拓扑地图的边表示环境中节 点之间的连通路径。另一种是从几何地图( 特别是栅格地图) 中提取节 点和连接关系，如常见的广义v o r o n o i 图法，c h o s e t t l 0 建的拓扑地图是 基于环境的g v g ( g e n e r a l i z e dv o r o n o ig r a p h ) 图【z 引。机器人在探索环 境的过程中，沿与两个障碍物等距的v o r o n o i 图的边移动，定义了接近 状态、探索状态、边界点状态等几个子状态，采用增量式算法构造g v g 的实现，逐步产生g v g 图的节点和路径。由于环境的复杂性或者传感 器噪声，v o r o n o i 图中会产生多余的节点或路径。因此，机器人必须沿 着v o r o n o i 图的路径移动，充分地感知拓扑信息。基于这种情况，c h o s e t 等人提出了r e d u c e dg e n e r a l i z e dv o r o n o ig r a p h ( r g v g ) ，消除了一些多 余的节点和路径，但是这样的设计不能很好地处理存在噪声的环境， 因为创建r g v g 图时带有固定的“修剪”，可能会删掉地图中有意义的 节点【30 1 。文献【31 】中，k w o n 仓j 建的拓扑地图是基于局部栅格地图，采 用细化算法建立的t t m ( t h i n n i n g - b a s e dt o p o l o g i c a lm a p ) ，能够较容易 地提取出环境中有效的拓扑信息。文章中，k w o n 定义了位置概率验证 末端节点的有效性，因为细化过程建立的是局部拓扑地图，全局拓扑 地图通过融合局部地图节点而得到。如果选择t t m 的边作为探索路径， 那么移动机器人就可以在未知环境中探索且躲避障碍物，完成其他导 航问题【32 1 。还有一种常见的方法是四叉树法【33 1 ，局部栅格地图作为层 次式结构地图的基层，采用标准四叉树结构，逐层减少栅格单元数目， 得到栅格地图的分层高精度四叉树表示，提取出拓扑地图的节点。 9 山东大学硕士学位论文 本文介绍的拓扑地图创建方法，是从栅格地图环境中提取节点和 连接关系。本章首先介绍了v o r o n o i 图的基本概念，对基于v o r o n o i 图的 拓扑地图的创建方法进行了仿真实验。然后采用图像处理中的细化算 法创建环境的拓扑地图，以栅格地图建模机器人工作环境，将环境的 栅格地图进行细化，提取出有用的拓扑信息，解决了v o r o n o i 图中易产 生多余节点和路径信息的问题。栅格地图可以看作原始传感器数据和 最终拓扑地图的过滤器，这样就会对传感器数据具有鲁棒性，并且能 够处理由任意形状物体组成的环境。在细化过程中，需要随时检测孤 立点和线段端点，对细化后有空洞、断点的图像进行实时处理，保持 细化后图像的连通性。 2 1v o r o n o i 图简介 v o r o n o i 图是一个关于空间划分的基础数据结构【34 1 ，在求解点集或 其他几何对象与距离有关的问题时有重要作用。 在v o r o n o i 图中，被用来划分空间的各个基本图形元素一般被称 为站点，最基本的v o r o n o i 图是以平面点集为站点的v o r o n o i 图，它将 平面划分成凸多边形形状的v o r o n o i 区域，区域中的每个站点p ，对应 一个区域y ，使得v 内的任何点到p 的距离，比距离其它站点近。因此， 平面点集的v o r o n o i 图是到某对点等距点的轨迹【35 1 ，v o r o n o i 图的边是 这对点的垂直平分线上的一条线段或半条直线。当机器人沿v o r o n o i 图的边移动时，通过距离传感器的数据而创建环境的v o r o n o i 图。此 方法能够创建多种环境的拓扑地图，但是由于传感器噪声的影响，会 产生多余的节点和路径。基于v o r o n o i 图的地图的有利之处是，机器 人沿着环境的v o r o n o i 图的路径行走是最安全的。 2 1 1v o r o n o i 图的定义 1 0 山东大学硕士学位论文 l ， 三 p l j _ - ，l p ： 图2 - 1 平面点集的v o r o n o i 图 平面点集的v o r o n o i 图的基本形式如图2 1 所示，p 。，p 2 是平面中 的两个点，称为站点，是线段一万i 瓦。的垂直平分线，即等距线，将平 面分成两部分厶和厶，位于厶内的点p 。具有这样的性质： d ( p ：，p 。) d ( p l ，p ：) ，其中( p ：，只) 表示p ：与只( f _ l ，2 ) 之间的欧几里得距 离，表示位于厶内的点比平面内其他点更接近点a ，记为v ( p 。) 。如果 用h ( p l ，p 2 ) 表示半平面厶，而l 2 = h ( p 2 ，p 1 ) ，则v ( p 1 ) = h ( p i ，p 2 ) ， v ( p 2 ) = h ( p 2 ，p i ) a 图2 - 2n = 6 ，v ( p 1 ) 示意图 给定平面上n 个点的集合s ，s = p l ，p 2 ，p 。) ，v ( p ) 是比其他点 更接近p 。的点的轨迹，是n 一1 个半平面的交集，是一个不多于n - 1 条 边的凸多边形区域，称为关联于p l 的v o r o n o i 域或p l 的v o r o n o i 多边形。 图2 2 为n = 6 ，p l 的v o r o n o i 多边形示意图。 山东大学硕士学位论文 图2 - 3n = 6 时的v o r o n o i 图 对于s = 死，p ：，p 。) ，其中的每个点都可以作一个v o r o n o i 多边 形，这样的n 个v o r o n o i 多边形就组成v o r o n o i 图，如图2 3 所示，记 作v o r ( s ) 。v o r ( s ) 把平面划分成n 个多边形区域，每个多边形域矿( 只) 包 含且只包含s 中的一个点，v o r ( s ) 的边是s 中某对点的垂直平分线上的 一条线段或者半条直线，从而为该点对所在的两个多边形区域所共有。 2 1 2 广义v o r o n o i 图 在平面内，将点集的概念扩展到几何体的集合，如多边形集合， v o r o n o i 图的概念就扩展为广义v o r o n o i 图g v d ( g e n e r a l i z e dv o r o n o i d i a g r a m ) ，点扩展为多边形。g v d 的基本思想是产生与所有多边形障 碍物边界点等距离的线，这些线叫做v o r o n o i 图的边，v o r o n o i 边之间相 交的点称为v o r o n o i 图的顶点【36 1 。如果扩展到三维空间，广义v o r o n o i 图就成为g v g 图( g e n e r a l i z e dv o r o n o ig r a p h ) 。g v d 和g v g 图中，障碍 物不能简单地看作质点，需要定义广义距离函数、广义v o r o n o i 域等概 念。 ( 1 ) 广义距离函数 1 2 山东大学硕士学位论文 图2 4 d ? 和v d i 示意图( 摘自文献【3 0 】) 如图2 - 4 所示，点x 到凸集c 的距离定义为：吖= m 铀i n i x - c oi ( 2 - 1 ) 距翱的梯度定义为：蹦2 南( 2 - 2 ) l i x c ( 式中，c 0 是使得c o = m i n 。e cl i x - c o i 的点) 梯度是一个单位向量，以x 为起始点，由岛指向x 。 对于凸集，障碍物到x 的距离是连续的，距离x 最近的点是唯一的。 ( 2 ) 广义v o r o n o i 域 在基本的v ：o r o n o i 图中，v o r o n o i 域是到某对点距离最近的点组成的 集合，而广义v o r o n o i 域是到某对障碍物距离最近的点组成的集合。 g v d 是到集合g 和c ，距离相等的点组成的集合。到两个障碍物的 距离相等，称为2 等距面。定义式为： 毛= 缸( cu c ，) z g ) 一d ，0 ) = o ( 2 - 3 ) 图2 52 一等距面乞示意图 图2 5 所示为2 - 等距面的示意图，2 一等距面是由到障碍物e 和q 距 离相等的点组成的集合，并且其上的任意一点到g 和q 的距离比到其 山东大学硕士学位论文 它任何障碍物的距离都近。最终定义式为： 毛= x ( u q ) ：o 巧0 ) - 哆o ) 以0 ) v h # l ，歹 ( 2 - 4 ) ( 且v 4 ( x ) v t ( 工) ，即其上任一点到各障碍物距离方向不同) 2 等距面是两个相邻的广义v o r o n o i 域的边界，毛= 巨n 弓。所有 的2 等距面就组合形成了g v d 。g v d = u = u ：。毛，如图2 6 所示。 图2 - 6g v d 不恿图 在平面的情况下，到两个障碍物距离相等的广义2 等距面就是边， 即广义等距边一g v d 边，广义等距边和广义等距边的交点称为广义交 汇点。 要定义g v g ，需要先定义3 一等距面s ，。，它是由到e 、c ，和c 。距 离都相等的点组成，。= 毛n 跌d s , 。，且其上的点到e 、q 和c 。的距 离最近。 等距边的定义式为： 毛t 。 o 三之工三_ 嘭( x ) = 畋( x ) 吒( 工) v 办f ，七) ( 2 - 5 ) = 毛ne ，。n 其中，v 4 ( x ) ，v d ，( x ) ，v 以( x ) 各不相等，即其上任何一点到各障碍 物的距离方向都是不同的。 2 2 细化( t h i n n i n g ) 算法介绍 2 2 1 细化算法的定义 图像细化就是把o 、l 二值化图像中具有一定宽度的线条状区域细 化成一条细线，象素值为l 的区域是需要细化的部分，象素值为0 的 区域是背景区域。一个图像的“骨架，是指图像中央的骨骼部分，是 描述图像几何及拓扑性质的重要特征之一。求图像骨架的过程通常称 1 4 山东大学硕士学位论文 为对图像“细化的过程【3 ”，图像细化的结果大大压缩了原始图像的 数据量，并保持原图像形状的基本拓扑结构不变。 细化算法应满足以下条件： ( 1 ) 将条形区域变成条细线： ( 2 ) 细线应位于原条形区域的中心； ( 3 ) 细线应保持原图像的拓扑特征。 细化算法从设计思想上来看，大部分都是基于逐层侵蚀剥离的， 逐层侵蚀的基本思路是：对图像进行多次迭代，每一次迭代过程中按 照一定的条件删除边界点，直到删除操作不能进行为止。这种方法的 优点是简单、直观、并且算法易于实现，缺点是迭代次数与处理的图 像的最大线宽有关，而且计算时间正比于最大线宽和图像面积的乘积， 所以计算量大，计算时间长。随着计算机技术的飞速发展，计算机的 处理速度已经有了很大的提高，基于逐层侵蚀剥离的细化算法已经得 到普遍的应用。 2 2 2 细化算法的基本步骤 p 9p 2p 3 p s 川 p 4 p p 6p 5 图2 7 中心单元p l 和它的八个临近单元 图2 7 描述的是中心单元p l 和它的八个临近单元p 2 p 9 ，“0 ”表示 单元为空，“l ”表示单元为满。对被占据栅格p l ，如果它的八个临近 单元满足如下细化条件，则其就被修改为空。 步骤1 】 ( 1 ) 2 n ( 绕) 6 ；( 2 ) s ( p 1 ) = 1 ；( 3 ) 岛 p 4 仇= 0 ；( 4 ) p 4 p 6 p s = 0 【步骤2 】 ( 1 ) 2 n ( f 7 1 ) 6 ；( 2 ) s ( p l ) = l ：( 3 ) p 2 p 4 p a = 0 ；( 4 ) p 2 p 6 p 8 = 0 其中，n ( 岛) = 仍+ p 3 +