（计算数学专业论文）基于智能计算的机器人路径规划方法研究.pdf

大连理工大学硕士学位论文 摘要 移动机器人最基本的路径规划问题是在完全已知的静态障碍物之间为机器人寻找 一条从给定的起始点到目标点的满足一定优化指标的无碰撞路径。本文介绍了移动机器 人路径规划的基本概念、路径规划的分类，并对模拟退火、神经网法、遗传算法、蚁群 算法在这一问题中的应用进行了比较。 本文重点讨论了蚁群算法，包括蚁群算法的基本原理及工作流程。为了模拟实际蚂 蚁的觅食行为，设机器人出发点h 为蚁穴位置，食物源则在最终目标点f ，蚂蚁觅食过 程就是从h 出发，在a s 范围寻找食物源的过程。经过蚂蚁群体的反复寻食，基于蚂蚁 留下信息素的正反馈作用，最终绕开所有障碍物找到了一条最短路径。 关键词：机器人路径规划；蚁群算法；信息素；最短路径 基于智能计算的机器人路径规划研究 r e s e a r c ho nm o b i l er o b o tp a t hp l a n n i g b a s e do ni n t e l l i g e n tc o m p u t i n g a b s t r a c t t h eb a s i cq u e s t i o no fm o b i l er o b o tp a t hp l a n n i n gi st of i n dac o l l i s i o n l - f r e ep a t h ，w h i c h s a t i s f i e sc e r t a i no p t i m i z ei n d e x e sf r o mg i v e ns t a r t i n gp o i n tt oo b j e c tp o i n tf o rr o b o ta m o n g c o m p l e t e l yk n o w n s t a t i co b s t a c l e s i nt h i sd i s c o u r s e ，t h eb a s i cc o n c e p ta n dt h ec l a s s i f i c a t i o n o fp a t hp l a n n i n ga r ei n t r o d u c e d ，a n ds i m u l a t i n ga n n e a l ，n e u r a ln e t w o r k ，g e n e t i ca l g o r i t h ma n d a n tc o l o n yo p t i m i z a t i o n ，a r ec o m p a r e dt o o i nt h i sp a p e r ，t h ea n tc o l o n yo p t i m i z a t i o n ，n a m e l yt h eb a s i cp r i n c i p l ea n dw o r k f l o wo f t h ea n tc o l o n yo p t i m i z a t i o ni sm a i n l yd i s c u s s e d i nt h ee n d ，t os i m u l a t et h ea n td e f a c t o f o r a g i n g , t h ea n t h i l la n df o o ds o u r c ea r ed e n o t e db ys t a r t i n gp o i n th o ft h er o b o ta n dt h e o b i e c tp o i n tf ，r e s p e c t i v e l y t h ep r o c e s so ft h ea n tf o r a g i n gi st h ep r o c e d u r et h a tt h ea n t b e g i n sw i t hh a n df i n d st h ef o o ds o u r c ew i t h i na sf r o mzb yt h ei t e r a t i v ef o r a g i n go ft h ea n t c o l o n ya n db a s e do i lp o s i t i v ef e e d b a c ke f f e c to ft h ep h e r o m o n ew h i c ht h ea n t sl e a v e ，f i n a l l ya s h o r t e s tp a t hi sf i n db yb y p a s s i n ga l lo b s t a c l e s k e yw o r d s ：p a t hp l a n n i n go fr o b o t ；a n tc o l o n yo p t i m i z a t i o n ；f e e d b a c k ；s h o r t e s tp a t h i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 疰 大连理上人学硕十学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日 日 大连理下大学硕十学位论文 1 综述 1 1 引言 2 0 世纪2 0 年代，“机器人( r o b o t ) 作为专有名词第一次出现嵋。1 9 2 0 年， 捷克作家卡雷尔查培克( k a r e lc a p e k ) 编写了一部幻想剧：罗沙姆的万能机器人 ( r o s s u m su n i v e r s a lr o b o t s ) 。剧中的人造机器取名为捷克语r o b o t a ，英语r o b o t 由此衍生而来，在我国则被译为“机器人 。二战后，多连杆操纵器和数控机床的出现 为机器人的产生准备了技术条件，机器人便从幻想世界走进现实世界的发展中。 宋健院士曾指出：“机器人的诞生、机器人学的建立和发展是本世纪自动控制最具 说服力的成就，是2 0 世纪人类科学技术进步的重大成就。”瞄。机器人从爬行到学会两 腿直立行走，仅仅花了2 0 年，而人类的这一过程则经历了上百万年。现在全世界已经 拥有将近1 0 0 万台机器人，有近万家工厂在生产机器人，销售额每年增长2 0 以上，机 器人工业和技术得到了前所未有的飞速发展。机器人能够使用工具，能看、能听、能说， 并且已经能够进行一些决策和思考的智能行为。其应用也从传统的加工制造业逐渐扩展 到军事、海洋探测、宇宙探索等领域，并开始进入家庭和服务行业。作为一种先进的机 电一体化产品，机器人技术的发展与自动控制技术的发展息息相关。自动控制系统是机 器人的中枢神经，它控制着机器人的思维、决策和行为。几乎所有的自动控制技术都在 机器人的设计上得到过应用。近些年来，智能控制的发展十分迅速，这必然将促使机器 人的智能化水平达到一个新的高度。 1 2 路径规划的定义 移动机器人最基本的路径规划问题是在完全已知的静态障碍物之间为机器人寻找 一条从给定的起始点到目标点的满足一定优化指标的无碰撞路径。以a s 表示无碰撞的 自由位形空间，路径规划问题可以描述为：给定一个起始结点b e g i n g 标结点e n d g ，在 a s 中寻找一条连接这两点的连续曲线，并满足某些性能指标。例如：行走路线距离最短、 行走时间最少、工作代价最小，或者确定不存在这样的连接。 1 3 路径规划问题的分类 路径规划根据对环境信息的把握程度可划分为全局路径规划和局部路径规划。其 中，全局路径规划需要掌握关于环境的所有信息，根据环境地图进行大粒度的路径规划， 在全局路径规划算法领域，目前使用的方法主要包括p e t r i 网算法、基于数据融合的模 基丁智能计算的机器人路径规划研究 糊规则、神经网络算法、人工势场法、计算几何法和遗传算法等等；局部路径规划只需 要了解行进中的机器人周围的障碍物信息，并在其行走过程中，分析、处理传感器采集 的信息以更新其内部环境表示，从而确定出机器人在地图的当前位置及其局部的障碍物 分布情况以选出从当前结点到某一子目标结点的较优弧。 从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划，局部路 径规划属于动态规划。本课题主要探讨如何利用蚁群算法解决机器人的全局路径规划问 题。 1 4 路径规划问题的环境表达 机器人的路径规划主要包括环境建模、路径搜索、路径平滑几个环节。 1 环境建模 环境建模是机器人路径规划的重要环节，目的是建立一个便于计算机进行路径规划 使用的环境模型，即将机器人实际工作的物理空间抽象成算法能够处理的抽象空间，实 现相互间的映射。合理的环境模型要求是便于计算机存储、处理、更新和使用。在本课 题中，环境模型的建立采用栅格法。环境模型建立后，任何一条路径( 可行路径或者不 可行路径) 都可以采取一定的表达方式。 2 路径搜索 路径搜索阶段是在环境模型的基础上应用蚁群算法寻找一条行走路径使预定的性 能函数获得最优值；路径搜索的结果通常是以环境模型的方式表达，例如，由结点序列 组成的路径形式或者由直线与曲线段序列组成的路径形式。 3 路径平滑 搜索出的路径并不一定是一条机器人可以跟踪的可行路径，需要作进一步处理与平 滑才能成为一条实际可行的路径。 1 5 国内外研究现状及发展趋势 机器人路径规划发展历程移动机器人的路径规划方法很多 1 l j 在该研究领域的发展 过程中，里程碑式的成就主要有： ( 1 ) 1 9 6 6 年，j e d o r a n 和d m i c h i e 将图论的原理应用于路径规划之中，开始了这 一领域的研究。 大连理t 大学硕士学位论文 ( 2 ) 1 9 6 8 年，w e h o w d e n 提出了著名的“搬沙发问题 ，用来处理机器人路径规 划中的几个问题。 ( 3 ) 1 9 6 8 年，p h a r t 、n n i i s s o n 和b r a f a e l 针对遍历型经典d i j k s t r a 算法运算 速度慢的缺点，提出了优化性的a 木算法，这一成果成为机器人学规划研究的经典性基础。 ( 4 ) 1 9 7 1 年，r e f i k e s 、p h a r t 和n n i i s s i o n 提出了s t r i p s 方法。 ( 5 ) 1 9 7 9 年，t l o z a n op e r e z 和m a w e s l e y 提出了路径搜索的概念，用来处理存 在障碍物空间的路径规划问题。同年，j a l b u s 提出任务分解的方法，这一方法后来总 结成为n i s t r c s 方法的核心，用来处理包含有嵌套多步路径规划的问题。 ( 6 ) 1 9 8 1 年，t l o z a n op e r e z 提出了机器人位置空间( c o n f i g u r a t i o ns p a c e ) 的 概念，将机器人缩小为点，同时将障碍物按比例相应的扩张，使得机器人能够在这个新 的空间中自由移动，这样可以大大简化机器人路径规划中碰壁问题的处理，这一概念也 经常被翻译为自由空间或结构空间。 ( 7 ) 1 9 8 3 年，m j u l l i e r e 、l m a r c e 和h p l a c e 提出了近似于栅格法的环境建模思 想，这一方法随后被e l f e s 和m o r a v e s 进一步完善成型。 ( 8 ) 1 9 8 5 年，j e h o p c r o f t 、d a h o s e p h 和s n w h i t e s i d e s 分析了二维有界空间 的机器人的几何特征，以及与路径规划之间的约束关系。 ( 9 ) 1 9 8 5 1 9 9 5 年的十年问，众多的经典路径规划方法被提出来，并且被逐步改善 和丰富，例如人工势场法、距离变换法、p r m 随机路图法等。 ( 1 0 ) 上世纪9 0 年代，人工神经网络、遗传算法和模糊算法等被成功地应用于移动 机器人的路径规划中，取得了很多成果。 到本世纪初，机器人路径规划的研究已经获得了大量的成果，一般的机器人路径规 划问题也得到了一定程度上的解决，但仍然存在有一些特殊的路径规划问题尚未得到较 好的解决。 移动机器人的路径规划方法根据其运用处理算法的不同，可以分为两类：经典方法 和智能方法8 儿2 。 1 经典方法 经典方法大致可以分为以下四类：基于图的方法、基于栅格的方法、势场法和数学 编程法。 ( 1 ) 基于图的方法瞄 在基于图的路径规划方法中，路径图由捕捉到的存在机器人的一维网格曲线在自由 空间中的结点组成，所建立起来的路径图可以看作是一系列标准路径，而路径的初始状 基丁智能计算的机器人路径规划研究 态和目标状态同路径中的点相对应，这样路径规划问题就演变为在这些点之间搜索路径 的问题。 需要指出的是，基于图的路径规划方法大多是在对工作空间进行显式的全局几何分 析的基础上，产生一个机器人位形空间的完整表示，进而开始有效的路径搜索，这种规 划方法能确保找到可行路径，或者证明并不存在可行路径，所以这种方法是完备的。虽 然确定性的方法能够提供完备的解，但实现起来却有一定的难度，在复杂的情况下计算 量会急剧膨胀。即使能够把随机的思想引入到路径规划中，通过随机式的路径规划以随 机采样的方式获得对位形空间的描述，在此基础上进行路径搜索，但是其缺点是仅具有 概率意义上的完备性。 ( 2 ) 基于栅格的方法川1 2 1 栅格法是由w e h o w d e n 在1 9 6 8 年提出的，他在进行路径优化时采用栅格表示地图， 在处理障碍物边界时，避免了复杂的计算。并且，栅格法易于实现计算机的建模、存储、 处理、更新与分析。该方法将机器人的工作空间按照一定的规则划分为多个简单区域， 一般称为栅格。这些栅格构成一个连通图，对该连通图进行搜索，获得连接起始栅格和 目标栅格的路径，这条路径通常由一系列栅格的序号来表示。 在利用栅格法建模的环境地图中，可以大大提高各种路径搜索方法的工作效率，获 得较好的路径规划结果。 ( 3 ) 势场法 势场法是由k h a t i b 首先提出的，他把机器手或移动机器人在环境中的运动视为一 种在抽象的人造受力场中的运动。目标点对机器人产生“引力 ，障碍物对移动机器 人产生“排斥力 ，最后求出合力来控制机器人的运动瞄。 势场法实际上是对机器人运行环境的一种抽象描述。势场法因其简单性和优美性受 到很多学者的青睐，但是后来通过实验研究，发现势场法存在以下缺陷：第一，容易陷 入局部最优点，即运动过程中存在合力为零的点；第二，将环境信息压缩成单一合力， 容易造成有价值信息的流失；第三，出现障碍物时会振荡，导致移动不稳定，这是最大 的局限性。 ( 4 ) 数学编程法 数学编程的方法用一组不等式来表示机器人的碰壁约束，机器人运动的起点和终点 分别用一个函数的起始条件和终止条件来表示，同时设定一个最优评价函数，这样就将 路径规划问题转化为一个纯数学的最优求解问题，利用计算机编程计算求解系统的最优 路径。 一4 一 大连理工大学硕士学位论文 2 智能路径规划方法 近2 0 年来，智能化方法的深入研究也带动了基于智能方法的机器人路径规划研究， 其中比较成熟的智能路径规划方法主要有模糊逻辑方法、神经网络和遗传算法。 ( 1 ) 基于模糊逻辑的机器人路径规划比副比 基于模糊推理的路径规划方法参考人的驾驶经验，通过查表的方法，实现实时局部 路径规划。这种方法通过移动机器人上装配的感应器来分辨障碍物，克服了其它方法的 缺点，在动态变化的未知环境中能够进行实时规划。该方法最大的优点是实时性非常好， 但是模糊隶属函数的设计、模糊控制规则的制定主要靠人的经验，如何得到最优的隶属 函数以及控制规则是该方法最大的问题。近年来一些学者引入神经网络技术，提出一种 模糊神经网络控制的方法，效果较好，但复杂度太高。 ( 2 ) 基于神经网络方法的机器人路径规划 基于神经网络方法的机器人路径规划，研究了障碍物形状和位置已知情况下的机器 人路径规划算法。其能量函数的定义利用了神经网络结构，根据路径点位于障碍物内外 的不同位置选取不同的动态运动方程，规划出的路径达到了折线形的最短无碰路径，计 算简单、收敛速度快。另外，在神经网络路径规划方法的基础上，引进线形再励的自适 应变步长算法，这种方法实现了步长的自适应选择，使路径规划速度比原来的神经网络 规划有了很大的提高。 将神经网络算法应用于机器人路径规划的最大不足之处在于其过长的运算时间，而 且在机器人运动空间数据不够详细完备时，还可能发生不收敛或所规划路径不可行的问 题。 ( 3 ) 基于遗传算法的机器人路径规划 遗传算法是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观 点，通过自然选择、交叉、变异等作用机制，实现各个个体适应性的提高。这一点体现 了自然界中“物竞天择、适者生存 进化过程。1 9 6 2 年h o l l a n d 教授首次提出了遗传算 法的思想，吸引了大批的研究者将其迅速推广到优化、搜索、机器学习等方面，并奠定 了坚实的理论基础。 但是，由于遗传算法本身具有容易陷入局部最优的缺陷，因此，在应用于机器人路 径规划时，仍然存在无法搜索到实际存在的可行路径的可能。 ( 4 ) 基于其它智能方法的机器人路径规划u u 除了模糊方法、神经网络和遗传算法这三种应用比较广泛的智能化路径规划方法 外，还有一些其它的智能化方法。 借鉴生物学中细胞生死平衡理论和基因控制的思想，提出了将其抽象成数学工 基于智能计算的机器人路径规划研究 具，并用其处理移动机器人路径规划的初步设想旧。 在分析车型移动机器人的运动学特性的基础上，设计一种适用于该类机器人路 径搜索与规划的免疫算法咄。 综上所述，这些路径规划方法都在一定程度上解决了机器人的路径规划问题，但是， 由于各种算法自身的局限，使得路径规划问题的探讨仍具魅力，新的算法也在不断地涌 现与发展。 大连理工大学硕士学位论文 2 移动机器人路径规划 2 1 全局路径规划 在环境信息全部己知的情况下，机器人的路径规划完全离线( o f - li n e ) 进行，即通 过一定算法，根据环境状况为机器人计算出一条可行路径。即全局路径规划方法，这种 方法依据己获取的全局环境信息，给机器人规划出一条从起点至终点的运动路径。规划 路径的精确程度取决于获取环境信息的准确程度。全局路径规划规划方法通常可以寻找 最优解，但需要预先知道准确的全局环境信息。通常该方法计算量大，实时性差，不能 较好地适应动态非确定环境。基于环境建模的全局路径规划的方法主要有：自由空间 哺“、构型空间法。和栅格法等。 全局规划方法主要是以基于c 空间的自由空间法等各种几何法以及拓扑法为主，它 包括环境建模和路径搜索两个子问题。最初开始研究路径规划的问题，主要采用基于直 角坐标空间的假设和检验方法，它是由p i e p e r 于1 9 6 8 年提出的，也是最早的机器人避 障方法。此法由三个步骤组成：第一，在初始点和目标点之间先假设一条路径：第二，为 了避免可能的碰撞，检验路径上一组选定的点：第三，如果发现碰撞，则通过检查导致 碰撞的障碍物来修改这条路径。对于修改后的运动再重复上述过程，直到完成无碰路径 规划。这种早期的全局规划方法比较简单，但实时性差，无法按指标优化路径。2 0 世纪 8 0 年代初，来自麻省理工学院人工智能实验室的切z a n o p e r e z 提出了基于c 空间的 自由空间法，并得到国内外很多学者的青睐，与之相关的各种几何法和拓扑法也应运而 生。 2 1 1 自由空间法 自由空间法旧闪。采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间， 并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划，此方法比较灵活， 即使起始点和目标点改变，也不必重构连通图，但是算法的复杂程度与障碍物的多少成 正比，且不能保证任何情况下都能获得最短路径。因而该方法仅适用于路径精度要求不 高，机器人速度不快的场合。自由空间法用于机器人路径规划可以分为两个步骤： ( 1 ) 寻空间问题。在指定的环境中，确定机器人的安全位置，使它不与已有的其他 物体相碰撞。将机器人简化为一个点，同时相应地“膨胀 环境中的障碍物体，从而形 成另外一个空间障碍区。这样，通过构造一个虚拟数据结构，将运动物体和障碍物的几 何约束关系转化到另外一个虚拟数据结构空间，从而简化问题的求解。 基丁智能计算的机器人路径规划研究 ( 2 ) 寻路径问题。在指定的环境中，确定机器人从初始位置移动到目标位置的安全 路径，使其在移动过程中不与任何障碍物发生碰撞。经过前面的空间变化，将问题进 步形式化为“可见 图的搜索问题。搜索从起始位置到目标位置的最短路径就可以得到 机器人的最短安全路径，进而确定具体的系统解决方案。 2 1 2 构型空间法 构型空间法。是目前研究移动机器人路径规划的一个基本工具，其基本思想是用构 型空间中的一个点来表征移动机器人的位置与方向。 如图2 1 所示，机器人的起点为s ，目标点为g ，s 、g 之间存在一些障碍物0 。、0 ：、 0 3 等( 把障碍物都看作为圆) 。规划任务为搜索一条由s 点到g 点的路径长度较短的无碰 路径。构型空间法的主体思想为：在已知环境下，将s 、g 、0 。、0 。、0 。每两点之间相互 连线，这些连线之间的交点以及和障碍物边缘的交点分别称为l ，互，l ，l ，这些交 点和s 、g 两点构成了一个交织网( 图中黑实线部分) ，再基于蚁群优化算法在这些线路 上行走和避障，经过一定时间的行走后，一条较优路径基本形成。其路程函数可表示为： f 。y l ； ( 2 1 ) 钎 其中 必。j ) 2 + 叫尸f 哪豌+ 聊 ( 2 2 ) i 目rf ，f + 1 曰形 ( 2 1 ) j r 阿l ( 2 2 ) 中，l ；表示为每一步的路程，m 是在行进中需要的几个关节点。尺 为第j 个障碍物的半径，o r 表示在遇到障碍物时沿边缘走需要的路程， 舨乏j 夏丁i 瓦而为在走直线时的距离，睨为第l 个障碍物上的点集。 大连理工大学硕士学位论文 图2 1 构型空间法示意图 为了简化问题，通常将机器人缩小为一点，将其周围的障碍物按比例相应地进行拓 展，使机器人在障碍物空间中能够任意移动而不与障碍物及其边界发生碰撞。目前研究 比较成熟的有可视图法( v - - - - g r a p h ) 和优化算法( 如d i j k s t r a 法哺1 a 木搜索算法心。等) 。 最常用的方法是可视图法，可视图法通过起始点和目标点及障碍物的顶点在内的一 系列点来构造可视图。即在一个无向图中，将移动机器人的起始点与终止点以及移动机 器人运动环境中各障碍物的顶点表征为点的形式，连接这些点使某点与其周围的某可视 点相连，即要求机器人和障碍物各顶点之间、目标点和障碍物各顶点以及各障碍物顶点 与顶点之间的连线均不能穿越障碍物，也即直线是可视的。从而移动机器人的有效路径 就是这样的一些点之间与障碍物不相交的相互连接的线段。搜索最优路径的问题就转化 为经过这些可视直线从起始点到目标点的最短距离问题。可视图法将机器人，目标点和 多边形障碍物的各顶点进行组合连接，连接的直线视为弧，使用这种方法时，缺乏灵活 性，一般需要机器人停止在障碍前搜集传感器数据，并且它受传感器精度影响较大。 一9 一 基于智能计算的机器人路径规划研究 优化算法( o p t i m i z a t i o na l g o r i t h m ) 优化算法可以删除一些不必要的连线以简化可 视图，从而缩短搜索时间，求得最短路径。但是，优化算法缺乏灵活性，一旦起点和目 标点改变，就必须重构可视图，并且搜索效率也较低。 2 1 3 棚格法 栅格法u 圳是由w e h o w d e n 在1 9 6 8 年提出的。他在进行路径规划时采用栅格( g r i d ) 表示地图。在处理障碍物的边界时，避免了复杂的计算。栅格法将机器人的工作环境分 解成一系列具有二值信息的网格单元，并假设工作空间中障碍物的位置和大小己知且在 机器人运动过程中不会发生变化。用尺寸相同的栅格对机器人的二维工作空间进行规 划，栅格大小以机器人自身的尺寸为准。若某一栅格范围内不含任何障碍物，则称此栅 格为自由栅格；反之，称为障碍栅格。这样，自由空间和障碍物均可表示为栅格块的集 成。栅格的表识方法有两种：直角坐标法和序号法。 栅格法的模型一般按照如下方法表示：首先按照机器人及其有限的活动场地大小进 行栅格的定义和场地的栅格划分。为便于讨论，假设机器人的有限活动场地为矩形，机 器人在场地上占据的空间也为小矩形。将矩形场地平均划分为多个小矩形栅格，以保证 机器人可以在其中自由移动。对栅格划分好的场地进行编号，编号方法可以采用序号法 等。于是，用栅格法便可以完全表示的机器人活动场地。针对每个栅格位置的不同，将 栅格分为两大类：边界栅格、中间栅格。对于中间栅格，假设其邻接周围没有障碍物，下 一步可以向邻接的8 个方位搜索。8 个方位分别为：右下、右、右上、上、左上、左、左 下、下。按照栅格编号规律，容易预知这8 个方位的序号及其与当前位置栅格序号的差 值。对于边界栅格，下一步搜索的方位表中要去掉不可达栅格序号。 栅格法以栅格为单位记录环境信息，栅格大小对环境信息存储量的大小和规划时间 的长短有着重要影响，栅格划分大了，环境信息存储量小，规划时间短，但分辨率就低； 反之，虽然分辨率高了，但规划时间长。可以看出，栅格粒度越小，障碍物的示会越精 确，但同时会占用大量的存储空间，算法的搜索范围将按指数增加栅格的粒度太大，规 划的路径会很不精确。所以栅格粒度大小的确定，是栅格法中的主要问题。 2 2 局部路径规划算法 当机器人对环境信息部分了解或全部未知时，机器人需要通过传感器对环境进行探 索，并通过对传感器反馈信息的分析进行实时路径规划，即通常所说的在线( o i l l i n e ) 规划，未知环境下的机器人路径规划问题包含了机器探索、机器发现、机器学习的智能 大连理工大学硕士学位论文 行为过程，在硬件设备( 包括移动机器人平台、传感器设备、定位系统等) 充分保证的情 况下，机器人被赋予在没有预先环境信息的状况下从环境中给定的出发点出发，最终到 达目标点的任务。在这一任务中，机器人的探索、发现是由传感器设备完成的，机器人 对环境信息的学习与掌握是依靠指导其行为的算法过程实现的。在线规划也即局部路径 规划，局部规划方法侧重考虑机器人探知的当前局部环境信息，这使机器人具有较好的 避碰能力。现有的不少移动机器人路径规划方法都采用局部方法，其规划仅依靠传感系 统实时感知的信息。与全局规划方法相比，局部规划更具实时性和实用性：对动态环境 具有较强适应能力：其缺点是由于仅依靠局部信息，有时会产生局部极值点或振荡，无 法保证机器人能顺利地到达目标点。这类方法包括：人工势场法、遗传算法、模糊逻辑 算法1 3 1 钔、1 神经网络方法n 5 1 、蚁群算法n 6 1 、粒子群算等。 2 2 1 人工势场法 人工势场法由k 五a t i b 于1 9 8 6 年提出，基本思想是构造目标位姿引力场和障碍物 周围斥力场共同作用的人工势场，搜索势函数的下降方向来寻找无碰撞路径。图1 2 为 建立的人工势场，o 和g 分别表示障碍物和目标，势场函数、吸引力函数、排斥力函数、 势场角度函数分别表示如下 妒；1 d f o 一1 d ，暑 e = l ( a d ，。) “ a ，- ( 兄+ e ) ，( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) 基于智能计算的机器人路径规划研究 图2 2 人工势场示意图 人工势场法是移动机器人局部在线避碰最常用的方法之一，其原理是：移动机器人 在一个虚拟的力场中运动，障碍物被斥力势场( u o 包围，其产生的排斥力( f r ) 随机器人与 障碍物距离的减少而迅速增大，方向背离障碍物；目标点被引力势场。) 包围，其产生 的吸引力( f a ) 随机器人与目标位姿的接近而减小，方向指向目标点；然后按各个障碍物和 目标位姿产生的人工势能的总和，取势函数梯度下降的方向( 即沿排斥力矢量和吸引力 矢量和的方向) 来实现无碰路径规划。在该势场中的移动机器人受到其目标位姿引力场 和障碍物周围斥力场的共同作用，朝目标前进。由于机器人是受引力和斥力的合力的作 用，合力为零时，机器人将停止前进，即陷入局部极小点，机器人不能到达目标位置。 在k h a t i b 研究机器人手臂在笛卡儿空间中如何直接由任务相关的参数、运动、受力来 控制其运动的问题中，k r o g h 引入了一个重要的概念：广义势场( g e n e r a l i z e d f i e l d ) ， 即既考虑位置，又考虑速度量和单位的使用。 常用的有以下几种势场：牛顿型势场、圆形对称势场、超四次方势场、调和势场及 虚拟力场。在人工势场中，障碍物被看作斥力场，目标被看作引力场，所以障碍物对机 器人产生斥力，目标对机器人产生引力，通过求引力和斥力的合力来控制机器人的运动。 人工势场法结构简单，计算量小，实时性好。因而广泛应用于实时避障和平滑轨迹控制 大连理工大学硕士学位论文 方面。但是在局部最优解的问题上容易产生死锁现象( d e a d l o c k ) 现象，从而可能导致 机器人陷入局部最优点。 人工势场法结构简单，计算量小，实时性好。因而广泛应用于实时避障和平滑轨迹 控制方面。但是在局部最优解的问题上容易产生死锁现象( d e a d l o c k ) 现象，从而可能 导致机器人陷入局部最优点。 2 2 2 遗传算法 遗传算法( g e n e t i e a l g o r i t h m s 简称g a ) 是由美国m i c h i g a n 大学的j o h n h o l l a n d 教授 于加世纪6 0 年代末创建的。它来源于达尔文的进化论和孟德尔、摩根的遗传学理论， 通过模拟生物进化的机制来构造人工系统。遗传算法的研究有着相当悠久的历史，至今 已经形成了非常成熟的理论。遗传算法应用到了很多领域。从1 9 8 5 年在美国卡耐基梅 隆大学召开的第一届国际遗传算法会议到1 9 9 7 年5 月i e e e 的t r a n s a e t i o n s o n e v o l u t i o n a r yc o m p u t a t i o n 创刊，遗传算法作为具有系统优化、适应和学习的高性能计算 和建模方法的研究渐趋成熟。遗传算法是一种自适应全局优化概率搜索算法，它不同于 枚举法、启发式算法、搜索算法等传统的优化方法，主要有以下特点： ( 1 ) 自组织、自适应和学习性( 智能性) 。遗传算法消除了算法设计中的一个最大障 碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施， 因此，它可用来解决复杂的非结构化问题，具有很强的鲁棒性。 ( 2 ) 直接处理的对象是参数的编码集而不是问题参数本身。 ( 3 ) 搜索过程中使用的是基于目标函数值的评价信息，搜索过程既不受优化函数连 续性的约束，也没有优化函数必须可导的要求。 ( 4 ) 具有显著的隐并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单 点。它的并行性表现在两个方面：一是遗传算法是内在并行的；二是遗传算法的内含并 行性。 ( 5 ) 形式上简单明了。 遗传算法是一种多点搜索算法，也是目前机器人路径规划研究中应用较多的一种方 法。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息，且作为并行算法其隐 并行性适用于全局搜索，所以解决了其它一些算法无法解决的问题。国内外很多专家、 学者等在这方面作了大量研究，并取得了很多成果。孙树栋等实现了离散空间下移动机 器人路径规划新方法，该方法采用栅格序号作为个体的编码形式，与传统的二进制编码 方法相比，具有编码长度短、易于进行遗传操作等优点。在该方法中，提出了间断无障 碍路径概念，引入插入和删除算子，方便了遗传算子的实现，保证了路径的连续和可行 基丁智能计算的机器人路径规划研究 性。但该路径规划是基于确定环境模型的，所以有其局限性。在离散空间下路径规划中， k a z u o s u g i h a r a a n d j o h n s m i t h 进行了更深入的研究，他们对栅格序号采用二进制编码， 随机产生障碍物位置和数目，在搜索到最优路径后再在环境空间中随机插入障碍物，以 此来模拟环境变化，仿真结果验证了其有效性和可行性。但是，规划空间的栅格法建 模有其自身的缺陷，所以还有待改进。周明等提出一种连续空间下基于遗传算法的移动 机器人路径规划方法，该方法在规划空间时有别于离散空间下的栅格法，而是在利用链 接图建模的基础上，先通过图论中成熟的算法粗略搜索出可行路径，再用遗传算法调整 路径点得到最优路径。这种编码方法效率较高，不会产生无效路径，使用基本遗传算法 就可以完成路径规划问题。但对于复杂环境链接图的建立有一定困难。此外，遗传算法 运算速度低，进化众多的规划要占据较大存储空间和运算时问。 2 2 3 模糊逻辑算法 模糊逻辑算法是基于实时传感信息的一种在线规划方法。模糊有向图是引入节点发 生故障概率的一种符号有向图。节点分别表示系统的各个部件，分支及其方向表示部件 因果联系及作用方向。节点可以用正号、零和负号来分别表示相对j 下常技术状况的正偏 移、无偏移和负偏移：分支可以用正号、零和负号来表示作用方向。h u r t m u s t s u n n a n n 等 提出一种未知环境下的高级机器人模糊导航方法，由八个不同的超声传感器来提供环境 信息，然后利用基于模糊控制的导航器计算。 2 2 4 神经网络方法 神经网络是一门新兴交叉学科，始于2 0 世纪4 0 年代，是人类智能研究的重要组成 部分，已成为脑科学、神经科学、认知科学、心理学、计算机科学、数学和物理学等共 同关注的焦点。它模仿人脑神经网络的结构和某些工作机制建立一种计算模型。神经网 络的研究已经进入更加成熟的发展阶段，其中一个很重要的标志是越来越多的心理学 家、神经生理学家、医学工作者、数学家以及计算机科学联合起来，开展跨学科的研 究，以探讨神经网络的机理、功能以及相应的模型，并且尽量与应用结合。 神经网络作为一个高度并行的分布式系统，为解决机器人系统实时性要求很高的问 题提供了可能性，并应用于智能自主移动机器人导航与路径规划等方面。在本研究中， 解决路径规划问题的思路是：利用神经网络来描述环境约束并计算碰撞能量函数。将迭代 路径点集的碰撞能量函数与距离函数的和作为优化目标函数，通过求优化目标函数的极 值，确定点集的运动方程，最终使迭代路径点集趋向于最优规划路径。禹建丽等提出了 一种基于神经网络的机器人路径规划算法。 人连理工大学硕士学位论文 禹建丽又引进了线性再励的自适应变步长算法，提高了机器人路径规划速度，研究 了障碍物形状和位置己知情况下的机器人路径规划算法，其能量函数的定义利用了神经 网络结构，规划出的路径达到了折线形的最短无碰路径，该方法计算简单、收敛速度快。 刘成良等提出了基于神经网络的机器人无碰撞路径规划方法，给出了无碰撞轨迹规划的 人工神经网络算法，证明了其可行性，为神经网络真正用于机器这些信息，规划机器人 路径：李彩虹等提出了一种在未知环境下移动机器人的模糊控制算人控制提供了基础。陈 宗海提出了一种在不确定环境中移动机器人的路径规划方法，采用基于案例的学习算 法，进行案例的匹配、学习和扩充，使用a r t - 2 2 神经网络实现，提高了路径规划的效 率，以满足移动机器人在线路径规划的实时性要求。樊长虹等针对移动机器人的未知环 境下采用了一种局部连接h o p f i e l d 神经网络规划器。对任意形状环境，a n n 中兼顾处 理了“过近 和“过远 来形成安全路径，而无需学习过程。为在单处理器上进行有效 的在线路径规划，提出用基于距离变换的串行模拟，加速了数值势场的传播，该方法具 有较高的实时性和环境适应性。 2 2 5 模拟退火算法 模拟退火算法最早的思想由m e t r o p o l i s 在1 9 5 3 年提出，是模拟加热熔化的金属的 退火过程。在金属退火过程中，往往先将金属加温熔化，使其中的分子可以自由运动， 然后逐渐降低温度，使分子形成低能态的晶体。在1 9 8 3 年儿k i r k p a t r i c k 2 】成功地将模拟 退火算法应用在组合优化问题中。模拟退火算法是模拟热力学中经典粒子系统的降温过 程，来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度下降时，系统近似 处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函 数的全局极小点。这种算法模拟固体退火过程，故称之为“模拟退火算法( s i m u l a t e d a n n e a l i n g a l g o r i t h m ，s a ) ，【2 】1 3 l 。 设优化问题的一个解i 及其目标函数f ( i ) 分别与固体的一个微观状态i 及其能量双等 价，令随算法进程递减的控制参数t 担当固体退火过程中的温度t 的角色，则对于控制 参数t 的每一取值，算法持续进行“产生新解一判断一接受舍弃 的迭代过程对应着固 体在某一恒定温度下趋于热平衡的过程，也就是执行了一次m e t r o p o l i s 算法。从某一初 始状态出发，经过大量解的变化后，可以求得给定控制参数值时组合优化问题的相对最 优解。然后减小控制参数t 的值，重复执行m e t r o p o l i s 算法，就可以在控制参数t 趋于 零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降温，才能使 固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也必须缓慢 衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。 基于智能计算的机器人路径规划研究 模拟退火算法用m e t r o p o l i s 算法产生组合优化问题解的序列，并由与m e t r o p o l i s 准 则对应的转移概率月确定是否接受从当前解i 到新解j 的转移，公式如下 f1 厂( j ) s 厂( f ) p ( 滂d 葛1e x p ( 掣) 舢) 朋 ( 2 7 l f 开始让t 取较大的值( 与固体的溶解温度相对应) ，在进行足够多的转移后，缓慢减 小t 的值( 与“徐徐降温相对应) ，如此重复，直至满足某个停止准则时算法终止。因 此，模拟退火算法可视为递减控制参数时m e t r o p o l i s 算法的迭代。 简单的模拟退火算法步骤为： 任选一个初始解x 0 ；x i - x o , k = o ；t o = t m 缸( 初始温度) 。 若在该温度内达到循环停止条件，则到。否则，从领域n ( x i ) 中随机选一x i ， a f t j = f ( x j ) 一f ( x i ) ；若f t j 0 ，则x i = x j ；否则，若e x p ( - - a f , j t t ) r a n d o m ( o ，1 ) ，则 x i = x j ；重复。 t k + 1 = d ( t k ) ，k = k + 1 ；若满足停止条件，终止计算；否则回到。 输出最后结果一一最优解。 模拟退火算法依据m e t r o p o l i s 准则接受新解，因此除接受优化解外，还在一个限定 范围内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所在。开始时t 值 大，可能接受较差的恶化解；随着t 值的减小，只能接受较好的恶化解；最后在t 值趋于零 值时，就不再接受任何恶化解了。这就使模拟退火算法既可以从局部最优的“陷井 中 跳出，更有可能求得组合优化问题的整体最优解，又不失简单性和通用性。因此，对大 多数组合优化问题而言，模拟退火算法要优于局部搜索算法。 但是，模拟退火算法收敛速度相当慢，尤其是在普通微机上运行时，需要花费大量 时间。 2 2 6 粒子群算法 k e n n e d y 和e b e r h a r t 等于1 9 9 5 年开发出一种新的演化算法一粒子群优化算法。它 的基本思路为：在问题的定义空间内将一定数量的等位微粒作随机分布，然后根据各微粒 在解空间中所处地位的相关信息作为微粒的优劣赋值记录，同时对各微粒运动的最优历 史信息作好记录，在随后的每次计算循环中，当前微粒的运动模式都由其自身的最优历 史记录和群体的最优历史记录决定，直到整个粒子群体找到问题的最优解或者满足其他 相关停止条件。 人连理工大学硕士学位论文 相比其它进化算法，p s o 保留基于种群的全局搜索策略，避免复杂的个体操作，采 用简单的速度调整模型，仅利用特有的记忆使其可以动态地跟踪当前搜索状况，具有较 强地鲁棒性和快速地寻优速度，且不需要借助问题的特征信息。因此，p s o 作为一种更 高效的并行搜索算法，非常适合于对实时性要求较高的复杂优化问题进行求解。基于 p s o 的高效寻优特性，本文将其应用于动态环境下对实时性要求较高的机器人路径规划 中。 粒子群算法虽然具有收敛速度快，算法简单，容易编程实现等特点，但p s o 算法 也有一些严重的缺陷，其一是容易陷于局部极值点，导致得不到全局最优解，到目前为 止，p s o 算法还不能从理论上严格证明收敛于任何类型函数的全局极值点。其二是p s o 算法本身的参数设置，当参数选择不当时，会导致寻优过程中粒子的多样性迅速消失， 造成算法“早熟收敛”。基于p s o 的不足，己经有大量学者对算法进行了改进研究，