好。因而广泛应用于实时避障和平滑轨迹控制方面。但是在局部最优解的问题上容易产生死锁现象，从而可能导致机器人陷入局部最优点。
遗传算法是一种多点搜索算法，也是目前机器人路径规划研究中应用较多的一种方法。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息，且作为并行算法，其隐并行性适用于全局搜索，所以解决了其它一些算法无法解决的问题。但在初始可行解的有效构造以及针对复杂环境特点设计相应的遗传算子等方面，存在着较大的困难。此外，遗传算法运算速度低，进化众多的规划要占据较大存储空间和运算时间。[3]
模糊逻辑算法是基于实时传感信息的一种在线规划方法。李彩虹[4]提出了一种在未知环境下移动机器人的模糊控制算法，庄晓东[5]提出一种动态环境中基于模糊概念的机器人路径搜索算法。然而，模糊逻辑应用于复杂未知动态环境中，模糊规则较难提取等。
神经网络作为一个高度并行的分布式系统，为解决机器人系统实时性要求很高的问题提供了可能性，并应用于机器人路径规划方面。禹建丽[6]等在《线性再励的自适应变步长机器人神经网络路径规划算法》中提出了一种基于神经网络的机器人路径规划算法。研究了障碍物形状和位置已知情况下的机器人路径规划算法，其能量函数的定义利用了神经网络结构，规划出的路径达到了折线形的最短无碰路径，该方法计算简单、收敛速度快。刘成良[7]等在《神经网络在机器人路径规划中的应用研究》中提出了基于神经网络的机器人无碰撞路径规划方法，给出了无碰撞轨迹规划的人工神经网络算法，证明了其可行性，为神经网络真正用于机器人控制提供了基础。但是随着神经网络研究和应用的深入，人们又发现人工神经网络模型和算法也存在问题。如神经计算由于不依靠先验知识，是靠学习与训练从数据中取得规律和知识，这固然是优点，但同时也带来困难，如效率问题，学习的复杂性也是困扰神经网络研究的一大难题。其次，由于先验知识少，神经网络的结构就很难预先确定，只能通过反复地学习寻找一个合适的结构，因此，由此所确定的结构也就很难为人理解。
综上所述，这些路径规划方法都在一定程度上解决了机器人的路径规划问题，但是，由于各种算法自身的局限，使得路径规划问题的探讨仍具魅力，新的算法也在不断地涌现与发展。而蚁群算法是基于生物界群体启发行为的一种随机搜索寻优方法，具有动态性、分布性和协同性等一些特性，采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布计算机制、易于与其它方法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力[1]。而机器人作为一种智能体，其路径规划是指机器人按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰撞路径，它是实现机器人控制和导航的基础之一，在很大程度上类似于蚂蚁觅食优选路径。因此，本文拟采用蚁群算法对机器人路径进行规划，期望能够很好地克服上述传统算法的不足。
1.2 主要研究内容及关键问题
本课题对已知的全局静态环境进行场景建模的基础上，重点研究了用于机器人全局路径规划的智能蚁群算法，为机器人寻找一条从给定的起始点到目标点的满足一定优化指标
的无碰撞路径，并在此基础上，用Matlab软件进行仿真实验，验证算法的有效性和优良性能。
本课题拟解决的关键问题：
1）环境建模：采用何种方法对机器人工作环境进行建模，建立一个便于计算机进行路径规划使用的环境模型，即将机器人实际工作的物理空间抽象成算法能够处理的抽象空间；
2）路径搜索：如何应用蚁群算法编写程序，并结合信息素更新策略，以及考虑在路径搜索阶段避免陷入局部最优解等问题，更好地规划出一条无碰撞、最优路径。
1.3 论文结构
本文的主要结构如下：
第1章：阐述了本课题的背景及意义，比较了目前常用的路径规划算法，并提出基于蚁群算法对机器人路径进行规划的问题。
第2章：描述机器人路径规划的问题，介绍了机器人工作环境的建模方法。 第3章：概述蚁群算法，介绍其基本原理和工作流程，并描述了算法的数学模型。 第4章：针对前面对路径规划问题与蚁群算法的研究，将蚁群算法引入到移动机器人的路径规划中，采用栅格法对环境进行建模，并描述算法的实施步骤。
第5章：编写程序对其进行仿真实验，并分析实验结果。 第6章：对全文进行总结，给出下一步研究方向。
2 机器人路径规划概述
路径规划技术是智能机器人领域中的一个重要分支，是机器人学中研究人工智能问题的一个重要方面，也是目前研究的重点领域。2003年底和2004年初分别登入火星的猎兔犬2号、勇气号和机遇号[8]，2007年8月份发射的凤凰号探测器，以及我国计划2009年发射的首个火星探测器，暂名为“萤火一号”，它们的路径规划技术代表着当今世界移动机器人路径规划技术的最高水平。我们希望未来的机器人能具有更智能的感知、规划和控制等高层能力。它们能从周围的环境中收集知识，构造一个关于环境的符号化模型，并且利用这些模型来规划、执行复杂的高层任务。在本课题讨论的移动机器人路径规划系统中主要的要求是：能在环境地图中寻找一条路径，保证机器人沿该路径移动时不与外界发生碰撞，并能够按照需要找到最优路径。
2.1 路径规划的定义
机器人路径规划问题可定义为：给定机器人的出发点和目标点，在有固定或移动障碍的环境中，规划一条无碰撞的、满足某种最优准则的路径，使机器人按照该路径从出发点顺利运动到目标点。考虑到机器人在运动过程中会消耗能量、占用时间、非直线运动，可以围绕这几个方面建立最优准则，如，要求所消耗的能量最少、所用的时间最短、路径长度最短等[9]。以FS表示无碰撞的自由空间，路径规划问题可以描述为：给定一个起始结点
S和目标结点E，在FS中寻找一条连接这两点并满足某一最优准则的连续曲线。
2.2 路径规划问题的分类
根据环境是否时变（即是否含有运动障碍）可以把机器人工作环境分为静态环境和动态环境。而机器人根据对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类：1）已知环境下的对静态障碍物的路径规划；2）未知环境下的对静态障碍物的路径规划；3）已知环境下对动态障碍物的路径规划；4）未知环境下的对动态障碍物的路径规划。另外，路径规划根据规划时是否能得到全部环境状态信息（即所有物体的位置和运动信息）又可分为基于全局信息的规划和基于局部信息的规划。[10]
全局路径规划方法是依据已获取的全局环境信息，给机器人规划出一条从起点至终点的运动路径。规划路径的精确程度取决于获取环境信息的准确程度。全局路径规划的规划方法通常可以寻找最优解，但需要预先知道准确的全局环境信息。
局部路径规划只需要了解行进中的机器人周围的障碍物信息，并在其行走过程中，分析、处理传感器采集的信息以更新其内部环境表示，从而确定出机器人在地图的当前位置及其局部的障碍物分布情况以选出从当前结点到某一子目标结点的较优弧。
从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划，局部路径规划属于动态规划。本课题讨论的机器人环境为静态全局环境已知，通过充分利用已知的环境，离线的规划出一条从指定起点到终点的最优或近似最优路径，属于全局路径规划。
2.3 环境建模
环境建模的目的是建立一个便于计算机进行路径规划使用的环境模型。环境建模是机器人路径规划的重要环节，采取何种规划方法建模由环境信息的完备程度以及环境模型的形式决定，比如，机器人所处环境中障碍物的几何特点、大小、数量等都是考虑的因素。移动机器人的工作空间是一个现实的物理空间，而路径规划算法所处理的空间是环境的抽象空间，称之为环境模型。环境建模是实现物理空间到算法处理抽象空间的一个映射，路径搜索的结果，通常是以环境模型的方式表达。
下面介绍两种较为常用的环境建模方法：可视图法、栅格法。 2.3.1 可视图法
可视图法[11]是将机器人视为一点，把机器人、目标点和多边形障碍物的各个顶点进行连接，要求机器人和障碍物各顶点之间，目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，都不能穿越障碍物，这样就形成了一张图，称之为可视图（如图2-1）。由于任意两直线的顶点都是可视的，显然移动机器人从起点沿着这些连线到达目标点的所有路径均是无碰路径。对可视图进行搜索，并利用优化算法删除一些不必要的连线以简化可视图，缩短搜索时间，最终就可以找到一条无碰最优路径。
图2-1 可视图法示意图
然而，可视图法是建立在机器人所在环境的所有的障碍物信息已知的前提下，不能用于未知障碍物和动态障碍物环境下的路径规划。而且该方法缺乏灵活性，若障碍物过多，搜索时间会很长。另外，一旦机器人的起点和目标点发生改变，就要重新构造可视图，比较麻烦。 2.3.2 栅格法
栅格法[11]在许多机器人系统中得到应用，是使用较为成功的一种方法。该方法以栅格为单位记录环境信息，用大小相同的栅格将机器人工作环境分解成一系列具有二值信息的网格单元。如图2-2所示，左图不规则的障碍物经栅格划分后得到右图。每个栅格点有两种表示方法：自由空间、障碍空间，经常在图形表示中用黑格代表障碍物，并用栅格数组来表示环境，在栅格数组中标记为1，白格代表自由空间，标记为0。最短路径就是通过
搜索这张栅格图得到的。这种方法的表示效率虽然不高，但其简单性为路径规划的实现带来了诸多方便，在处理障碍物的边界时，避免了复杂的计算。而且栅格地图容易创建和维护，机器人所了解的每个栅格的信息直接与环境中某区域对应，借助于该地图，可以方便地进行自定位和路径规划。
图2-2 任意形状障碍物的栅格划分
基于对机器人路径规划问题的环境分析，本文利用栅格法模拟、划分机器人工作物理环境，建立环境模型。为实现设想的路径规划算法，本文在机器人运动空间建模时作如下假定：1）移动机器人在二维有限空间中运动；2）机器人运动空间中分布着有限个已知的大小不同的静态障碍物，障碍物可以由多个栅格描述，忽略障碍物的高度信息。
同时，在栅格法的应用中，栅格粒度（即单位面积内栅格的数量）的划分非常关键，直接影响着环境信息存储量的大小和规划时间的长短。栅格粒度越小，障碍物的表示会越精确，但同时会占用大量的存储空间，算法的搜索范围将按指数增加。然而，栅格的粒度太大，规划路径的精确度就大大降低。因此，在选择栅格粒度时应权衡好利弊关系，兼顾考虑实验结果的有效性与优良性。