摘 要

随着计算机及自动化技术的不断发展,移动机器人技术在工业生产、医疗器械、航空航天等诸多领域得到越来越广泛的应用。路径规划问题涉及环境感知、数据处理及动作协同等多方面跨学科技术,是移动机器人导航技术研究的重要环节之一。目前科学家们虽然提出了多种算法来解决路径规划问题,但并没有找到最为有效的路径规划算法。因此,需要更深入对路径规划算法进行研究。本文针对传统蚁群算法容易陷入局部最优以及收敛速度较慢等问题,进行改进。通过启发蚁群进行路径搜索,避免算法早期由于盲目搜索而导致的路径交叉及收敛速度慢等问题,同时以收敛次数构建负反馈通道,使全局信息素和局部信息素的更新速率跟随收敛次数的变化自适应调节,从而保证了算法实施过程中中收敛速度与全局搜索能力的协调与统一。最后,在Matlab中对本文算法和传统蚁群算法进行计算机图形化仿真实验，结果表明改进后的算法在搜索速度以及收敛能力方面有明显提升。

关键词：机器人；路径规划；计算机图形

ABSTRACT

With the continuous development of computer and automation technology, mobile robot technology has been more and more widely used in industrial production, medical equipment, aerospace and many other fields. Path planning, which involves many interdisciplinary technologies such as environmental perception, data processing and action Synergy, is one of the important links in the research of mobile robot navigation technology. At present, although scientists have proposed a variety of algorithms to solve the path planning problem, but did not find the most effective path planning algorithm. Therefore, the path planning algorithm needs to be studied in greater depth. In this paper, the traditional ant colony algorithm is easy to fall into the local optimization and slow convergence speed and other problems, and improve. By inspiring the ant colony to search the path, avoid the problems such as path crossover and slow convergence speed caused by blind search in the early stage of the algorithm, and construct the negative feedback channel with the convergence times, so that the update rate of global pheromone and local pheromone follows the change of convergence times to adjust adaptively, Thus, it ensures the coordination and unification of the convergence speed and the global search ability in the process of algorithm implementation. Finally, the computer graphical simulation experiment of this algorithm and the traditional ant colony algorithm is carried out in Matlab, and the results show that the improved algorithm has obvious improvement in search speed and convergence ability.

KEY WOEDS：robot; path planning; computer graphics

目录

1. 绪论 1
   1. 移动机器人路径规划技术 1
   2. 研究背景及意义 1
   3. 国内外研究现状 2
2. 传统蚁群算法分析 4

2.1经典蚁群算法 4

2.1.1蚁群算法的产生 4

2.1.2蚂蚁道路选择分析 4

2.1.3蚁群算法的数学模型 5

2.1.4蚁群算法的特点 6

2.1.5蚁群算法的优缺点 7

2.2环境建模 8

2.3蚁群算法的执行流程 10

2.4蚁群算法的仿真分析 11

第3章 改进蚁群算法分析 14

3.1对传统蚁群算法的改进思路 14

3.1.1蚁群算法的缺陷分析 14

3.1.2改进途径分析 14

3.2蚁群算法的改进方案 15

3.2.1初始信息素分布改进 15

3.2.2转移概率改进 15

3.2.3全局信息素更新的改进 16

3.3蚁群算法参数的选取 17

3.3.1蚂蚁数目 18

3.3.2信息素挥发因子 20

3.3.3信息素启发因子和期望启发因子 23

3.3.4信息素的强度 25

3.4改进蚁群算法的执行流程 25

3.5改进蚁群算法的仿真分析 26

第4章 结论 28

参考文献 29

致谢 31

第1章 绪论

1.1移动机器人路径规划技术

在移动机器人的研究领域中，路径规划始终是一个重要的研究问题。移动机器人路径规划^[2]就是在指定区域中确定一条从起点到终点的最佳路线，这个最佳指的是运动的路径最短或是消耗时间最短，这个问题的本质是根据某些限制条件算出可行解或最优解。 路径规划是机器人与人工智能相结合的重要研究内容。 机器人能否平稳有效地完成指定的任务，与道路规划的结果密切相关。

一般情况下可以把路径规划分为局部路径规划和全局路径规划^[11]。在局部路径规划中，机器人在执行任务过程中需要携带一个传感器，由传感器采集到局部环境信息，根据搜集的信息进行实时动态路径规划,它的灵活性和实时性都比较强。局部路径规划依靠局部环境特征来发挥作用,有时会得到局部最优解而非全局最优解, 甚至可能会出现无法到达目标地点的解。在全局路径规划中，全局的环境信息都是已知的,需要将整个区域环境用地图模型的形式体现,然后使用某种搜索算法进行计算，找出全局最优或较优路径, 于是移动机器人就可以沿着规划的路径向目标点移动。全局路劲规划包括两部分内容:一是环境信息理解及地图模型构建, 二是全局路径搜索及机器人引导。在移动机器人路径规划中, 通常需要全局和局部路径规划结合起来, 前者可用于寻找全局优化路径, 后者用于实时避障。在移动机器人的路径规划中，搜索算法是最关键的一部分, 只要有一个优秀的算法，就能较好地解决路径规划问题。

路径规划问题有很多种算法^[8]，可以把它们分为两个大类。一类是传统的穷举搜索方法，如：Dijkstra、A*算法和图论。该类方法搜索的是整个空间，这意味着它一定可以找到最优解，但执行时间会随着问题的大小成指数增长。另一类是比较智能的仿生算法，它是解决优化问题的一种常用方法。由于路径应该是无碰撞的，并且应该满足一组优化准则，因此路径规划也被认为是优化问题。常用的仿生算法有禁忌搜索法、蚁群算法、遗传算法、粒子群算法等。如果使用传统的路径规划算法来求解复杂环境的路径规划问题，就会出现计算代价高、容易陷入局部最优、效率低等问题。而仿生智能算法效率高、便于实施^[9]，现已取得了良好的成果，成功解决了许多复杂的路径规划问题。

1.2研究背景及意义

自20世纪60年代初以来，对于移动机器人的研究十分活跃^[6]，相关技术的发展迅速，对人们的生产和生活方式产生了很大的影响，机器人产业正在逐渐发展成为一个热门的高新技术产业。

由于社会生产发展的需要，移动机器人的研究也在不断更新。现如今，移动机器人有着非常广阔的应用范围，包括制造业、轻重工业以及服务业等诸多领域。目前移动机器人最成功的应用就是作为自动化生产系统中的物料搬运装置，用以传递工件和工具等。移动机器人具有能灵活运动的特性，这使生产系统的柔性和自动化程度均能得到提升，使生产效率显著提升。除此之外，国内外的星际探索和海洋开发两大高端技术领域对移动机器人的市场需求较大。20世纪60年代，美国MIT开始研究为了进行火星探索而使用的移动机器人，使其完成在火星软着陆并进行收集数据的工作。在海洋开发方面，移动机器人的作用是资源调查、石油矿藏开采和沉船打捞等。除了上述应用外，还有很多其他领域正在逐渐挖掘移动机器人的价值，如在采矿业中进行隧道的掘进和矿藏的开发，用于军事上的探测、侦察和爆炸物处理。在一些具有危险性的操作中，例如核电厂的废料搬运和有毒的化工厂作业，移动机器人的应用价值格外突出。最近几年，在智能交通系统方面也开始运用到移动机器人技术。

与任何一门现代技术分支一样，移动机器人研究的兴起一方面是社会生产发展的需要，另一方面也是相关技术领域交叉互相促进发展的结果。其中一个最直接的因素就是计算机技术的发展。随着科学的不断进步，计算机的运算速度和存储能力有了大幅度提高，这让移动机器人有能力运行更复杂的实时控制算法，完成各种复杂任务。此外，在计算机科学中出现了人工智能、专家系统等新兴技术分支学科，随着这些学科的逐渐发展，移动机器人开始拥有在未知或动态环境下实时导航的能力。由此可见，移动机器人技术是众多高新技术的产物，同时它也促进了其他相关技术的发展。

随着时代的发展与进步，移动机器人已在工业自动化领域得到广泛的应用。路径规划技术对于提高移动机器人的自主移动性能起着至关重要的作用,它对于移动机器人的研究非常关键。然而,目前的很多算法存在着收敛性差、可靠性低等问题,这导致移动机器人路径规划效率不高、路径质量差。因此, 如何提高路径规划效率和改善路径质量, 具有重大的研究意义。

1.3国内外研究现状

国外对移动机器人的研究始于上20纪60年代末期，在1966至1972年，在斯坦福研究院工作的Nion和 CharlesRosen等人研制了出名为 Shakey的自主移动机器人^[4]，目的是研究人工智能技术在复杂环境下机器人系统中的自主推理、规划和控制的应用。

20世纪70年代末，随着计算机应用和传感技术的发展，人们对于移动机器人有了一些新的研究方向，开始进行面向实际应用的室内移动机器人的研究^[15]，并逐步形成了自主式移动机器人AMR( Indoor Autonomous mobile robot)概念。特别是在20世纪80年代中期，一大批世界著名的公司开始投入大量人力、财力研制移动机器人，各大学实验室以及研究机构都开始搭建移动机器人实验平台^[16]，这促进了移动机器人学向多种研究方向发展。

美国国家科学委员会曾预言：“20世纪的核心武器是坦克，21世纪的核心武器是无人作战系统，其中2000年以后遥控地面无人作战系统将连续装备部队，并走向战场”。为此，从20世纪80年代开始，美国国防高级研究计划局( DARPA)成立了相关的项目组，着力于制定地面无人作战平台的战略计划。从此，在全世界范围内，室外移动机器人的相关研究在全面进行着，如 DARPA的“战略计算机”计划中的自主地面车辆计划，能源部制订的为期10年的机器人和智能系统计划，以及后来的空间机器人计划，日本通产省组织的极限环境下作业的机器人计划等。美国航空暨太空总署(NASA)研制的火星探测机器人索杰那于1997年登上火星，这一事件得到了全世界人们的广泛关注。德国研制了一种轮椅机器人，并在乌尔姆市中心车站的客流高峰期的环境和1998年汉诺威工业商品博览会的展览大厅环境中进行了实地现场表演。该轮椅机器人在公共场所拥挤的环境中进行了超过36个小时的表演，它所表现出的性能比当时其他的轮椅机器人或移动机器人都要强很多。美国火星探测机器人：精神号( Spirit)与机会号( Opportunity)，分别在2004年1月3日及24日登陆火星，这也引起了各国科学家的注意。

我国对于移动机器人的研究工作起步较晚，自20世纪80年代末，国家“863”计划启动智能机器人主题立项工作^[5]，从而开始了遥控驾驶防核化侦察车的研制工作，于此同时国防科工委也开始投资AGV( Automatic Guided Vehicle)方面的研究工作。在“九五”期间，我国继续组织研究了第二代地面自主车ALVLAB的研制工作。这些项目的实施加快了我国机器人领域的发展。

经过这么多年来的发展，我国移动机器人的研究已经取得了一定的成绩，其中具有代表性的系统有清华大学研制的 THMR-V,吉林大学研制的JLUⅣV系列实验车以及西安交通大学研制的 SPringrobot实验车等。但是与那些早已开始研究移动机器人的西方发达国家相比，无论是在研究规模、投资强度、技术水平方面，还是在成果应用程度与效益等方面，都存在明显的差距。

第2章 传统蚁群算法分析

2.1经典蚁群算法

2.1.1蚁群算法的产生

19世纪50年代中期^[1]，仿生算法开始引起人们的注意，科学家们发现仿生算法可以应用于路径规划。随着人们对于仿生算法的研究越来越深，仿生算法的问题也慢慢地被大家发现。为此，科学家们不得不进行大量的思考以及实验，寻找出合适的优化方案，从而对已有的算法进行完善。

蚁群算法由Dotigo M等人于1992年首次提出，属于一种群体智能算法。在一个蚁群当中，每一个个体的行为模式都很简单，但是当它们组成一个整体后，就会产生巨大的变化。在一个蚁群中，蚂蚁会通过相互协作完成各种复杂的行为，比如觅食。经研究表明，蚂蚁的觅食行为十分灵活，它们会及时察觉周围环境的变化并作出反应，改变自己的运动状态。当遇到障碍物的时候，它们会快速地调整方向，寻找新的路径继续向目标点行进。

在解决组合优化问题上，蚁群算法为人们带来了极大的便利。我们可以利用数学建模的方式来分析蚁群算法，把它看作是基于求解空间参数化概率分布模型的问题，在这个模型的基础上，结合蚁群的觅食行为特点，根据蚂蚁前进时产生的信息素进行搜索、更新，从而得出关于觅食路径的最优解。

2.1.2蚂蚁道路选择分析

经科学家研究表明，蚂蚁的视觉能力和记忆能力都非常差，但是它们可以通过相互协作来完成很多及其复杂的任务。蚂蚁之间通过信息素来进行沟通交流，后出发去寻找食物的蚂蚁会检测先前出发的蚂蚁留下的信息素并判断其浓度大小，从而决定下一步应该沿哪个方向移动。在觅食刚开始的时候，从蚁穴出发的蚂蚁在选择路径时有很强的随机性，因为刚开始信息素的浓度并没有明显差异，所以蚂蚁朝各个方向移动的概率基本相等。但是只要觅食行为继续进行下去，从蚁穴到食物之间最短的那条路径上留下的信息素会越来越多，而在那些比较长的路径上留下的信息素会逐渐变少，于是在不同的路径上信息素的浓度会产生越来越明显差距。后出发的蚂蚁在到达一个道路交叉点时都会沿信息素浓度高的路径前行，最终蚁群能确定那一条最短的路径。

2.1.3蚁群算法的数学模型

在经典蚁群算法中,t时刻蚂蚁k由节点i运动到节点j的概率主要受两个因素的影响：信息素量的大小以及期望启发因子。

现在将蚂蚁在当前节点i向节点j移动的概率设为P，则转移概率公式为

（2.1）

其中， τ_ij(t)表示t时刻节点i到节点j之间的信息素浓度的大小,η_ij(t)表示t

时刻节点i和节点j之间的启发式因子，在经典蚁群算法中，该值的取值大小为节点i和节点j之间距离的倒数。α表示信息素浓度对转移概率P影响的大小，j∈allowed_k表示蚂蚁k下一步可以选择的路径节点。

为了避免信息素积累过多，当所有蚂蚁均到达目标节点后，需要对路径上的信息素进行更新，更新公式如下

（2.2）

其中τ_ij(t 1)表示在t 1时刻节点i,j之间的信息素浓度，ρ表示信息素的挥发系数，Δτ_ij^k(t,t 1)表示从t到t 1节点i,j之间信息素的增量，其计算公式为

（2.3）

随着对蚁群算法研究的深入，Dorigo M博士将蚁群算法模型分为以下几种

（1）蚁密系统模型

该模型中信息素的总量与两个节点之间距离的长短没有关联，具体公式为

（2.4）

其中，Q为蚂蚁一次迭代所释放的信息素量，k∈Passed_ij表示蚂蚁k在t到t 1之间经过节点i,j。

(2) 蚁周系统模式

在该模型中信息素释放工作是在蚂蚁k完成一次循环后进行的，具体公式为

（2.5）

其中Q为一次迭代结束所释放的信息素量，k∈Cycle_ij表示蚂蚁k在本次迭代中经过节点I,j，L_k表示本次迭代中蚂蚁k走过的路径总长度。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：