移动机器人环境地图实时构建算法系统(最新)13页

1、西北工业大学2010年大学生创新性实验计划项目申 请 书项目名称 移动机器人环境地图实时构建算法系统 所在学院/基地 舞蹈机器人基地 申 请 人 严家祺 罗国佳 秦博奇 詹东昀 导师姓名 黄英亮 联系电话E-mail: luogj8904 填表日期 2010年9月13日 西北工业大学教务处制表项目名称移动机器人环境地图实时构建算法系统起止时间2010年9月至2011年9月申请经费20000申请人或申请团队学 号姓 名年级所在学院、专业联系电话E-mail2007301716严家祺07级电子信息学院电子信息工程137599426572292885032008302577

2、罗国佳08级计算机学院计算机科学与技uogj89042008302578秦博奇08级计算机学院计算机科学与技inboqi01162008302604詹东昀08级计算机学院计算机科学与技han89616导师姓 名黄英亮学院机电学院职务/职称高级讲师E-mailhuangyl电 、申请立项依据（包括项目背景、项目来源、技术依据、前期已有的研究基础，自身具备的知识条件、自己的兴趣爱好、特长等）项目背景、来源： 现代社会当中，火灾、爆炸、坍塌等事故多发，在救援过程中因灾难现场情况不清，意外坍塌事故等

3、导致救援人员遇难的惨剧时有发生。为避免此类事故，应用救援机器人首先进入现场及时探知险情和受困人员的位置和状况，有着极大的应用意义。因此，在每年的Robocup国际机器人赛事中，Robocup救援组是最热门项目之一，其主要目的就是促进大规模灾难情况下使用机器人进行人员搜救任务的研究。灾难现场实时环境地图的创建是移动救援机器人领域中的一个基本而重要的问题。环境地图被广泛地应用在移动机器人的导航系统中，在移动机器人导航定位和全局路径规划中起到重要作用。要实现移动机器人的自主导航，最重要的是通过定位来获知机器人在环境中的准确位姿。根据先验地图进行的移动机器人定位和自主导航技术得到了广泛的研究，并取得很

4、好的应用效果。但是实际环境往往是未知的，不能提供诸如环境中障碍物大小、形状、位置等先验信息，而且实际突发灾难事件环境中也不存在路径、灯塔等人为设定的标志物，这给移动机器人的自主导航带来了很大的问题。因此，移动机器人在未知环境中同时精确定位和地图创建（SLAM simultaneous localization and mapping）成为移动机器人研究领域的一个亟待解决的问题。自然而然，地图的构建质量也就成为每年Robocup救援组比赛项目的一个重要评分依据。技术依据：本项目采用几何特征地图来反映机器人所处外部环境，如灾难现场中的墙壁、较大的家具等。几何特征地图是一种紧凑的地图表示方法，通过传

5、感器感知环境数据，从中提取抽象几何特征如线段、圆、弧线等来表示环境信息。对于大多数环境特别是室内环境利用几何特征描述的地图都能精确的反映环境信息，而且几何特征地图存储信息量小，方便应用于位姿估计和目标识别。前期已有的研究基础：本项目拟通过激光测距仪扫描采集外部环境数据，并设一套高效的算法处理所得数据来实时创建并更新现场环境地图。舞蹈机器人基地目前已具备救援机器人的机械和电子部件，曾经采取过的构建地图的方法主要是依靠超声波传感器、电子罗盘、加速度传感器等多传感器的信息融合，来构建几何特征地图。但由于这个方法结构复杂，受多个传感器的影响，系统的精度一般不高，而且系统抗电磁干扰能力太差，往往得不出理

6、想的地图构建效果。而本项目采取的方法只需要一个激光传感器采取数据，通过算法处理优化，完全可以替代以上多传感器的融合，大大简化了系统的复杂性，提高了系统的可靠性与稳定性，减小了系统误差。自身具备的知识条件：本项目的项目组人员都是西北工业大学舞蹈机器人基地的成员，在过去的实践中，对传感器的操作与传感器的应用都有一定的了解。本项目的人员由电子信息专业和计算机专业的学生组成，首先可以解决底层硬件通信的问题，而上层数据处理算法则由计算机专业的成员完成，我们在计算方法、计算机图形学、算法设计与分析、信号处理等学科上有扎实的基础，因此可以胜任信息采取与算法设计的工作。自己的兴趣爱好、特长： 本项目组的人员都

7、是舞蹈机器人基地里的核心人员，动手能力强，善于思考，对MFC绘图、算法的设计、传感器网络通信等都有过经验。二、立项研究的目的和意义环境地图是移动机器人自主完成任务的首要条件，未知环境中移动机器人同时定位和地图创建对于智能机器人技术的发展有着重要的意义。本项目预设计并实现一个简单而有效的系统，该系统能快速、准确地构建出现场环境的几何特征地图。由于只采用激光测距仪采集数据，相比多传感器融合系统而言，大大降低了多传感器导致的系统误差，且激光测距仪采集数据精度高，抗外部干扰能力强，更适合于灾难现场的复杂环境。后期数据处理及地图生成采用软件实现，相对硬件实现更易于改进和优化。几何特征地图意义重大：第一：

8、对灾难现场实现地图重现，可以有助于救援人员开展救援工作，提前预知现场环境，避免再次意外对救援人员的伤害。也有利于及时调度救援人员，最大限度的救出受困人员，具有很大的社会意义； 第二：环境地图是智能移动机器人自主行走、自动避障、自主识别救援目标的技术基础和重要保障，促进了智能移动机器人的发展。三、项目计划实施研究内容第一：对激光传感器的特性以及参数的研究，保证采集到的环境数据的精确度和数据传输的准确性，深入了解激光传感器的原理，还可以利用其特性简化日后数据处理的工作。第二：对算法中涉及到的激光扫描频率、扫描范围、动态阈值等一些参数的设计作预估，建立数学模型分析，得出一个精度较高的模型。第三：结合

9、传感器的实际数据，进一步验证模型的精确程序，根据实际数据对模型进行优化，选择最适合的算法参数。第四：搭建灾难现场摸拟环境，对系统进行大量的试验，不断改进和优化算法方案。第五：编写高效的作画程序，能快速、精确绘出现场的几何特征地图。四、国内外研究概况扫描匹配方法是环境地图创建的一种有效的方法，可分为迭代匹配算法和非迭代匹配算法。迭代最近点（ICP）算法是一种典型的迭代匹配算法。ICP算法通过在迭代过程中不断降低配准误差，获得两组点集间相对位姿变化。该算法的缺点是匹配收敛速度慢而且容易陷入局部最优解。此后，出现了许多基于ICP算法的改进算法。直方图匹配算法是典型的非迭代匹配算法，该算法的最大优点是

10、算法容易实现，匹配速度快，但是受构建特征直方图时分辨率选取的影响，匹配精度很难得到有效的提高。总体而言，迭代匹配算法匹配精度高，但匹配收敛速度较慢，很难完成实时条件下环境地图的创建；非迭代匹配算法的匹配速度优于迭代匹配算法，但是匹配精度不高。五、研究方法、技术路线及研究中面临的技术难点和拟采取的解决办法 本项目利用激光测距仪测得环境数据，从中提取出特征点对，采用非迭代的方式，在误差函数的解空间里采用聚类的方法完成点对的匹配，进而完成环境地图的创建。1、 特征点对的提取：激光传感器在i时刻扫描得到描述环境信息的点集uki，对uki中的数据进行特征点对的提取，特征点对是描述现场环境的多变形的线段的

11、起点和终点，如图1所示。 (a)激光数据点集 (b)特征点对集 图1 提取特征信息效果2、 特征点对集的匹配：特征点对集的匹配基于以下两个假设：一是环境中的特征点之间具有拓扑结构稳定性，即两个特征点之间的欧式距离在相邻两组数据中是相等的，在静态环境中这一假设一般能够满足；二是在二维平面内，相邻两组特征点集之间的变换可以视为刚体变换，可由两组特征点对集中的对应匹配点对之间的变换来表示，这样可以提高算法效率，降低计算复杂度。匹配算法可以概括为匹配、计算、聚类三个步骤。I 匹配是指在两组特征点对集中选出所有欧式距离相近的对应特征点对，构成对应特征点对集合。II 计算是针对每对对应特征点对，求得相应的

12、旋转角Ri和位移Ti，加入到三维向量解空间 (,)中。III 一般情况下，对于配对过程中错误的特征点对，即相对应的特征点不是环境中的同一个特征点，用这些特征点对求得的变换参数(,)在空间中是随机分布的；而对于配对过程中正确的特征点对，求得的变换参数(,)在理论上是相等的，即对应于空间中的同一点。但由于测量误差和计算误差的影响，这些变换参数不会完全相等，即对应于空间中的不是某一点，而是由许多点构成的密集点簇。显然，以点簇中点作为最优变换参数是比较合理的。在空间中对所有求得的变换参数(,)，采用适当的阈值进行聚类，选出元素个数最多的类，将此类的中心作为最优变换参数，从而完成两组点集的匹配。整个过程

13、主要分为特征点的提取和特征点集的匹配两个步骤，算法框图如2所示。特征点对之间两两成对匹配，得到解空间特征点对提取点集uki对解空间内所有的解元素进行聚类，求得最优旋转角R与最优位移T特征点对提取点集uki+1uki =uki+1进行点集变换uki+1=R x uki+1+T 图2 算法流程图技术路线：一、特征点对的提取（区域分割线段端点（特征点对）提取）：1、把激光测距仪一个扫描周期内采集到的离散点按照连续两点间的欧式距离大小是否超过某一阈值分成彼此不连通的区域。假设采集到N个点，那么首先认为是一个区域，即。按照下列公式计算连续两个点之间的距离 其中i=1,2,N判断Di和阈值的关系，如果Di

14、大于阈值（动态设定），则认为（Xi，Yi）是两个区域的分割点，以这个点为分割点将区域分成两部分，可以得到区域，。按照同样的原则对区域A2进行分割，得到区域A2,A3。依此类推，最后可以得到相互不连通的区域（A1,A2,AN）。判断每个区域内的数据点的个数，如果某个区域包含数据点的个数小于等于3个，那么该区域被视为噪声区域，舍弃这些噪声点。在每个区域Ai中，以区域Ai的第一个点Ps（Xs，Ys）和最后一个点Pe（Xe，Ye）作一条直线L，计算区域内其余各点到这条直线L的距离，假设在点Pm（Xm，Ym）处取得距离的最大值Dmax，如果距离最大值大于阈值Dthr，以点Pm为分割点将区域Ai分成两部分

15、，。然后对区域A和A采用同样的方法进行迭代处理，直到该区域内所有点到所在区域起点终点构成直线的距离的最大值不大于阈值Dthr，这样这个区域就被分为M个可以用一条线段线性表示的点集Li（i=1,2,M）。如图3所示。 图3 特征点提取效果图对A1,A2,AN进行上述操作，使得每个区域由若干个点集组成，每个点集里的所有点都依附于一条直线。则从每个点集提取第一个点和最后一个点（可优化提取），形成点对，代表线段的起点和终点。这些点对中的点就是多边形的端点或角点，即我们想得到的特征点。 二、特征点对匹配已经提取出了局部地图的所有特征点对，即，计算出各点对的欧式距离，即。将与上一次的局部地图（现已并入全局

16、地图）的所有特征点对计算出的欧式距离进行匹配。找出阈值范围内欧式距离近似相等的点对。计算出每个相匹配点对之间的变换旋转角Rk和变换位移Tk，（km,n），加入到三维向量解空间 (,)中。三、对解空间进行聚类 以中的第一个元素作为初始类和类的中心，类的个数采取动态设置阈值，动态设定的方式如下确定：如果一个元素到任何一个类的中心的距离都大于某一阈值，则将此元素构成一个新的类。最后找出所含元素个数最多的类，该类的中心，即为所求的最优变换参数。 技术难点：1、 准确提取局部地图的特征点是正确匹配的关键，但是受原始数据精度和阈值参数选取的影响，一些情况下也会出现线段提取不当或者分割太细的情况（如图4）。

17、 图4实际可以用三条线段来表示的区域被错误的分成了四条线段。因此可在当前基础上，将线段提取分为两个步骤完成。选按照原来的方法进行分割，然后利用最小二乘线段拟合算法，得到线段参数，然后计算任意相邻两条线段L1和L2之间的夹角和相邻两条线段端点的最小值。如果满足条件 且那么假设认为这两条线段是被错误分开的线段，应该为同一条线段，直接取前一条线段的起点和后一条线段的终点作为特征点对加入到特征点对集合当中。 2、 局部地图和全局地图需要比较多的相匹配的特征点对，这样才能提高匹配精度。然而在实际环境中，由于激光传感器扫描范围有限、离障碍物过近或位姿变化过大等情况，导致局部地图和全局地图中符合匹配条件的点

18、对过少。解决办法是通过大量的实验，确定一套符合该算法系统的阈值方案以及较合适的激光传感器的扫描频率、范围等。 六、进度安排（选题、自主设计实验、实验研究、数据处理、研制开发、撰写总结报告、项目鉴定、成果推广或论文发表等）内容时间段选 题2010年7月算法系统规划与设计2010年7月至2010年9月结合传感器参数进一步优化和完善算法结构2010年9月根据算法的描述设计数据结构与类2010年9月至2010年10月算法的程序实现及各模块的测试2010年11月至2011年4月对于算法实现上的进行速度优化2011年4月至2011年5月开展大量的实验及现场模拟2011年5月至2011年8月完善细节，发表论文2010年8月至2011年9月七、拟利用资源（开展研究工作所需要的实验室、创新竞赛基地、主要仪器设备、试剂、参考资料及其他工作条件等）实验室：西北工业大学舞蹈机器人基地 传感器： URG-04LX激光测距仪 测试平台： 救援机器人八、经费使用计划 经费支出项目名称具体支出内容金 额（千元）使用时间URG