（电路与系统专业论文）智能计算在移动机器人路径规划中的应用[电路与系统专业优秀论文].pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：廑! 叠堑日期：垫里磕曼基 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：度国蟊 导师签名： 日期：兰q 垒z 垒五旦 摘要 本文针对智能计算在移动机器人路径规划问题中的应用进行探讨。分析和总 结了该领域现有算法之间的区别以及它们各自的不足，并根据这些不足提出了相 应的改进算法。通过计算机仿真实验验证了这些改进型算法的有效性和相对与原 算法的性能提高。根据这些内容出现的先后顺序，本文工作摘要如下： 1 移动机器人路径规划与智能计算综述 论述移动机器人路径规划的发展历史与研究现状，对现有的路径规划算法作 出分类。介绍智能计算在移动机器人路径规划中应用。以标准遗传算法和蚁群算 法分别作为进化计算和群集智能的代表，描述了它们的基本原理与框架。并以伪 代码的形式给出了标准遗传算法和求解t s p 问题的蚁群算法的算法流程。 2 遗传算法在移动机器人路径规划中的应用与改进 介绍遗传算法应用于机器人路径规划问题的研究现状，分析现有算法存在的 不足，并针对这些不足之处提出改进型遗传算法。根据环境模型的不同，分为连 续空间下的改进型遗传算法和栅格模型下的改进型遗传算法。在连续空间下的改 进型算法中，通过矢量染色体编码实现了算法搜索空间和机器人运动空间的同 一，进而使得地图建模过程可以省略。同时，以矢量染色体编码作为基础，对遗 传算子的设计进行优化，提出了考虑交叉点位置优化的多点交叉算子、将障碍物 分布信息作为约束条件的变异算子、以及考虑操作位置优化的插入算子和删除算 子。在栅格模型中，本文引入了离散化的矢量染色体编码方案，使得栅格模型下 的染色体表示和连续空间下的染色体表示具有了统一性，从而连续空间下的改进 型遗传算子可以继续使用于栅格模型下。通过这些改进型遗传算子的使用，算法 的进化效率显著提高。计算机仿真结果证明了改进型算法的性能优势。 3 蚁群算法在移动机器人路径规划中的应用与改进 介绍蚁群算法应用于机器人路径规划问题的研究现状，分析存在的不足之 处，并针对采用旋转栅格模型的蚁群算法提出改进。通过引入反向运动机制、双 向信息素记录、信息素节点分布方式、节点访问记录、能见度信息分段化处理、 附加信息素机制等措施，成功的扩展了以该模型为基础的蚁群算法在路径规划问 题中的应用范围。改进型蚁群算法的有效性及其相对于非改进型算法的优势在仿 真实验中证实。 关键字：进化计算，群集智能，移动机器人，路径规划，地图建模 中图分类号：t p 2 4 2 6 a b s t r a c t r e g a r d i n g 如a p p l i c a t i o ni nr o b o t i cp a t hp l a n n i n g , c o m p u t a t i o n a li n t e l l i g e n c ei sd i s c u s s e d i nt h i sp a p e r a f t e ra n a l y z i n ga n ds u m m a r i z i n gt y p i c a ja p p l i c a t i o ns c h e m e sn o wi ne x i s t e n c e s e v e r a li m p r o v e da l g o r i t h m sw e r ep r o p o s e dw h o s ee f f e c t i v e n e s sa n da d v a n t a g e sw e r et h e n p r o v e db ym u l t i t u d e so fs i m u l a t i o ne x p e r i m e n t s a c c o r d i n gt ot h eo r d e ro fa p p e a r a n c e ，w o r k s o ft h i sp a p e ra r ea sf o l l o w s ： 1 i n t r o d u c t i o no fr o b o t i cp a t hp l a n n i n ga n dc o m p u t a t i o n a li n t e l l i g e n c e h i s t o r y a n d p r e s e n tr e s e a r c h i n t op a t hp l a n n i n ga l g o r i t h m sf o rm o b i l er o b o t sw a s e x p a t i a t e da sw e l la sc a t e g o r i z e d c o m b i n i n gw i t ht h eo p u m i z a t i o np r o b l e mf o r m u l a t e di np a t h p l a n n i n g ，t w ob i o n i c sa l g o r i t h m sd e r i v e df r o mt h ec o n c e p to fc o m p u t a t i o n a li n t e l l i g e n c ew e r e i n t r o d u c e d t h e s g a ( s t a n d a r dg e n e t i ca l g o r i t h m lw a sd i s c u s s e d 笛er e p r e s e n t a t i v e a l g o r i t h mo fe v o l u t i o n a r yc o m p u t a t i o nw h i c hi so n em a j o rb r a n c ho fc o m p u t a t i o n a li n t e l l i g e n c e c o o r d i n a t e l y , s w a r mi n t e l l i g e n c ew h i c hi sa n o t h e ri m p o r t a n tb r a n c ho fc o m p u t a t i o n a l i n t e l l i g e n c ew a sa l s os t u d i e d 。w i t ha s ( a n ts y s t e m ) b e i n gd i s c u s s e da sar e p r e s e n t a t i v e a l g o r i t h mt h a tf a l i si n t ot h i sc a t e g o r y 2 a p p l i c a t i o n sa n di m p r o v e m e n t so fg a ( g e n e t i ca l g o r i t h m ) i nt h ef i e l do fp a t hp l a n n i n g d e v e l o p m e n ta n dc u r r e n tr e s e a r c hs t a t u so fg a si m p l e m e n t a t i o nd e s i g n sf o rr o b o u cp a t h p l a n n i n gw a ss u m m a r i z e di nt h i ss e c t i o n b yc l a s s i f y i n ga n da n a l y z i n gt h e s ed e s i g n s ，t h e i r d i f f e r e n c e sa n ds h o r t c o m i n g sw e r ep a i n t e do u t a i m i n ga tt h ed e f i c i e n c i e se x i s t e di nm a i n s t r e a ma l g o r i t h m s ，c o r r e s p o n d i n gi m p r o v e m e n t sw e r ep r o p o s e d a c c o r d i n gt ot h em a pm o d e l b a s e do nw h i c ht h ea l g o r i t h mi sa p p l i e d ，t h ep r o p o s e da l g o r i t h m sc a nb ed i f f e r e n t i a t e da s i m p r o v e dg ai nc o n t i n u o u ss p a c ea n di m p r o v e dg a i ng r i dm o d a l i nc o n t i n u o u ss p a c e ，t h e v e c t o rc h r o m o s o m ee n c o d i n gs c h e m ew a sp r o p o s e d b ya d o p t i n gt h i ss c h e m e ，t h es e a r c h s p a c eo fi m p r o v e dg ai nc o n u n u o u ss p a c ea n dt h ep h y s i c a ls p a c eo fr o b o t sm o t i o nb e c o m e i d e n t i c a l ，w h i c hn o to n l ye n a b l e st h ea l g o r i t h mt ob y p a s st h em a pm o d e l i n gp r o c e s sb u ta l s o e n h a n c e dt h ee v o l u t i o n a r ye f f i c i e n c yo fg an o t i c e a b l y m e a n w h i l et h es t a n d a r dc r o s s o v e r o p e r a t o ra n dm u t a t i o no p e r a t o rw e r es p e c i f i c a l l yo p m i z e df o rt h ea p p l i c a t i o no fp a t hp t a n n i n g a n dt w oc u s t o m i z e dg e n e t i co p e r a t o r sw e r ei n t r o d u c e da sw e l l a sf o rt h eg r i dm o d e an e w m e t h o df o rg d dd e s i g n a t i o nw a sa d o p t e dw h i c hm a k e sa l lt h eo p t i m i z e dg e n e t i co p e r a t o r si n c o n t i n u o u ss p a c ea f o r e m e n t i o n e da l s oa p p l i c a b l ei nd i s c r e t ee n v i r o n m e n t d e m o n s t r a t e db y s i m u l a t i o nr e s u l t s ，t h ep r o p o s e da l g o r i t h m sb o t hi nc o n t i n u o u ss p a c ea n dg r i dm o d e la c h i e v e d c o n s i d e r a b l ei m p r o v e m e n t s 2 3 a p p l i c a t i o n sa n di m p r o v e m e n t so fa c o ( a n tc o l o n y0 d 日m i z a u o n ) i nt h ef i e l do fp a t h p l a n n i n g d e v e l o p m e n ta n dc u r r e n tr e s e a r c hs t a t u so fa c o si m p l e m e n t a t i o nd e s i g n sf o rr o b o t i c p a t hp l a n n i n gw a ss u m m a r i z e di nt h i ss e c t i o n a c c o r d i n gt ot h ed i f f e r e n c e sb e t w e e nt h e i rm a p m o d e l i n gp r o c e s s e s ，m a i ns t r e a ma p p l i c a t i o nd e s i g n so fa c o i np a t hp l a n n i n gw e r ec l a s s i f i e d i n t ot w oc a t e g o d e sa n dt h e i rs h o r t c o m i n g sw e r ep o i n t e do u t a i m i n g 砒s o l v i n gt h ep r o b l e m e x i s t e di nt h ea p p l i c a u o nd e s i g nw h i c hi sb a s e do nar o t a t e dg d dm o d e l ，a ni m p r o v e da c o a l g o r i t h mi sp r o p o s e d 0 p t i m i z e df o rt h ea p p l i c a t i o no fp a t hp l a n n i n go nc o m p l e xm a p ，t h e m e c h a n i s mf o ra n tt ot r a v e li nr e v e r s ed i r e c t i o no ft h et a r g e ti si n t r o d u c e d t h ea l g o r i t h m s f l e x i b i l k yo v e rd i f f e r e n tm a p sa sw e l la si t sa b i l i t yt of i n dc i r c u i t o u sr o u ti sn o t i c e a b l ye n h a n c e d b ym o d i f y i n gt h em o d eo fp h e r o m o n ed i s t r i b u t i o n ，t h er e q u i r e m e n to fd a t as t o r a g ei s d e c r e a s e dw i t h o u ta f f e c t i n gt h ea l g o r i t h m sp e r f o r m a n c e d e m o n s t r a t e db ys i m u l a t i o nr e s u l t s ， t h ep r o p o s e da l g o r i t h ma c h i e v e dc o n s k l e r a b l ei m p r o v e m e n t s k e y w o r d s ：e v o l u t i o n a r yc o m p u t 融i o n ，s w a r mi n t e l l i g e n c e ，m o b i l er o b o t 。p a t hp l a n n i n g 。m a p m o d e l i n g 3 第一章绪论 第一章绪论 自古以来人类就一直梦想并尝试制造可以代替人类完成各种工作的机器人， 帮助我们完成复杂而危险的任务，克服不适宜人类涉足的环境，从事机械单调的 操作，以便将人类从繁重的体力劳动中解放出来。公元前二世纪，亚历山大时代 的古希腊人发明了最原始的机器人自动机，它是以水、空气和蒸汽压力为动 力的会动的雕像，它可以自己开门并借助蒸汽唱歌。我国的汉代，张衡发明了计 里鼓车，计里鼓车每行一里，车上木人击鼓一下，每行十里击钟一下。到了近代， 各种利用齿轮、发条等设计的自动玩偶更是层出不穷。尤其是工业革命以后，自 动化技术有了很大的进步，开始出现初级机器人装置，人类开始越来越多地把繁 重重复的工作交给各式各样的机器人完成，对社会的生产、生活方式产生了深远 的影响。 1 1 机器人发展概述 现代意义上的机器人诞生于1 9 4 7 年，当时原子能实验室的恶劣环境要求使 用机械代替人来处理放射性物质。在这一背景下，美国原子能委员会阿尔贡研究 所开发了遥控机械手。随着现代控制理论和计算机技术的发展，机器人的研制和 应用也突飞猛进。1 9 6 2 年美国a m f 公司生产的v e r s t r a n 和u n i m a t i o n 公司生产 的u n i m a t e 成为最早的实用机型。作为商业化的工业机器人，它们被出口到世界 各国，掀起了全世界对机器人领域的研究热潮。以此为起点，机器人发展至今大 约经历了三代： 第一代是示教再现型机器人，v e r s t r a n 和u n i m a t e 这两种最早的工业机器人 就是示教再现型机器人的典型代表。它由人操纵机械手做一遍应当完成的动作或 通过控制器发出指令让机械手臂动作，在动作过程中机器人会自动将这一过程存 入记忆装置。当机器人工作时，能再现人教给它的动作，并能自动重复的执行。 这类机器人不具有外界信息的反馈能力，很难适应变化的环境。 第二代是有感觉的机器人，是一种按人事先编好的程序对机器人进行控制， 使其自动重复完成某种操作。它们对外界环境有一定感知能力，并具有听觉、视 觉、触觉等功能。机器人工作时，根据传感器获得的信息，灵活调整自己的工作 状态，保证在适应环境的情况下完成工作。 4 第一章绪论 第三代是具有智能的机器人，智能机器人通过各种传感器来获取环境的信 息，然后利用智能技术进行识别、理解、推理并最后作出决策，不用人的参与就 可以完成一些复杂的工作。如f 1 本h o n d a 公司研制的a s i m o 人形机器人，不仅可 图1 1 铆接机器人 闰1 2a s | m o 以行走、爬楼梯、识别各种声音指令，还能够通过头部的摄像机捕捉画面，识别 人类的各种手势动作以及不同的脸型。 目前，随着计算机技术和人工智能技术的飞速发展，机器人在功能和技术层 次上有了很大的提高，机器人技术正源源不断地向人类活动的各个领域渗透。结 合这些领域的应用特点，人们发展了各种特种机器人和智能机器，推动了机器人 概念的延伸。机器人在形式上也不再只是第一代工业机器人时代的机械手臂，出 现了仿人机器人、仿生机器人、空间机器人、水下机器人等等。同时在智能上也 不断进步，向着自我学习和自主决策的方向发展。8 0 年代后，人们将具有感觉、 思考、决策和动作能力的系统称为智能机器人，这一概念不但指导了机器人技术 的研究和应用，而且又赋予了机器人技术向深度和广度发展的巨大空间。 1 9 9 7 年，i 酬“深蓝”计算机在与国际象棋大师卡斯帕罗夫的对弈中取得胜 利，这是电脑首次战胜人脑，这次胜利标志着人类在人工智能方面取得了突破性 进展，使人们对人工智能有了全新的认识。2 0 0 4 年美国国家航空航天局的“勇 气”号探索机器人登陆火星并成功完成自主导航、避障、火星物质采集分析等科 学考察任务。是机器人代替人类探索未知环境的典型代表。2 0 0 5 年斯坦福大学 设计的“斯坦利”夺得由美国国防先进项目研究局赞助发起的美国无人驾驶汽车 大赛冠军，自主行驶完成了2 1 3 公里的崎岖山路和沙漠路段，期间成功地自动避 险并躲避预设障碍物。， 这些令人瞩目的进展和成功不断地打破机器人原有的概念范围，赋予机器人 新的内涵，充分地说明机器人领域所具有的活力。可以预见，未来社会中各种各 样的机器人将越来越多的进入人们的生活，更加的智能化，可完成的任务更加复 杂和多样。不仅仅成为人类身体的延伸，同时也成为人类智能的延伸。 5 第一章绪论 图1 3 “勇气”号探索机器人 图1 4 。斯坦利”无人驾驶汽车 1 2 移动机器人 智能移动机器人是机器人研究领域重要的分支，随着机器人智能程度的提 高，功能的多样化，机器人在机械结构上也由最早的固定手臂演变为各种各样的 可移动形式。如：轮式移动机器人、步行移动机器人、蛇形机器人、履带式移动 机器人、爬行机器人等。“勇气”号探索机器人以及“斯坦利”无人驾驶汽车就 都是轮式移动机器人的例子。此外，按功能和用途来分还可以分为：医疗机器人、 军用机器人、娱乐机器人、等等。按作业空问来分可分为：陆地移动机器人、水 下机器人、空问机器人。依靠人工智能、图像处理、智能控制、网络通讯等技术 的进步，越来越多、功能各异的机器人被开发出来，不断充实着移动机器人这一 领域的内容。 图1 - 5 “s h a k c y ”自主移动机器人 图1 6 “q r i o ”娱乐机器人 移动机器人的研究最早可以追溯到上世纪6 0 年代末期，斯坦福研究院的 n i l sn i l s s e n 和c h a r l e sr o s e n 等人研制出取名为s h a k e y 的自主移动机器人， 目的是研究和应用人工智能技术，在复杂环境下机器人系统的自主推理、规划和 控制。与此同时，最早的操作式步行机器人也研制成功，从而开始了机器人步行 第一章绪论 机构方面的研究，以解决机器人在不平整地域内的运动问题。7 0 年代末，随着 电子计算机和传感器技术的进一步发展，移动机器人研究出现高潮，特别是在 8 0 年代中期，设计和制造移动机器人的浪潮席卷全世界，许多公司开始设计、 制作和销售移动机器人平台，这些移动机器人平台被广泛用于教育和研究目的， 很短时间内就引起全世界的广泛关注，促进了移动机器人学多种研究方向和研究 成果的出现。 1 3 自主导航与路径规划 对于智能移动机器人来说，在其众多的决策过程中最基本的就是自主导航行 为。它是机器人移动过程中必不可少的环节，包括以下几个方面： 1 导航方式：根据不同的应用环境，机器人导航方式也多种多样，常见的 有： 地型匹配导航，它通过机器人自身的各种传感器探测周围环境，并构造局部 地图与事先存储的完整地图进行匹配。如匹配成功，机器人可确定自身的位置， 并利用路径跟踪技术沿预先规划好的全局路径前进。 惯性导航，它利用陀螺仪测量机器人的行进方向，利用加速度计测量的加速 度值积分计算机器人运行速度以及经过的路程。由此估算出机器人所处的坐标和 运动轨迹，再与预先确定好的路径进行对比，发现有偏差时立即计算出偏差量， 然后控制机器人移向预定路径。 其它基于各种导航信号的导航方式，如g p s 定位系统导航、路标导航等等。 2 定位：导航和定位密不可分。作为导航过程中的一个重要环节，定位就 是要确定机器人在给定坐标系中的坐标。而不同的导航方式往往对应不同的定位 方式，常见的定位方式有： 光电编码盘定位，在轮式移动机器人的车轮上装有光电编码器，当车轮转动 时测量各个车轮产生的脉冲信号，并配合已知的机器人车轮尺寸就可以估算出机 器人的转动角度以及前进距离进而计算出机器人当前坐标。该方法简单易实现， 在很多小型的室内机器人上获得了广泛应用。但由于车轮打滑，以及地面的不平 整都会严重影响其测量精度，同时其误差具有累积效应，随着时间的推移测量误 差会不断增大，所以大多数情况下它需要配合其它定位方法联合导航。 惯性定位，联合陀螺仪和加速度计两者的测量序列，可以计算出机器人的坐 标。该方法简单有效且不依赖外界信息，具有很好的抗干扰能力和多用途适应性， 获得了广泛的应用。但它同样有一大缺陷就是积累误差问题，随着时间的推移， 每次测量的误差都会被累积下来最后导致计算结果的误差越来越大直至超出允 7 第一章绪论 许范围。所以对于较长时间的运行，惯性导航一般要配合其它辅助定位方法来使 用。 6 p s 定位，全球定位系统( 6 1 0 b a lp o s i t i o n i n gs y s t e m g p s ) 是一个高精 度、全天候和全球性的无线电导航、定位和定时的多功能系统，具有在海、陆、 空进行全方位实时三维导航与定位能力。通过给机器人装载g p s 接收机可以实现 高精度的定位，但其缺点是成本较高且无线信号传输要求对应用环境有所限制。 路标定位，在机器人的工作环境中预先设定多个路标，机器人定位时在同一 点测量至少与三个路标的距离，通过几何运算可以解得自身和路标间的相对坐标 位置。如果路标的坐标值已知，则机器人的绝对坐标也可得。该方法可获得较高 的定位精度且计算量小，但需要对环境作一些改造，不太符合真正意义的自主导 航。 其它的定位方法，如传感器网络对机器人跟踪定位，利用监控摄像机的视频 定位等等。由于这些方法应用要求的限制，只在一些特定的场合得到采用。 3 路径规划：不论采用何种导航方式，路径规划是智能移动机器人必须完 成的任务。可以说，路径规划是智能机器人自主移动的关键。它是按照某一个或 多个性能指标的约束要求，搜索一条从起始状态到目标状态的最优或近似最优的 无碰撞路径。根据机器人对环境信息的了解程度可分为三类，环境全部已知、环 境部分未知、环境完全未知，路径规划的难度也逐步上升。当环境完全已知时， 机器人可以进行离线( o f f - l i n e ) 的路径规划，即根据已知的地图环境信息，使 用一定算法，计算出到达目标位置且满足规划要求的可行路径，然后由控制模块 驱动机器人沿该路径运动。而当环境部分未知或全部未知时，机器人需要使用传 感器对环境进行探测并不断根据新获取的信息进行实时的路径规划。这种方式也 被称为在线( o n - i i n e ) 规划。 在实际应用中，导航、定位和路径规划这三者是相辅相成、缺一不可的。有 了定位技术，机器人才能知道自己所处的位置，路径规划才有起始点和坐标系。 同时，也只有有了路径规划得出的可行路径，导航才能有目标的进行，机器人才 能避免与障碍物碰撞。而在其中，路径规划是对算法要求较高的，针对不同的环 境条件、规划要求，研究者们提出了众多不同特点的算法。 1 4 路径规划概述 路径规划问题源于计算机几何学的传统研究课题。七十年代未由于智能移动 机器人的研究需要，路径规划问题得到了促进和发展。作为机器智能的一部分， 它的任务就是使机器人在其工作环境中能够自主的从起始点运动到目标点同时 8 第一章绪论 满足一定的约束条件。这些约束条件可以是不与障碍物碰撞，也可以是运动路径 最短，或者是机器人耗费能量最小，等等。 由于应用条件以及规划要求的不同，路径规划领域中存在许多不同的基本思 路及算法。根据对环境信息掌握程度的不同，大致可分为两类：基于先验完全信 息的全局路径规划和基于传感器信息的局部路径规划。前者是拥有完整的环境信 息并以此构造模型，再从模型中找出从起始点到目标点的符合规划要求的最优路 径。其规划的精度取决于所掌握先验知识的准确程度，其计算的复杂度受建模方 式和路径搜索策略影响较大。在后者中，环境信息是未知或部分未知的，障碍物 的几何性质、位置坐标等信息由传感器获取。所以局部规划方法主要侧重于考虑 机器人当前所处的局部环境，算法计算复杂度一般较低，反应速度快，通常具有 很好的避障性能。同时由于环境信息是通过传感器不断获取和更新的，所以它可 以很好的跟随环境变化并作出反应，具有良好的实时性。但其缺点是仅依靠局部 信息，不一定能完全满足优化要求。可见，全局路径规划和局部路径规划在性能 上存在互补，根据具体应用的需要，可以把它们两者结合起来使用。如g u l d n e r 在 2 1 中提出了三层控制结构，以全局规划作为最高层，采用势场法的局部规划 为第二层，最底层用航向角方法来进行避障，适合于杂乱环境中的路径规划。 d i e g u e zar 在 5 0 中提出了多级结构，包括全局规划、局部规划、智能监督、 传感器信息融合、路径选择和导航六个层次。通过全局路径规划和局部路径规划 的融合，这些混合型方法实现了更好的规划效果。 1 4 1 全局路径规划算法 按照环境建模方式的不同，全局路径规划可细分为：可视图法、切线图法、 v o r o n o i 图法、自由空间法、拓扑法、栅格法等等。其中，可视图法、切线图法、 v o r o n o i 图法是经典的规划方法，它们主要采用图论的思想，将目标、机器人及 其工作空间用一个连接图表示，从而路径规划问题就转化为在图上寻找一条从起 始点到目标点的最优路线。 1 ) 可视图法 在可视图法中机器人被视为一点。在此基础上，将机器人、目标点和多边形 障碍物的各顶点进行组合连接，只保留其中不穿越障碍物的连线，从而所有直线 是可视的，所有经过这些连线段而到达目标点的路径都是可行路径。于是路径规 划就转化为按一定的优化标准，从所有的这些可行路径中搜索出最优路径的问 题。该方法主要的缺点在于其计算复杂度随障碍物的增加迅速增加，并且对机器 人起始点、目标点以及障碍物位置变化敏感，位置变动时将需要重新建模。另一 9 第一章绪论 方面，在实际运行中，它要求能精确地控制机器人到达障碍物顶点附近，而这往 往时较难实现或不安全的。此外，可视图法仅适用于多边形障碍物，对于圆形障 碍物该法失效，所以有切线图法、v o r o n o i 图法对可视图法进行了改进。 2 ) 自由空问法 自由空间法应用于移动机器人路径规划，采用预先定义的如广义锥形和凸多 边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来 进行路径规划。自由空间的构造方法是：从障碍物的一个顶点开始，依次作其它 顶点的连接线，删除不必要的连接线，使得连接线与障碍物边界所围成的每一个 自由空间都是面积最大的凸多边形。连接各连接线的中点形成的网络图即为机器 人可自由运动的路线。其优点是机器人可运动的自由空间有清晰的几何模型描 述，如果在已知的自由空间中存在可行路径，那么一定可以找到这样的路径。另 外，该方法和可视图法相比较灵活，起始点和目标点的改变不会造成连通图的重 构，但缺点同样是计算复杂度随障碍物的增加迅速增长，使连通图的构造和路径 搜索都非常耗时。 3 ) 拓扑法 上述的可视图法、自由空间法等模型都没有考虑机器人的几何特点，在解决 姿态这个很重要的路径规划问题时，如细长形杆状机器人的路径规划，有一定的 局限性。拓扑法利用状态空间的连通性分析来解决路径规划问题，它根据环境和 机器人的几何特点，将规划空间划分成若干拓扑特征一致的子空间，根据彼此的 连通性建立一个拓扑网络，在该网络上寻找起始点到目标点的拓扑路径，最终由 拓扑路径求出几何路径。拓扑法基本思想是降维法，即将在高维几何空间中求路 径的问题转化为低维拓扑空间中判别连通性的问题。优点在于利用拓扑特征大大 缩小了搜索空间。算法复杂性仅依赖于障碍物数目，理论上是完备的。而且拓扑 法通常不需要机器人的准确位置，对于位置误差也就有了更好的鲁棒性。其缺点 是建立拓扑网络的过程相当复杂、费时，比较难以实现。 4 ) 栅格法 栅格法是目前研究和应用最广泛的环境表示方法。它将整个地图划分为许多 小栅格，并要求栅格的尺寸不小于机器人自身的尺寸。若某个栅格范围内不含任 何障碍物，则称此栅格为自由栅格，所有自由栅格的集合构成机器人运动的自由 空间。在进行栅格划分的同时，记录各栅格问的邻接关系，然后把起点栅格和目 标栅格之间的邻接栅格连接起来就得到一条无碰撞的可行路径。最后再通过优化 算法在众多的可行路径中进行搜索，以找到满足规划要求的路径。栅格法简单易 懂、容易实现，但由于环境被量化成具有一定分辨率的栅格，所以导致了计算资 源耗费和规划结果质量之间的矛盾。大栅格划分，会使环境信息存储量减小，寻 第一章绪论 优时间缩短，但算法分辨率下降，复杂环境下发现路径的能力减弱。栅格划分减 小，则环境分辨率提高，在复杂环境下发现路径的能力增强，但环境信息存储量 增大，寻优时间加长。考虑到自由空间中往往存在大片连续的邻接栅格，如果仅 仅将这些栅格合并为大栅格，其它区域保持原有划分不变，那么不仅可以大大减 少计算量而且保持了复杂区域的路径发现能力。为了在不同的区域使用尽可能大 的栅格，单元树法应运而生。以四叉树法为例，首先把整个地图分成四个大小相 等的栅格，考察每个栅格，如果是自由栅格或障碍栅格就停止该栅格的生长。如 果该栅格内既有障碍物又有自由空间就再次划分为四个小栅格，依此类推直到栅 格大小达到算法定义的下界。这类方法有效的取得了精度和计算量上的平衡，获 得了广泛的使用。 1 4 2 局部路径规划算法 局部路径规划最初的研究是一种基于直角坐标系的碰撞惩罚函数方法。在此 基础上由k h a t i b 提出的人工势场法是局部规划中的代表性算法，除此以外，局 部规划算法还有：模糊逻辑算法、b u g 算法、神经网络算法等等。局部路径规划 算法和全局路径规划算法间最大的区别在于，全局规划算法考虑全局信息，其规 划目标是取得全局最优化的路径；而局部路径规划中环境信息是不完全的，所以 局部规划算法是仅仅基于局部信息进行计算的，也就是说，即使在掌握全局信息、 环境完全已知的情况下，使用局部规划算法其效果仍然和环境未知情况是一样的 或改善不明显的。 1 ) 人工势场法 人工势场法是由k h a t i b 3 7 提出的一种虚拟力法。其基本思想是将移动机器 人在环境中的运动视为一种在虚拟的人工力场中的运动。障碍物在空间中形成假 想的斥力场，对移动机器人产生虚拟排斥力，并随机器人与障碍物距离的减小而 迅速增大。目标点在空间形成假想的引力场，对移动机器人产生虚拟吸引力，并 随机器人与目标的接近而减小。于是机器人处于引力场和斥力场叠加的人工势场 中，沿势场梯度的负方向运动便可得到无碰撞路径。该算法计算简单、实时性好、 容易与机器人运动方程结合，在实时避障和平滑轨迹控制方面得到了广泛应用。 其不足之处在于存在局部势场零点，因而可能使移动机器人在到达目标点之前就 陷入其中而无法脱离。为此，人们在经典的人工势场法的基础上进行改进，包括 尝试设计合适的势函数使得整个势场无局部势能最小点，如s a t o 提出的l a p l a c e 势场法 3 6 ；或是提出可脱离局部最小点的算法，如随机运动法( r a n d o m w a l k ) 3 1 、虚拟障碍物( v i r t u a lo b s t a c l e ) 3 5 等。 i i 第一章绪论 2 ) 模糊逻辑算法 模糊逻辑算法是通过对驾驶员的工作过程观察研究得出的。驾驶员避碰动作 并非对环境信息精确计算完成的，而是根据模糊的环境信息，靠经验来决策采取 什么样的操作。模糊逻辑算法基于实时传感器的信息，根据障碍物的位置及机器 人运动状态构造隶属度函数，然后通过查寻运动策略表决定将采取的路线，从而 完成局部路径规划。优点是克服了势场法易产生的局部极小问题，计算量较低， 能够达到实时在线规划的要求，适合处理未知环境下的路径规划。该方法对解决 定量方法难以处理的问题，以及在外界只能提供定性而非定量的、不确定信息时 具有明显的优势。 3 ) b u g 算法 b u g 算法是最早提出的解决未知环境下机器人路径规划问题的方法之一。它 的主要思想是：将起始点与目标点的连线视为机器人的运动的主线( m - l i n e ) ， 从起始点出发，机器人首先沿主线移动，当环境中有障碍物被探测到且与机器人 前进路线发生冲突时，则改变运动策略为沿此障碍物边界移动，直到机器人再次 回到主线并且与其目标点的距离较前一次脱离主线时有所减少，机器人再继续沿 主线向目标点移动。 1 5 智能计算 基于可视图、v o r o n o i 图、切线图等环境模型的图搜索方法是机器人路径规 划问题中的传统算法，但它们普遍存在计算复杂、起始点和障碍物位置的变动导 致模型重构等问题。当障碍物的增多或是由二维情况扩展到三维时，计算量将迅 速增加，导致最优路径搜索策略失败或是耗费巨大的时间代价。 随着智能计算概念的提出，各种仿生型智能算法相继出现，其强大的复杂空 间寻优能力吸引了众多研究者的注意。这些算法在机器人路径规划领域的应用大 大促进了自主移动机器人的研究，为全局路径规划中的最优路径搜索过程提供了 新的具有竞争力的解决方法。其中最具有代表性的是两类算法：进化计算 ( e v o l u t i o n a r yc o m p u t a t i o n ) 和群集智能( s w a r mi n t e l l i g e n c e ) 。它们不仅 在复杂解空间搜索效率、收敛速度和问题适应性方面大大超过了传统算法，而且 由于其算法结构所决定的内在并行性更是为并行计算和超大规模优化问题的求 解奠定了基础，使得许多传统算法难以处理的问题，现在只需较小的时间代价即 可得到最优解或近似最优解。而移动机器人路径规划问题的复杂性、多样性则正 好为智能计算的应用留下了广阔的空间和丰富的内容。 目前在机器人路径规划问题中，遗传算法作为典型的进化算法。是研究和应 第一章绪论 用最广泛的。k a z u os u g i h a r a 等 3 4 研究了栅格模型下遗传算法的应用并取得 较好的结果，但二进制编码方案使得个体长度较长，并且随栅格划分的精细化编 码串长度迅速增加，存在较严重的路径规划精度和计算量之间的矛盾。t a k a n o r i s h i b a t a 等 4 4 研究了遗传算法在基于链接图模型的路径规划问题中的应用，通 过一系列自由链接线的中点来表示路径，达到简化环境的目的，降低了遗传算法 搜索解空间的难度。但是由于前期的建模过程需要很大的计算量，尤其是在障碍 物数目较多时，所以算法在计算总量上实际并没有改善。除此以外，遗传算法在 路径规划问题中的应用方面的研究还有许多，如 1 5 等等。 和遗传算法相比，群集智能算法的提出和研究相对较晚，但它在众多优化问 题中的出色性能表现使其逐渐成为了一个新的研究热点。尤其是蚁群算法，由于 其自身算法结构的特点使得它对离散空间寻优具有特别的适用性，在各种组合优 化问题显示了特有的优势。在机器人路径规划问题中，由于栅格法地图建模实质 就是对机器人工作空间的离散化处理，所以正好为蚁群算法的应用提供了基础。 基于这样的构架，文献 3 9 研究了蚁群算法在基于旋转坐标系的栅格模型中的应 用。它针对自由飞行空间机器人( f f s r ) 路径规划问题的特点，为人工蚂蚁提供 了一个指向目标点的前进方向，使得其每一步运动轨迹在该方向上的投影都为 正。这样虽然提高了算法的搜索效率但同时却限制了该方法的应用范围。对于陆 地移动机器人，如果地图上的最优路径包含远离目标点的反向运动轨迹时，该算 法将会失效。文献 3 8 在蚁群算法与栅格模型的结合方面采用了不同方式，提出 a c o g r i d 算法，该算法中使用了相邻栅格转移规则以及目标点导向的距离启发 式信息，理论上具有任意地图的适用性。但由于忽略了多种倾斜角度运动的可能， 所以它在路径长度方面的优化是不足的。 综上所述，目前在智能计算和机器人路径规划相结合的方面还有需要深入研 究和改进的地方。本文的后续部分就是围绕遗传算法和蚁群算法这两种算法展 开，研究了它们在路径规划问题中的应用、不足以及改进方法。 1 6 主要工作与创新点 本文针对连续空间下遗传算法的应用、栅格模型下遗传算法的应用和旋转栅 格模型下蚁群算法的应用分别提出改进型算法。主要创新点如下： a 连续空间下的改进型遗传算法 1 矢量染色体编码方案，为在改进型遗传算子中引入地图信息奠定了 基础，使遗传操作易于实现。 2 在多点交叉算予中引入交叉点位置优化，实现优良基因在单一个体 第一章绪论 上的集中 3 提出带有约束条件的变异算子，避免了大量的负面进化效果 4 考虑插入点位置优化的插入算子和考虑删除点位置优化的删除算 子，提高了优良性状的产生率 b 栅格模型下的改进型遗传算法 1 提出基于离散坐标的栅格模型和离散化的矢量染色体编码，在此基 础上实现了连续空间下和栅格模型下染色体表示的统一，以及改进 型遗传算子在连续空问和栅格模型中的通用。 c 栅格模型下的改进型蚁群算法 1 引入人工蚂蚁在x 轴方向上的反向运动机制和双向信息素记录，保 证了改进型算法对复杂路径的发现能力 2 信息素的节点分布方式，在不影响算法性能的同时大大降低了数据 存储量的要求 3 能见度信息的分段化处理，避免了路径搜索和避障过程相分离的结 构，提高了蚂蚁在解空间的搜索效率 4 附加信息素机制，有效引导蚂蚁在算法迭代初期迅速抵达目标点 1 7 本论文结构 第一章“引言”，介绍机器人发展历史和移动机器人研究现状，简单论述智 能移动机器人自主导航及路径规划的概念以及机器人路径规划领域的主流算法。 第二章“智能计算概述”，以遗传算法和蚁群算法分别作为进化计算和群集 智能的代表，说明它们各自的特点以及它们在移动机器人路径规划问题中的应用 模型与算法流程。 第三章“遗传算法的应用和改进”，介绍遗传算法应用于机器人路径规划问 题的研究现状，分析存在的不足之处，并分别针对连续空间和栅格模型条件下的 应用提出改进型遗传算法