1、辽宁科技大学本科生毕业论文 第 I 页基于改进蚁群算法的机器人路径规划摘 要路径规划技术是机器人导航中最重要的环节，同时也是自主式移动机器人技术的一个重要组成部分。目前使用的方法有遗传算法、神经网络、人工势场、计算几何法等。但以上方法在复杂环境下存在明显不足，特别是在包含大量不规则障碍物的情况下，算法或计算量过大或不能得到最优解。蚁群算法是一种较全面的启发优化算法，它不仅能够解决不同类型的优化问题，而且在求解大量问题时也能获得极佳的性能。在机器人路径规划领域不少学者已对此算法的应用做了大量的研究。本文是在基本蚁群算法的基础上，借鉴带精英策略的蚂蚁系统、基于最大最小蚂蚁系统等改进算法的思想，提出
2、了一种基于改进蚁群算法的机器人路径规划算法。与其它的蚁群算法比较本算法主要有以下几个方面的改进：引入精英蚂蚁策略，并对精英思想进行了创新运用；引入视觉探测功能，加强了蚂蚁的探测视野；运用路径的优化功能和优化结果的定时输出，提高了机器人行走路径的可用性和规划算法的实时性；改进了蚂蚁状态转移策略，增强了蚂蚁对目标的方向感；运用了死锁检测机制，并提出了相应的死锁解除策略。在论文后面，还用 VC6.0 开发了一个完备的算法仿真实验平台，以分析、验证所提算法。仿真实验结果表明了算法的有效性和可行性。 关键词：蚁群算法；精英策略；死锁检测；路径规划 辽宁科技大学本科生毕业论文 第 II 页THE RESE
3、RCH OF MOBILE ROBOT PATH 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 us
4、ed are genetic algorithms 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 algori
5、thm can not be solved in 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 sch
6、olars also have done a lot 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 ki
7、nd of path planning algorithm 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
8、；The introduction of visual 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 stat
9、e ants，then strengthened the ants sense of direction to the target；use of the deadlock detection mechanisms and proposed the corresponding relieving strategy of deadlock.In the 辽宁科技大学本科生毕业论文 第 III 页end of paper. we also use VC6.0 to develop a comprehensive algorithm simulation platform for the demon
10、stration of the algorithm、analysis、verification and convergence of research，simulation results also fully demonstrates the feasibility and the effectiveness of the algorithmKeywords：ant algorithm；elitist strategy；deadlock detection ；path planning 辽宁科技大学本科生毕业论文 第 IV 页目 录1 绪论 .11.1 本课题研究的意义 .11.2 路径规划
11、的评价标准 .11.3 路径规划算法分类 .21.4 路径规划算法的研究现状 .31.5 论文的主要研究内容和章节安排 .72 蚁群算法概述 .82.1 概述 .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 基于改进蚁群算法的机器
12、人路径规划 .253.1 环境的表示 .253.2 算法中相关问题的描述和定义 .283.3 蚁群算法的改进策略 .293.3.1 精英蚂蚁的引入 .29辽宁科技大学本科生毕业论文 第 V 页3.3.2 蚂蚁的视觉探测功能 .313.3.3 最优路径的优化功能 .323.4 状态转移策略 .333.5 躲避障碍实现 .353.6 死锁的检测和解除 .363.7 改进蚁群算法的原理和基本步骤 .373.7.1 算法基本原理 .373.7.2 算法基本步骤 .383.8 算法中部分参数的研究 .403.9 小结 .424 仿真实验及其实验结果的分析 .444.1 仿真实验系统设计 .444.2 仿
13、真实验系统简介 .444.3 仿真实验结果分析 .464.3.1 仿真实验系统中参数的设置研究 .464.3.2 算法性能的比较研究 .514.4 小结 .545 结论与展望 .55参考文献 .56致谢 .57辽宁科技大学本科生毕业论文 第 1 页1 绪论1.1 本课题研究的意义 机器人是 20 世纪人类最伟大发明之一，伴随着社会和科学技术的迅速发展，机器人的应用领域也不断扩大，在天空、地面、大洋海底，从工业拓广到农、林、牧、渔业等甚至进入寻常百姓家。 路径规划技术是机器人导航中最重要的环节，同时也是自主式移动机器人技术的一个重要组成部分，仍然是研究的一个重要方面，随着各种新方法和新技术的不断
14、出现，对路径规划的研究有了更广阔的天地。下面以恩格尔伯格于 1985年研制的“护士助手“机器人为例做一下简单介绍。 “护士助手“是自主式机器人，它主要可以完成以下各项任务：运输医疗器材和设备；为病人送饭；送病例、报表及信件：运送药品；运送试验品及试验结果：在医院内送邮件及包裹等。机器人中装有医院的建筑物地图，在确定目的地后机器人利用路径规划算法自主沿走廊行走，由结构光视觉传感器及超声传感器探测突然出现的静止或运动物体。它的全方位触觉传感器保证机器人不与人和物相碰撞。 由以上可知机器人如何规划自己的行走路线，如何有效躲避障碍物，对整个机器人系统来说都是非常重要的。而对机器人路径规划算法的研究就是
15、从全局环境的角度来考虑如何有效解决这两个问题。我国在智能移动机器人研究方面虽然已经取得了一定的成果，如地面自主导航车、水下自主机器人和飞行机器人等。但由于起步较晚，在研究和应用方面都落后于一些西方国家，而且有些方面还没有达到完全实用。因此，进行移动机器人路径规划算法的研究，仍然具有一定的理论意义和工程应用意义。 1.2 路径规划的评价标准 在路径规划研究成果中，设计者可有多种技术选择，像机器人的其他方面一样，技术的选择取决于机器人运行的生态小环境。评估路径规划的标准包括 1： (1)算法复杂度：算法是不是太复杂或者占用太多存储空间，以至于机器人不能执行或存储空间不够。 辽宁科技大学本科生毕业论
16、文 第 2 页(2)地形表示的充分性：许多研究工作是基于室内是平地的环境。室外机器人可能工作在粗糙地形，有陡峭斜坡或者没有估计到的区域，例如滑溜沙地或泥浆。如果路径规划算法所产生的路径只能针对适于航行或不适于航行区域的两种极端情况，那么在复杂多变的环境中运行时，机器入将陷入困境。 (3)机器人平台物理限制表示的充分性：机器人有物理限制，最影响路径规划的限制在于机器人是否是完整的。注意到完整机器人能够原地转弯，故它们能在狭小地方转身。这时路径规划算法不必考虑机器人转动半径。同样机器人也可能不是圆的为了研究目的而制造的机器人通常是圆的，因此它们原地转弯时不会碰撞任何东西。非圆形机器人会引起更多的复
17、杂性，为在狭窄大厅转身，它必须关注后面以确保它不会撞到任何东西。 (4)与反应层的兼容性：路径规划应为慎思式，然而在混合型结构中，反应层应负责实现该路径，因此需要有从路径规划器到反应层进行转换的技术。 (5)能支持地图的修正和重新规划：路径规划需要一个先验地图，但这张地图可能被证明是严重错误的。因此机器人可能根据一幅地图出发，然后发现地图的错误，通过更新地图实现重新规划。显然允许修取已有规划结果比废弃已有规划并从头开始计算更易被人接受。 1.3 路径规划算法分类 所谓路径规划是指移动机器人在有障碍的环境中，寻找一条从起点到终点的路径、这条路径不仅要使机器人躲避障碍，而且要在一定指标下如距离、时
18、间、能量等尽可能的优化。 根据对环境信息的掌握程度不同，路径规划可分为全局路径规划和局部路径规划。其中，全局路径规划环境信息完全己知，包括障碍物的位置及其几何性质；全局规划方法包括环境建模和路径搜索两个子问题，一般情况下先对环境信息进行建模，然后采用某种搜索方法搜索最优路径；全局规划是一种事前规划，因此对机器人系统的实时计算能力要求不高，规划结果是全局的、较优的，但是对环境模型的错误及噪声鲁棒性差。局部路径规划，环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以获取障碍物的位置和几何性质等信息，这种规划需要搜集环境数据，并且对该环境模型的动态更新能够随时进行校正；局部规
19、划方法将对环境的辽宁科技大学本科生毕业论文 第 3 页建模与搜索融为一体，要求机器人系统具有高速的信息处理能力和计算能力，对环境误差和噪声有较高的鲁棒性，能对规划结果进行实时反馈和校正，但是由于缺乏全局环境信息，所以规划结果有可能不是最优的，甚至可能找不到正确路径或完整路径本文主要研究基于蚁群算法的全局规划算法。 1.4 路径规划算法的研究现状 1 自由空间法 自由空间法采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划，此方法比较灵活，即使起始点和目标点改变，也不必重构连通图，但是算法的复杂程度与障碍物的多少成正比，且不能保证
20、任何情况下都能获得最短路径。因而该方法仅适用于路径精度要求不高，机器人速度不快的场合。自由空间法用于机器人路径规划可以分为两个步骤。(1)寻空间问题。在指定的环境中，确定机器人的安全位置，使它不与已有的其他物体相碰撞。将机器人简化为一个点，同时相应地“ 膨胀” 环境中的障碍物体，从而形成另外一个空间障碍区。这样，通过构造一个虚拟数据结构，将运动物体和障碍物的几何约束关系转化到另外一个虚拟数据结构空间，从而简化问题的求解。 (2)寻路径问题。在指定的环境中，确定机器人从初始位置移动到目标位置的安全路径，使其在移动过程中不与任何障碍物发生碰撞。经过前面的空间变化，将问题进一步形式化为“ 可见“图的
21、搜索问题。搜索从起始位置到目标位置的最短路径就可以得到机器人的最短安全路径，进而确定具体的系统解决方案。 2 可视图法(Visibility Graph Method)可视图法通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。即在一个无向图中，将移动机器人的起始点与终止点以及移动机器人运动环境中各障碍物的顶点表征为点的形式，连接这些点使某点与其周围的某可视点相连，即要求机器人和障碍物各项点之间、目标点和障碍物各顶点以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是可视的。因此，移动机器人的有效路径就是这样的一些点之间与障碍物不相交的相互连接的线段。搜索最优路径的问题就转化为经
22、过这些可视直线从起始点到目标点的最短距离问题。可视图法将机器人、目标点和多边形障碍辽宁科技大学本科生毕业论文 第 4 页物的各顶点进行组合连接，连接的直线视为弧，使用这种方法缺乏灵活性，一般需要机器人停止在障碍前搜集传感器数据，并且受传感器精度影响较大。 3 栅格法(Grids Method)将机器人工作环境分解成一系列具有二值信息的网格单元，多采用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密集环境下
23、发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境下发现路径能力强，但环境信息存储量大，规划时间长。 4 人工势场法 该方法是由Khatib提出的虚拟力法。其基本思想是把移动机器人在环境中的运动视为一种在抽象的人工受力场中的运动，即在环境中建立人工势场的负梯度方向指向系统的运动控制方向。目标点对移动机器人产生引力，障碍物对移动机器人产生斥力。其结果是使移动机器人沿“势峰“间的“势谷”前进，最后求出合力来控制移动机器人的运动。这类方法的突出的优点是系统的路径生成与控制，直接与环境实现了闭环，从而大大加强了系统的适应性与避障性能。但是，人工势场法也存在若干缺陷如在陷阱区域容易陷入局部最小，
24、在相近的障碍物之间不能发现路径等。 5 模糊逻辑算法 模糊逻辑算法是基于实时传感信息的一种在线规划方法。模糊有向图是引入节点发生故障概率的一种符号有向图。节点分别表示系统的各个部件，分支及其方向表示部件因果联系及作用方向。节点可以用正号、零和负号来分别表示相对正常技术状况的正偏移、无偏移和负偏移：分支可以用正号、零和负号来表示作用方向。Hartmust Stmman等提出一种未知环境下的高级机器入模糊导航方法，由八个不同的超声传感器来提供环境信息，然后利用基于模糊控制的导航器计算这些信息，规划机器人路径 6 神经网络方法 神经网络方法是一种仿效生物神经系统的信息处理方法。它是一个高度并行的分布
25、式系统，处理速度高且不依赖于系统精确的数学模型，还具有自适应和自学习的能力一个神经网络包括以各种方式联接的多层处理单元神经网络对输入的数据进行非线性变换，从而完成了聚类分析技术所进行的从数据到属性的分类。目前神经网络辽宁科技大学本科生毕业论文 第 5 页的类型很多，大多数的神经网络都用于增强移动机器人避障能力与路径规划上，通常采用的是三层感知器模型和算法，禹建丽等提出了一种基于神经网络的机器人路径规划算法，研究了障碍物形状和位置己知情况下的机器人路径规划算法，其能量函数的定义利用了神经网络结构，根据路径点位于障碍物内外的不同位置选取不同的动态运动方程，规划出的路径达到了折线形的最短无碰路径，计
26、算简单，收敛速度快。陈宗海等提出了一种在不确定环境中移动机器人的路径规划方法，将全局路径规划分解为局部路径规划的组合，为了提高规划的效率，在避障规划中采用了基于案例的学习方法，以神经网络实现案例的匹配学习和扩充，满足了规划的实时性要求。 7 遗传算法 遗传算法(genetic algorithm.GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘
27、汰的生物进化过程，对群体反复进行基于遗传学的操作(遗传，交叉和变异) ，根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优 个体，求得满足要求的最优解。 孙树栋等用遗传算法完成了离散空间下机器人的路径规划，并获得了较好的仿真结果。但是，该路径规划是基于确定环境模型的，即工作空间中的障碍物位置是己知的、确定的。和在采用离散空间进行路径规划的同时，将问题更深入化，栅格序号采用二进制编码，统一确定其个体长度，随机产生障碍物位置及数目，并在搜索到最优路径后再在环境空间中随机插入障碍物，模拟环境变化，通过仿真结果验证了算法的有效性和可行性。但是，规划空间栅格法建模还存在缺陷，若栅格划分过粗，则规划精度较低，若栅格划分太细，则数据量又会太大。 周明等提出一种连续空间下基于遗传算法的机器人路径规划方法，该方法在规划空间利用链接图建模的基础上，先使用图论中成熟算法粗略搜索出可选路径，然后再使用遗传算法来调整路径点，逐步得到较优的行走路线。该方法的染色体编码不会产生无效路径，且仅使用基本遗传算法就可以完成路径规划。但是该方法对于环境复杂、障碍物数目较多的情况，链接图的建立会有一定的困难。在遗传算法的改进上周明等
