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

西北工业大学2010年大学生创新性实验计划项目申请书项目名称移动机器人环境地图实时构建算法系统所在学院/基地舞蹈机器人基地申请人严家祺罗国佳秦博奇詹东昀导师姓名黄英亮联系电话[phone]E-mail:[e-mail]填表日期2010年9月13日1西北工业大学教务处制表项目名称移动机器人环境地图实时构建算法系统起止时间2010年9月至2011年9月申请经费20000申请人或申请团队学号姓名年级所在学院、专业联系电话E-mail2007301716严家祺07级电子信息学院电子信息工程[e-mail]2008302577罗国佳08级计算机学院计算机科学与技术[e-mail]2008302578秦博奇08级计算机学院计算机科学与技术[e-mail]2008302604詹东昀08级计算机学院计算机科学与技术[e-mail]导师姓名黄英亮学院机电学院职务/职称高级讲师[e-mail]电话131521606552一、申请立项依据（包括项目背景、项目来源、技术依据、前期已有的研究基础，自身具备的知识条件、自己的兴趣爱好、特长等）项目背景、来源：现代社会当中，火灾、爆炸、坍塌等事故多发，在救援过程中因灾难现场情况不清，意外坍塌事故等导致救援人员遇难的惨剧时有发生。为避免此类事故，应用救援机器人首先进入现场及时探知险情和受困人员的位置和状况，有着极大的应用意义。因此，在每年的Robocup国际机器人赛事中，Robocup救援组是最热门项目之一，其主要目的就是促进大规模灾难情况下使用机器人进行人员搜救任务的研究。灾难现场实时环境地图的创建是移动救援机器人领域中的一个基本而重要的问题。环境地图被广泛地应用在移动机器人的导航系统中，在移动机器人导航定位和全局路径规划中起到重要作用。要实现移动机器人的自主导航，最重要的是通过定位来获知机器人在环境中的准确位姿。根据先验地图进行的移动机器人定位和自主导航技术得到了广泛的研究，并取得很好的应用效果。但是实际环境往往是未知的，不能提供诸如环境中障碍物大小、形状、位置等先验信息，而且实际突发灾难事件环境中也不存在路径、灯塔等人为设定的标志物，这给移动机器人的自主导航带来了很大的问题。因此，移动机器人在未知环境中同时精确定位和地图创建（SLAMsimultaneouslocalizationandmapping）成为移动机器人研究领域的一个亟待解决的问题。自然而然，地图的构建质量也就成为每年Robocup救援组比赛项目的一个重要评分依据。技术依据：本项目采用几何特征地图来反映机器人所处外部环境，如灾难现场中的墙壁、较大的家具等。几何特征地图是一种紧凑的地图表示方法，通过传感器感知环境数据，从中提取抽象几何特征如线段、圆、弧线等来表示环境信息。对于大多数环境特别是室内环境利用几何特征描述的地图都能精确的反映环境信息，而且几何特征地图存储信息量小，方便应用于位姿估计和目标识别。前期已有的研究基础：本项目拟通过激光测距仪扫描采集外部环境数据，并设一套高效的算法处理所得数据来实时创建并更新现场环境地图。舞蹈机器人基地目前已具备救援机器人的机械和电子部件，曾经采取过的构建地图的方法主要是依靠超声波传感器、电子罗盘、加速度传感器等多传感器的信息融合，来构建几何3特征地图。但由于这个方法结构复杂，受多个传感器的影响，系统的精度一般不高，而且系统抗电磁干扰能力太差，往往得不出理想的地图构建效果。而本项目采取的方法只需要一个激光传感器采取数据，通过算法处理优化，完全可以替代以上多传感器的融合，大大简化了系统的复杂性，提高了系统的可靠性与稳定性，减小了系统误差。自身具备的知识条件：本项目的项目组人员都是西北工业大学舞蹈机器人基地的成员，在过去的实践中，对传感器的操作与传感器的应用都有一定的了解。本项目的人员由电子信息专业和计算机专业的学生组成，首先可以解决底层硬件通信的问题，而上层数据处理算法则由计算机专业的成员完成，我们在计算方法、计算机图形学、算法设计与分析、信号处理等学科上有扎实的基础，因此可以胜任信息采取与算法设计的工作。自己的兴趣爱好、特长：本项目组的人员都是舞蹈机器人基地里的核心人员，动手能力强，善于思考，对MFC绘图、算法的设计、传感器网络通信等都有过经验。4二、立项研究的目的和意义环境地图是移动机器人自主完成任务的首要条件，未知环境中移动机器人同时定位和地图创建对于智能机器人技术的发展有着重要的意义。本项目预设计并实现一个简单而有效的系统，该系统能快速、准确地构建出现场环境的几何特征地图。由于只采用激光测距仪采集数据，相比多传感器融合系统而言，大大降低了多传感器导致的系统误差，且激光测距仪采集数据精度高，抗外部干扰能力强，更适合于灾难现场的复杂环境。后期数据处理及地图生成采用软件实现，相对硬件实现更易于改进和优化。几何特征地图意义重大：第一：对灾难现场实现地图重现，可以有助于救援人员开展救援工作，提前预知现场环境，避免再次意外对救援人员的伤害。也有利于及时调度救援人员，最大限度的救出受困人员，具有很大的社会意义；第二：环境地图是智能移动机器人自主行走、自动避障、自主识别救援目标的技术基础和重要保障，促进了智能移动机器人的发展。三、项目计划实施研究内容第一：对激光传感器的特性以及参数的研究，保证采集到的环境数据的精确度和数据传输的准确性，深入了解激光传感器的原理，还可以利用其特性简化日后数据处理的工作。第二：对算法中涉及到的激光扫描频率、扫描范围、动态阈值等一些参数的设计作预估，建立数学模型分析，得出一个精度较高的模型。第三：结合传感器的实际数据，进一步验证模型的精确程序，根据实际数据对模型进行优化，选择最适合的算法参数。第四：搭建灾难现场摸拟环境，对系统进行大量的试验，不断改进和优化算法方案。第五：编写高效的作画程序，能快速、精确绘出现场的几何特征地图。5四、国内外研究概况扫描匹配方法是环境地图创建的一种有效的方法，可分为迭代匹配算法和非迭代匹配算法。迭代最近点（ICP）算法是一种典型的迭代匹配算法。ICP算法通过在迭代过程中不断降低配准误差，获得两组点集间相对位姿变化。该算法的缺点是匹配收敛速度慢而且容易陷入局部最优解。此后，出现了许多基于ICP算法的改进算法。直方图匹配算法是典型的非迭代匹配算法，该算法的最大优点是算法容易实现，匹配速度快，但是受构建特征直方图时分辨率选取的影响，匹配精度很难得到有效的提高。总体而言，迭代匹配算法匹配精度高，但匹配收敛速度较慢，很难完成实时条件下环境地图的创建；非迭代匹配算法的匹配速度优于迭代匹配算法，但是匹配精度不高。五、研究方法、技术路线及研究中面临的技术难点和拟采取的解决办法本项目利用激光测距仪测得环境数据，从中提取出特征点对，采用非迭代的方式，在误差函数的解空间里采用聚类的方法完成点对的匹配，进而完成环境地图的创建。1、特征点对的提取：激光传感器在i时刻扫描得到描述环境信息的点集{uki}，对{uki}中的数据进行特征点对的提取，特征点对是描述现场环境的多变形的线段的起点和终点，如图1所示。(a)激光数据点集(b)特征点对集图1提取特征信息效果2、特征点对集的匹配：特征点对集的匹配基于以下两个假设：一是环境中的特征点之间具有拓扑结构稳定性，即两个特征点之间的欧式距离在相邻两组数据中是相等的，在静态环境中这一假设一般能够满足；二是在二维平面内，相邻两组特征点集之间的变换可以视为刚体变换，可由两组特征点对集中的对应匹配点对之间的变换来表示，这样可以提高算法效率，降低计算复杂度。匹配算法可以概括为匹配、计算、聚类三个步骤。I．匹配是指在两组特征点对集中选出所有欧式距离相近的对应特征点对，构成对应特征点对集合。II．计算是针对每对对应特征点对，求得相应的旋转角Ri和位移Ti，加入到三维向量解空间6(,x,y)中。III．一般情况下，对于配对过程中错误的特征点对，即相对应的特征点不是环境中的同一个特征点，用这些特征点对求得的变换参数(,x,y)在空间中是随机分布的；而对于配对过程中正确的特征点对，求得的变换参数(,x,y)在理论上是相等的，即对应于空间中的同一点。但由于测量误差和计算误差的影响，这些变换参数不会完全相等，即对应于空间中的不是某一点，而是由许多点构成的密集点簇。显然，以点簇中点作为最优变换参数是比较合理的。在空间中对所有求得的变换参数(,x,y)，采用适当的阈值进行聚类，选出元素个数最多的类，将此类的中心作为最优变换参数，从而完成两组点集的匹配。整个过程主要分为特征点的提取和特征点集的匹配两个步骤，算法框图如2所示。图2算法流程图技术路线：一、特征点对的提取（区域分割——线段端点（特征点对）提取）：1、把激光测距仪一个扫描周期内采集到的离散点按照连续两点间的欧式距离大小是否超过某一阈值分成彼此不连通的区域。①假设采集到N个点，那么首先认为是一个区域，即10011((,),(,),(,))NNAXYXYXY。按照下列公式计算连续两个点之间的距离1221()()iiiiiDXXYY其中i=1,2,…N②判断Di和阈值的关系，如果Di大于阈值（动态设定），则认为（Xi，Yi）是两个区域的分割点，以这个点为分割点将区域分成两部分，可以得到区域点集{uki}特征点对提取点集{uki+1}特征点对提取特征点对之间两两成对匹配，得到解空间对解空间内所有的解元素进行聚类，求得最优旋转角R与最优位移T进行点集变换uk’i+1=Rxuki+1+Tuki=uk’i+1710011((,),(,),(,))iiAXYXYXY，21122((,),(,),(,))iiiiNNAXYXYXY。按照同样的原则对区域A2进行分割，得到区域A2,A3。依此类推，最后可以得到相互不连通的区域（A1,A2,…,AN）。③判断每个区域内的数据点的个数，如果某个区域包含数据点的个数小于等于3个，那么该区域被视为噪声区域，舍弃这些噪声点。④在每个区域Ai中，以区域Ai的第一个点Ps（Xs，Ys）和最后一个点Pe（Xe，Ye）作一条直线L，计算区域内其余各点到这条直线L的距离，假设在点Pm（Xm，Ym）处取得距离的最大值Dmax，如果距离最大值大于阈值Dthr，以点Pm为分割点将区域Ai分成两部分，'1(,,...,)issmAPPP，''1(,,...,)immeAPPP。然后对区域A’和A’’采用同样的方法进行迭代处理，直到该区域内所有点到所在区域起点终点构成直线的距离的最大值不大于阈值Dthr，这样这个区域就被分为M个可以用一条线段线性表示的点集Li（i=1,2,…,M）。如图3所示。图3特征点提取效果图⑤对A1,A2,…,AN进行上述操作，使得每个区域由若干个点集组成，每个点集里的所有点都依附于一条直线。则从每个点集提取第一个点和最后一个点（可优化提取），形成点对，代表线段的起点和终点。这些点对中的点就是多边形的端点或角点，即我们想得到的特征点。二、特征点对匹配已经提取出了局部地图的所有特征点对，即1122{(,),(,),(,)}iiiiiiisesemsmeUuuuuuu，计算8出各点对的欧式距离，即12{,,...,}iiiimDuuu。将iD与上一次的局部地图（现已并入全局地图）的所有特征点对11111111122{(,),(,),(,)}iiiiiiisesensneUuuuuuu计算出的欧式距离12{,,...,}iiiinDuuu进行匹配。找出阈值范围内欧式距离近似相等的点对。计算出每个相匹配点对之间的变换旋转角Rk和变换位移Tk，（km,n），加入到三维向量解空间(,x,y)中。三、对解空间进行聚类以中的第一个元素作为初始类和类的中心，类的个数采取动态设置阈值，动态