改进生成树算法的多机器人在线地图覆盖

《改进生成树算法的多机器人在线地图覆盖》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文改进生成树算法的多机器人在线地图覆盖作者姓名：陈泽涛学号：2013919309学科专业：控制工程研究方向：多机器人任务分配指导教师：戴学丰教授答辩日期：年月齐齐哈尔大学MasterdegreethesisImprovedspanningtreecoveringalgorithmformulti-robotmapcoverageonlineAuthor:ChenZetaoStudentid:2013919309Major:ControlEngineeringResearchdirection:Multi-robottaskallocatio

2、nTutor:DaiXuefengProfessorQiqiharUniversity学位论文独创性声明作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：改进生成树算法的多机器人在线地图覆盖作者签名：日期：年月日学位论文版权使用授权书本人完全了解学校有关学位

3、论文知识产权的规定，在校攻读学位期间论文工作的知识产权属于齐齐哈尔大学，允许论文被查阅和借阅。学校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。作者签名：日期：年月日导师签名：日期：年月日摘要本文主要研究的是多机器人在线地图覆盖问题。多机器人技术是机器人学发展的一个新的研究方向，使用多个机器人比单个机器人拥有更多优势。相比单个机器人的能力、可靠性、效率、鲁棒性等，协作的机器人表现得更加出色。地图覆盖对于移动机器人是一个重要的

4、任务。能够更有效地完成任务覆盖问题反应了机器人的移动、协作和感知之间的关系，是目前控制学科和移动机器人研究的前沿课题之一。覆盖问题的本质是个体或团队的机器人通过移动，感知范围并逐步覆盖整个地图。在很多情况下，覆盖必须在没有区域地图或没有地图的先验知识下完成。这样，机器人不能依赖工作区域的先验知识，必须通过一步一步构建移动轨迹，在它们移动过程中解决发现的障碍（或碰撞，在多机器人情况下），覆盖的过程每个机器人个体通过自身所能得到的信息决定其自身的运动。多机器人覆盖问题在机器人系统中是一个基本的方向，应用于很多不同领域。从人道主义使命，如矿业中跟军事行动中

5、的搜索和营救；到农业应用，像播种和收割；到家庭生活服务方面，如清洁机器人等等。本文在单机器人生成树（SpanningTreeCovering，STC）算法基础上做出改进，融入了市场拍卖算法，使机器人团体扩散地生成树，并沿机器人各自的生成树完成地图覆盖。讨论了为多机器人建立有效覆盖路径的问题，一个有效的多机器人覆盖算法应该为每个机器人规划好覆盖路径，这些路径联合构成覆盖地形，整个覆盖过程的时间最少，同时重复覆盖最少。最后通过仿真实验说明改进生成树算法的可行性与优势。为了达到更佳的实际效果，利用无障碍地图、规则障碍物地图以及非结构化地图三种不同地图模拟实

6、际地图环境。通过三种不同环境地图覆盖仿真结果验证改进后的STC（ImprovedSpanningTreeCovering，IMPSTC）算法能够使机器人团队在更少的时间和重复覆盖区域情况下完成在线覆盖地图任务。关键词：生成树；多机器人；覆盖；市场拍卖IAbstractThispaperdiscussestheproblemofmulti-robotmapcoverageonline.Multi-robottechnologyisanewresearchdirectioninroboticsdevelopment.Usingmultiplerobots

7、hasmoreadvantagesthanasinglerobot.Comparedtothecapability,reliability,efficiency,robustnessofsinglerobot,collaborativerobotsbehavebetter.Mapcoverageisanimportanttaskforthemobilerobot.Tocompletecoveringtaskmoreeffectivelyreflectstherelationshipbetweenmovement,coordinationandperc

8、eptionoftherobots,whichisoneoftheforefronttopicsofcont