移动机器人路径规划研究--优秀毕业论文.pdf
分类号ＵＤＣ密级１９３３５２１移动机器人路径规划研究作者姓名：指导教师：**灵教授东北大学系统科学研究所申请学位级别：硕士学科类别：理科学科专业名称：运筹学与控制论论文提交日期：论文答辩日期：２００８年７月珀学位授予日期：．答糊会主席：评阅人：豹＼口移１２目，盼雪蜂东北大学２００８年６月ＡＴｈｅｓｉｓｉｎＯｐｅｒａｔｉ伽ａｌＲｅｓｅａｒｃｈａｎｄＣｙｂｅｍｅｔｉｃｓＳｔｕｄｙｏｆＭｏｂｉｌｅＲｏｂｏｔＰａｔｈＰｌａｎｎｉｎｇＢｙＳｈｅｎｘｉａｏｗｅｉＳｕｐｅｉｓｏｒ：ＰｒｏｆｅｓｓｏｒＺｈａｎｇＱｉｎ百ｉｎｇＮｏｒｔｈｅａｓｔｅｒｎＵｎｉＶｅｒｓｉｔｙＪｕｎｅ２００８独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。．学位论文作者签名：签字日期：朋ｉ６．２／６学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。
本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年口学位论文作者签名：锄少吖午导师签名：彬灰灵签字．日期：’沙呵、１签字日期：即．７东北大学硕士学位论文摘要移动机器人路径规划研究机器人学是近４０多年来迅速发展起来的综合性学科，它综合了机械学、电子学、计算机科学、自动控制工程、人工智能、仿生学等多个学科的最新研究成果，代表了机电一体化的最高成就，是当今世界科学技术发展最活跃的领域之一。移动机器人最优路径规划技术是机器人研究领域中的一个重要分支。所谓机器人的最优路径规划问题，就是依据某个或某些优化准则（如工作代价最小、行走路线最短、行走时间最短等），在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。移动机器人路径规划技术是机器人应用中的一项重要技术，许多学者在这方面做了大量的工作，但也遗留了一些问题。本文针对移动机器人路径规划问题进行了广泛的研究，在对传统方法进行改进的同时，提出了新的思想和视角。具体工作如下：首先，对智能优化方法进行了研究，尤其对蚁群算法进行了认真的研究和讨论，针对蚁群算法中信息素和启发函数之间的矛盾进行了分析，并针对蚁群算法中对启发函数依赖过大的问题，改造了启发函数。
其次，本文认真分析了传统栅格法中所存在的安全性和最优性不能兼顾的固有缺陷，并首次提出了基于正六边形栅格的栅格法，有效地解决了这一问题。最后，本文对人工势场法进行了研究。该方法在移动机器人路径规划技术中应用广泛，但一些固有缺陷却难以克服，如在面对障碍物时会发生严重的抖振。本文改进了传统的人工势场法，有效地解决了该问题。关键词：移动机器人；路径规划；蚁群算法；栅格法；人工势场法．ＩＩＩ－东北大学硕士学位论文Ａｂｓｔ“ＩｃｔＳｔｕｄｙｏｆＭｏｂｉｌｅＲｏｂｏｔＰａｔｈＰｌａｎｎｉｎｇＡｂｓｔｒａｃｔＲｏｂｏｔｉｃｓｉｓ孤ｉｎｔｅｒｄｉｓｐｌｉＩｌｅｒ印ｉｄｌｙｄｅｖｅｌｏｐｅｄｉｎｔｈｅｓｅｆ．ｏｕｒｄｅｃａｄｅｓ，、ＶｈｉｃｈｉｓｂａＳｅｄｏｎｔｈｅｎｅｗｐｒｏｄｕｃｔｉｏｎｏｆＶ撕ｏｕＳｄｉｓｃｉｐｌｉｎｅｓ，Ｓｕｃｈ嬲Ｍｅｃｈａｎｉｃｓ，Ｅｌｅｃｔｒｏｌｌｉｃｓ，Ｃｙｂｅｍａｔｉｏｎ，Ａｎｉ６ｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅＢｉｏｌｌｉｃｓ．Ｒ．ｏｂｏｔｉｃｓｒｅｐｒｅｓｅｎｔｓｔ１１ｅｔｉｐｔｏｐａｃｈｉｅｖｅＩｎｅｎｔＭｅｃｈａＩｌｉｃｓ＆Ｅｌｅｃｔｒ０ＩｌｉｃｓａｌｌｄｉｓｏｎｅｏｆｔｈｅｍｏＳｔａｃｔｉＶｅＳｕｂｊｅｃｔｓｔｏｄａｙ’ｓｔｅｃｌｕｌｏｌｏｇ），．Ｒｏｂｏｔｐａｍｐ１锄１ｉｎｇａＩｌｉＩｌｌｐｏｒｔ趾ｔｏ凰ｅｔｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｒｏｂｏｔｉＣｓ．ｎｅｄｅｆｉＩｌｉｔｉｏｎｏｆｒｏｂｏｔｐａｍｐｌ卸Ｉｌｉｎｇｉｓｔｏｆｉｎｄａｐａｍ行ｏｍｍｅｓｔａｎｉｎｇｐｏｓｉｔｉｏｎｔ０ｔｈｅｔａｒｇｅｔｗｔｌｉｃｈｓａｔｉｓ母ｓｏｍｅｏｐ恤ｌｉｚａｔｉｏｎｒｕｌｅｓ，ｓｕｃｈ嬲ｌｏｗｅｓｔｃｏ璐１ｕＩＩｌｅ，Ｓｈｏｎｅｓｔｌｅｎｇｔｈ，ｓｈｏｒｔｅｓｔｔｉｍｅ．ＩｔｉｓａＩｌｉＩｎｐｏｎａＩｌｔｔｅｃｌｌｎｏｌｏｇ）ｒｏｆｔｈｅｒｏｂｏｔｉｃｓ印ｐｌｉｃａｔｉｏｎ．Ａ删肌ｅｂｅｒｏｆｓｃｈｏｌａｒｓａｒｅｃｏＩＩｌ】［１１ｉｔｔｅｄｔ０ｒｅｓｅａｒｃｈｉｎｍｉｓａｒｅａ，ｂｕｔｓｏｆ缸ｔｈｅｉｓｓｕｅｈ嬲ｒｅｍａｉｎｅｄｉｍｐｒｏｐｅｒｌｙｓｅｔｔｌｅｄ．ＩＩｌｔ１１ｉｓｔｌｌｅｓｉｓ，ａＩｌｉｎｔｅｎｓｉｖｅｓｔｕｄｙｈａＳｂｅｅｎｍａｄｅｔｏｔｈｉｓｉｓ吼ｌｅ趾ｄｔｌｌｅｍａｉｎｃｏ删ｂｕｔｉｏｎｉｓ硒ｆｏｌｌｏｗ：Ｆｉｒｓｔｌｙ，ＡＩ—ＢａＳｅｄＯｐｔｉｍｉｚａｔｉｏｎＭｅｔｈｏｄｉｓｓｔｕｄｉｅｄ，ｅｓｐｅｃｉａｌｌｙａｂｏｕｔｔｈｅＡｎｔＣｏｌｏｎｙ撕ｍｍｅｔｉｃ．Ｆｏｒｔ１１ｅｃｏｎｔｒａｄｉｃｔｉｏｎｂｅ时ｅｅｎｐｈｅｒｏｍｏｎｅａｎｄｈｅｕｒｉｓｔｉｃ丘ｍｃｔｉｏｎｉｎｔｈｅＡｎｔＣｏｌｏｎｙ撕ｔ１１１ｎｅｔｉｃ，ｍｉｓｐ印ｅｒｒｅｂｕｉｌｄｓｔｌｌｅｈｅ谢ｓｔｉｃ鼬ｌｃｔｉｏｎ．ＳｅｃｏＩｌｄｌｙ，ｍｉｓｐａｐｅｒｐｏｉｎｔｏｕｔ‘ｔｌｌｅｉ１１ｔｒｉｎｓｉｃｄｉｓｆｉｇｕｒｅｍｅｎｔｉＩｌｔｌｌｅｃｏｒｅｍｉｏｒｌａｌ（ｈｉｄｓｍ砒ｏｄ．ＩｌｌｃｏｎＶｅｎｔｉｏＩ脚．Ｇｒｉｄｓｍｅｍｏｄ，ｔｈｅｓｅｃｕｒｉｔ），ａ１１ｄｏｐｔｉｍｉｚａｔｉｏｎｃａｎｎｏｔｂｅｅ１１ＳｕｒｅｄｉｎｔｈｅｓａｍｅｔｉｍｅｉＩｌａ１１ｙａｌｇｏｒｉｔｈｍ．ＦｏｒｔＩｌｉｓ，ｌｉｓｐａｐｅｒｐｕｔｓｆｏ确，ａｒｄａｎｅｗｍｅｔｌｌｏｄ，ｕＳｉｎｇｔ１１ｅｈｅｘａｇｏｎｐｌｏｔｔｌｌｅｇｒｉｄｓ．Ｌ嬲ｔｌｙ，ｃｏｎｖｅｎｔｉｏｎａｌ枷ｆｉｃｉａｌｐｏｔｅｎｔｉａｌｆｉｅｌｄｍｅｔｌｌｏｄｉｓ洲ｉｅｄ．ＩｔｉｓｏｎｅｏｆｍｅｍｏＳｔｅ圩ｅｃｔｉＶｅｍｅｔｌｌｏｄｓｒｏｂｏｔｐａｔｌｌｐｌａＩｌ曲１９ｔｅｃｌｌｌｌｏｌｏｇ）ｒ，ｂｕｔａｌｓｏｅｘｉｓｔｓｏｍｅｉ１１．晡ＩｌＳｉｃｄｉｓａｄＶａＩｌｔａｇｅ．Ｆ０ｒｅＸａｎｌｐｌｅ，ｔｈｅ蚋ｊｅｃｔｏ巧晰ｌｌｓｅＶｅｒｅｌｙｚｉｇｚａｇｗｈｅｎｆａｃｉｎｇａｎｏｂｓｔａｃｌｅ．Ｓｏｍｅｅ丘．ｅｃｔｕａｌｉｍｐｒｏＶｅＩｎｅｎｔｓｂｒｏｕｇｈｔｆｏｒｗａｒｄｉｎｔｌｌｉｓｐａｐｅｒ．Ｋｅｙｗｏｒｄｓ：Ｍｏｂｉｌｅｒｏｂｏｔ；Ｐａ＿ｔｌｌｐｌ锄Ｉｌｉｎｇ；ＡｎｔＣｏｌｏｎｙａｌｇｏｒｉｔｈｍ；Ｇｒｉｄｓｍｅｔｌｌｏｄ；Ａｒｔｉｆｉｃｉａｌ ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄｍｅｔｌｌｏｄ 东北大学硕士学位论目录 要……………………………………：…………………………………ＩＩＩＡＢＳＴＲＡＣＴ……………………………………………………………………………………．Ｖ 第１章绪论………………＂………………．．＝．．…………………………１ １．１引言……………………………………………………………………………………………………………。
１ １．２智能优化算法介绍…………………………………………………………………．３ １．２．１遗传算法…………………………………………………………………．．．…３ １．２．２模拟退化算法…………………………………………………………………４ １．２．３蚁群算法………………………………………………………………………５ １．２．４禁忌搜索………。．．．…………………………………………………………．．５ １．３移动机器人路径规划方法概述……………………………………………………．６ １．３．１全局路径规划方法．．．．……………………．．：…………………………………６ １－３．２局部路径规划方法……………………………………………………………７ １．３．３混合方法………………………………………………………………………。８ １．４论文组织结构…………………………………………………………………………．９ 第２章蚁群算法在路径规划中的应用……………………………“．１１ ２．１蚁群算法的基本原理…………………………………．．ｊ……………………………１ｌ ２．１．１蚁群行为的描述………………………………………………………………。
１１ ２．１．２蚁群算法的机制原理……………………………………………………………１２ ２．２蚁群算法在移动机器人路径规划中的应用…………………………………………１２ ２．２．１蚁群算法在移动机器人路径规划中的数学模型…………………………。１２ ２．２．２蚁群算法在移动机器人路径规划中的具体实现…………………………．１４ ２．３参数确定仿真结果…………………………………………………………………………１６ ．ＶＩＩ． 大学硕士学位论 目录 ２．３．１算法分析改进与参数确定…………………………………………………。１６ ２．３．２仿真实例……………………………………………………………………．１７ ２．４本章小结……………………………………………………………………………１９ 第３章正六边形栅格划分在移动机器人路径规划中的应用……２１ ３．１传统栅格法的缺陷分析……………………………………………………………２ｌ ３．２正六边形桐格的提出与应用………………………………………………………２２ ３．３正六边形棚格的编码分析与其在路径规划中的应用……………………………２４ ３．４本章小结……………………………………………………………………………２６ 第４章基于速度保持法的人工势场法………………………………２７ ４．１传统人工势场法的数学描述和固有缺陷分析……………………………………２７ ４．２人工势场法的改进………．：………………………………………………………．２９ ４．３基于速度保持法的人工势场法的基本实现………………………………………．３１ ４．４仿真结果与结果分析………………………………………………………………３２ 屯５本章小结………………………………………………………………………………．３５ 第５章总结与展望……………………………………………………３７ 参考文献……………………………………………………………………３９ 致谢……………………………………………………………………………：…………．４５ 东北大学硕士学位论文第１章绪论 第１章绪论 １．１引言 机器入学是人工智能研究的一个重要分支，是近４０多年来迅速发展起来的综合性 学科，它综合了机械学、电子学、计算机科学、自动控制工程、人工智能、仿生学等多 个学科的最新研究成果，代表了机电一体化的最高成就，是当今世界科学技术发展最活 跃的领域之一。
机器人的研究、制造和应用，正受到许多国家的广泛重视，是一个国家 科技水平和经济实力的象征。在机器人４０多年的发展过程中，其功能已经从进行简单 的操作发展到能承担多种任务；工作环境也从固定的工厂或车间转移到户外，从陆地延 伸到海洋、天空；服务对象也从机械装置发展到家庭、医院和娱乐场所等。应用范围遍 及航空航天、水下作业、危险和极限作业环境（如核工厂、火灾、地震现场等）、工农 业生产、日常生活、福利、直至娱乐等诸多场所【蚴。 关于机器人如何分类，国际上没有制定统一的标准。若按移动性可将其分为固定机 器人和移动机器人。固定机器人固定在底座上，整个机器人只能移动它的各个关节；移
