（控制理论与控制工程专业论文）移动机器人自主地图库构建与环境认知.pdf

大连理工大学硕士学位论文 1绪论 1 1 研究背景和意义 机器人的诞生和机器人学的建立，无疑是2 0 世纪人类科学技术的重大成就。不到 4 0 年时间，机器人从无到有，现在已拥有“百万大军”，在世界经济各个领域和人民生 活的众多方面忠诚地为人类服务，做出了不可磨灭的贡献【l j 。 移动机器人是机器人技术的一个重要研究领域，也是机器人学的一个重要分支。移 动机器人研究涉及到图像实时处理、计算机视觉、传感技术及多传感器数据融合技术、 人工智能、自动控制、机电一体化等多个学科，体现了计算机科学与人工智能的综合技 术成果。移动机器人研究的主要目标是使机器人在复杂环境下实时安全完成任务，而对 环境的认知与同步地图构建是完成任务的前提和保证。在移动机器人相关技术的研究中， 地图构建与导航是其核心，一直是移动机器人的重要研究方向，也是机器人学的基础问 题。只有机器人在环境探测数据的基础上构建出精确并且描述简洁的地图才能保证机器 人更好并且更有效率地完成运动和探索任务。而环境认知问题作为机器人学研究的一个 新兴研究问题，越来越受到大家的关注，也是人工智能研究的关键课题。 本论文旨在研究自主移动机器人在完全未知环境下的同步地图构建，并且在有先验 地图的情况下研究机器人的环境认知问题。文中提出了地图库的概念，旨在更精确地描 述环境，并且为机器人的定位与路径规划打下基础。本论文采用激光测距仪传感器，在 机器人路径规划的同时，以线段特征的概率模型和散乱障碍区域的点聚类算法为基础， 借助栅格地图模型，实现了环境几何模型的构建。在已知先验几何地图的条件下，研究 拓扑高级特征的提取方法，实现了拓扑地图的构建。在此基础上，研究了有地图库信息 时机器人对当前环境的认知。最后由于激光测距仪具有精度高、方向性好以及受环境因 素影响小的优点，本论文所提出的地图表示方式和构建方法有良好的实时性和鲁棒性， 并且对机器人导航和路径规划很有意义。在环境认知方面的探索对将来这个领域的研究 起到了一定作用。 1 2 地图构建方法的研究现状和趋势 地图构建是指获取机器人所在物理工作环境的空间模型【2 】【3 1 ，通过摄像机、激光测 距仪、声纳等车载传感器获取环境信息，经过数据处理，建立环境地图。 移动机器人创建地图必须解决三个基本问题： 如何表示环境地图，即地图的表示方法。 移动机器人自主地图库构建与环境认知 怎样获得环境信息，机器人在环境中漫游并记录传感器的感知数据，这涉及到机 器人导航问题。 怎样表示获得的环境信息并根据环境信息更新地图，这就需要解决对不确定信息 的描述和处理方法问题。 1 2 1 研究现状 在自主移动机器人领域，目前流行的地图模型构建方法主要有五种：占据栅格法、 几何表示法、统计区域法、拓扑地图法和合成地图法【4 】，每种方法都有各自的优缺点， 如表1 1 所示。 表1 1 地图模型的比较 t a b 1 1 c o m p a r i s o no f m a pm o d e l s 地图表示基本原理 优点缺点 地图以网格表示。网地图存储容量大、 占据网格法 格分占有、空和未知适合于运动规划 网格精度低、不适 三种状态合定位 利用点、线段和圆等 环境表示模型 几何表示法 精度高、适合定位 单一、不适合 几何元素表示地图 室外复杂环境 用随机变量的数学特不需要任何环境 统计区域法征如均值方差和协方模型，适合于复杂精度低、计算复杂 差表示地图环境 利用节点和节点之间 适合于基于行为几何信息过少、不 拓扑地图法的连线表示环境位置 的导航适合定位 以及它们之间的关系 几何表示法和拓扑地 集合了几何地图相对复杂，存在几 合成地图法法和拓扑地图法何地图和拓扑地图 图法的综合应用 的优点的相互转化的问题 早期的许多系统是由操作者手动指挥机器人在环境中运动，要么是依靠预先存储的 地图，要么是采用被动机构来构建地图。而在另外的系统中，构建地图所需要的传感器 数据是由机器人在人工控制下采集得到的，然后再采用离线的学习算法来找到与数据匹 配的最好的地图来。尽管这些方法有一定的优点，但是人工干预代价太大，而且容易产 生认为误差。但却不能保证在复杂大环境下建造出完整的地图来 同样的，尽管反应式行为通常具有很好的鲁棒性。因此最灵活的方法是让机器人通 过基于地图的自动搜索来自行构造地图，根据自己构建的地图导航到这些区域，同时也 不断地更新它所构建的地图【副。 大连理工大学硕士学位论文 从移动机器人构建地图方面公开发表的文章来看，多数研究工作处于模型或设计模 拟阶段，大多数是实验室成果，真正用于工程的还不多。通过这些年的研究工作，涌现 了一批比较有代表性的研究系统。 美国和意大利的一些研究已经使用了立体视觉和激光雷达扫描仪，从而能构建出三 维地图来。美国c m u 用一个名为m i n e r v a 的交互式导游机器人在一座博物馆中为游人 做向导。他们在研究中运用了多种理论进行了地图构建，包括贝叶斯理论、马尔可夫方 法、卡尔曼滤波算法、概率论算法等。c a i 和p a g a c 分别应用范围传感器进行单个机器 人和多个机器人对简单环境的探n f 6 j 忉。h a n s 用基于特征的方法产生扩展卡尔曼滤波器 对机器人的定位和环境图绘制加一合成【引。而s h a n a h a n 对这一问题的研究侧重于用逻辑 公式描述智能体与环境的关系，他采用的是事件积分法 9 1 。 1 2 2 未来的研究趋势 虽然几十年来众多学者在地图创建领域进行探索，对现有方法进行了扩展和改进， 但是仍然面对诸多问题p j 。 1 适用环境问题 目前的概率方法基于先验模型，多数研究均假设机器人处在静态环境。但实际应用 中环境一般会变化或存在动态障碍物，导致构建的地图误差增大。因此需要选取适合的 地图描述方法，如在基于地图导航时应该采用拓扑地图更有效，而描述局部动态环境更 适合用基于几何特征的地图。 2 数据关联问题 数据关联是地图构建，特别是动态环境的地图构建中极其重要的问题。数据管理处 理不好，可能会出现静态物体产生的观测数据被错误地关联到动态物体或者相反。这样 会影响环境地图的一致性。在复杂环境中，需要更准确，更高效的数据关联技术，以便 克服感知的不确定性。 3 地图构建中的闭环问题 所谓环形闭合问题就是由于里程计误差，机器人在进行地图构建时，当机器人不能 确定经过的区域是否已经创建过地图，使同一环境对应多个地图，导致地图不一致。采 用基于主动闭环约束策略的地图构建方法可以修正机器人位姿，提高机器人定位的不确 定性，进而提高地图精度。 4 实时在线探测 实际应用中很多任务需要机器人独立完成未知环境的地图构建工作，这需要机器人 能实时在线探测环境。在有循环通道的大环境中，累积误差会无限增加。目前的多数算 移动机器人自主地图库构建与环境认知 法在消除环境信息的不确定性时需要很大的计算量，实时性会因此受到影响。因此，适 当的传感器和更好的算法对机器人实时工作至关重要。 1 3 移动机器人环境认知研究现状 环境认知对于移动机器人而言，是一个重要的研究环节。在未知环境中导航，尤其 需要移动机器人对环境的理解。对环境的认知是实现移动机器人在未知环境中导航的关 键技术。以往的研究是离散的、感知层次上的研究，难以为复杂未知环境下的机器人导 航提供足够的导航信息。 未知环境中的移动机器人只具有较少的先验知识，因此对环境的认知是实现环境建 模、定位、规划、行动等自主导航控制的基本前提。移动机器人的认知理论与方法研究 涉及计算机科学、人工智能、认知心理学、仿生学等领域，是新兴的交叉学科认知 科学的一项重要前沿研究项目【1 0 】。该研究从认知科学的理论与方法出发，探讨移动机器 人的环境认知过程，模仿人类选择性关注机制下的心理活动与智能行为，着重于对自然 环境的感受与理解；将移动机器人对环境的理解从片面的、离散的、被动的感知层次， 提高到全局的、关联的、主动性的认知层次上；探索一套适合于复杂环境的认知理论与 方法，适应移动机器人自主导航控制的鲁棒性环境建模与定位要求。 根据目前移动机器人的技术水平与所担负的任务，把移动机器人的环境限定为机器 人工作运行空间中的一切与之关联的对象，因此，环境认知的基础是空间认知。自主式 移动机器人通过传感器获取环境信息，对感知系统而言，需要完成的基本功能是，对象 与路标的识别、自身的定位、环境地图的获得( 建立合理的环境模型) 【1 2 j 【l3 。虽然人工 智能在机器推理方面已经取得了很大的进展，但在环境感知与理解方面却处于比较低级 的水平。机器人学的先驱h a n sm o r a v e c 曾经指出：在某些智能活动中，机器推理的能 力可以达到成年人所具有的推理和思考能力，而在对环境的感知与理解方面，人工机器 的能力尚不如一岁的婴儿【1 4 】。这不仅是受限于现有的传感器、计算机等硬件，更受限 于对环境认知机理的了解不够深入以及认知方法论不完备等原因。研究未知环境中的移 动机器人，比如要模拟人或动物在与环境交互过程中形成的有意识的认知方法和无意识 的反应机理。 认知科学以人和高等动物的智力行为以及大脑的功能为主要研究对象。空间认知是 存在于相对早期的动物进化中的重要认知能力，非常适合于研究从简单的定式行为向复 杂认知行为进化的一般性机理。移动机器人研究从智能控制的基础出发，期望赋予机器 人更多的人工智能【1 0 】。研究人类以及动物对环境的认知能力( 空间的感知与空间的行为 大连理工大学硕士学位论文 能力) 已成为研究人类以及其它高级动物对环境的认知科学研究成果应用于移动机器人 的研究，将有助于建立一个鲁棒的未知环境中的移动机器人认知体系。 1 4 本文主要内容与安排 传统的机器人地图构建主要采用四种地图表示方法：占据栅格法、几何表示法、统 计区域法和拓扑地图法。它们分别有不同的优缺点，这决定了每种地图表示方法有各自 适用方面：占据栅格法适用于机器人运动规划、几何表示法适用于机器人自定位、统计 区域法适用于精确描述复杂环境、拓扑地图法适用于机器人导航。但在实践应用中要求 机器人有很高的自主性，需要独立完成一系列工作，单一的地图不能满足要求。本文基 于现有的研究工作，提出了复合地图库的方法，提出了由多种不同地图表示形式构成的 地图库，综合了其各自的优点，也避免了不同地图表示形式之间的转化运算，可以为机 器人提供完备且便于应用的环境信息。 现有的机器人环境认知主要采用视觉信息，通过精确的数学分析方法实现特征提取 与匹配。但激光数据信息量远低于视觉信息，因此采用基于典型特征的概率匹配方法。 研究中借鉴了认知学和指纹识别技术提出了环境指纹的概念，将大量的环境信息简化为 由特征点集合构成的多个模板。采用同时路径规划与环境认知( s a p c ) 方法实现了环 境指纹间的匹配，进而实现了环境认知。 第一章绪论首先介绍了机器人地图构建的研究现状，并对地图构建的热点问题和研 究趋势做了综述，最后介绍了移动机器人环境认知这个热门的学科交叉课题的研究现 状。然后介绍了本文的主要内容与安排。 第二章首先介绍s m a r t r o b 2 移动机器人所装配的内部传感器和外部传感器，总结 并建立了里程计、激光测距仪两种传感器的模型。接着，提出了一种基于激光测距仪的 线段特征提取和几何地图构建的s p l i t m e r g e 算法。本文的地图构建工作主要基于这种 线段提取方法。 ， 第三章提出了复合地图库的环境表述方法，包括长线段、非规则障碍区和通路特征。 首先实现了几何地图和拓扑特征结构的提取。之后采用基于栅格的点聚类算法解决了非 规则障碍区的描述问题。最后从实际角度出发，将环境分为结构化环境和非规整、杂乱 环境两种，针对各自的结构特征分别实现了地图构建。 第四章研究了基于激光测距仪的环境认知问题。在第三章构建的环境地图基础上， 提出了实现了结构化环境的认知算法。针对非规整、杂乱环境，参考指纹识别的点匹配 算法将环境提取为基于通路特征的环境模板，即环境指纹。采用i c p 算法和同时路径规 划与环境匹配算法( s p a c ) 实现了环境指纹的匹配，实现了非规整、杂乱环境的识别。 移动机器人口土地幽库构建_ 环境认知 2 传感器模型及基于激光测距的特征提取 在本文研究中所使用的s m a r i r o b 2 移动机器人平台装配有里程计、激光测距仪等 多种传感器，这些传感器能采集到大蛀的室内环境信息和机器人自身位姿的变化信息， 为移动机器人完成地图构建、自定位、避障和导航等任务提供了信息基础。本章首先介 绍s m a n r o b 2 移动机器人所装配的内部传感器和外部传感器，然后对论文中所应用的 单程计和激光测距仪的模型及其误芹进行系统的分析和讨论。接着，采用s p l i t - m e r g e 算法对激光数据进行线段特征提取。 21 里程计模型 晕程计作为相对定位的有效传感器已经成为自主移动机器人的缺省配置，它的主要 原理是通过装在机器人车轮上的编码器对其进行计数，检测出两个轮转过的圈数，应用 航迹估算法估计出机器人的相对佗姿。内部传感器里程计u r 以提供短距离范围内机器人 定位和导航所必须的位姿信息，但在较长距离的运动中需要外部传感器提供校正信息。 陶21 所示的就足s m a r t r o b 2 自主移动机器人平台所使用的a g i l e n tt e c h n o l o g i e s 公司 的h e d s - 5 5 4 0 型号的光屯编码器。 勺 图21安捷伦公司生产的- = 三通道 e d s5 5 4 0 型号光电编码 | f i g2j t h r e ec h a n n e lo p t i c a le n e o d e r h e d s - 5 5 4 0 m a d e b y a g i l e n t t e c h n o l o g i e s 里程计的工作原理是根据安装在两个驱动轮电机上的光电编码器来检测车轮在 定时问内转过的弧度，进而推算机器人相对位姿的变化。设车轮半径为r ，光电码盘为p 线转，时剧内光码盘输出的脉冲数为则该车轮移动距离甜为： a d = 2 x ( n p ) x ( 21 ) 人连理大学硕士学位论文 假设由光码盘检测出机器人左右轮的移动距离分别为a d ，和a d 。，且两轮的阃距为 “一机器人从他姿x 。= k yb ) 运动到x 川= b 川，川，& + ) ，则机器人移动的距离为 a d = a d ，+ 划。) 2 ，机器人转过的角度为目= ( 鲋，一甜。) ，a 。 实验所使片j 的s m a r t r o b 一2 移动机器人平台单程计的远行周期为00 0 1 秒，所出完 全可以采用直线模犁对早程计数据进行推算。在s m a r t r o b 一2 机器人平台附带的软件中 所采用的是改进的直线甲稗计模型，即以卣线模 弘为主，同时在位姿方向角差值的推算 中使用弧线模型，只体表述如下： ，( x k “ ) ( 2 2 ) 22 激光测距仪模型 激光测距仪是一种基于t o f ( t i m eo f f l i g h t ) 原理的高精度、高解析度的外部传感措。 以s m a r t r o b 一2 平台装备的德固s i c k 公司l m s2 0 0 为例( 如图22 所不) ，其扫描区 域为1 8 0 。，扫描方向为逆时针方同，最大有限测距8 m ，距离和角度分辨率分别为1 0 n u n 和o5 。，并具有扫捕快速扫捕周期】33 m s ) 、数据点密集和测量精度高的优点。为了 减小反射咒强度不均带来的不良影响，l m s 采用一值化的方法对反射光强度进行处理， 对环境光线不敏感，主要受障碍物材料及其表而光滑度的影响较大“。 囊 幽22 l m s2 0 0 型激光4 距仪小意罔 f i g2 , 2 l m s2 0 0s c a n n c f 激光测距仪作为一种高精度的外部传感器，其与图像传感器村i 比，其具有不受光线 影响、处理方法简单和数据精度高等优点。与曾经在移动机器人研究中广泛使用的声纳 唱峨 澄 移动机器人自主地图库构建与环境认知 传感器相比较，激光测距仪不但具有更高的距离与角度分辨率，而且其极短的采样周期 和较低的测量误差使其成为当前移动机器人测距的主要手段。 l m s 系统是一种非接触式主动测距系统，不需要预设发射器和定位标志，其工作 原理是基于对激光束飞行时间的测量。脉冲红外激光束被发射出去后如遇到物体则被反 射回来，并被测距仪的接收器记录。激光脉冲从发射到接收的时间与测距仪和被测量物 体间的距离成正比。脉冲激光束被测距仪内部的一个旋转光镜( 旋转速度为7 5r p s ) 所 偏转以便对周围环境形成一个扇面扫描区域。目标物体的轮廓线从所接收到的一系列脉 冲序列来确定。通过高速串行接口( 5 0 0 k b i t sr s 4 2 2 ) 可实时的将测量数据传送给机器 人的主机进行及一步的数据处理【1 6 】。 我们实验中所配备的s i c kl m s 2 0 0 型激光测距仪扫描区域为1 8 0 。，有效测距8 m ， 距离和角度分辨率分别为1 0 m m 和o 5 。1 。( 对应的扫描数据点为3 6 1 或1 8 1 个) 。 l m s 2 0 0 型激光测距仪具有扫描速度快、数据点密集和测量精度高的优点，扫描数据可 表示为： = ( 毛，儿) 。，n = 1 ，n f 23 、 其中x 。= 巩c o s n ，y 。= d 。s i n # ，n 为扫描数据点个数。 2 3 基于激光测距仪的特征提取 激光测距仪可以提供特定水平面物体的精确距离信息，因此特别适合在室内环境中 提取水平线段特征。研究人员对激光测距仪进行环境特征提取已提出多种理论和方法， 而且也有一些成功的应用实例1 7 】【2 1 1 。与上述提及文献中机器人所配备的激光测距仪相 同，我们所使用的实验平台s m a r t r o b 一2 移动机器人也配备的是德国s i c k 公司的l m s 2 0 0 激光测距仪。 2 3 1 直线拟合 激光原始数据的密集程度与其对应的测量距离有密切关系。当物体距离激光测距仪 的距离超过3 m 时，数据点间距显著增加。所以我们只对测量距离在3 m 以内的数据进 行处理。这样不但有利于后续特征提取算法中共线准则阈值的选取方便，同时抛弃了不 确定信息较大的数据，降低了计算负担。 首先将激光测距仪数据点由机器人局部坐标系转换成为全局地图的坐标系，设机器 人的当前位姿为i x 足y r 靠r ，x p = i x py p r 为当前直角坐标系中的数据有： 大连理工大学硕士学位论文 由激光数据点提取线段的直线拟合采用s p l i t - m e r g e 算法。同时参考了几篇采用同 样方法拟合直线的论文，进行补充和改进。算法实现见图2 3 。其中d m 双表示设定的阈 值，以区分数据点是否属于某条线段。 图2 3s p li t - m e r g e 算法拟合直线 f i g 2 3s p l i t - m e r g ea l g o r i t h mf i t t i n gs t r a i g h tl i n e p b 具体的算法如下： 1 设定点与线段关系的阈值，一般为经验数值，并且受激光传感器和环境影响。认 为与线段距离大于这个阈值的点不属于这条线段，否则认为其属于这条线段。 2 将待处理数据点的第一个和最后一个分别作为线段的起点和终点，建立一个线段 的数学模型。 3 分别计算线段起点和终点之间所有数据点到这条线段之间的距离。 4 记录到线段的距离最大的点p j ，判断点p i 到线段的距离是否大于设定的阈值。 如是，判断点r 是否是孤点。 如是，将其前一个点作为线段终点。然后转到第5 步。 如否，将其作为线段终点； 如否，转第5 步。 5 如果所有数据点都被分析完就停止直线拟合，否则将线段终点后的所有数据点作 为待处理点，转到第2 步，继续直线拟合。 线段的起点和终点分别表示为a ( x 。，y 。) 和b ( x by 。) ，点p ( x p ，y p ) 到线段距离的公 式为： 幻q x + + 欧靠 g s c 蚱 一 + 靠 证 c s b = = x y 移动机器人口主地图库构建与环境认知 如点p ( o ，蚱) 是到这条线段距离蛙大的点，则新拟合线段的公式为 232 实验结果 ( 25 ) ( 26 ) 等嚣 大连理工大学硕士学位论文 图2 4 几何地图 f i g 2 4 m e t r i cm a p 图2 4 是基于实验室房间环境的直线拟合实验结果图，其中上图是实验室真实环境； 中图是机器人采集的激光原始数据点；下图是直线拟合后的结果图。 实验中，根据环境的实际特点和激光误差范围取直线拟合算法中的阈值为o 5 c m 。 s p l i t m e r g e 算法较好地实现了从原始激光数据点中提取线段，但某些极端情况中也存在 这误差。结果图中绿色的线段表示房间墙壁，可见长线段可以很好地反映环境结构。较 短的线段一般描述房间内障碍物，小的拐角等等，形状不规则而且数量很多。对比原始 激光数据可以发现，图中左侧较长的一条蓝色线段是误提取的，由于拟合直线过程中， 这条线段的起点和终点之间的数据点很少，因此将这两个相距较远、分别属于不同障碍 物的数据点划分为同一条线段。 移动机器人自主地图库构建与王 = 境认知 3 移动机器人地图库的实时构建 31 移动机器人地图库构建的意义 室内环境是指采用天然材料或人工材料围隔而成的小空间，是与外界人环境相对分 隔而成的小环境。包括居室、教室、会议室、办公室、候车( 机、船) 大厅和医院等各种 非生产性审内场所。室内环境的主要特点是区域封闭性，而积相埘较小，由规则几何形 物体( 如长线段、直角彤拐角等等) 和杂乱的障碍( 桌椅腿等等j 共同组成。 幽31 复合地图库结构图 f i g3l a b s t r a c tv i e w o f t h ec o m p o s i t e m a pb a s e 大连理工大学硕士学位论文 传统的地图表示法包括栅格地图、几何地图、拓扑地图及几何拓扑混合地图。其 各自的优缺点参加表1 1 。每种地图表示方法都有各自的适用局限性，没有能对机器人 定位、环境探索、路径规划等任务全部适用的地图表示。为了解决这个问题，本文提出 了复合地图库的概念，构建一种适合对机器人主要任务提供适当地图信息的地图数据表 示方法合集。其主要结构如图3 1 。 地图库的结构主要分为五层，传感器层、原始数据层、特征提取层、地图信息层和 任务层。传感器层包括里程计、激光传感器和摄像头等。其中激光传感器和里程计采集 表示环境信息的激光点和机器人自身的位置信息。经过特征提取层的处理得到初级几何 特征，进一步提取高级几何特征( 门、拐角、路口等) ，采用拓扑点记录这些高级几何 特征的信息。不能用长线段表示的杂乱数据点经过基于栅格统计的数据预处理滤掉动态 点和噪声后，由基于栅格的共享近邻聚类算法( g n n ) 得到非规则障碍区的具体参数， 用椭圆形状表示。最终得到了地图库中的几何地图、拓扑地图和非规则障碍区。这也是 本文关于地图库部分的主要工作，见图3 1 中虚线圈起的部分。机器人在路径规划中， 由几何特征通过一定的算法得到通路特征，作为通路地图存储在复合地图库中。由摄像 头采集的图像信息首先经过预处理去噪、滤波，再提取s i f t 特征，h a r r i s 特征等，构 成视觉信息集。这五个地图集是复合地图库的主要构成部分。不同的地图表示方式分别 对应机器人任务层的不同任务。几何地图主要用于机器人定位( l o c a l i z a t i o n ) ，拓扑地图 主要用于机器人导航( n a v i g a t i o n ) ，通路点地图主要用于机器人探索( e x p l o r a t i o n ) 。而机 器人环境认知( e n v i r o n m e n tc o g n i t i o n ) 需要与多种地图信息集进行数据交互。机器人在需 要完成某种任务时，可以在地图库中找到更适合的环境信息表示方式进行数据交互，提 高了机器人工作效率，并且对环境的适应能力更强。 3 2 由几何元素构建的地图 传统的几何地图表述是使用线段及线段的组合以及多边形等几何元素来表述环境 中的各种静态物体。但室内环境中的杂物障碍较多，决定了单纯的几何地图表述会包含 很多小线段。这些小线段包含的环境信息对机器人定位意义不大，并且无法简化成简洁 的地图模型。由此考虑保留较长的线段，将短线段还原成激光数据点表示成其他地图形 式。这样可以突出线段的优势，并且保留了环境的基本结构信息。 实验中取线段的限长为2 5 c m ，直线拟合算法见2 3 节。实验结果如图3 2 。左图为 环境真实地图，整体结构为封闭的房间环境，其中存在很多杂乱的障碍物。右图是直线 拟合后的效果图。 移动机器人自主地图库构建与环境认知 广 f i 、 _ - ，_ 一 图3 2 长线段几何地图 f i g 3 2 m e t r i cm a pb u i l d i n go fl o n gl i n e s 可见，长线段基本保留了环境的结构信息。且去掉短线段后，地图简洁清晰，方便 机器人完成其他任务时对环境信息的分析和处理。实验结果图也反映了一个问题，直线 拟合过程中由于算法本身原因和实验中的误差干扰造成了一些线段的提取失败，有部分 环境直线特征未能保存在地图中，这样造成了地图不能完整、确切地反映真实环境。但 是本次研究不仅仅用线段描述环境，同时也保留了无法提取出长线段的激光数据点，采 用特定算法从中提取出障碍区的信息，从而弥补了这一缺陷。具体方法将在3 4 节中具 体介绍。 3 3 拓扑地图构建 拓扑是指从严格定量测量中抽象出来的各种对象之间的关系，因此拓扑表述实际上 是一种经过抽象的环境关系，其包括由环境特征所确定的拓扑节点和用于表示节点间连 接路径的拓扑边。 室内环境中最常见的高级几何特征包括门、拐角和路口。这些特征由线段构成，但 比线段包含更多的环境信息，并且一般多存在于走廊等结构化环境中，如图3 3 是实验 室真实走廊环境的3 d 视图。因此构建拓扑地图首先要解决的问题是如何准确提取这些 高级几何特征，并将这些由线段构成的复杂特征合理地转化为拓扑结构，进而得到图3 1 复合地图集中的拓扑地图。 大连理上人学硕士学位论文 阿33 走廊环境的3 d 地图 f i g3 33 d m a p o f a h a l l w a y 3 31环境模型中高级几何特征的提取 夺门( d o o r s ) 特征 门是室内走廊环境所具有的典型环境特征，当走廊的走向已知时，门的提取就易于 实现。判断门的主要依据是门的宽度和两边的间断特征，如圈3 4 所示，由此构建门的 几何模型。 矛工墨工墨 i 类型断点lb 粪型断点 罔34a 型间断特征jb 型间断特征示意圈 f i g3 4 a b s t r a c tv i e w o f s t y p ed i s c o n t i n u i t i e sa n d “z ”t y p ed i s c o n t i n u i t i e s fj 有二个状态，全开、半开和全关，如图35 。无论哪种状态下，机器人存走廊中 单向行走采集环境信息只能记录下门的两个间断特征之间的距离和个间断特拭。 移动机器人自土地幽库构建o 环境认知 _ j + - l lj 1 目35f 的= 种状态 f i g3 5 t h r e es t a t e so f ad o o r 问断特征判断的主要依据构成间断的两条相互垂直线段的相百关系来实现。判断两 条线段是否垂直和线段长度是否在合理范围内。两条线段的起点和终点分别为 ( z 小y 。) 、( 扎y ，) 和( j 埘y 。) 、( z y 。，) ，下面公式是判断方法的数学表达。 派i 再瓦j 了c ( 3 ( 3 2 ) 其中阔值，和s ：为根据具体环境通过实验获取的经验值。 j 的拓扑点表示为门的中点到走廊对面墙壁垂线与走廊巾线的交点。如网36 ，图 中是实验室外部走廊的3 d 地图的一部分，红色表示f j ，白色圆点表示门对麻的拓扑点。 图36 门的拓扑点 f i g3 6t o p o l o g y p o i n t so f a d o o r 丑嘞丝 壶一 人连理工大学顾十学位论文 夺拐角( c o t r e r s ) 特征 拐角冉两条相互垂直相交的线段特缸构成，所以拐角的提取对于间断和通路特征简 单且鲁棒性好。设s ，( 。，咒，h ) 和s ：( 如儿t ，儿) 是形成拐角的两条乖直线段，拐角可 以用、 和q 三个参数唯一确定，、儿表示在机器人坐标下的拐角顶点牛标，哎 表示拐角的角分线与机器人坐标中x 轴的夹角。但由于实际府用中测量噪声丁扰及机器 人所处位置角度的限制，由激光测距仪原始数据中提取出的构成拐角的两条线段未必有 其同的顶点，而且两条直线也无法保证完全垂直。因此实际应用中，我们采用如下公式 对拐角进行判断。 j 等等卜m 鲁专忡卜 。， 、厩= 了瓦而c 旬 ( 34 其中闽值0 和。是通过实验获取的经验值。由于。的取值般比较小，所以t 、， 的计算叫使用如下公式近似。 t = 学以= 半 当精度要求比较高时可以利用延长直线法计算出。和儿的精确值。 圈37 拐角的拓扑点 f i g3 7t o p o l o g yp o i n to f ac o m e t 35 拐角的拓扑结构表示为拐角顶点到走廊两边墙肇分别做的两条垂线所构成矩形的 几何中心，拓扑信息包括了拐角两个走廊的宽度信息( 要用于环境认知，见第四章) 。 如图37 中，白色的点表示拐角对应的拓扑点。 移动机器人自主地图库构建与环境认知 路口( c r o s s e s ) 特征 路口由两个或者四个拐角构成，如图3 8 。因此首先采用判断拐角的方法，之后进 步判断几个拐角的相对位置即可。 一l l 厂 图3 8 两种路口 f i g 3 8 t w ok i n d so f c r o s s e s 判断路口的方法是：判断是否存在两个拐角，它们的顶点连线与这两个拐角的相应 边在同一条直线上，并且两个拐角顶点的距离在一定范围内。如图3 9 ，两个拐角的顶 点分别为q ( 杨l ，y d 。) 和q 0 2 ，y 0 2 ) ，其对应边分别为厶( x i ，y l ，x d l ，y d 。) 和 三2 ( x 2 ，y 2 ，x d 2 ，y d 2 ) 。 l l o l 0 2 图3 9 路口的两个拐角 f i g 3 9t w oc o m e r so fac r o s s e s 我们采用如下公式对路口特征进行判断。 f a r c t a n ( 必) 一a r c t a n ( 蚴) | 占l z d 2 一x d lx d 2 一x 2 瓜i 乏再瓦而 其中乃。、：和占。是通过实验取的经验值。 ( 3 6 ) ( 3 7 ) ( 3 8 ) 移动机器人自主地图库构建与环境认知 闭区域，并不符合人类对环境进行区域划分与认知的习惯( 当然也不符合通路点定义中 对区域面积的要求) ，因此被称为伪通路点，具体如图3 11 中灰色空心点所示。 机器人根据获取的感知信息对其所处环境的抽象表示被称为环境表述。在机器人运 动过程中，利用传感器信息能够迅速的实现局部环境中所存在通路点的提取。将各个时 刻提取的通路点按树形结构连接起来，即实现了基于通路点的室内环境表述，也就是将 全局环境中相邻且大于一定面积的开阔区域通过一系列的通路点关联起来，并利用树形 拓扑结构构建出通路点关系图。该表述方法不但提取快速、简洁实用，还具有动态适应 性好的特点，并能保证通路点关系图全局维护上的一致性。 3 3 2 拓扑地图构建的实验结果 拓扑地图生成的关键是如何合理的完成拓扑节点的选择，具体可分为等间距法和变 间距法两种规划方式。等间距法是按照统一的间距来安排所有的拓扑节点分布。这种方 法易于实现，而且拓扑边的迸一步规划也非常简单，但会造成部分拓扑节点没有足够的 环境特征与其对应，从而增加该节点处定位的难度。而变间距法对拓扑节点的选取则根 据是否能有足够的环境特征与之绑定这一前提条件，虽然判断过程相对复杂，但其具有 更强的灵活性，使得应用于实际环境中的移动机器人定位、导航易于实现。 图3 1 2 走廊环境与拓扑地图实验结果 f i g 3 1 2h a l l w a ya n dt o p o l o g i c a lm a pb u i l d i n g 大连理工大学硕士学位论文 为了更好地表示拓扑地图，建立理想化走廊环境的仿真地图。根据走廊环境特点， 所有拓扑节点均处于走廊中线。与单一高级特征绑定的拓扑节点横坐标处于高级特征的 中轴线，而同时与两个高级特征进行绑定的节点其横坐标则位于两者轴线的中间位置。 由于拓扑节点都选择在走廊的中线上，所以拓扑边的规划是将走廊中线上相邻节点直接 连接起来。走廊拓扑地图的实验环境与实验结果如图3 1 2 。 在机器人环境探索中，可通过通路点来指导机器人进行有效的探索。这种在全局环 境中采用通路点表述的方法简洁实用、特征提取迅速、构建方便且具有动态适应性。房 间环境的拓扑节点选择为通路点，拓扑边的规划是连接各个通路点的树形结构。这样可 以记录机器人路径规划的行走轨迹，使基于拓扑地图的机器人导航时便于实现。实验环 境与实验结果如图3 1 3 。 境与通路点环境表述 f i g 3 13 r o o ma n do p e n p o i n t s 3 ，4 非规则障碍区域的表示与地图构建 3 4 1实际环境中障碍区域分析 室内环境，特别是房间中存在各种障碍物，比如桌椅、纸箱、盆栽等等，种类繁多。 实际工作中几乎不可能为所有的障碍物建立模型，这样做代价太大，会导致前期工作非 常复杂，而且鲁棒性不好，不具有普遍适用性。而传统的几何地图主要以线段形式表示 环境信息，这种方法也存在不足，详见表格1 1 和第3 2 节。 大连理工大学硕十学位论文 呈一次线性关系，而主要由网格的划分及数据的空间分布情况决定。如数据的分布越集 中，则实际所占的网格数越少，则聚类效率越高。 传统的基于网格聚类算法在处理孤立点或噪声方面精度都不高。因此本次研究中采 用一种基于网格的共享近邻聚类算法( a 州) 来进行不规则障碍区的划分。g n n 算法 的基本思想是：首先将数据集v 所在区域s 分割成m 个网格单元，一个栅格单元的邻 居是指与其有共同边界的或有共同点的那些栅格单元。计算出非空的网格单元数 g r i d n u m 和网格单元中点数的最大值m a xg r i d ，再利用密度闽值处理方法计算出密度 阈值m i n p t s 。若一个网格单元中数据点个数大于密度阈值认为其是高密度单元，否则为 低密度单元。对高密度单元利用网格中心点技术计算其中心点，而对低密度单元中的数 据点进行边界点的提取或作为噪声数据处理。聚类就是将相邻高密度单元相连形成的最 大集合。 g n n 算法如下： 输入：s h a r e d p o i n t s ，k ，m i n 输出：c l u s t e r s ，o u t l i e r s n o i s e s 步骤1 ：调用网格中心点处理过程c e n t e r ( ) ； 步骤2 ：f o r ( i = l ；i = h d e n s i t y ；i + + ) 查找c e n t e r i 的k 个近邻中心点集合k n e i g h b o r ( c e n t e r i ) ； 步骤3 ：对任两个k - n e i g h b o r ( c e n t e r i ) 和k n e i g h b o r ( c e n t e r j ) ( 1 = i = h d e n s i t y ， 1 = j s h a r e d p o i n t s ， 那么c e m e r i 矛ic e n t e r j 聚为一类，则对应的第i 个高密度单元和第j 个高密度单元中的 数据点也归为一类； 步骤4 ：检查每个类c 如果i c i m i n ，那么该类即是所得的最终聚类； 否则c 中数据点作为噪声数据处理； 步骤1 是通过调用网格中心点处理过程获得中心点集。步骤2 是对每个中心点，找 出距离其最近的k 个邻近中心点，形成一个集合。步骤3 若两个中心点对应的邻近点集 合中的公共点数超过s h a r e d p o i n t s ，则将两个中心点归于一类，同时将每个中心点对应 的高密度单元中的数据点归于中心点所在的簇，以达到对原始数据集的聚类。步骤4 是 当聚类结果生成时，要检查聚类结果中每个聚类中的点数，若点数小于用户给