（生物医学工程专业论文）基于改进蚁群算法的机器人路径规划研究.pdf

哈尔滨工程大学硕十学位论文 a b s t r a c t p a t hp l a n n i n gt e c h n o l o g yi sn o t o n l yt h em o s ti m p o r t a n tp a r ti nr o b o t n a v i g a t i o nb u ta l s oa l li m p o r t a n tc o m p o n e n to fa u t o n o m o u sm o b i l er o b o t s s oi ti s s t i l la ni m p o r t a n ta s p e c to ff u r t h e rr e s e a r c h t h em e t h o d sc u l t e n t l vu s e da r e g e n e t i ca l g o r i t h m s ，n e u r a ln e t w o r k s ，a r t i f i c i a lp o t e n t i a lf i e l d ，a n dc o m p u t a t i o h a l g e o m e t r ya n ds oo n h o w e v e r , t h ea b o v em e t h o di nac o m p l e xe n v i r o n m e n ti s o b v i o u s l yi n s u f f i c i e n t ，e s p e c i a l l yi n t h ec i r c u m s t a n c e so fc o n t a i n i n gal a r g e n u m b e ro fi r r e g u l a ro b s t a c l e sw h e na l g o r i t h m so re x c e s s i v ea l g o r i t h mc a l ln o tb e s o l v e di nt h e o p t i m a ls o l u t i o n a n ta l g o r i t h mi san e we m e r g i n gi n s p i r a t i o n o p t i m i z a t i o na l g o r i t h m ，w h i c hn o to n l yc a ns o l v ed i f f e r e n tt y p e so fo p t i m i z a t i o n p r o b l e m s ，b u ta l s o i n s o l v i n gt h en u m e r o u sp r o b l e m sa l s oc a l lo b t a i nt h e e x t r e m e l yg o o dp e r f o r m a n c e i nt h ef i e l do fr o b o tp a t hp l a n n i n gm a n ys c h o l a r s a l s oh a v ed o n eal o to fr e s e a r c hi na p p l i c a t i o no ft h ea l g o r i t h m s t h i sa r t i c l ei sb a s e do na n tc o l o n ys y s t e m ，p r o f i t sf r o mt h ea n ts y s t e mw i t h e l i t i s t s t r a t e g y , r a n k - b a s e dv e r s i o no fa n ts y s t e m ，m a x - m i na n ts y s t e m ， b e s t - w o r s ta n ts y s t e m ，s e l f - a d a p t i v ea n tc o l o n ya l g o r i t h mt o i m p r o v ea n t a l g o r i t h mt h i n k i n g ， a u t o a d a p t i v ea l g o r i t h m t o i m p r o v e a n t a l g o r i t h m t h i n k i n g ，t h e no n ek i n do fp a t hp l a n n i n ga l g o r i t h mb a s e do nt h ei m p r o v e m e n t a n tc o l o n ys y s t e ma l g o r i t h mr o b o ti s p r o p o s e d c o m p a r e dw i t ho t h e ra n tc o l o n y a l g o r i t h m ，t h i sa l g o r i t h mm a i n l yh a v es e v e r a lf o l l o w i n ga s p e c t so ft h e i m p r o v e m e n t ：t h ei n t r o d u c t i o no ft h ee l i t ea n ts t r a t e g y , a n di n n o v a t i v eu s eo ft h e t h i se l i t ef l l i n k i n g t h ei n t r o d u c t i o no fv i s u a ld e t e c t i o nc a p a b i l i t yt oe n h a n c e dt h e d e t e c t i o na n t sv i s i o n ；u s e sp a t ho p t i m i z a t i o nf e a t u r e sa n do p t i m i z a t i o nr e s u l t so f t h er e g u l a ro u t p u t ，i m p r o v i n gt h ea v a i l a b i l i t yo fw a l k i n gr o b o tp a t ha n do f r e a l - t i m e p l a n n i n ga l g o r i t h m ；p r o v i d i n gan e ws t r a t e g yf o rt h et r a n s f e ro fs t a t e a n t s ，t h e ns t r e h g t h e n e dt h ea n t s s e n s eo fd i r e c t i o nt ot h e t a r g e t ；u s eo ft h e d e a d l o c kd e t e c t i o nm e c h a n i s m s ，a n dp r o p o s e dt h e c o r r e s p o n d i n gr e l i e v i n g s t r a t e g yo fd e a d l o c k t h i sa r t i c l eh a da l s od e v i s e dp l a n n i n gs y s t e ma sap a r to ft h e 一 哈尔滨r t 程大学硕士学位论文 i 薯昌每宣写号；暑i 宣宣鲁宣葺亍专奄；i 薯；= ；暑稿1一i i i 韵 w h o j er o b o ts y s t e m ；t h ea l g o r i t h mw i l l a l w a y sr u nf o rt h et i m e l yp r o c e s s i n go f e n v i r o n m e n t a li n f o r m a t i o na n dt h ei m p a c to f c h a n g e i nt h e c o m p l e t i o n o ft h e p r o c e s so ft h ep a p e r , w ea l s o d e v e l o pa c o m p r e h e n s i v ea l g o r i t h ms i m u l a t i o n p l a t f o r mf o r 也ed e m o n s t r a t i o no ft h e 2 l l g o r i t h r n ，a n a l y s i s ，v e r i f i c a t i o na n dc o n v e r g e n c eo fr e s e a r c h ，s i m u l a t i o nr e s u l t s a j s of u l l yd e m o n s t r a t e st h ef e a s i b i l i t ya n dt h ee f f e c t i v e n e s so f t h ea l g o r i t h m k e yw o r d s ：a n ta l g o r i t h m ；e l i t i s ts t r a t e g y ；v i s i o nd e t e c t i n g ；d e a d l o c k d e t e c t i o n ； p a t hp l a n n i n g 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：丞壹尘 日 期：加奄荔年；月丫日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 本课题研究的意义 机器人是2 0 世纪人类最伟大发明之一，伴随着社会和科学技术的迅速发 展，机器人的应用领域也不断扩大，在天空、地面、大洋海底，从工业拓广 到农、林、牧、渔甚至进入寻常百姓家。 路径规划技术是机器人导航中最重要的环节，同时也是自主式移动机器 人技术的一个重要组成部分，仍然是研究的一个重要方面，随着各种新方法 和新技术的不断出现，对路径规划的研究有了更广阔的天地。下面以恩格尔 伯格于1 9 8 5 年研制的“护士助手 机器人为例做一下简单介绍。 “护士助手 是自主式机器人，它主要可以完成以下各项任务：运输医 疗器材和设备；为病人送饭；送病例、报表及信件：运送药品；运送试验品 及试验结果：在医院内送邮件及包裹等。机器人中装有医院的建筑物地图， 在确定目的地后机器人利用路径规划算法自主沿走廊行走，由结构光视觉传 感器及超声传感器探测突然出现的静止或运动物体。它的全方位触觉传感器 保证机器人不与人和物相碰撞。 由以上可知机器人如何规划自己的行走路线，如何有效躲避障碍物，对 整个机器人系统来说都是非常重要的。而对机器人路径规划算法的研究就是 从全局环境的角度来考虑如何有效解决这两个问题。我国在智能移动机器人 研究方面虽然已经取得了一定的成果，如地面自主导航车、水下自主机器人 和飞行机器人等。但由于起步较晚，在研究和应用方面都落后于一些西方国 家，而且有些方面还没有达到完全实用。因此，进行移动机器人路径规划算 法的研究，仍然具有一定的理论意义和工程应用意义。 1 2 路径规划器的评价标准 在路径规划研究成果中，设计者可有多种技术选择，像机器人的其他方 面一样，技术的选择取决于机器入运行的生态小生境。评估路径规划器的标 准包括1 ： ( 1 ) 算法复杂度：算法是不是太复杂或者占用太多存储空间，以至于机 哈尔滨工程大学硕士学位论文 器人不能执行或存储空间不够。 ( 2 ) 地形表示的充分性：许多研究工作是基于室内是平地的环境。室外 机器人可能工作在粗糙地形亡，有陡峭斜坡或者未估计到的区域，例如滑溜 沙地或泥浆。如果路径规划算法所产生的路径只能针对适于航行或不适于航 行区域的两种极端情况，那么在复杂多变的环境中运行时，机器入将陷入团 境。 ( 3 ) 机器人平台物理限制表示的充分性：机器入有物理限制，最影响路 径规划的限制在于机器人是否是完整的。注意到完整机器人能够原地转弯， 故它们能在狭小地方转身。这时路径规划算法不必考虑机器人转动半径。同 样机器人也可能不是圆的为了研究目的而制造的机器人通常是圆的，因此 它们原地转弯时不会碰撞任何东西。非圆形机器人会引起更多的复杂性，为 在狭窄大厅转身，它必须关注后面以确保它不会控到任何东西。 ( 4 ) 与反应层的兼容性：路径规划器应为慎思式，然而在混合型结构中， 应层应负责实现该路径，因此需要有从路径规划器到反应层进行转换的技术。 ( 5 ) 能支持地图的修正和重新规划：路径规划需要一个先验地图，但这 张地图可能被证明是严重错误的。因此机器人可能根据一幅地图出发，然后 发现地图的错误，通过更新地图实现重新规划。显然允许修取已有觌划结果 比废弃已有规划并从头开始计算更易被人接受。 1 3 路径规划算法分类 所谓路径规划是指移动机器人在有障碍的环境中，寻找一条从起点到终 点的路径，这条路径不仅要使机器人躲避障碍，而且要在一定指标下如距离、 时间、能量等尽可能的优化。 根据对环境信息的掌握程度不同，路径规划可分为全局路径规划和局部 路径规划。其中，全局路径规划环境信息完全己知，包括障碍物的位置及其 几何性质；全局规划方法包括环境建模和路径搜索两个子问题，一般情况下 先对环境信息进行建模，然后采用某种搜索方法搜索最优路径；全局规划是 一种事前规划，因此对机器人系统的实时计算能力要求不高，规划结果是全 局的、较优的，但是对环境模型的错误及噪声鲁棒性差。局部路径规划，环 境信息完全未知或部分未知，通过传感器在线地对机器入的工作环境进行探 2 哈尔滨工程大学硕士学位论文 测，以获取障碍物的位置和几何性质等信息，这种规划需要搜集环境数据， 并且对该环境模型的动态更新能够随时进行校正；局部规划方法将对环境的 建模与搜索融为一体，要求机器人系统具有高速的信息处理能力和计算能力， 对环境误差和噪声有较高的鲁棒性，能对规划结果进行实时反馈和校正，但 是由于缺乏全局环境信息，所以规划结果有可能不是最优的，甚至可能找不 到正确路径或完整路径 本文主要研究基于蚁群算法的全局规划算法。 1 4 路径规划算法的研究现状 1 自由空间法 自由空间法剐采用预先定义的如广义锥形和凸多边形等基本形状构造自 由空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划， 此方法比较灵活，即使起始点和目标点改变，也不必重构连通图，但是算法 的复杂程度与障碍物的多少成正比，且不能保证任何情况下都能获得最短路 径。因而该方法仅适用于路径精度要求不高，机器入速度不快的场合。自由 空间法用于机器人路径规划可以分为两个步骤。 ( 1 ) 寻空间问题。在指定的环境中，确定机器人的安全位置，使它不与 已有的其他物体相碰撞。将机器人简化为一个点，同时相应地“膨胀”环境 中的障碍物体，从而形成另外一个空间障碍区。这样，通过构造一个虚拟数 据结构，将运动物体和障碍物的几何约束关系转化到另外一个虚拟数据结构 空间，从而简化问题的求解。 ( 2 ) 寻路径问题。在指定的环境中，确定机器人从初始位置移动到目标 位置的安全路径，使其在移动过程中不与任何障碍物发生碰撞。经过前面的 空间变化，将问题进一步形式化为“可见 图的搜索问题。搜索从起始位置 到目标位置的最短路径就可以得到机器人的最短安全路径，进而确定具体的 系统解决方案。 2 可视图法( v i s i b i l i t yg r a p hm 甜的m 可视图法通过起始点和目标点及障碍物的顶点在内的一系列点来构造可 视图。即在一个无向图中，将移动机器人的起始点与终止点以及移动机器人 运动环境中各障碍物的顶点表征为点的形式，连接这些点使某点与其周围的 哈尔滨工程大学硕士学位论文 器人不能执行或存储空间不够。 ( 2 ) 地形表示的充分性：许多研究工作是基于室内是平地的环境。室外 机器人可能工作在粗糙地形亡，有陡峭斜坡或者未估计到的区域，例如滑溜 沙地或泥浆。如果路径规划算法所产生的路径只能针对适于航行或不适于航 行区域的两种极端情况，那么在复杂多变的环境中运行时，机器入将陷入团 境。 ( 3 ) 机器人平台物理限制表示的充分性：机器入有物理限制，最影响路 径规划的限制在于机器人是否是完整的。注意到完整机器人能够原地转弯， 故它们能在狭小地方转身。这时路径规划算法不必考虑机器人转动半径。同 样机器人也可能不是圆的为了研究目的而制造的机器人通常是圆的，因此 它们原地转弯时不会碰撞任何东西。非圆形机器人会引起更多的复杂性，为 在狭窄大厅转身，它必须关注后面以确保它不会控到任何东西。 ( 4 ) 与反应层的兼容性：路径规划器应为慎思式，然而在混合型结构中， 应层应负责实现该路径，因此需要有从路径规划器到反应层进行转换的技术。 ( 5 ) 能支持地图的修正和重新规划：路径规划需要一个先验地图，但这 张地图可能被证明是严重错误的。因此机器人可能根据一幅地图出发，然后 发现地图的错误，通过更新地图实现重新规划。显然允许修取已有觌划结果 比废弃已有规划并从头开始计算更易被人接受。 1 3 路径规划算法分类 所谓路径规划是指移动机器人在有障碍的环境中，寻找一条从起点到终 点的路径，这条路径不仅要使机器人躲避障碍，而且要在一定指标下如距离、 时间、能量等尽可能的优化。 根据对环境信息的掌握程度不同，路径规划可分为全局路径规划和局部 路径规划。其中，全局路径规划环境信息完全己知，包括障碍物的位置及其 几何性质；全局规划方法包括环境建模和路径搜索两个子问题，一般情况下 先对环境信息进行建模，然后采用某种搜索方法搜索最优路径；全局规划是 一种事前规划，因此对机器人系统的实时计算能力要求不高，规划结果是全 局的、较优的，但是对环境模型的错误及噪声鲁棒性差。局部路径规划，环 境信息完全未知或部分未知，通过传感器在线地对机器入的工作环境进行探 2 哈尔滨工程大学硕士学位论文 测，以获取障碍物的位置和几何性质等信息，这种规划需要搜集环境数据， 并且对该环境模型的动态更新能够随时进行校正；局部规划方法将对环境的 建模与搜索融为一体，要求机器人系统具有高速的信息处理能力和计算能力， 对环境误差和噪声有较高的鲁棒性，能对规划结果进行实时反馈和校正，但 是由于缺乏全局环境信息，所以规划结果有可能不是最优的，甚至可能找不 到正确路径或完整路径 本文主要研究基于蚁群算法的全局规划算法。 1 4 路径规划算法的研究现状 1 自由空间法 自由空间法剐采用预先定义的如广义锥形和凸多边形等基本形状构造自 由空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划， 此方法比较灵活，即使起始点和目标点改变，也不必重构连通图，但是算法 的复杂程度与障碍物的多少成正比，且不能保证任何情况下都能获得最短路 径。因而该方法仅适用于路径精度要求不高，机器入速度不快的场合。自由 空间法用于机器人路径规划可以分为两个步骤。 ( 1 ) 寻空间问题。在指定的环境中，确定机器人的安全位置，使它不与 已有的其他物体相碰撞。将机器人简化为一个点，同时相应地“膨胀”环境 中的障碍物体，从而形成另外一个空间障碍区。这样，通过构造一个虚拟数 据结构，将运动物体和障碍物的几何约束关系转化到另外一个虚拟数据结构 空间，从而简化问题的求解。 ( 2 ) 寻路径问题。在指定的环境中，确定机器人从初始位置移动到目标 位置的安全路径，使其在移动过程中不与任何障碍物发生碰撞。经过前面的 空间变化，将问题进一步形式化为“可见 图的搜索问题。搜索从起始位置 到目标位置的最短路径就可以得到机器人的最短安全路径，进而确定具体的 系统解决方案。 2 可视图法( v i s i b i l i t yg r a p hm 甜的m 可视图法通过起始点和目标点及障碍物的顶点在内的一系列点来构造可 视图。即在一个无向图中，将移动机器人的起始点与终止点以及移动机器人 运动环境中各障碍物的顶点表征为点的形式，连接这些点使某点与其周围的 哈尔滨工程大学硕士学位论文 某可视点相连，即要求机器人和障碍物各项点之间、目标点和障碍物各顶点 以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是可视的。 因此，移动机器人的有效路径就是这样的一些点之间与障碍物不相交的相互 连接的线段。搜索最优路径的问题就转化为经过这些可视直线从起始点到目 标点的最短距离问题。可视图法将机器人、目标点和多边形障碍物的各顶点 进行组合连接，连接的直线视为弧，使用这种方法缺乏灵活性，一般需要机 器人停止在障碍前搜集传感器数据，并且受传感器精度影响较大。 3 栅格法f 伽d sm e t h o d ) 将机器人工作环境分解成一系列具有二值信息的网格单元四，多采用四 叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该法以栅格为 单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接 影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息 存储量小，规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱； 栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境信 息存储量大，规划时间长。 4 人工势场法 该方法是由k h a t i b 提出的虚拟力法h 。其基本思想是把移动机器人在环 境中的运动视为一种在抽象的人工受力场中的运动，即在环境中建立人工势 场的负梯度方向指向系统的运动控制方向。目标点对移动机器人产生引力， 障碍物对移动机器人产生斥力。其结果是使移动机器人沿“势峰 间的“势 谷”前进，最后求出合力来控制移动机器人的运动。这类方法的突出的优点 是系统的路径生成与控制，直接与环境实现了闭环，从而大大加强了系统的 适应性与避障性能。但是，人工势场法也存在若干缺陷如在陷阱区域容易陷 入局部最小，在相近的障碍物之间不能发现路径等。 5 模糊逻辑算法 模糊逻辑算法是基于实时传感信息的一种在线规划方法。模糊有向图是 引入节点发生故障概率的一种符号有向图。节点分别表示系统的各个部件， 分支及其方向表示部件因果联系及作用方向。节点可以用正号、零和负号来 分别表示相对正常技术状况的正偏移、无偏移和负偏移：分支可以用正号、 4 哈尔滨工程大学硕士学位论文 零和负号来表示作用方向。h a r t m u s ts t m m a n 等提出一种未知环境下的高级机 器入模糊导航方法，由八个不同的超声传感器来提供环境信息，然后利用基 于模糊控制的导航器计算这些信息，规划机器人路径 6 。神经网络方法 神经网络方法是一种仿效生物神经系统的信息处理方法。它是一个高度 并行的分布式系统，处理速度高且不依赖于系统精确的数学模型，还具有自 适应和自学习的能力一个神经网络包括以各种方式联接的多层处理单元 神经网络对输入的数据进行非线性变换，从而完成了聚类分析技术所进行的 从数据到属性的分类。目前神经网络的类型很多，大多数的神经网络都用于 增强移动机器人避障能力与路径规划上，通常采用的是三层感知器模型和算 法，禹建耐卅等提出了一种基于神经网络的机器人路径规划算法，研究了障 碍物形状和位置己知情况下的机器人路径规划算法，其能量函数的定义利用 了神经网络结构，根据路径点位于障碍物内外的不同位置选取不同的动态运 动方程，规划出的路径达到了折线形的最短无碰路径，计算简单，收敛速度 快。陈宗海等提出了一种在不确定环境中移动机器人的路径规划方法，将全 局路径规划分解为局部路径规划的组合，为了提高规划的效率，在避障规划 中采用了基于案例的学习方法，以神经网络实现案例的匹配学习和扩充，满 足了规划的实时性要求。 7 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，o a ) 是一种基于自然群体遗传演化机制的 高效探索算法，它是美国学者h o l l a n d 于1 9 7 5 年首先提出来的。它摒弃了传 统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间 进行随机化搜索。它将问题域中的可能解看作是群体的一个体或染色体，并 将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进 化过程，对群体反复进行基于遗传学的操作( 遗传，交叉和变异) ，根据预定 的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规 则不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优 个体，求得满足要求的最优解。 孙树栋等用遗传算法完成了离散空间下机器人的路径规划唧，并获得了 哈尔滨工程大学硕士学位论文 较好的仿真结果。但是，该路径规划是基于确定环境模型的，即工作空间中 的障碍物位置是己知的、确定的。和在采用离散空间进行路径规划的同时， 将问题更深入化，栅格序号采用二进制编码，统一确定其个体长度，随机产 生障碍物位置及数目，并在搜索到最优路径后再在环境空间中随机插入障碍 物，模拟环境变化，通过仿真结果验证了算法的有效性和可行性。但是，规 划空间栅格法建模还存在缺陷，若栅格划分过粗，则规划精度较低若栅格划 分太细，则数据量又会太大。 周明等提出一种连续空间下基于遗传算法的机器人路径规划方法川，该 方法在规划空间利用链接图建模的基础上，先使用图论中成熟算法粗略搜索 出可选路径，然后再使用遗传算法来调整路径点，逐步得到较优的行走路线。 该方法的染色体编码不会产生无效路径，且仅使用基本遗传算法就可以完成 路径规划。但是该方法对于环境复杂、障碍物数目较多的情况，链接图的建 立会有一定的困难。在遗传算法的改进上周明等提出一种遗传模拟退火算法， 利用遗传算法与模拟退火算法相结合来解决机器人路径规划问题，有效地提 高了路径规划的计算速度，保证了路径规划的质量。 8 粒子群算法口s o ) 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 算法也有一些严重的缺陷，其一是容易陷于局部极值点，导致得不到全 6 哈尔滨工程大学硕士学位论文 局最优解，到目前为止，p s o 算法还不能从理论上严格证明收敛于任何类型 函数的全局极值点。其二是p s o 算法本身的参数设置，当参数选择不当时， 会导致寻优过程中粒子的多样性迅速消失，造成算法“早熟收敛一。 9 蚁群算法 a c o 算法是c o l o r n i 和d o r i g o 等在2 0 世纪9 0 年代初提出的一种新型分 布式智能仿生类算法q ，它模拟和借鉴了现实世界中蚂蚁种群的觅食行为特 征圳。 蚁群算法在机器人路径规划中的应用早已有所研究，但是在国内还属于 比较新的领域朱庆保，张玉兰提出了基于栅格法的机器人路径规划蚁群算 法刀，该算法用栅格法对场景进行建模，模拟蚂蚁的觅食行为，由多只蚂蚁 协作完成最优路径的搜索。朱庆保提出了动态复杂环境下的机器人路径规划 蚂蚁预测方法”9 1 ，该方法模拟蚂蚁的觅食行为，由多组蚂蚁采用最近邻居搜 索策略和趋近导向函数相互协作完成全局最优路径的搜索。在此基础上用虚 拟蚂蚁完成与动态障碍物碰撞的预测，并用蚁群算法进行避障局部规划。朱 庆保还提出了复杂环境下的机器人路径规划蚂蚁算法嗍，用于复杂的静态环 境下的机器人路径规划。可见，动态环境下的机器人路径规划方法也适合于 静态环境。 蚁群算法也有其明显的缺陷，如它的计算量较大，搜索时间较长，易于 陷于局部最优解。 1 5 论文的主要研究内容和章节安排 本文在基本蚁群算法的基础上，以栅格对环境建模，并借鉴传统精英策 略的的基本思想对机器人路径规划算法进行了研究。算法中引入视觉探测功 能、路径优化功能、死锁检测和解除功能，并对精英思想进行了创新的应用。 在算法研究的过程中构建了完备仿真系统平台，对算法演示、分析、验证起 到了关键性的作用。 根据研究的内容论文可分为五个章节。 第l 章对机器人路径规划进行了简要概述，介绍了路径规划的定义、分 7 哈尔滨工程大学硕士学位论文 类和路径规划的评价标准，阐述了机器人路径规划的研究现状等基本问题。 第2 章作为论文的理论基础和后续章节的需要，对蚁群算法的基本原理、 基本实现作了介绍，并对几种改进的蚁群算法作了较详细的论述。 第3 章介绍了机器人系统的智能组织系统和系统体系结构，以便对整个 机器人系统的控制方式有个整体的认识。 第4 章是论文核心部分，详细介绍了一种改进蚁群算法在机器人路径规 划领域中的应用。它包括了机器人运动环境的建模、改进算法的基本思想和 具体改进策略等几个主要部分。 第5 章作为算法改进成败的一个评价标准，首先对算法仿真系统作了简 要介绍，然后对算法的仿真结果作出了详细的分析、比较和验证 最后对论文的工作进行必要的总结，并指出了算法中仍然存在的问题， 为以后以后研究工作指明了方向。 8 哈尔滨1 j 程大学硕j ：学位论文 第2 章蚁群算法概述 2 1 概述 蚁群算法最初由意大利学者d o r i g om 于1 9 9 1 年首次提出，其本质是一 个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制、易于与 其它算法结合等优点。如今这一新兴的仿生算法已经成为人工智能领域的一 个研究热点，目前对其研究已渗透到多个应用领域，并由解决一维静态优化 问题发展到解决多为动态组合优化问题。如今在国内外许多学术期刊和重要 国际会议上，蚁群算法已经成为交叉学科中一个非常活跃的前沿性研究问题。 近年来，随着蚁群算法应用领域的扩展，该算法在机器人路径规划、多 机器入协作、机器人控制等方面均取得了丰富的研究成果。 2 2 基本蚁群算法原理 蚁群算法模拟了蚂蚁群体觅食行为，是一种新的计算智能模式，它基于 如下基本假设弘“： ( 1 ) 蚂蚁之间通过信息素和环境进行交互。每只蚂蚁仅根据其周围的局 部环境作出反应，也只对其周围的局部环境产生影响。 ( 2 ) 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁 的行为实际上是其基因的适应性表现，即蚂蚁是反应性主体。 ( 3 ) 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上， 单只蚂蚁的行为是随机的，但蚂蚁可通过自组织过程，形成高度有序的群体 行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包括两个基本阶段： 适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身 的结构，路径上蚂蚁经过的蚂蚁的越多，信息素越大，该路径容易被选择； 时间越长，信息素会越小；在协助阶段，候选解之间的通过信息交流，以期 望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一种多智能体系统，其自组织机制使的蚁群算法不需 要对所求问题的每方面广都有详尽的认识。蚁群算法的自组织机制本质上 9 哈尔滨工程大学硕七学位论文 是在没有外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态 演化，其逻辑结构如图2 1 所示。 图2 1 基本蚁群算法的逻辑结构 由图2 1 可见，先将具体的组合优化问题表述成规范的格式，然后利用 蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点， 同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随 后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化问 题的最优解。 2 3 基本蚁群系统模型 为了便于理解，此处我们以求解平面上一个，2 阶旅行商问题( t s p ) 为例， 来说明基本蚁群算法的原理b ”。t s p 问题就是给定一组城市，求得一条遍历 所有城市的最短回路的问题。该问题空间可以用一个静态图来描述，并且可 以用距离矩阵d = z ， 来描述问题空间本身的特征。在t s p 问题中，城市数 目称为该问题的阶数。为了模拟实际蚂蚁的行为，首先说明如下符号的意义。 d = f ，= 1 ，2 刀) ，表示城市f 和城市，之间的距离( 欧式空问的距 y 离) ； 1 0 哈尔滨工程大学硕十学位论文 仍，= 1 谚，表示边( 上的启发函数，也称能见度，表示由城市f 转移 到城市，的期望程度： ，z ，表示蚁群中蚂蚁的数量； r , j ( t ) ，表示f 时刻边( 忉上的信息素浓度； a r 。) ，表示t 时刻边( 上的信息素增量； 口，表示信息启发因子，表示信息素轨迹的相对重要性： ，表示期望启发因子，表示能见度的相对重要性； p ，表示在时间间隔 ，+ 刀) 内信息量衰减的系数，其中o p ，j 按照公式( 2 - 1 ) 计算概率，此时蚂蚁采取“轮盘赌”的方 法选择下一个城市节点。随着时间的推移，以前留下的信息激素逐渐消逝， 用参数p 表示信息激素的残留程度，则参数l p 表示信息激素的挥发程度。 蚁群算法的信息激素更新主要有两种方式：在线更新和延迟更新。在线更新 方式是蚂蚁每移动一步，立即对所走的边上的信息激素进行更新；延迟更新 方式是蚂蚁完成一次遍历，再对所走过的边上的信息激素进行更新。经过刀 哈尔滨丁程大学硕十学位论文 个时刻，蚂蚁完成一次循环，即找到了一条遍历所有城市节点的回路，各路 径上信息激素要根据公式( 2 3 ) ，( 2 4 ) 作调整。 乃( t + n ) = p 乃( ，) + 毛( ，) ( 2 3 ) 勺( f ) = 芍( f ) ( 2 4 ) 其中，( f ) 表示第k 只蚂蚁，时刻在城市i 和歹之间留下的信息素增 量，不同的蚁群算法模型露( f ) 的表达方式不同。m d o r i g o 曾提出三种模 型：蚁周模型( a n t c y c l es y s t e m ) 、蚁量模型( a n t - q u a n t i t ys y s t e m ) 、蚁密模型 ( a n t d e n s i t ys y s t e m ) 。 蚁周模型 苟( ，) = 孑7 厶碧蠡蚂蚁七通过路径“ ( 2 - 5 ) 蚁密模型 哆( ，) = 孑 薯翥蚂蚁k 通过路径t ( 2 6 ) 蚁量模型 f ：( f ) ： 孑7 秀薯翥蚂蚁k 通过路径( 屯) ( 2 7 ) 其中，q 称为总信息量，为一个给定的常数；若采用在线更新方式，则厶为 第k 只蚂蚁到目前所走过路径的长度：若采用延迟更新方式，则厶为第k 只 蚂蚁遍历所有城市节点后得到的回路的距离。 经过实验证明，蚁周模型的性能要好于其他两个模型。国外学者在研究 蚂蚁系统的时候也是将主要研究活动放在了蚁周模型上，而放弃了其他两类 模型。 2 4 几种改进的蚁群算法 蚂燃( a n ts y s t e m ，简称a s ) 是第一个蚁群算法，被称为基本蚁群算 1 2 哈尔溪工程大学硕士学位论文 法。虽然a s 算法具有极强的发现较好解的能力，但同时也存在一些缺陷如 收敛速度慢，易出现停滞现象等，针对a s 算法的不足，许多学者对其进行 深入研究，提出一些改进的蚁群算法。 2 4 1 精英蚁群系统 带精英策略的蚂蚁系统( a n ts y s t e mw i t he l i t i s ts t r a t e g y , a s , ；, , , ) 是最早的 改进的蚁群算法，在某些方面它类似遗传算法中所使用的精英策略。在遗传 算法中精英策略的思想是为了保留住一代中的最适应个体，类似地，在么胁 中，为了使到目前为止所找到的最优解在下一次循环中对蚂蚁更有吸引力， 在每次循环之后给予最优解以额外的信息素增量。信息素按式( 2 8 ) 和式( 2 9 ) 进行更新 o + 1 ) = ( 1 一p ) 毛( f ) + f | ：，+ a t i ( 2 - 8 ) = f ； ( 2 9 ) 艺：偿如果蚂蚁七在本次循环中经过路黜 1 0否则 弓： 盯睾如果边( f ，_ ，) 是所找出最优解的一部分 【0否则 ( 2 1 0 ) ( 2 1 1 ) 其中，a r , j 是最优蚂蚁在边( f ，力上增加的信息素量；仃为最优蚂蚁数；r 为 所找出的最优解的路径长度。 2 4 2 基于排序的蚂蚁系统 和蚂蚁系统一样，带精英策略的蚂蚁系统有一个缺点，若在进化过程中， 解的总质量提高了，解元素之间的差异减小了，导致选择概率的差异也随之 减小，使得搜索过程不会集中在到目前为止的所找出的最优解附近，从而阻 止了对更优解的进一步搜索。当路径长度变得非常接近，特别是当很多蚂蚁 1 3 哈尔滨丁程大学硕士学位论文 沿着局部极优的路径进行时，则对短路径的增强作用被削弱了。 在遗传算法中，为了解决这种维持选择压力( s e l e c t i o np r e s s u r e ) 的问题， 一个可行的选择机制是排序，首先根据适应度对种群进行分类，然后被选择 的概率取决于个体的排序。适应度越高表明该个体越优，个体在种群中的排 名越靠前，则被选择的概率就越高。 将遗传算法中排序的概念可以扩展应用到蚂蚁系统中，称之为基于优化 排序的蚂蚁系统( r a n k b a s e dv e r s i o no f a n ts y s t e m ，a s 。邮k ) 。具体实施如下： 当每只蚂蚁都生成一条路径后，蚂蚁按路径长度排序，蚂蚁对激素轨迹量更 新的贡献根据该蚂蚁的排名u 的位次进行加权；此外，只考虑肌只最好的蚂 蚁。因此，可以有效避免上述的某些局部极优路径被很多蚂蚁过分重视的情 况发生。 2 4 3 蚁群系统 蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) 口4 1 是由m d o r i g o 和g a m b a r d e l l a 在1 9 9 6 年提出的，用于改善蚂蚁系统的性能。 蚁群系统在基本蚁群算法的基础上做了三个方面的改进。 ( 1 ) 状态转移规则为更好地利用新路径和关于问题的先验知识提供了方 法。 ( 2 ) 全局更新规则只用于最优的蚂蚁路径上。 ( 3 ) 在建立解决方案的过程中，应用局部更新规则。 蚁群系统的实现过程如图2 2 1 4 哈尔滨工程大学硕七学位论文 图2 2 蚁群系统流程图 1 蚁群系统状态转移规则 蚂蚁七由，节点转移到s 节点，其状态转移规则如下： s ：, 一r g m a x 。 e f ( ，“) 4 玎( “) 尹 【 s 如果g q o 按先验知识选择路径 否则按公式( 2 - 1 ) 进行概率选择 ( 2 1 2 ) 其中，g 是在 o ，1 】区间均匀分布的随机数，吼是一个参数( o 吼1 ) ， 哈尔滨工程大学硕士学位论文 s 为根据方程式( 2 1 ) 所选出的一个随机变量。 由公式( 2 一1 ) 和( 2 1 2 ) 产生的状态转移规则被称为伪随机比例规则。这 个状态转移规则，和前面所述的随机比例规则一样，都倾向于选择短的且有 着大量信息素的边作为移动方向。 2 蚁群系统全局更新规则 在蚁群系统中，只有全局最优的蚂蚁才被允许释放信息素。这种选择， 以及伪随机比例规则的使用，其目的都是为了使搜索过程更具有指导性：蚂 蚁的搜索主要集中在当前循环为止所找出的最好路径的领域内。全局更新在 所有蚂蚁都完成它们的路径之后执行，应用公式( 2 1 3 ) 对所建立的路径进行更 新。 r ( ，j ) 卜( 1 一口) f ( ，s ) + 口幸a r ( r ，s ) ( 2 - 1 3 ) 小一= 愕0 烈r ，幻等黜船 其中，口为信息素挥发参数，0 口 1 ；厶为到目前为止找出的全局最优路 径。式( 2 1 3 ) 规定，只有那些属于全局最优路径的边上的信息素才会得到增强。 全局更新规则的另一个类型称为迭代最优( i t e r a t i o n b e s t ) ，它不同于上述的全 局最优( g l o b a l b e s t ) 。在迭代最优中，式( 2 1 3 ) q b 使用了厶，代替三曲，厶为当 前迭代( 循环) 中的最优路径长度。并且，只有属于当前迭代中的最优路径才 会得到激素增强。实验表明，这两种类型对蚁群系统性能的影响差别很小， 全局最优的性能要稍微好一些。 3 蚁群系统的局部更新规则 在建立一个解决方案的过程中，蚂蚁应用式( 2 1 4 ) 的局部更新规则对它们 所经过的边进行激素更新。 f ( ，j ) 卜( ，s ) + p * a r ( r ，s ) ( 2 - 1 4 ) 其中，p 为一个参数，( 0 乃( f ) ，则设置乃( t ) - - r , i 。 若在每个选择点上，其中一个解元素上的轨迹量为f 。，而所有其他可 选择的解元素上的轨迹量为f n 则称m m a s 收敛。若m m a s 收敛，通过 始终选择信息素量最大的解元素所构造的解将与算法找出的最优解相一致。 m m a s 收敛的概念与停滞的概念有一点不同，停滞是指所有的蚂蚁都沿着