论文题目：_ 基于蚁群算法的机器人路径规划 系 ：__ 信息与机电工程系__ 专业年级：__ __ 学 号：_____ _ _ _ 姓 名：_________ _ _ 指导教师、职称：_ _

2010年 5月 15 日

Robot’s Path Planning Based on

Ant Colony Algorithm College: Specialty and Grade: Number: Name: Advisor: Submitted Time: 目 录

摘要 ................................................................................................................................................... Abstract ............................................................................................................................................. 1 引言 ...............................................................................................................................................

1.1 课题背景及意义 ................................................................................................................. 1.2 主要研究内容及关键问题 ................................................................................................. 1.3 论文结构 ............................................................................................................................. 2 机器人路径规划概述 ...................................................................................................................

2.1 路径规划的定义 ................................................................................................................. 2.2 路径规划问题的分类 ......................................................................................................... 2.3 环境建模 .............................................................................................................................

2.3.1 可视图法 .................................................................................................................. 2.3.2 栅格法 ......................................................................................................................

3 蚁群算法概述 ...............................................................................................................................

3.1 蚁群算法的基本原理 ......................................................................................................... 3.2 基本蚁群算法的数学模型 .................................................................................................

3.2.1 对蚂蚁个体的抽象 .................................................................................................. 3.2.2 问题空间的描述 ...................................................................................................... 3.2.3 寻找路径的抽象 ...................................................................................................... 3.2.4 信息素挥发的抽象 .................................................................................................. 3.2.5 启发因子的引入 ......................................................................................................

4 基于蚁群算法的机器人路径规划 ...............................................................................................

4.1 环境建模 ............................................................................................................................. 4.2 算法的描述 ......................................................................................................................... 4.3 算法的步骤 ......................................................................................................................... 5 仿真实验及结果分析 ...................................................................................................................

5.1 仿真实验 ............................................................................................................................. 5.2 结果分析 ............................................................................................................................. 6 结束语 ........................................................................................................................................... 参考文献 ........................................................................................................................................... 致谢 ...................................................................................................................................................

摘要

移动机器人的研究开始于上个世纪60年代末期，是人工智能、机器入学、仿生学、控制理论和电子技术等多种技术学科交叉的产物。随着科技的发展和社会的进步，机器人已经走出实验室，在深海勘测、汽车制造、医学科研、能源开采、军事现代化等领域中都占有着其不可取代的位置。机器人的应用越来越广，越来越深入，各应用领域对机器人的要求也越来越高，因而移动机器人的研究逐渐成为趋势，成为高新技术应用领域的热点。 目前，对于移动机器人相关技术的研究，虽然已取得了大量的成果和突破性的进展，但是在很多关键理论和实际问题上，还有待解决和完善。因此，进行移动机器人相关技术的研究，实现移动机器人的全智能化具有非常重要的现实意义。

本文讨论的机器人环境为静态全局环境已知，通过栅格法对已知环境进行抽象，建立机器人工作空间模型，并采用蚁群算法，模拟蚂蚁觅食行为，根据优化条件搜索出一条从指定起点到终点的最优或近似最优路径，即全局路径规划。机器人利用自身视觉传感器按照规划出的最优路径自动导航，无碰撞地移动到目标点。

通过Matlab平台实施仿真，实验结果表明，在环境地图已知的情况下，该算法能迅速规划出较优的全局路径，并且算法简单有效。与传统的搜索算法比较，它可以避免陷入过早收敛，能实现移动机器人在较短时间内搜索到最佳路径并规避障碍。 关键词：蚁群算法；组合优化；机器人；路径规划

Abstract

Mobile robot began in the late 60s of last century, is artificial intelligence, machine school, bionics, control theory and electronic technology, and other technical disciplines cross product. With the technological development and social progress, the robot has been out of the laboratory, in the deep-sea exploration, automobile manufacturing, medical research, energy, mining, military modernization in all fields occupy an irreplaceable position. Used more and more robots, more depth, the applications of robots more and more demanding, so mobile robot become a trend, a high-tech hot spot applications. Currently, the mobile robot related technology research, though there has been a lot of achievements and breakthroughs, but in many key theoretical and practical issues remain to be resolved and improved. Therefore, for mobile robot related technology research, all intelligent mobile robots have very important practical significance.

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

1 引言

1.1 课题背景及意义

随着计算机技术、控制理论、人工智能理论、传感器等技术的不断成熟和发展，机器人的研究已经发展到一个崭新的阶段。其中，移动机器人作为一个重要分支，在国内外研究领域已经得到普遍重视。移动机器人是一类能够通过传感器感知环境和自身状态、实现在有障碍物的环境中面向目标位置的自主运动，从而完成某种作业功能的机器人系统。图1-1(a)是美国斯坦福研究院于上世纪60年代末至70年代初研制的机器人Shakey，它是全球第一个能自动避开障碍物的机器人。图1-1(b)是日本SONY公司研制的娱乐机器狗AIBO。图1-l(c)是日本SONY公司研制的家庭娱乐机器人QRIO，它通过随身的多个传感器可以感知周围环境并根据程序对环境做出实时反应，是世界上第一个能够完成跑、跳、投等高难度动作的双足机器人。图1-1(d)是2004年美国太空总署登陆火星的“勇气号”和“机遇号”探测器。

图1-1 各种新型机器人

在各种新技术中，机器人技术尤其得到许多国家的重视，而且随着科学技术的进步，发展日益迅速。机器人在许多领域得到广泛应用，已经对许多国家的工业生产、外太空的探索、国防的建设以及整个国民经济和人民生活产生了重大影响，而且这种影响还在不断扩大中，比如，广泛应用于军事侦察、工业生产、娱乐服务领域中，尤其是在一些作业环境比较恶劣的情况下，如排雷排险、焊接、生化探测、火灾侦察、隧道凿岩及抢险救灾等。而机器人路径规划是机器人学的一个重要研究领域，也是人工智能与机器人学的重要结合点[1]。

路径规划是移动机器人研究领域的重要内容，也是一种比较典型的优化问题，本身具有复杂性、约束性、非线性、建模规范等特点[2]。路径规划算法的计算量取决于任务、环境的复杂性以及对规划路径质量的要求，一个好的路径规划算法应该兼顾对规划速度和路径质量的期望。因此，通过研究此问题，探索与改进一种适合于大规模并行且具有智能特征的路径优化算法已成为有关学科的一个主要研究目标和引人注目的研究方向。与20世纪80年代研究初期相比，近年来有关机器人路径规划的文献日益增多，无论是在研究的深度还是广度上都有了巨大的发展，初步形成了理论、算法和应用的多方位研究。在机器人路径规划的算法领域中，目前使用的方法有人工势场法、遗传算法、模糊逻辑算法、神经网络算法等。

人工势场法最早是由Khatib和Krogh提出的一种虚拟力法。在人工势场中，障碍物被看作斥力场，目标被看作引力场，所以障碍物对机器人产生斥力，目标对机器人产生引力，通过求引力和斥力的合力来控制机器人的运动。人工势场法结构简单，计算量小，实时性