（计算机应用技术专业论文）基于蚂蚁自动分流的机器人路径规划新算法研究.pdf

南京师范大学硕士学位论文 摘要 移动机器人路径规划问题是机器人研究中的关键技术。一直以来是国内外学者们热衷的 课题然而，传统的路径规划方法都存在各自的缺陷寻求更佳的算法就成为该领域的一个 研究热点。本文首先依据真实蚂蚁具有自动分流功能这一本性，提出了一种机器人路径规划 全新蚂蚁算法该方法首先用栅格法对机器人运动环境进行建模，在此基础上，两组蚂蚁进 行相向觅食，当某节点被多只蚂蚁选择时，则自动分流，并且采用了目标导引启发函数，从 而扩大了搜索范围增强了搜索的多样性，有利于获得最优解帚l 加快收敛。随后本文提出了 一种基于自动分流蚂蚁算法的机器人路径滚动规划方法该方法首先将目标点映射在机器人 视野域内侧边界附近，规划出机器人局部最优路径，机器人根据此局部路径前进一步机器 人每前进一步就重复这一过程，最终机器人可沿一条全局优化的路径安全的到达终点。接着 针对自由链接图建模方法的不足，本文又研究了粒子群算法与自动分流蚂蚁算法融合的机器 人路径规划算法该方法首先用自由链接图建立机器人运动空间模型，在此基础上利用自动 分流蚂蚁算法进行全局搜索得到全局导航路径，然后用粒子群算法局部调节全局导航路径上 的路径点，得到更优路径文章最后针对栅格法建模的不足，研究了遗传算法与自动分流蚂 蚁算法融合的机器人路径规划算法该方法首先用栅格法建立机器人运动空间模型在此基 础上利用自动分流蚂蚁算法迸行全局搜索得到全局导航路径，然后用遗传算法局部调节全局 导航路径上的路径点，得到更优路径仿真结果表明，本文研究的算法都能有效的规划出机 器人路径，效果十分令人满意 关键词：移动机器人，路径规翅l ，蚂蚁算法，滚动规划，粒子群算法，遗传算法 南京师范大学硕士学位论文 a b s t r a c t p a t hp l a n i n go f m o b i l er o b o t si so n eo f k e yi s s u e si nr o b o t i c sr e s e a r c h i ti sa l w a y s af o c u st o p i cf o rt h er e s e a r c h e r sa l lo v e rt h ew o r l d h o w e v e r , t r a d i t i o n a lm e t h o d so f p a t hp l a n n i n ga l lh a v et h e i ro w n d r a w b a c k sr e s p e c t i v e l y t of i n da s u p e r i o ra l g o r i t h m f o rt h ep r o b l e mb e c o m e sa s t u d yh o t s p o ti nt h ef i e l d f i r s t l y , ad i f f i c u l ti s s u eo fr o b o t p a t hp l a n n i n gi nad u t t e r e de n v i r o n m e n ti st h a tp l a n e dp a t hi sg l o b a lo p t i m a l b a s e d o na u t o m a t i cd i f f i u e n ta n tn e wa n ta l g o r i t h mi sp r o p o s e d f i r s tt h e 嘶dm e t h o di s b u i l tt od e s c r i b et h ew o r k i n gs p a c eo ft h em o b i l er o b o t ，t h e nt h ef o r a g i n gb e h a v i o ro f a n ti ss i m u l a t e da n do p t i m a lp a t hs e a r c hi sf i n i s h e db ym a n ya n tc o o p e r a t i v e l y f u r t h m o r e ，t h es t r a t e g i e so fp r o b a b i l i s t i cs e a r c h , n e a r e s tn e i g h b o rs e a r c ha n d ag o a l g u i d i n gf i m c t i o na r ea p p l i e d t oe n a b l et h es e a r c h i n gt ob er a p i da n de f f i c i e n t s e c o n d l y , an o v e la l g o r i t h mf o rr o b o tr o l l i n gp a t hp l a n n i n gi sp r e s e n t e d i nt h e a l g o r i t h m , t h et a r g e ti sm a p p e di n t ot h ec l o s e s tn o d ei n s i d et h er o b o tv i s u a ld o m a i n a n das t a t i c ，b c a l l yo p t i m a lp a t hw h i c hr o b o tm a k e sas t e p f o l l o w i n gb yi s a c c o m p l i s h e d t h ep r o c e d u r eo ft h ea l g o r i t h mi sr e p e a t e do ne v e r yl o c o m o t i o ns t e po f r o b o ta n dr o b o tc a nf i n da n df o l l o wag l o b a l l yo p t i m a lp a t ht oa p p r o a c ht h et a r g e t w i 也o mt h er i s ko fc o l l i s i o n s t h i r d l y , ab a s e d0 1 1a n ta l g o r i t h m ( a a ) a n dp a r t i c l e s w a r mo p t i m i z e ro s o ) a l g o r i t h mf o rp a t hp l a n n i n go ft h er o b o ti sp r o p o s e d f i r s t t h em a k l i n k g r a p hi sb u i rt od e s c r i b et h ew o r k i n gs p a c eo ft h em o b i l er o b o t ，t h e n t h ea n t a l g o r i t h mi su s e dt oo b t a i nt h eg l o b a ln a v i g a t i o np a t h , a n dt h ep a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mi sa d o p t e dt og e tt h eb e t t e rp a t h f i n a u y , ab a s e do na n t a l g o r i t h m 阻qa n dg e n e t i ca l g o r i t h r n ( o a ) f o rp a t hp l a n n i n go ft h er o b o ti s p r o p o s e d f i r s tt h eg r i dm e t h o di sb u i l tt od e s c r i b et h ew o r k i n gs p a c eo ft h em o b i l e r o b o t , t h e nt h ea n ta l g o r i t h mi su s e dt oo b t a i nt h eg l o b a ln a v i g a t i o np a t h , a n dt h e g e n e t i ca l g o r i t h mi sa d o p t e dt og e tt h e b e t t e rp a t h o u rc o m p u t e re x p e r i m e n t s d e m o n s t r a t et h a tt h ea l g o r i t h m sa r er o b u s ta n ds t a b l e k e yw o r d s ：m o b i l er o b o t , p a t hp l a n n i n g , a n ta l g o r i t h m , r o l l i n gp l a n n i n g , p a r t i c l es w a r m o p t i m i z e r , g e n e t i ca l g o r i t h m n 学位论文独创性声明 本人郑重声明： i 、坚持以一求实、创新一的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研 究成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实 的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机 构已经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表 示了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 作者签名1 虱) 莶彗作者签名：l 必1 垒弱 日期：髫。竖边 南京师范大学硕士学位论文第一章绪论 第一章绪论 1 1 概述 1 1 1 研究背景及意义 移动机器人路径规划“。1 是机器人学中非常重要的研究分支，是研究机器人控制系统的 重要基础问题，因而得到了广大研究者的关注并成为经久不衰的研究热点，在这一领域取得 了很多重要成果，诸如传统的人工势场法臼一、a 宰算法日川等但传统的优化方法在机器人 路径规划这类复杂非线性优化问题中缺乏白适应性，计算太复杂优化过程缺乏鲁棒性偿1 ， 近年来，随着智能方法的广泛应用。机器人路径规划方法也有了长足的进展许多研究者把 目光放在了基于智能方法的路径规划研究上其中，应用较多的算法主要有：神经网络方法 7 硼、蚁群算法唑枷、遗传算法“、免疫算法“k 等与传统方法相比，智能方法具有更 大的灵活性、自主性和稳定性，在机器人技术领域具有更大的发展前途和研究空间因此机 器人路径规划算法向仿生算法发展是一个必然的趋势，特别是蚁群算法具有群体智能的特 点，用于机器人路径规划具有独特的优势，然而，传统的蚁群算法n 5 1 一方面存在算法初期信 息素匾乏导致搜索时间过长难以满足实时规划或导航的要求等缺陷另一方面不能扩大解的 搜索范围导致解空间的探索不够、搜索容易陷入局部最优导致搜索易于停滞1 ，难以保证每 次都能找到全局最优或者较优路径虽然文献c 1 7 较好地避免了搜索的局部停滞但是由于 只更新最优路径上的信息素，所以也会导致路径的搜索陷入停滞 自由空间法是常见的建模方法，由于其本身的缺陷导致不能保证任何情况下都能获得最 短路径锄。因而该方法仅适用于路径精度要求不高，机器人速度不快的场合如何使机器入 在这种环境下所走路径全局最优或较优，仍是有待解决的问题。 未知环境下机器人的运动规划问题一直是移动机器人研究领域的一个比较难解决的问 题在未知环境下，不仅机器人本身是运动的而且有的障碍物也是运动的如何保证在这 种复杂环境下使机器人所走路径全局最优或较优则一直是这一领域的个研究热点，更是一 个有待解决的难题 根据这些已有研究的不足及该领域的需求，在两个。基金项目的支持下本课题拟研 究一系列新的算法，其目标是：( 1 ) 解决传统的蚁群算法停滞及收敛时间过长的问题；( 2 ) 解决在已知及未知环境下使机器人所走路径全局最优的问题；( 3 ) 解决在使用自由空间建 模法时得到的路径往往不是最优或者较优的问题( 4 ) 为这一领域提供新算法，以促进这一 领域的技术进步 1 1 2 机器人路径规划国内外研究现状 路径规划根据机器人掌握环境信息的完整程度可以分为：环境信息完全已知的全局路径 规划和环境信息完全未知或部分未知的局部路径规划n k 嘲局部路径规划和全局路径规划 国家自然科学基金( 编号6 0 6 7 3 1 0 2 ) 和江苏省科自然科学基金( 编号b k 2 0 0 6 2 1 8 ) 南京师范大学硕士学位论文第一章绪论 并没有本质区别前者只是把全局路径规划的环境考虑得更复杂一些即环境是动态的。很 多适用于全局路径规划的方法经过改进都可以用于局部路径规划；而适用于局部路径规划的 方法都可以适用于全局路径规划 由于环境模型是已知的全局路径规划的设计标准是尽量使规划的效果达到最优在此 领域已经有了许多成熟的方法，包括可视图法【纠，自由链接倒建模方法嗍、栅格法洲、蚂 蚁算法瞰删、遗传算法协似1 等 在上述方法中栅格法建模是较为常用的方法之一，环境被量化成具有一定分辨率的栅 格，栅格大小直接影响环境信息存储量大小和规划时间长短栅格划分大了，环境信息存储 量小，规划时间短，但分辨率下降。在密集环境下发现路径的能力减弱；栅格划分小了，环 境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长嘲栅格 法经改进也广泛应用于路径规划，文献 4 3 设计了基于栅格法的实时避障和导航控制算法 文献 “ 将改进栅格法与回归预测结合该算法适用于具有静态和动态障碍物的移动机器人 规划路径问题。对栅格的改进采用以障碍物为单位记录的信息量大大减少克服了栅格法中 环境存储量大的问题。但它还有一个重要的缺陷即在无障碍物区，机器人还是按照栅格走折 线路径而折线是次优路径，增加了机器人到达目的地的时间到目前为止还没有很好的改 进方法 跟栅格法存在类似问题的还有自由链接图建模方法。在自由链接图建模方法中自由空间 实际上是障碍物的扩大，在该建模方法中机器人实际上沿着自由链接线的中点行走，而机器 人在保证安全距离的条件下是可以沿着障碍物的边界行走的疆因此使用这种建模方法时不 是任何情况下都能获得最短路径嘲虽然文献 4 5 提出了改进的方法但是存在局部最优问 题 智能算法在机器人路径规划中的应用是一个比较活跃的研究领域，蚂蚁算法就是其中之 一然而传统蚂蚁算法存在搜索时问过长、易于停滞的问题删为了克服这些缺点不少学 者提出了改进算法文献 1 5 】提出使用伪随机比例状态转移规则选择下个节点，仅让每一 代中最好的个体所走过的路径上的信息素进行更新，以加快收敛速度由于强化了最优信息 的反馈，会导致早熟、停滞现象嗍文献 3 3 提出最大一最小蚂蚁系统( m a x - l i i na n ts y s t e m ， 删a s ) ，对路径上的信息素进行限制，虽然在一定程度上避免了早熟、停滞现象，但在解的 分布较分散时收敛速度较慢虽然学者们提出了各种各样的改进蚂蚁算法，但所有的改进都 是基于原始模型的，仍然有不少关键理论和技术问题急需解决就目前改进的蚂蚁算法而言 仍有共同问题存在：由于其信息素加强正反馈的同时造成了早收敛h 町无法对解空间进一步 搜索，而不能发现全局最优路径信息素的更新不是很合理使最优路径、次优路径、不可行 路径之间的信息素差距不是很大，限制了搜索的多样性，容易陷入局部循环当中，以至于早 熟伽，而不能发现全局最优因此如何解决容易早熟、停滞和收敛速度之间的矛盾? 如何 在加大搜索空间的同时又能跳离局部最优解? 是该领域当前急需解决的问题，本文提出的自 2 南京师范大学硕士学位论文第一章绪论 动分流蚂蚁算法正是解决了上述问题 作为当前规划研究的热点问题，未知环境下的机器人路径规划得到了深入细致的研究 对于环境信息较为复杂的未知环境，还有很多需要解决的难题期待研究在国内文献 4 6 提出了基予滚动窗口的规划方流也取得了较好的效果。但文献 4 6 中滚动规划方法有时会 出现不能到达终点的情况嘲动态时交环境中，运动障碍物的位姿是随着时间不断变化的， 如何更好的避开动态及静态障碍物是需要解决的一个难点对环境信息完全未知的情况，机 器人没有任何先验信息，目前的规划方法大部分是以提高机器人韵避障能力为主而效果作 为其次。如何使二者都能尽善尽美，是一个值得研究的课题 1 1 3 本文的主要研究内容 本文的主要研究内容有以下三个部分： ( 1 ) 根据上述传统蚂蚁算法的不足之处，研究一种较为复杂环境下机器人路径规划自 动分流蚂蚁算法 ( 2 ) 动态环境下基于自动分流蚂蚁算法的机器人路径滚动规划算法及其避障策略 ( 3 ) 为解决自由链接图建模和栅格法建模上述不足之处，研究了自动分流蚂蚁算法和 粒子群算法、遗传算法相融合的融合算法 1 1 4 本文主要解决的闯题 本文主要解决了如下目题； ( 1 ) 本课题提出的自动分流蚂蚁算法主要是针对传统蚂蚁算法中正反馈可能导致早收 敛这一点，设计一个新蚂蚁算法新算法即能保证扩大搜索的范围，又能保证算法的收敛， 还缩短了规划时问本课题对该算法进行了实验分析，通过不断改进和完善达到了预期的效 果 c 2 ) 自由链接图建模和栅格法建模是常用的建模方法，但是很多算法没有解决建模方 法本身的缺陷，致使所得到的路径往往不是最优的。本课题利用融合算法基本解决了这个问 题 1 1 5 本文的主要创新点 目前，已经存在很多优化算法来解决机器人路径规划问题，但大都存在一定的局限性， 本课题旨在总结和分析现有算法的不足之处，设计一个高性能的机器人路径规划算法与已 有算法相比本文的创新之处在于： c 1 ) 对真实蚂蚁的最新研究成果表明m ：蚂蚁在觅食过程中，当某条路径上蚂蚁过 多时，蚂蚁具有自动分流功能根据这一研究成果，设计了一种新的仿生算法一自动分 流蚂蚁算法在该算法中，根据蚂蚁分流特点设计了启发信息，当某节点已被多只蚂蚁选 择时，后来的蚂蚁则自动分流到其它节点即先前的蚂蚁留下的信息素对后来的蚂蚁起到 抵制的作用，这样可以扩大搜索范围，增加解的多样性，跳出局部最优找到全局更优路 径解决了传统蚂蚁算法因早收敛而无法对解空间进步搜索，因容易停滞而陷入局部最 3 南京师范大学硕士学位论文第一章绪论 优的闯题 ( 2 ) 针对自由空间建模法本身的缺陷，即在自由空间建模方法中机器人实际上沿着 自由链接线的中点行走，因此使用这种建模方法时不是任何情况下都能获得最短路径伽 为此本课题利用滑动思维解决该问题，分别提出了基于蚂蚁分流的蚂蚁算法和粒子群算法 及遗传算法相结合的融合算，解决了栅格法和自由空间建模的不足另外，本课题还对两 个融合算法在同一环境下进行了实验对比 ( 3 ) 将自动分流蚂蚁算法应用到未知环境下的机器人路径规划中，设计了基于蚂蚁 自动分流的机器人滚动规划算法，并给出了遇到动态障碍物时的避障策略，而且对算法的 安全性进行了分析证明 1 2 论文的组织结构 本论文是笔者在研究生学习期间依据个人参与的课题项目的基础上，对智能算法在移动 机器人路径规划中的应用这一领域进行了深入的分析后的一个总结本论文共分七章如下： 第一章：绪论部分对本文的研究目的、内容、创新点进行了介绍 第二章：对机器人路径规划的现有的算法及其建模方法的研究现状进行了介绍 第三章：根据传统蚂蚁算法的不足之处及其对真实蚂蚁生活的最新研究，提出了基于 蚂蚁自动分流的机器人路径规划新算法 ， 第四章：将第三章提出的新算法应用到动态环境中，提出了基于蚂蚁自动分流的机器 人路径滚动规划算法 第五章：提出利用新蚂蚁算法找到全局导航路径，用粒子群算法局部搜索，两者相结 合解决链接图建模的不足的融合算法 第六章：提出利用新蚂蚁算法找到全局导航路径，用遗传算法局部搜索，两者相结合 解决栅格法建模的不足的融合算法 第七章：介绍本文的研究成果并给出值得进一步研究的问题。 南京师范大学硕士学位论文 第二章机器人路径规划方法概述 第二章机器人路规划研究方法概述 不论采用何种导航方式，智能移动机器人主要完成路径规划、定位和避障等任务路径 规划是自主式移动机器人导航的基本环节之一路径规划根据对环境信息的把握程度可划分 为全局路径规划和局部路径规财在全局路径规划算法领域，目前使用的方法主要包括：蚂 蚁算法、基于数据融合的模糊规贝i j 、神经网络算法、人工势场法、计算几何法和遗传算法等 等；局部路径规划只需要了解行进中的机器人周围的障碍物信息，并在其行走过程中，分析， 处理传感器采集的信息以更新其内部环境表示，从而确定出机器人在地图的当前位置及其局 部的障碍物分布情况以选出从当前结点到某一子目标结点的较优路径本章节主要对本课题 涉及到的机器人路径规划方法的研究现状进行阐述 2 1 基于蚂蚁算法的机器人路径规划 在2 0 世纪9 0 年代，意大利学者kd o r i g o y 1 l a n i e z z ，a c o l o r n i 等人从生物进 化的机理中受到启发，通过模拟自然界蚂蚁寻食的行为提出了一种全新的模拟进化算法； 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m 简称a c o a ) 近几年许多学者开始用 蚁群算法在机器人路径规划方面进行了一系列出色的研究工作脚喇 2 0 0 3 年樊小平等人嘲首先将基本蚊群算法引入到机器人路径规划研究领域，并尝试在蚁 群算法中通过调整避障系数，可以得到不同的优化轨迹但由于传统的蚁群算法存在一定的 不足，如算法收敛速度慢，不能解决复杂环境下尤其是具有凹型障碍环境的路径规划问题， 所以随后很多学者对其进行了改进文献 2 8 首先对传统蚁群个体进行行为解析为蚂蚁个 体引入了目标导向行为、惯性行为、沿障碍行走行为从而改善了算法的性能，克服了传统 蚁群算法不能应用于复杂环境的不足文献 2 9 首次将蚂蚁算法与栅格法环境建模相结合用 于机器人路径规划中，并提出了双蚂蚁思想，但该算法没有考虑机器人路径规划中的死锁问 题文献r 3 0 中的算法提出了蚂蚁死亡的概念即当蚂蚁无路可选时蚂蚁死亡重新初始 化一只蚂蚁，这样避免了死锬此文中也是采用双向蚂蚁相向搜索，但是两组蚂蚁采用的搜 索策略不同澳大利亚学者r u s s e l l m 设计了一种用于移动机器人的气味传感器导航机制 并深入分析了蚁群算法在该领域应用的鲁棒性瑞士学者m i c h a e l 等将蚁群算法的程序编入 微型机器人中。使众多微型机器人象蚂蚁一样协周工作，完成复杂任务这项研究成果已被 国际著名刊物( n a t u r e ) 报道嘲 但是目前蚂蚁算法用于机器人路径规划时所建立的模型与方案不是很成熟，仍具有很 大的可研究空间。机器人的路径规划问题属于一种带约束条件的连续函数优化问题，研究解 决此类问题的蚁群优化算法，能够扩大蚂蚁算法的应用领域，并探索与改进一种新的路径优 化算法，促进优化理论与实践的发展，并且为经济领域以及工程领域的优化问题( 如：生产 调度、系统控制、物流配送等) 提供借鉴 2 2 基于遗传算法的机器人路径规划 5 南京师范大学硕士学位论文 第二晕机器人路径规划方法概述 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜 索算法删1 由于其思想简单、易于实现以及表现出来的健壮性，遗传算法赢得了许多学者的 青睐特别是近年来在问题求解、优化和搜索、机器学习、智能控制、模式识别和人工生命 等领域取得了许多令人鼓舞的成就 根据遗传算法的流程将其应用于路径规划所需解决的问题如下：环境表示、路径编码、 构造适应度函数、构造选择算子、构造交叉算子和构造变异算予针对上述问题所提出的不 同解决办法构成了大量的基于遗传算法的路径规划算法解决方案舡嘲目前针对这些问题的 解决方法概述如下： 环境表示的解决方法：因为遗传算法要对路径进行编码，因此环境表示的方法将直接影 响到路径的表示一般而畜可以将原始环境表示为栅格，即采用栅格法建模嘲或者如文献 3 6 所示将环境划分为若干( 凸) 多边形区域，建立。紧凑”区域图，区域的权表示机器人在 区域内行走单位距离所需代价；也可以如文献 3 7 直接用二维笛卡几坐标表示环境，还可以 事先对环境做结构化处理比如文献r 3 8 将环境中可行区域用自由链接图表示，这样整个环 境就可以用链接图中的各个链接点来表示 路径编码的解决方法：经典的遗传算法使用二进制串来表示种群中的个体，因此许多基 于遗传算法的路径规划也采用二进制串来表示路径，串中的每一位代表环境中表示的一个单 位但是当所处环境比较复杂时表示路径的二进制串也较长使算法的搜索空问急剧扩大， 降低遗传算法的性能。针对复杂环境可以采用浮点数编码或符号编码以提高遗传算法性能和 保持更好的种群多样性姗文献 4 0 】在= 维结构化空间中，采媚栅格划分机器人工作空间， 将栅格序号采用二进制编码统一确定其个体长度，通过仿真结果验证了算法的有效性和可 行性 适应度函数构造方法：遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为 依据利用种群中每个个体的适应度值来进行搜索因此适应度函数的选取至关重要，直接 影响到遗传算法的收敛速度以及能否找到最优解一般而言，适应度函数是由目标函数变换 而成的对目标函数值域的某种映射交换称为适应度的尺度变换 路径规划的目标一般是对从起点到终点的可行路径选取时间最短或长度最短的一条路 径，因此根据路径编码的方式可以时间函数或路径长度函数映射为适应度函数。而各种针对 具体情况的算法的编码并不一致、规划目标也不相同，因此适鹿度应视具体的算法而定 选择算子的构造方法：选择过程的第一步是计算适应度在被选可行路径集中每条路径 具有一个选择概率这个选择概率取决于种群中个体的适应度及其分布路径个体选择概率 的常用分配办法有：轮盘堵选择法、按比例的适应度分配脚、基于排序的适应度分配、随机 遍历抽样法、局部选择法、锦标赛选择法等不管采用哪种选择方法都要体现出适应度高的 路径个体要得到更多的机会进入新一轮循环的思想 交叉算子的构造方法；交叉就是把两个父路径个体的部分结构加以替换重组而产生新路 6 南京师范大学硕士学位论文 第二簟机器人路径规划方法摄述 径个体的操作交叉的目的是为了能够在下一代产生新的路径个体，通过萤组交叉操作，遗 传算法的搜索能力得以飞跃地提高对于二进制串个体可采用单点交叉、多点交叉h 和均匀 交叉等交叉方法；对于实数个体可以采用离散重组、中间重组和线性重组等方法 变异算予的构造方法：交叉之后是子代的变异，路径子个体以很小的概率或步长产生转 变。变量转变的概率或步长与维数( 即变量的个数) 成反比，与种群的大小无关变异本身是 一种局部随机搜索，与选择、交叉算子结合在一起，保证了遗传算法的有效性，使遗传算法 具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性以防止出现非成熟收敛 在变异操作中，变异率不能取得太大，如果变异率大于q 5 ，遗传算法就退化为随机搜索， 而遗传算法的一些重要的特性和搜索能力也不复存在了文献 4 2 还引入了删除、交换、修 复变异操作。 现在有很多学者已经将遗传算法用于机器人路径规划中，但是因为其本身的缺陷( 早熟、 局部能力搜索差) ，还不能保证计算机效率和路径的可靠性，因此还存在很大的改进发展空 间 2 3 基于粒子群算法的机器人路径规划 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n 简称p s o ) 1 是基于群体智能的一种进 化计算方法，由e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出与一般的进化算法相比p s o 概念简单、 容易实现并且需要调整的参数少，目前广泛应用于函数优化、模式分类、优化调度、神经网 络训练、模糊系统控制等领域到目前为止在国内外高档杂志上看到的单纯将粒子群算法用 于机器人路径规划的文章不是很多文献 4 5 】首次将p s 0 引入移动机器人路径规划中，开创了 很好的先例针对文献【4 8 的缺陷文献 4 9 提出了一种新的建模方法用粒子群在新的建 模方法中进行优化，取得良好的效果文献 5 0 研究了s w a r m - b o t s 每个粒子就是一个机器 人每个机器人只搜索自己附近的区域只更新自己的速度和自己的位置建立一个由多个 比较简单的，类似昆虫的机器人的群体s w a r m - b o t s 这些机器人使用相对便宜的构件，具有 自组织和自组装能力来适应环境文献 5 l 】将路径规划问题抽象为对一个罚函数的优化问题， 该罚函数通过神经网络结构构造，其中包含环境中障碍物的约束及路径的长度信息将该罚 函数作为粒子群算法中的适应度函数，而路径中除去起点与终点外的路径节点作为粒子，通 过混合粒子群算法进行寻优由于适应度函数中包含了环境约束信息及路径长度信息，最后 规划结果为一条安全无碰且长度较短的路径这种转化思想在文献 4 9 中也出现了，通过新 的建模方法将机器人路径规划问题转化为函数优化问题不失一种解决问题的好思路 2 4 其他机器人路径规划算法 本小节所列的算法同样被大量应用于路径规划当中，但由于篇幅有限不再归类阐 述，就此进行简单的描述船矧有文献提出了使用模糊控制算法模拟驾驶员的驾驶思想， 将模糊控制本身所具有的鲁棒性与基于生理学上的“感知一动作”行为结合起来，为移动机 器人在未知环境中的导航提出一种新思路；采用链接图法建立机器人工作空间模型，应用遗 7 南京师范大学硕士学位论文第二章机器人路径规划方法概述 传算法规划出初步全局优化路径，采用基于行为的方法进行局部路径规划；将改进的以障碍 物为单位记录信息量的栅格法和回归预测法结合，应用于具有静态和动态障碍物的环境中； 利用拓扑降维构造状态空间，然后在状态空间中搜索出一条可行路径；通过定义转移费用矩 阵的概念及其上的二元运算。将最优路径的生成转化为矩阵运算的路径规划方法：利用图论 d i j k s t r a 算法研究大尺度简单多边形障碍物，进行最短路径规划的几何算法；将路径规划 的收缩法与势场函数相结合，形成完整的数值导航函数的路径计算方法；以及对于各种已有 算法在不同特点环境下的改进等 2 5 常用的建模方法 全局路径规划包括环境建模和路径搜索策略两个子问题其中环境建模的主要方法有： 可视图法( v - g r a p h ) 、栅格法( g r i d s ) 和自由空间法( f r e es p a c ea p p r o a c h ) 等下面对本课 题用到的建模方法进行重点介绍 2 5 1 栅格法 栅格法是将机器人的运动空问用固定大小的栅格分成许多小空间，每个栅格代表一个节 点，所有节点分为障碍物节点和自由节点两大类每个自由节点连接相邻的自由节点组成一 个自由区，用搜索算法生成从初始节点到目标节点的路径可以看出栅格粒度的大小与环境 描述的精确度以及搜索算法的计算量密切相关，栅格划分越细，障碍物的表示越精确，但会 占据大量的存贮空同，算法的搜索范围将成指数增加如果栅格粒度太大，计算量小，但规 划的路径就不精确了栅格法的规划目的是建立数字地图，在地图中存贮机器人的运动轨迹 和障碍物等信息因此，栅格法主要包括地图建模与信息编码两部分。地图建模的思想是将 一块实际的场地划分成等面积的小区，每个小区称为一个栅格栅格面积的大小一般由机器 人车体大小来决定机器人在该栅格化的场地中运动时，可以通过传感器获取每个栅格的障 碍物信息和机器人行走情况，并以此来定义栅格的属性，从而构成基本的地图信息信息编 码是对地图进行数字化编码最常见的编码方法是对每个栅格的障碍物信息用一个二进制数 表示，有障碍物时表示为。l 。，无障碍物时表示为9 0 ”地图上的栅格采用行列划分的矩 阵存储方法 根据利用栅格法并依据图论思想建立的环境模型，可以从图的角度直观上理解路径寻优 的性质 ( 1 ) 如果某个。孤立的栅格点”和其他任何栅格点之间不可达，也就是说，没有任何 一条路径可以到达该栅格点，那么该栅格点在问题空间的存在也就失去了意义。例如，在机 器人的路径规划问题中，被障碍物封闭的栅格点为孤立栅格点，可以抽象为障碍物栅格点进 行处理 ( 2 ) 各条连通路径具有权值数据路径寻优问题相邻结点之间的联系就是两个结点之 间路径上的权值如果没有权值，其实就是各条路径“等权值”的含义权值的取值可以是 任意与该条道路有关的数值 矗 南京师范大学硕士学位论文第二晕机器人路径规划方法概述 ( 3 ) 可行解的表达方式是由一个或者一组点的。序列”表示的通路或者回路，在本课 题中，可行解是由一组点的搿序列”组成的通路从这个意义上讲，大部分的“路径规划” 问题是组合数学中的膏组合优化一向题 ( 4 ) 阅题的空闻是离散的路径寻优所涉及的实际闯题大多是一些离散的问题，如果 有“连续”的问题要用“路径寻优扫的方法解决，那么必须将其连续闯题空间离散化，最后 得到一个离散的“边”和_ 结点一的组合，然后用求导最优路径的方法来加以解决对于本 来就是离散的甸题，如果要用。最优路径一的方式来表达，同样也要把闯题的各要素转化 为搿边”和搿结点”机器人路径规划属于连续空间优化| | ；习题，首先需要将其阀题空问离散 化 2 5 2 自由空间法 把机器人的工作空间分成两部分，即自由空间和障碍物空间用某种搜索策略在自由空 间中找到一条路径，机器入沿着障碍物之间的通道中心运动对于较狭窄的空间区域，它能 保证机器人最大的允许误差，而避免与障碍物碰撞：面另一方面，在某些情况下路径偏离机 器人前进的目标太远，路径会因复杂多折而不利于机器人行走，因而该方法仅适用于路径精 度要求不高，机器人速度不快的场合4 机器人环境中的自由空问是由自由链接线围成的凸区域构建的，自由链接代表如下含 义： 8 ) 该链接线的两个端点或者是两个多边形障碍物的顶点，或者一个是障碍物顶点，另 个在工作空间的边界上在此意义下网一障碍物的顶点的连线也计算在内； b ) 每条链接线都是两相邻自由凸区域公共边； ， c ) 自由链接线不能与环境内的任何障碍物的边相交： d ) 每个自由凸区域至少有两条自由链接线作为其边界每条自由链接线按如下规则计 算： s t e pl 找到当前顶点与所有其他顶点的连线，在此意义下该顶点到工作区边界的垂线 也计算在内； s t e p2 将s t e pl 获得的所有连线根据长度从短到长捧列成表； s t e p3 选取排列表中的第一条线： s t e p 4 检查该线与工作区中多边形障碍物的边是否相交，若相交则该线不是自由链接 线选取排列表中的下一条线并重复上述检查：若不相交则继续进行下一步； s t e p5 检查由当前链接线形成的当前顶点的外角： a ) 若两个外角的度数均小于1 8 0 。则该线为最佳自由链接线，因此忽略该顶点所有已 确定的自由链接线，后转s t e p8 ； b ) 若选取的线不是最佳，例如其中有一个角大于1 8 0 。，则将该线加入当前顶点的自由 链接线表； 9 南京师范大学硕士学位论文第二章机器人路径规划方法概述 s t e p6 检查当前顶点已确定的自由链接线所形成的角是否仍然有大于1 8 0 的：若有则 继续取s t e p2 所获得的排列表中的下一条线并转s t e p4 ：否则继续进行下一步； s t e p7 检查并删除当前顶点可能的冗余链接线； s t e p8 重复s t e pl 至s t e p7 ，获得属于每个障碍物所有顶点的自由链接线链接线的 中点作为机器人路径点，连接各路径点形成的网络图即为机器人可自由运动的线路 从上述算法中可以看出在自由链接图建模方法中自由空间实际上是障碍物的扩大，而机 器人在保证安全距离的条件下是可以沿着障碍物的边界行走的因此，机器人如果沿自由链 接线的中点行走肯定不是最优的这是一个值得研究的闯题 2 6 机器人路径规划技术的展望 随着计算机、传感器及控制技术的发展，特别是各种新算法不断涌现，移动机器人路径 规划技术已经取得了丰硕成果特别是周围环境已知的全局路径规划，其理论研究已比较完 善目前比较活跃的领域是研究在环境未知情况下的局部规划从研究成果看有以下趋势： ( 1 ) 移动机器人路径规划的性能指标不断提高 这些性能指标包括：实时性、安全性和可达性等在动态环境中，由于环境信息是时刻 变化的，如果移动机器人实时性差，滞后于动态环境就可能会导致避障失败安全性和可 达性也很重要一个性能指标不好的方法，即使它能使移动机器人走出完美的轨迹，也将被 淘汰而有些方法没有高深的理论但计算简单，实时性、安全性好，就有存在的空间。如 何使性能指标更好是各种算法研究的一个重要方向 ( 2 ) 智能化的算法将会不断涌现模糊控制、神经网络、遗传算法以及它们的相互结合 也是研究热点之一 目前在移动机器人导航中，智能方法的应用是一个重要的发展方向。但目前智能算法在 机器人导航中的应用范围却受到了很大限制，如神经网络应用往往局限在环境的建模和认知 上，例如机器人地图构建同时由于目前在导航过程中主要采用前馈网络，需要教师信号进 行训练，因此难予实现在线应用：模糊逻辑应用于复杂未知动态环境中模糊规则很滩提取， 导航的效果也不理想智能化方法能模拟人的经验，逼近非线性，具有自组织、自学习功能 并且具有一定的容错能力这些方法应用于路径规划会使移动机器人在动态环境中更灵活 更具智能化因此在移动机器人导航中，智能方法还有极大的发展空间 ( 3 ) 多移动机器人系统的路径规划协调路径规划已成为新的研究热点 随着应用不断扩大，移动机器人工作环境复杂度和任务加重，对其要求不再局限于单个 移动机器人在动态环境中多移动机器人的合作与单个机器人路径规划要很好地统一从规 划者和规划时间考虑。可分为集中式和分布式规划；离线和在线规划两者各有所长，许多 研究工作是将二者结合嗍。文献 6 1 3 基于一种相对固定的协调策略，提出分布式运动规划方 法文献 6 2 提出速度障碍物观点，根据机器人之间相对速度进行在线规划；文献 6 3 采用 离线和在线相结合方法，提出运动规划的体系结构，并将最优控制与智能决策结合建立实 南京师范大学硕士学位论文笫= 章机器人路径规划方法概述 时专家系统，实现多机器人路径规划随着科学技术发展，工农业、医疗等行业对多机器人 系统的要求会越来越高，这种研究还会不断发展 ( 4 ) 多传感器信息融合用于路径规划 移动机器人在动态环境中进行路径规划所需信息都是从传感器得来单传感器难以保证 输入信息准确与可靠多传感器所获得信息具有冗余性、互补性、实时性和低代价性，且可 以快速并行分析现场环境t n o 移动机器人的多传感器信息融合也是当今个比较活跃的研究 领域具体方法有采用概率方法表示信息的加权平均法、贝叶斯估计法、多贝叶斯法、卡尔 曼滤波法、统计决策理论法有采用命题方法表示信息的d _ s 证据推理、模糊逻辑、产生式 规则嗍还有仿效生物神经网络的信息处理方法、人工神经网络法 ( 5 ) 多目标机器人路径规划 很多方法都不同程度上提高了机器人路径规划的效率但其研究的对象大多局限于机器 人单目标搜索，对单机器人进行多目标搜索鲜有报道。随着机器人技术的发展，机器人有可 能被应用于多目标搜索，如机器人邮递员需要将每一份邮件递送到指定的地点等即如何保 证机器人在有障碍物的工作环境中可以快速地沿一条较优化避碰路径安全地访问多个目标 点。在这类应用中机器人需要遍历多个目标，当目标数增多时算法的复杂度呈指数级增长， 将严重影响规划的时效性 2 7 本章小结 对路径规划的研究已近四十年，国内外学者提出了很多高性能的算法，取得了丰硕的成 果本章是作者在阅读大量国内外文献的基础上，对机器人路径规划的现有算法及其建模方 法的研究现状进行了综述和自己的一点见解，主要介绍的是本课题涉及到的路径规划算法和 建模方法 首先对本课题涉及到的算法：蚂蚁算法、粒子群算法、遗传算法在机器人路径规划中的 应用进行了详细的介绍接着对本课题涉及到的建模方法进行了详细的介绍，并对这些方法 的优缺点进行简单的说明机器人路径规划的研究有很好的现实意义所以对该领域的研究 有很大的前景因此，在本章最后一部分对机器人路径规划领域未来发展的方向发表了自己 的看法这些看法仅仅是作者在参加三年文献选读和参加基金课题研究过程中对该领域的一 点见解 南京师范大学硕士学位论文第三章基于蚂蚁自动分流的机器人路径规划新算法 第三章基于蚂蚁自动分流的机器人路径规划新算法 在复杂障碍环境下，如何使机器人所走路径最优，一直是这一领域里的一个研究热点 近几年，不少学者将蚁群算法应用到路径规划中，对此研究取得了不少成果，但其共同的问 题是所应用的算法基本是在原始蚁群算法基础上的改进，由于受原始模型的限制其算法不 一定是最好的，特别是原始蚁群算法采用正反馈机制，不利于搜索的多样性n 司能否找到一 种更好的算法，是该研究领域当前所关注的问题依据真实蚂蚁具有自动分流功能这一新研 究成果w 1 ，本章提出了一种全新的机器人路径规划蚂蚁算法该方法首先用栅格法