《郭洪席的毕业成品.doc》由会员分享，可在线阅读，更多相关《郭洪席的毕业成品.doc（62页珍藏版）》请在金锄头文库上搜索。
1、辽宁科技大学本科生毕业论文 第V页基于改进蚁群算法的机器人路径规划摘 要路径规划技术是机器人导航中最重要的环节，同时也是自主式移动机器人技术的一个重要组成部分。目前使用的方法有遗传算法、神经网络、人工势场、计算几何法等。但以上方法在复杂环境下存在明显不足，特别是在包含大量不规则障碍物的情况下，算法或计算量过大或不能得到最优解。蚁群算法是一种较全面的启发优化算法，它不仅能够解决不同类型的优化问题，而且在求解大量问题时也能获得极佳的性能。在机器人路径规划领域不少学者已对此算法的应用做了大量的研究。本文是在基本蚁群算法的基础上，借鉴带精英策略的蚂蚁系统、基于最大最小蚂蚁系统等改进算法的思想，提出了一
2、种基于改进蚁群算法的机器人路径规划算法。与其它的蚁群算法比较本算法主要有以下几个方面的改进：引入精英蚂蚁策略，并对精英思想进行了创新运用；引入视觉探测功能，加强了蚂蚁的探测视野；运用路径的优化功能和优化结果的定时输出，提高了机器人行走路径的可用性和规划算法的实时性；改进了蚂蚁状态转移策略，增强了蚂蚁对目标的方向感；运用了死锁检测机制，并提出了相应的死锁解除策略。在论文后面，还用VC6.0开发了一个完备的算法仿真实验平台，以分析、验证所提算法。仿真实验结果表明了算法的有效性和可行性。 关键词：蚁群算法；精英策略；死锁检测；路径规划 THE RESERCH OF MOBILE ROBOT PATH
3、 PLANNING ALGORITHM BASD ON ANT COLONY ALGORITHMABSTRACTPath planning technology is not only the most important part in robot navigation but also an important component in autonomous mobile robotsTherefore, it is an important aspect of further researchThe methods currently used are genetic algorithm
4、s neural networks，artificial potential field and computational geometry and so onHowever the above method in a complex environment is obviously insufficient，especially in the circumstances of containing a large number of irregular obstacles when algorithms or excessive algorithm can not be solved in
5、 the optimal solutionAnt algorithm is a comprehensive optimization algorithm，which not only can solve different types of optimization problems，but also in solving the numerous problems also call obtain the extremely good performanceIn the field of robot path planning many scholars also have done a l
6、ot of research in application of the algorithmsThis article is based on ant colony system，profits from the Ant system with elitist strategy Rank based on Max-Min Ant System to improve Ant Algorithm thinking auto adaptive algorithm to improve Ant Algorithm thinking，then one kind of path planning algo
7、rithm based on the improvement ant colony system algorithm robot is proposedcompared with other ant colony algorithm，this algorithm mainly have several following aspects of the improvement：the introduction of the elite ant strategy and innovative use of the this elite linking；The introduction of vis
8、ual detection capability to enhanced the detection ants vision；uses path optimization features and optimization results of the regular output，improving the availability of walking robot path and of real-time planning algorithm；providing a new strategy for the transfer of state ants，then strengthened
9、 the ants sense of direction to the target；use of the deadlock detection mechanisms and proposed the corresponding relieving strategy of deadlock.In the end of paper. we also use VC6.0 to develop a comprehensive algorithm simulation platform for the demonstration of the algorithm、analysis、verificati
10、on and convergence of research，simulation results also fully demonstrates the feasibility and the effectiveness of the algorithm Keywords：ant algorithm；elitist strategy；deadlock detection；path planning 目 录1 绪论11.1 本课题研究的意义11.2 路径规划的评价标准11.3 路径规划算法分类21.4 路径规划算法的研究现状31.5 论文的主要研究内容和章节安排72 蚁群算法概述82.1 概述
11、82.2 基本蚁群算法原理82.3 基本蚁群系统模型92.4 几种改进的蚁群算法112.4.1 精英蚁群系统122.4.2 基于排序的蚂蚁系统122.4.3 蚁群系统132.4.4 最大最小蚂蚁系统162.4.5 最优最差蚂蚁系统202.4.6 其它改进蚁群算法212.5 蚁群算法求解问题的基本步骤222.6 机器人路径规划问题的蚁群算法求解232.7 小结243 基于改进蚁群算法的机器人路径规划253.1 环境的表示253.2 算法中相关问题的描述和定义283.3 蚁群算法的改进策略293.3.1 精英蚂蚁的引入293.3.2蚂蚁的视觉探测功能313.3.3最优路径的优化功能323.4 状态
12、转移策略333.5 躲避障碍实现353.6 死锁的检测和解除363.7 改进蚁群算法的原理和基本步骤373.7.1 算法基本原理373.7.2 算法基本步骤383.8 算法中部分参数的研究403.9 小结424 仿真实验及其实验结果的分析444.1 仿真实验系统设计444.2 仿真实验系统简介444.3 仿真实验结果分析464.3.1 仿真实验系统中参数的设置研究464.3.2 算法性能的比较研究514.4 小结545 结论与展望55参考文献56致谢57辽宁科技大学本科生毕业论文 第52页1 绪论1.1 本课题研究的意义 机器人是20世纪人类最伟大发明之一，伴随着社会和科学技术的迅速发展，机器
13、人的应用领域也不断扩大，在天空、地面、大洋海底，从工业拓广到农、林、牧、渔业等甚至进入寻常百姓家。 路径规划技术是机器人导航中最重要的环节，同时也是自主式移动机器人技术的一个重要组成部分，仍然是研究的一个重要方面，随着各种新方法和新技术的不断出现，对路径规划的研究有了更广阔的天地。下面以恩格尔伯格于1985年研制的“护士助手机器人为例做一下简单介绍。 “护士助手是自主式机器人，它主要可以完成以下各项任务：运输医疗器材和设备；为病人送饭；送病例、报表及信件：运送药品；运送试验品及试验结果：在医院内送邮件及包裹等。机器人中装有医院的建筑物地图，在确定目的地后机器人利用路径规划算法自主沿走廊行走，由
14、结构光视觉传感器及超声传感器探测突然出现的静止或运动物体。它的全方位触觉传感器保证机器人不与人和物相碰撞。 由以上可知机器人如何规划自己的行走路线，如何有效躲避障碍物，对整个机器人系统来说都是非常重要的。而对机器人路径规划算法的研究就是从全局环境的角度来考虑如何有效解决这两个问题。我国在智能移动机器人研究方面虽然已经取得了一定的成果，如地面自主导航车、水下自主机器人和飞行机器人等。但由于起步较晚，在研究和应用方面都落后于一些西方国家，而且有些方面还没有达到完全实用。因此，进行移动机器人路径规划算法的研究，仍然具有一定的理论意义和工程应用意义。 1.2 路径规划的评价标准 在路径规划研究成果中，
15、设计者可有多种技术选择，像机器人的其他方面一样，技术的选择取决于机器人运行的生态小环境。评估路径规划的标准包括1： (1)算法复杂度：算法是不是太复杂或者占用太多存储空间，以至于机器人不能执行或存储空间不够。 (2)地形表示的充分性：许多研究工作是基于室内是平地的环境。室外机器人可能工作在粗糙地形，有陡峭斜坡或者没有估计到的区域，例如滑溜沙地或泥浆。如果路径规划算法所产生的路径只能针对适于航行或不适于航行区域的两种极端情况，那么在复杂多变的环境中运行时，机器入将陷入困境。 (3)机器人平台物理限制表示的充分性：机器人有物理限制，最影响路径规划的限制在于机器人是否是完整的。注意到完整机器人能够原地转弯，故它们能在狭小地方转身。这时路径规划算法不必考虑机器人转动半径。同样机器人也可能不是圆的为了研究目的而制造的机器人通常是圆的，因此它们原地转弯时不会碰撞任何东西。非圆形机器人会引起更多的复杂性，为在狭窄大厅转身，它必须关注后面以确保它不会撞到任何东西。 (4)与反应层的兼容性：路径规划应为慎思式，然而在混合型结构中，反应层应负责实现该路径，因此需要有从路径规划器到反应层进行转换的技术。
