基于蚁群算法的机器人路径规划(附仿真程序)☆

摘要
随着科学技术的进步，智能机器人系统开始应用在服务行业。服务型的自主式移动机器人的研究和设计越来越受到企业界和商业界的重视。目前，已经存在很多组合优化算法来解决机器人路径规划问题，但很多算法都存在一定的局限性。而蚁群算法具有正反馈、灵活性和协同性等特点，顺应路径规划算法的研究现状和向智能化、仿生化发展的趋势。因此，本课题拟采用蚁群算法对机器人路径进行规划。
本文讨论的机器人环境为静态全局环境已知，通过栅格法对已知环境进行抽象，建立机器人工作空间模型，并采用蚁群算法，模拟蚂蚁觅食行为，根据优化条件搜索出一条从指定起点到终点的最优或近似最优路径，即全局路径规划。机器人利用自身视觉传感器按照规划出的最优路径自动导航，无碰撞地移动到目标点。
通过Matlab平台实施仿真，实验结果表明，在环境地图已知的情况下，该算法能迅速规划出较优的全局路径，并且算法简单有效。与传统的搜索算法比较，它可以避免陷入过早收敛，能实现移动机器人在较短时间内搜索到最佳路径并规避障碍。
关键词：蚁群算法；组合优化；机器人；路径规划
 
Abstract
With the development of the science and technology, intelligent robotic systems have been applied in the service industry, and the R&D of service-type autonomous mobile robot has received greater attention from business circles in China. Now, many combination optimization algorithms have been developed to solve the robot path planning, but with some limitation for each algorithms. The newly-developed ant algorithm has superiorities of positive feedback, flexibility and collaboration, which enables it to adapt to the trend of path planning algorithms in the intelligent and bionic direction. Thus, ant colony algorithm is proposed to plan the robot’s path in this paper.
The stoical and global environment is given, which is abstracted with grid method before the workspace model of the robot being built. With the adoption of the ant colony algorithm, the foraging behavior of ant colony is simulated. According to the optimization condition, the robot tries to find a path which is optimal or optimal-approximate path from starting point to goal, that is global path planning. The robot uses its built-in vision sensors to navigate autonomously following the optimal path which has been built, and move to the object collision-freely.
On the Matlab platform, the simulation result shows that the optimal path can be built quickly by this algorithm if the environment map is known. Also, the algorithm is simple and efficient. Comparison with traditional search algorithms—the mobile robot can find the goal within the shortest path without the collision and the stagnation.
Key words: ant colony algorithm; combination optimization; robot; path planning
 

仿真实验
本论文使用Matlab7.0软件仿真实现移动机器人路径规划，程序文件共有三个，其中RPPACA.m是主程序，完成蚁群算法的路径规划功能，G2D.m是将地图数据转化为邻接矩阵，DATA.mat存储的是地图信息。
首先将三个文件复制到Matlab的当前路径下，程序调用格式如下：
load DATA
[ROUTES,PL,Tau]=RPPACA(G,ones(400,400),50,30,1,400,1,10,0.95,1);
全部蚂蚁爬过的轨迹如图5-1所示，图5-2是大多数蚂蚁选择前往目标点的一条路径，这条路径就是所要的最优路径，即机器人的移动路径。
 
移动机器人的路径规划是一种比较典型的优化问题，本身具有复杂性、约束性、非线性、建模规范等特点[18]，目前对路径规划算法的研究方兴未艾，尤其是新型的蚁群算法。
蚁群算法的正反馈性、协同性和隐含的并行性使其具有极强的发展潜力，灵活性使其在解决组合优化问题上具有良好的适应性，因此将蚁群算法应用于智能移动机器人避障的路径规划问题研究，能够探索与改进一种新的路径优化算法，促进优化理论与实践的发展，并且为经济领域以及工程领域的优化问题提供借鉴。

主要研究内容及关键问题
本课题对已知的全局静态环境进行场景建模的基础上，重点研究了用于机器人全局路径规划的智能蚁群算法，为机器人寻找一条从给定的起始点到目标点的满足一定优化指标的无碰撞路径，并在此基础上，用Matlab软件进行仿真实验，验证算法的有效性和优良性能。
本课题拟解决的关键问题：
1）环境建模：采用何种方法对机器人工作环境进行建模，建立一个便于计算机进行路径规划使用的环境模型，即将机器人实际工作的物理空间抽象成算法能够处理的抽象空间；
2）路径搜索：如何应用蚁群算法编写程序，并结合信息素更新策略，以及考虑在路径搜索阶段避免陷入局部最优解等问题，更好地规划出一条无碰撞、最优路径。

论文结构
本文的主要结构如下：
第1章：阐述了本课题的背景及意义，比较了目前常用的路径规划算法，并提出基于蚁群算法对机器人路径进行规划的问题。
第2章：描述机器人路径规划的问题，介绍了机器人工作环境的建模方法。
第3章：概述蚁群算法，介绍其基本原理和工作流程，并描述了算法的数学模型。
第4章：针对前面对路径规划问题与蚁群算法的研究，将蚁群算法引入到移动机器人的路径规划中，采用栅格法对环境进行建模，并描述算法的实施步骤。
第5章：编写程序对其进行仿真实验，并分析实验结果。
第6章：对全文进行总结，给出下一步研究方向。
 
2 机器人路径规划概述
路径规划技术是智能机器人领域中的一个重要分支，是机器人学中研究人工智能问题的一个重要方面，也是目前研究的重点领域。2003年底和2004年初分别登入火星的猎兔犬2号、勇气号和机遇号[8]，2007年8月份发射的凤凰号探测器，以及我国计划2009年发射的首个火星探测器，暂名为“萤火一号”，它们的路径规划技术代表着当今世界移动机器人路径规划技术的最高水平。我们希望未来的机器人能具有更智能的感知、规划和控制等高层能力。它们能从周围的环境中收集知识，构造一个关于环境的符号化模型，并且利用这些模型来规划、执行复杂的高层任务。在本课题讨论的移动机器人路径规划系统中主要的要求是：能在环境地图中寻找一条路径，保证机器人沿该路径移动时不与外界发生碰撞，并能够按照需要找到最优路径。

目  录
摘要 I
Abstract II
1 引言 1
1.1 课题背景及意义 1
1.2 主要研究内容及关键问题 2
1.3 论文结构 3
2 机器人路径规划概述 4
2.1 路径规划的定义 4
2.2 路径规划问题的分类 4
2.3 环境建模 5
2.3.1 可视图法 5
2.3.2 栅格法 6
3 蚁群算法概述 7
3.1 蚁群算法的基本原理 7
3.2 基本蚁群算法的数学模型 8
3.2.1 对蚂蚁个体的抽象 8
3.2.2 问题空间的描述 9
3.2.3 寻找路径的抽象 9
(优秀毕业设计:www.2bysj.cn)
3.2.4 信息素挥发的抽象 9
3.2.5 启发因子的引入 9
4 基于蚁群算法的机器人路径规划 11
4.1 环境建模 11
4.2 算法的描述 12
4.3 算法的步骤 13
5 仿真实验及结果分析 16
5.1 仿真实验 16
5.2 结果分析 17
6 结束语 20
参考文献 21
致谢 22
附录A 基于蚁群算法的机器人路径规划主程序 23
附录B 机器人工作环境的地图数据转化程序 30
附录C 机器人工作环境的地图数据信息 33