基本信息
- 项目名称：
- 基于图形匹配技术的移动机器人二维环境地图实时构建方法的研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 本文提出了一种基于激光测距仪的移动机器人定位及环境地图构建的方法。通过图形块匹配、最小二乘拟合、聚类、线段优化等技术，对激光测距仪采集的数据进行处理，对机器人进行定位并形成一幅现场二维环境地图。 开发了仿真系统对算法进行验证，搭建模拟场地对算法进行实物验证，算法达到预期效果。 该算法对促进机器人的智能化与实际应用有很大意义。
- 详细介绍：
- 研究内容：移动机器人在未知环境下行进时，需要利用传感器感知周围环境并进行如路径规划、自主导航等智能行为。因此，机器人定位及环境地图的构建是移动机器人研究领域的重点。本文提出一种图形匹配算法对移动机器人定位，并在移动中不断拼合局部地图，最终形成一幅完整的二维现场环境全局地图。该算法的研究对促进移动机器人的智能化有重要意义，同时，环境地图的构建对移动机器人在救灾等实际应用中有重大价值。 创新点：传统的图形匹配算法只依赖线段的欧氏距离进行匹配，在实际应用中准确性和稳定性不高。本文提出了根据图形块进行匹配的方法，提高了图形匹配的准确度；利用拟合、 聚类等技术，提高了图形匹配的稳定性；利用在不同环境中动态改变阈值的方法，提高 了算法应用的灵活性；特别提出了最终全局地图的优化方法，使构建的地图更加真实反 映现场环境。 研究成果：本算法提出了新的研究角度和方法，注重应用性，并基于激光测距仪，开发了移动机器人二维环境地图实时绘制软件，并在实际应用中取得良好效果，对智能机器人的发展提供重要支持和保障。具有较大的研究价值与社会价值。
作品图片
作品专业信息
撰写目的和基本思路
- 环境地图的构建对机器人的智能行走、全局路径规划起到重要作用。本文旨在设计一个高效的定位建图算法，并将其应用于实践。实际环境往往是未知的，而且环境中也不存在标志物，要求移动机器人必须有感知周围环境信息的能力。因此，利用传感器采集环境数据并通过高效的算法处理是解决问题的关键。本文基于激光测距仪采集数据，并通过线段提取、拟合、图形块匹配、聚类、优化等技术解决上述问题。
科学性、先进性及独特之处
- 本算法的设计依据数理统计、计算机图形学、模式匹配、传感器技术等学科的相关理论，结合较多学科知识。 该算法提出了地图构建中的图形块匹配与动态阈值技术，比传统方法匹配更加准确、适用性更强。此外，运用了聚类、拟合、滤波等技术对算法进行优化。 图形块匹配技术，使定位信息更加准确；运用单一传感器减少系统误差；结合数学建模思想对所建地图作进一步优化，使地图更能反映实际环境。
应用价值和现实意义
- 本作品较好地解决了移动机器人的定位问题，对移动机器人的自主导航、地图构建和路径规划有很大的促进作用。 实时环境地图的构建意义重大，对于室内移动机器人而言，该地图能实时提供导航信息，实现机器人的定位、避障、走迷宫等功能，是移动机器人智能化的基础；对于救援、勘探类机器人来说，环境地图意义更为重大，不仅能为机器人提供全局路径规划信息，还能为工作人员提供现场环境信息，具有很大的应用价值。
学术论文摘要
- 提出了一种基于模式识别技术的点集数据特征提取、近似匹配算法。该算法与传统算法相比，由于使用了精度可调的图形块匹配技术与聚类处理技术，因此算法适应性更强，配合巧妙的数据结构设计和有效的算法优化，能使结果精度更高，匹配速度更快。结合上述匹配算法，本文给出了一种基于激光测距仪的移动机器人二维环境地图实时构建方法。该方法通过提取环境信息数据点中的关键点，根据环境情况选择合适的精度，并在两组关键点集中进行匹配，从而完成环境地图的构建。利用自行开发的环境仿真系统及模拟激光对算法进行了验证，实验结果表明，该算法能有效完成在不同室内环境下移动机器人环境地图的实时构建。
获奖情况
- 本作品获我校大学生课外学术科技作品竞赛银奖； 作品已投稿于国家级计算机类核心期刊《计算机应用》
鉴定结果
- 此算法曾应用于RoboCup机器人公开赛救援组比赛中，并获得好成绩。
参考文献
- 技术：模式匹配，动态阈值，聚类，最小二乘拟合，多元多次方程的动态规划等 【1】LUFENG，MILIOS E．Robot pose estimation in unknown environ-merits by matching 2D range sc¨s【J】//Proceedings of the IEEE Computer Vision and Pattern Recognition Conference(CVPR’94)． 【2】Dissanayake G Newman P，Clark S，et a1．A solution to the simultaneous localization andmap building(SLAM)problem．IEEE Transactions on Robotics and Automation 【3】Castellanos J A and Tardos J D．Mobile robot localization and map building：a multi-sensorfusion approach．Boston,MA：Kluwer Academic Publishers 【4】Gasos J，Rosetti A．Uncertainty representation for mobile robots：Perceptio，modeling and navigation in unknown environments[J]．Fuzzy Sets and Systems，1999，107(1)：1—24． 【5】罗荣华，洪炳镕．基于信息融合的同时定位与地图创建研究【J】．哈尔滨工业大学学报 【6】张辉，蔡向东，海丹，朱登科 NuBot救援机器人整体设计.机器人技术与应用,2010.7 【7】刘丽雯 基于激光传感器的移动机器人定位和地图构建研究，合肥工业大学， 2009.4 等等
同类课题研究水平概述
- 移动机器人定位及建图问题是国内外机器人领域研究的热点。当前定位方法大致可以归纳为两大类：推算导航、基于环境特征匹配。 推算导航技术有定位精度较高、成本低以及高采样率等特点，用于室内定位比较合适。然而，在不断的积分运算过程中误差会随着运动时间急剧增加，必须通过其他方式来对其进行补偿与校正。Lu提出了一种迭代的算法来建立两次测量数据间的对应关系进行匹配， 利用最近点规则和对应距离点规则，得到两次测量间机器人位置的变化。该算法的不足是匹配收敛速度慢且容易陷入局部最优解。Wei提出了直方图的概念，利用直方图统计的方法计算出机器人的位移及转角，但受分辨率选取的影响，匹配精度很难得到提高。卡尔曼滤波的方法通过比较当前距离测量结果和根据地图应该得到的距离值，基于误差矩阵得到最优估计结果。然而该方法的计算量大。马尔可夫定位是通过计算机器人位置栅格上概率分布来确定机器人位置的定位方法。 特征匹配定位是通过比较已有地图和当前局部地图种的特征来实现定位的方法。特征匹配算法是整个感知过程的核心，主要有两类：直接推理法和概率推理法。当前较为常用的方法有：基于线段欧氏距离的特征匹配，该算法简单容易实现，但算法适应性不高，在环境特征较为规律的时候算法效果不太理想；基于声纳信息与视觉信息相融合的SLAM，有效提高了定位与地图创建的准确度和鲁棒性，但是基于视觉信息要求较好环境，在缺乏光线的情况下算法并不适用；无线传感器网络环境下基于粒子滤波的移动机器人SLAM 算法，需提前在环境中设置大量的微型传感器节点，对于未知环境则有极大的考验。此外，基于“二次匹配”的概念，结合两种匹配方法，实现“粗匹配”与“精匹配”，此算法进一步提高了匹配精度，但算法效率较低。卡尔曼滤波估计、蒙特卡罗法等方法是概率推理方法的代表。其中基于扩展卡尔曼滤波的位姿跟踪是一种成熟的局部定位方法，但其在未知机器人初始位姿情况下无法进行全局定位。以马尔可夫定位方法为代表的位置占有网格方法虽然可以在初始位置未知或被“绑架”情况下实现全局定位，但其计算复杂。 在使用匹配的方法构建环境地图时，会出现线段“毛刺”现象。对于该问题，国内普遍采用分情况处理的方法来处理“毛刺”线段。这容易忽略某些特殊情况，且算法效率不高。
