（模式识别与智能系统专业论文）迷宫机器人路径规划算法研究.pdf

迷宫机器人路径规划算法研究 迷宫机器人路径规划算法研究 摘要 随着科技的不断进步，机器人逐渐向智能化发展，智能机器人应运而生。智 能机器人具有人的五官及大脑，可以识别周围的环境和自身的状态，并能进行分 析判断，采取相应的行动。 路径规划问题是智能机器人的关键技术之一，自主移动机器人如何在未知 的、复杂的环境中自主规划从起点到终点的路径，并且躲避障碍是智能机器人的 最基本、最重要的能力之一，是其它应用的基础。迷宫机器人的路径规划是智能 移动机器人路径规划的典型应用，由于迷宫环境的特殊性，迷宫机器人的路径规 划有着比一般避障路径规划算法更加复杂的要求。 首先，本文实现了以a t m e l 公司的a t m e g a 16 8 单片机为主芯片的迷宫机 器人平台，使用两个l 9 1 10 集成芯片分别控制两个直流电机，使机器人实现了 前进、转弯、后退等功能。通过r s 2 3 2 接口与电脑相连，将算法程序下载到机 器人本体，机器人根据算法程序和传感器的障碍物信息自主运行。 其次，在研究了国内外智能机器人路径规划技术的基础上，本文对人工势场 法、栅格法、遗传算法的路径规划进行了研究，并分别将势场法、遗传算法以及 深度优先算法应用到迷宫这种特殊环境的路径规划问题上。文章最后在人工势场 法和栅格法的基础上，针对迷宫的特点，设计了一个更加简单有效的离散势场算 法来解决迷宫问题。 接着，本文对实际迷宫进行了大量的研究分析，提出了迷宫的数字化表示方 法，为计算机的仿真提供了方便。文章分析了迷宫中存在的八种路况，提出了相 应的解决方案。 最后，对全文工作进行了总结，并对机器人路径规划技术进行了展望。 关键词：迷宫机器人，路径规划，人工势场，遗传算法，离散势场 雾季天学 迷宫机器人路径规划算法研究 r e s e a r c ho fm a z er o b o tp a t hp l a n n i n g a l g o r i t hm a b s t r a c t w i t hm e r a p i d ( 1 e v e l o p m e n to f t h et e c h n o l o g y ，r o b o t sg r a d u a l l y b e c o m em o r ea n dm o r ei n t e l l e c t u a l i z e d a ni n t e l l i g e n tr o b o ta c q u i r e s i n f o m a t i o no fi t s e l f2 u l dt h ee n v i r o r 皿e n t st h r o u g ht h es e n s o r s i tt h e n a n a l y z e st h ei n f o m l a t i o na n dm a k e saj u d g m e n tt ot a k es u i t a b l ea c t i o n s p a m p l a n n i n gi so n eo fm ek e yp r o b l e m so fi n t e l l i g e n tr o b o ts m d y a b a s i c 如n c t i o n a l i t yo fi n t e l l i g e n tr o b o ti si t sa b i l i t yt oa p p r o a c ht h e d e s t i n a t i o na u t o n o m o u s l yb ya v o i d i n gt h eo b s t a c l e si ni t sw a yi na n u n p 同i c t a l b l e ，c o m p l e xe n v i r o n m e n t 1 h i s 血n c t i o n a l i t yi st h eb a s i so fi t s o t h e r 向n c t i o n a l i t y t h ep a t hp l a i l n i n go nm a z er o b o ti st h et y p i c a l l y 印p l i c a t i o n so f t h em o b i l er o b o t ni sm o r ec o i n p l e xb e c a u s et h es p e c i a l c h a r l c t e i so ft h em a z ee n v i r o n 瑚【e n t f i r s t ，t h i sp 印e rd e v e l o p e dam o b i l er o b o tp l a t f o mf o rp a t hp l a n n i n g ， w l l i c hb a s eo nt h es i n g l ec h i pm a c h i n ea t m e g al6 8 t h ei n t e g r a t e dc i r c u i t l 91loi su s e dt oc o n 臼o lt h em o t i o no fe l e c t i om o t o r s o nt h eb a s i so ft h e o b s t a c l e si n f o 衄a t i o na n dt h ea l g o r i t h mp r o 舒l md o 、釉l o a d e d 肺mt h e 2 黜 迷宫机器人路径规划算法研究 c o m p u t e rt l 啪u g ht h ei n t e m c er s 2 3 2 ， t h er o b o tc a nm a k et h eb e s t d e c i s i o n s e c o n d l y ，t h ep 印e r m a k e sas u i m n a 巧o fas t u d yu po na n i f i c i a l p o t e n t i a lf i e l d ，g e n e t i ca n t h m e t i c ，a n dg r i dm e t h o do np a t hp l a n n i n go f m o b i l er o b o t s t h e n 、耽u s et h ea l g o r i t h mt oc a r 可o u tt h ep a t hp l a m l i n g o fm a z er o b o t c o m p 撕n gt h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h o s e a l g o r i t t l r n s ，a n dc o m b i n e dw i t ht h ec h a r a c t e ro f t h em a z e ，w ed e s i g n e da s i i n p l e ra n dm o r ee f f e c t i v ea l g o r i t l nt os o l v et h em a z e t h e n ，is t u d i e dt h em a z ea n dp u tf o 刑a r dam e t h o do ff i g u r ea b o u t r e a lm a z e ，a n a l y z ea i l dr e s o l v et h ep r o b l e m sb yc o l l l p u t e r ia n a l y z ee i g h t h n d so fm a z es t a m sa i l dt h es t r a t e g yt os o l v ep r o b l e m sw h e nr o b o t si n m a z e f i n a l l y ，t h e 凡l lt e x ti ss u m m 蕊z e da n dm o b i l er o b o tp a t h p l a n n i n g p r o b l e m i sp r o s p e c t e d z h 忉e l i a n g ( p a t t e mr e c o g n i t i o n & i n t e h i g e n ts y s t e i n ) s u p e r v i s e db yc h e n j i n g c h a o k e yw o i 己d s ：m a z er o b o t ，p a t hp l a i m i n g ，a n i f i c i a lp o t e n t i a l ，g e n e t i c a l g o d t h m ，d i s c r e t e l yp o t e n t i a l 3 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者签名：抹力红k 日期：缈忤1 月加 v 忉 玉放 魂佣 陔r 月 名 年 签夕 磁罗 咖 0 教 ： 导 期 乜日 了 指 日 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位 论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除 文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对 所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名： t 1 缸0 ， 日期： 沙 年 1 月25 日 。 迷宫机器人路径规划算法研究 1 1 课题研究的背景 第一章绪论 自从人类创造了第一台机器人以后，机器人就开始显示出它极大的生命 力。但进入2 0 世纪9 0 年代以来，由于具有一般功能的传统工业机器人的应用 趋向饱和，而许多高级生产和特种应用则需要具有各种智能的机器人参与，因而 促使智能机器人获得较为迅速的发展。无论从国际或国内的角度来看，复苏和继 续发展机器人产业的一条重要途径就是开发各种智能机器人，以求提高机器人的 性能，扩大其功能和应用领域【1 。3 】。 从上世纪8 0 年代末9 0 年代初开始，制造业围绕生产模式，出现了一系列 的新概念，如虚拟制造、扩展企业等等，伴随而来的是各种先进制造技术的不断 涌现和发展，如敏捷制造、柔性制造、仓库物流自动化等。随着工厂自动化( f a ) 、 计算机集成制造系统( c i m s 技术的逐步发展和柔性制造系统“f m s 以及自动化 立体仓库( a w ) 的不断发展和广泛应用，传统的自动导引车( a u t o m a t e d g u i d e dv e h i c i e 简称a g v ) 已经不能满足要求，具有智能特性的自主式移动机 器人，如自主导航车辆( a u t o n o m o u sg u d e dv e h i c i e ( 简称a g v ) ，越来越 成为现代制造业的主要选择【“l 。 随着科学技术的迅速发展和人们物质生活的日益提高，机器人的应用领域正 在逐渐扩大。机器人的功能已不再是只能从事某项简单的操作，而是可以承担多 种任务；机器人的工作环境也不再是固定在工厂和车间现场，而是开始走向海洋、 太空和户外，有些甚至己经进入医院、家庭和娱乐场所，具有智能特性的自主式 移动机器人正在向非制造业方向扩展。开发适应于非结构环境下工作的移动机器 人将是机器人发展的一个长远方向。这些非制造业包括航天、海洋、军事、建筑、 医疗护理、服务、农林、办公自动化和灾害救护等，如飞行机器人、海难救援机 器人、化肥和农药喷洒空中机器人、护理机器人等同。 因此，无论是在制造业还是在非制造业，具有智能特性的自主式移动机器人 成为了国内外研究的热点。 6 迷宫机器人路径规划算法研究 1 2 课题研究的意义 移动机器人路径规划作为自主式移动机器人技术的一个重要组成部分， 仍然是研究的一个重要方面。随着各种新方法和新技术的不断出现，对路径规划 的研究有了更广阔的天地。我国在智能移动机器人研究方面虽然已经取得了一定 的成果，如地面自主导航车、水下自主机器人和飞行机器人等。但由于起步较晚， 在研究和应用方面都落后于一些西方国家，而且还没有达到完全实用。因此，进 行移动机器人路径规划算法的研究，具有一定的理论意义和工程应用意义，而迷 宫机器人是移动机器人的典型应用，也是检验路径规划算法较好的平台。 1 3 论文的主要工作和创新点 移动机器人路径规划是移动机器人技术的主要研究内容之一，虽然已经有近 四十年的研究工作，即从不同的环境建模，针对不同的应用领域等提出了很多路 径规划的方法，但远远没有达到完全实用的程度，国内外研究者仍在继续探索， 移动机器人的路径规划问题仍是一个值得研究的问题。本文在总结前人研究成果 的基础上在这方面做了一部分研究工作，并且应用在迷宫机器人路径规划上面， 使能按最优路径自主走出迷宫。 本文的组织结构如下： 第一章，绪论，讨论了本论文研究的背景和研究的意义。 第二章，国内外移动机器人的发展状况，主要讨论了国内外移动机器人硬件 的发展历程和发展现状，其中特别对迷宫机器人的发展作了介绍。 第三章，国内外移动机器人路径规划技术的发展现状，首先给出了国内外一 些对路径规划的定义。接着对常用的移动机器人路径规划技术进行了介绍，对人 工势场法、栅格法、遗传算法的原理做了一个比较详细的说明，为后文打下伏笔。 第四章，迷宫机器人的硬件体系结构，讨论了迷宫机器人硬件部分的车体构 成，以及各种功能模块的选取。然后对迷宫机器人的运动学原理进行了理论上的 分析。 7 。 迷富机器人路径规划算法研究 第五章，迷宫机器人软件实现，从软件实现角度讨论了路径规划算法在迷宫 机器人上面的实现。利用模块化的思想，不但有利于程序理解和编写，而且有利 于程序的移植。 第六章，迷宫机器人路径规划算法的研究，对迷宫机器人的路径规划从理论 上作了探讨。首先，对实际的迷宫利用二维数组进行了数字化表示，有利于计算 机仿真的实现。利用深度优先法对迷宫路径规划问题进行了实现，证明是可解的。 对遗传算法在迷宫机器人路径规划上的应用也进行了探究，在此基础上，提出了 离散势场方法来解决迷宫机器人的路径规划问题，并进行了仿真。 8 。 迷宫机器人路径规划算法研究 第二章国内外移动机器人的发展现状 2 1 国外移动机器人发展现状 移动机器人的研究开始于上世纪6 0 年代术期。斯坦福研究院( s r l ) 的 n i sn i s s e n 和c h ar i e sr o s e n 等人，在1 9 6 9 年至1 9 7 2 年中研制出了取名为 s h a k e y 的自主移动机器人，与此同时，最早的操作式步行机器人也研制成功， 其中最著名的是g e n e r a ie l e c t r cq u a d r u p e d 的步行机器人。上世纪7 0 年代 末，随着计算机的应用和传感器技术的发展，移动机器人又有了新的进展。上世 纪8 0 年代，移动机器人的研究进入了一个高潮时期。从上世纪8 0 年代开始， 美国国防高级研究计划局( d a r p a ) 专门立项，制定了地面天人作战平台的战略 计划。从此，在全世界掀开了全面研究室外移动机器人的序幕，如d a r p a 的“战 略计算机计划中的自主地面车辆( a l u ) 计划；日本通产省组织的极限环境下作 业的机器人计划：欧洲尤里卡中的机器人计划等。初期的研究，主要从学术角度 研究室外机器人的体系结构和信息处理，并建立实验系统进行验证。虽然对机器 人的智能行为期望过高，导致室外机器人的研究未达到预期的效果，但却带动了 相关技术的发展，为探讨人类研制智能机器人的途径积累了经验，同时，也推动 了其它国家对移动机器人的研究与开发。进入上世纪9 0 年代，以研制高水平的 环境信息传感器和信息处理技术，高适应性的移动机器人控制技术，真实环境下 的规划技术为标志，展开了移动机器人更高层次的研究。随着技术的进步，移动 机器人开始在更现实的基础上，开拓各个应用领域，向实用化进军。如美国n a s a 资助研制的“丹蒂i i ，八足行走机器人；美国n a s a 研制的火星探测机器人索杰 那于1 9 9 7 年登上火星；德国研制了一种轮椅机器人，并在乌尔姆市中心车站的 客流高峰期的环境和1 9 9 8 年汉诺威工业商品博览会的展览大厅环境中进行了实 地现场表演，获得了巨大的成功。 美国d a r p a 的战术移动机器人计划是一个4 年研究计划，于19 9 8 年开 始。该计划研究的是一个多机器人系统，分两阶段进行：技术开发和系统设计。 美国的m d a r s 项目是在著名的保安机器人r o b a r t 的基础上建立的一个多移 9 迷宫机器人路径规划算法研究 动机器人平台，用来在指定地点执行随机巡逻任务。美国的f e t c h 计划是在 b u g s 计划的基础上，研究使用一群小的、坚固的自主的移动机器人去清除地表 上的未爆炸的m4 2 炮弹。机器人正在从工厂的结构化环境进入人们每天的生活 环境医院、办公室、家庭、建筑工地和其它杂乱及不可控环境。因此要求机 器人不仅能自主完成工作，而且能与人共同协作完成任务或在人的指导下完成任 务。k h a b 计等讨论了这个问题，并在斯坦福大学的两个完整性移动平台上进行 了演示。 自从19 9 6 年成功地举行了第一次世界机器人足球赛以来，一年一度的世界 机器人足球赛己经吸引了越来越多的团体参加，极大地推进了多移动机器人技术 的研究，成为研究和验证人工智能成果的实验床。国际迷宫机器人大赛( t h e i n t e m a t o n a lm i c r or o b o tm a z ec o n t e s t ) 自从首次举办以来，每年主办一 次，也吸引了国际上研究人工智能的广大爱好者，也成为广大人工智能工作者交 流和竞争的平台。从技术和算法上来说，相比上一年，每年都有很大的进步。为 其他移动机器人的路径规划提供了很好的实验基础。 2 2 国内移动机器人发展现状 国内在移动机器人的研究起步较晚，但是经过近2 0 年的发展，在各项技 术上都有较大进步，行走机器人和人形机器人的研究得到进一步重视，开放式网 络机器人的开发成为新热点，随着时间的推移和技术的发展，智能移动机器人技 术将成为我国机器人技术关注和开发的重点。 清华大学与香港中文大学合作，联合研制开发出一种全方位移动清扫机器 人。该机器人具有如下特点：采用全方位轮实现任意方向的移动，使得机器入可 执行对狭窄区域的清扫任务。采用开放式机器人控制结构，实现硬件可扩展，软 件可移植、可继承，使机器人作为服务载体具有更好的功能适应性。机器人具有 在拥挤环境下的实时避障功能，能适应不断变化的清扫工作环境。具有遥控操作 和自主运动两种运行方式。吸尘机构可实现吸尘腔路的自动转换，提高了吸尘效 1 0 迷宫机器人路径规划算法研究 率。有智能电源管理功能，延长了运行时间，提高了对有限的移动动力资源的利 用率。 清华大学的t h m r - l i l 系统的车体选用b j10 2 3 面包车改制，t h m r 一川上集成 了二维彩色摄像机、磁罗盘光码盘定位、g p s 、超声等传感器，计算机系统采用 s u ns p a r k1 0 一台、p c 4 8 6 二台和8 0 9 8 单片机数台。s u n 完成任务规划，根 据地图数据库信息进行全局规划。一台p c 机完成视觉信息处理，另一台p c 完 成局部规划、反射控制及系统监控，数台8 0 9 8 单片机完成超声测量、位置测量、 车体方向速度的控制。它的体系结构以垂直式为主，采用多层次“感知一动作 行为控制及基于模糊控制的局部路径规划及导航控制。利用t h m r - i i i 研究了直 线跟踪算法、白线跟踪算法、连续障碍物跟踪算法、漫游避障、路标识别、视觉 神经网道路识别、道路模糊识别等多种导航算法，完成了主楼前穿越主干道、路 口进人、主楼前绕“o o 字等整体实验。t h m r 一川在自主道路跟踪时达到 5 1 0 k m h ，避障达5 k m h 。 2 。3 国内外迷宫机器人的发展现状 迷宫机器人是移动机器人路径规划算法的典型应用，在国际上迷宫机器人一 直是控制领域和计算机领域的研究热点问题。19 7 2 年，t h em a c h i n ed e s i g n 发起走迷宫比赛，19 7 7 年，作为走迷宫比赛的解决方案，l e l 三es p e c t r u m m a g a z i n e 提出一个“m i c r o m o u s e 的概念。自那以后，关于“m i c r o m o u s e 走迷宫的比赛就一直没有中断过。2 0 0 6 年迷宫机器人大赛( u k m m 2 0 0 6 c o m p e 卅i o n ) 冠军机器人用了5 9 o o 秒的时间去熟悉迷宫，只用了3 6 4 秒的 时间去完成迷宫。迷宫机器人的硬件也越来越先进，算法也越来越多。早期的有 向左( 右) 算法，在迷宫中，机器人一直沿着迷宫隔栅的左边或者右边行走，可 以顺利找到迷宫出口，但是对于有孤岛的迷宫，这种算法很容易陷入死循环，后 来又有水流法也即广度优先算法等等，在这里就不一一举出了。 。 迷宫机器人路径规划算法研究 2 4 本章小结 本章从硬件出发，首先介绍了移动机器人在国内外的发展历史及发展现状， 然后对迷宫机器人的一些现状也作了简单介绍。为后面的工作做下铺垫以及必要 的说明。 1 2 迷宫机器人路径规划算法研究 第三章移动机器人的路径规划技术 3 1 移动机器人路径规划方法概述 j ts c h w a r t z 和m s h a r 在文章中这样定义路径规划：设曰是一个有若干 刚体部件( 其中一些可能与其它部分用关节相连，另一些可能会独立的存在) 所 组成的机器人系统，它共有k 个方向的自由度，并假设b 在一个充有若干机器人 系统己知的障碍物的二维和三维空间y 自由运动。对b 来说，路径规划问题就是 给定b 的起始位置z 和一个希望达到的终止目标z ，确定是否有一条对曰来说 从z 到z ，的无碰路径，如有，则规划出来【8 】。 蒋新松在水下机器人中为规划路径做出了这样定义：路径规划是自治 式移动机器人的一个重要组成部分，它的任务就是在具有障碍物的环境内，按照 一定的评价标准，寻找一条从起始状态( 包括位置和姿态) 到达目标状态( 位置 和姿态) 的无碰路径。障碍物在环境中的不同分布情况当然直接影响到规划的路 径，而目标位置的确定则是由更高一级的任务分解模块提供【2 l 。 路径规划技术是智能机器人领域中的核心问题之一，也是机器人学中研究 人工智能问题的一个重要方面。我们希望未来的机器人能具有感知、规划和控制 等高层能力。它们能从周围的环境中收集知识，构造一个关于环境的符号化的世 界模型，并且利用这些模型来规划、执行由应用者下达的高层任务。其中的规划 模块能生成大部分机器人要执行的命令，其目标是实现机器人的使用者在较高层 次上给机器人下达一些较宏观的任务，由机器人系统自身来填充那些较低层的细 节问题。 路径规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化 程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况 下，对路径规划算法的研究更显得尤为重要，这将从根本上改变移动机器人的导 航性能，将提高移动机器人的智力水平，减少移动机器人在移动过程中存在的不 1 3 。 迷宫机器人路径规划算法研究 确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机 器人、探测机器人、服务机器人、汽车自动驾驶系统打下基础。下面将简单综述 国内外移动机器人路径规划的方法。 3 2 路径规划问题的分类 根据机器人对环境信息知道的程度不同，路径规划可分为两种类型：环境 信息完全知道的全局路径规划和环境信息完全未知或部分未知，通过传感器在线 地对机器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局 部路径规划。 3 2 1 全局路径规划 机器人全局路径规划基本上都要包括以下两个步骤【9 】： 1 ) 建立环境模型，对己知的静态环境进行抽象后建立相关的模型。 2 ) 搜索路径，根据优化条件搜索出合乎条件的路径。 采取何种方法对己知全局环境进行描述是全局路径规划中的一个重要课题。 其中全局路径规划按世界模型表达方法的不同，目前存在4 种比较典型的全局路 径规划方法：可视图法、自由空间法( f r e es p a c ea p p r o a c hj 、环境地图法和 栅格法( g r i d s ”0 1 可视图法视机器人为一点，将机器人、目标点和多边形障碍物的各顶点进行 组合连接，要求机器人和障碍物各项点之间、目标点和障碍物各顶点之间以及各 障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的【1 1 1 。搜索 最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。 运用优化算法，可删除一些不必要的连线以简化可视图，缩短搜索时间。常用的 优化方法d i i k s t r a 算法【1 2 】和搜索算法【1 3 】等。该法能够求得最短路径，但假设机 器人的尺寸大小忽略不计，使得机器人通过障碍物顶点时离障碍物太近甚至接 触，并且搜索时间长。另外的缺点就是此法缺乏灵活性，即一旦机器人的起点和 目标点发生改变，就要重新构造可视图，比较麻烦。己经证明用可视图法计算对 于n 条连线的搜索时间为d ( 2 ) 【1 4 15 】。可视图法能求得最短路径，但缺乏灵活 1 4 迷宫机器人路径规划算法研究 性，若障碍物过多，搜索时间会很长。如果采用优化算法删除一些不必要的连线， 可以简化可视图，缩短搜索时问。因此，可视图法适用于多边形障碍物，但对于 圆形障碍物该法失效【1 6 l 。 自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形 等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行 路径规划。该法比较灵活，起始点和目标点的改变不会造成连通图的重构，但算 法的复杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短路径。 栅格法【17 】将机器人工作环境分解成一系列具有二值信息的网格单元，多采 用四叉树或八叉树表示工作环境。并通过优化算法完成路径搜索。该法以栅格为 单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响 着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量小， 规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了， 环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时 间长，可以采用改进的栅格法弥补栅格法的不足。 3 2 2 局部路径规划 局部路径规划的主要方法有：人工势场法、遗传算法、模糊逻辑算法、神经 网络法等。 人工势场法是由k h a t b 提出的一种虚拟力法。其基本思想是将机器人在环 境中的运动视为一种虚拟的人工受力场中的运动【18 j 。障碍物对机器人产生斥力， 目标点产生引力，引力和斥力的合力作为机器人的加速力，来控制机器人的运动 方向和计算机器人的位置。该法结构简单，便于低层的实时控制，在实时避障和 平滑的轨迹控制方面，得到了广泛的应用，但对存在局部最优解的问题，容易产 生死锁现象，因而可能使机器人在到达目标点之前就停留在局部最优点【1 9 】。 j h o i i a n d 在6 0 年代初提出了遗传算法，以自然遗传机制和自然选择等生 物进化理论为基础，构造了一类随机化搜索算法。它利用选择、交叉和变异来培 养控制机构的计算程序，在某种程度上对生物进化过程做数学方式的模拟【捌。 它不要求适应度函数是可导或连续的，而只要求适应度函数为正，同时作为并行 算法，它的并行性适用于全局搜索。多数优化算法都是单点搜索算法，很容易陷 1 5 迷宫机器人路径规划算法研究 入局部最优，而遗传算法却是一种多点搜索算法，因而更有可能搜索到全局最优 解。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息，所以解决了一 些其它优化算法无法解决的问题。但遗传算法运算速度不快，进化众多的规划要 占据较大的存储空间和运算时间。 基于实时传感信息的模糊逻辑算法参考人的驾驶经验，通过查表得到规划 信息，实现局部路径规划。该方法克服了势场法易产生的局部极小问题，适用于 时变未知环境下的路径规划，实时性较好。 神经网络法是基于神经网络的智能控制，由于神经元网络具有很强的自学 习、自适应能力，可以在训练样本中自动获取知识，具有并行处理的特征，所以 在信息处理、模式识别、智能控制等领域有着广泛的应用前景。神经网络为解决 非线性系统的控制问题提供了活力，被广泛的应用于复杂系统的辨识、建模和控 制。 3 3 人工势场法 3 3 1人工势场法简介 人工势场法是移动机器人局部路径规划中常用的一种理想算法，其特点主 要表现为：计算量小、易满足实时性要求和产生路径相对比较平滑。基于以上特 点和实际情况的考虑，本论文的路径规划算法将在人工势场法原理的基础上进行 研究、分析和实现。 k h a t b 把机械手或者是移动机器人在环境中的运动视为在一种抽象的人 造受力场中运动【1 8 l ：目标点对机器人产生引力，障碍物对机器人产生斥力，最 后根据合力来确定机器人的运动。应用势场法规划出来的路径一般是比较平滑并 且安全，但是这种方法存在局部最优点问题。为了解决这个问题，许多的学者进 行了研究：如r i m o n ，s h a h i d 和k h o s i a 等。他们期望通过建立统一的势能函 数来解决这一问题。但这就要求障碍物最好是规则的，否则算法的计算量将很大， 有时甚至是无法计算的。 势场法的基本思想是在移动机器人的上作环境中构造这样的一个人工势 场，使得在该势场中移动的机器人受到其目标位姿引力场和障碍物周围斥力场的 1 6 迷宫机器人路径规划算法研究 共同作用。由于其在数学描述上简洁、美观，这种方法仍是最具吸引力的。但它 也有其内在的局限性，即当目标附近有障碍物时，移动机器人可能永远也到达不 了目的地。在以前的许多研究中，目标和障碍物都离的很远，当机器人逼近目标 时，障碍物的斥力变的很小，甚至可以忽略，机器人将只受到吸引力的作用而直 达目标。但在许多实际环境中，往往至少有一个障碍物与目标点离的很近，在这 种情况下，当移动机器人逼近目标的同时，它也将向障碍物靠近，如果利用以前 对引力场函数和斥力场函数的定义，斥力将比引力大的多，这样目标点将不是整 个势场的全局最小点，因此移动机器人将不可能到达目标。 综合看来，传统势场法存在四方面问题【2 1 】：f 1 ) 陷阱区域；( 2 ) 在相近障 碍物之间不能发现路径；( 3 ) 在障碍物前面震荡；( 4 l 在狭窄通道中摆动。 尹 图3 1 人工势场法中引力和斥力示意图 3 3 2 势场函数的建立 移动机器人可以简化为一个质点，它的移动空间为二维的，机器人在移动空 间中的位置为x = 五j ，】r 通常，目标势场函数的建立如下【勿【2 3 l ： 1 7 迷宫机器人路径规划算法研究 吃，( = 去蠡( 石一，) 2 式【3 1 】 其中后为位置增益，( x x 州) 为当前位置与目标位置的相对距离，相应的 吸引力为目标势场的负梯度： j 乙( x ) = 一胛d u 二( x ) = 七( x j 叫) 式【3 2 】 当机器人接近目标过程中这个量收敛到零。 通常的斥力场函数为： u 。x ，： 三刁( 刍一去) 2 p 岛式。3 3 ， 【o 其中刁为位置增益系数，p 为机器人在空间的位置x 与障碍物之间的最 短距离，岛是一个常数，代表障碍物的影响距离。 相应的斥力为： 兄似，：一胛饥。别： 文吉一去) 2 专罢 p 风 式。孓4 ， 【o 其中罢= c 警，争 机器人所受的合力为： k = 疋+ 兄 式【3 5 】 这个力决定了机器人的运动。实际上，当我们用这个力来控制机器人时，如 果目标在障碍物的影响范围之内，则机器人永远也到不了目标。因为当机器人向 目标靠近时，距离障碍物也越来越近，这样吸引力减小，斥力增加，机器人将受 到排斥而不是吸引。这个问题在以前的文献中很少提及，但它确实存在，尤其是 在像迷宫这样狭窄的环境中，值得研究。存在的原因是目标点不是整个势场的全 局最小点。为解决这个问题，可以通过建立一个新的斥力场函数，这个斥力场函 数把机器人与目标之间的相对距离也考虑进去，从而确保整个势场在目标点全局 最小。关于此将在第六章中作详细的分析。 1 8 迷宫机器人路径规划算法研究 3 4 栅格法 3 4 1 栅格法简介 栅格法是由w e h o w d e n 在1 9 6 8 年提出的，他在进行移动机器人路径 规划时采用了栅格( gr d ) 表示地图，在处理障碍物的边界时，避免了复杂的计算。 这种算法是将机器人的运动空间用固定大小的栅格分成许多小空间，每个栅格代 表一个节点，所有节点分为障碍物节点和自由节点两大类。每个自由节点连接相 邻的自由节点组成一个自由区，用搜索算法生成从初始节点到目标节点的路径。 可以看出栅格粒度的大小与环境描述的精确度以及搜索算法的计算两密切相关， 栅格划分越细，障碍物的表示越精确，但会占据大量的存贮空间，算法的搜索范 围将成指数增加，如果栅格粒度太大，计算量小，但规划的路径会很不精确。所 以栅格粒度大小的确定，是栅格法中的主要问题【2 4 1 。 3 4 2 栅格法的建模 用栅格法来表示格子环境模型中存在障碍物的可能性的方法起源于美国 c m u 大学。栅格法的基本思想是将一块实际的场地划分成等面积的小区，每个 小区称为一个栅格，栅格面积的大小一般由机器人车体大小来决定。图3 2 显 示了一个场地的栅格划分情况。如果让机器人遍历整个场地，则我们可以记录机 器人在每个栅格上的中心位置的运动情况，同时，还可以记录机器人在运动过程 中探测到的障碍信息，这样，将机器人的运动情况以及障碍信息记录在一个栅格 上，就定义了这个栅格的属性。所有栅格的属性就构成了一幅关于场地的地图。 利用栅格法进行任务规划的目的是建立所谓的数字地图，在地图中存储移 动机器人的运行轨迹和障碍等相关信息。栅格法要将连续路径信息离散化，这样 在地图中记录的路径信息和实际路径信息会有误差，误差的大小由栅格大小，即 地图分辨率决定。机器人的路径信息被离散化后，机器人的运动轨迹被分解为单 个的运动，这些单个的运动被记录在每个栅格上。每个栅格上的运动信息规定了 机器人在这个栅格上的运动方向( 例如，向前，向后，向左，向右等) 。理论上， 1 9 迷宫机器人路径规划算法研究 移动机器人在每个栅格上的微小运动有无数种，但考虑到建模的复杂性，一般在 实际运用上只定义了八种运动，它们分别是：前、后、左、右、右前、右后、左 后、左前，如图3 3 所示。在简单的迷宫中，可以更加简单的只用考虑四种运 动方式，即：前、后、左、右。 栅格场地 广。 ? ? 栅格 气卢 。 图孓2 栅格场地的划分图3 3 移动机器人的八种运动方式 3 4 3 栅格法的信息编码 栅格法的模型建立起来后，就应该对模型进行信息的编码。最常见的信息编 码格式如下： 障碍物信息：1 一当前栅格有障碍( 障碍物节点) ；0 一当前栅格无障碍 ( 自由节点) 。 地图上的栅格采用行列划分的矩阵存储方法，如图3 - 3 所示，深色小块代 表一个栅格，记为侧g ( f ，) ，这个栅格的信息将记录在存储器的栅格存储阵列中 的第f 行，第_ ，列，采用这种“栅格一存储 映射办法，可以建立起整幅地图。 根据该地图，就可以建立一条从起点到终点的无碰安全路径。 栅格场地 广 f 栅格g ( i ，j ) 。黝 迷靓器人路径规划算法研究 图3 4 栅格地图的存储 这种方法相对于常规的路径规划方法有如下优点： ( 1 ) 无需考虑运动对象的运动轨迹、数量及形状； ( 2 ) 该算法计算量小，可实时计算以使机器人适应动态环境进行在线路径 规划； ( 3 ) 可通过改变障碍物地图的初值和减函数来调整路径的安全性和优化 路径。 3 5 遗传算法 3 5 1 遗传算法的特点和步骤 遗传算法( g e n e t i ca i g o r t h m ) 简称g a 是以遗传学和自然选择等生物进 化理论为理论基础所构造的一类搜索算法，它在某种程度上对生物进化过程进行 了数学方式的模拟【硼。h o l l a n d 在他的著作“自然和人工生命中的适应性中 将遗传算法的基本框架分为适应系统和进化系统两个方面f 2 6 l 。它作为一种新的 全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理以及应用范围广等 显著特点，越来越多的受到人工智能领域学者们的关注。 遗传算法是一种通过模拟自然进化过程搜索最优解的方法。过去3 0 年中， 在解决复杂的全局优化问题方面，遗传算法已经取得了成功的应用，并受到了人 们广泛的关注。与传统优化方法相比，遗传算法具有较好的健壮性，有以下特点 像7 l ： ( 1 ) ，遗传算法是对参数的编码进行操作，而不是对参数本身； ( 2 ) ，搜索过程是从一组解迭代到另一组解，这样避免陷入局部最优解 的可能性，而有较大的可能求得全部最优解； ( 3 ) ，使用的是随机搜索过程，而非确定性搜索过程； ( 4 ) ，遗传算法对于函数基本上没有任何特殊要求，只利用适应度信息， 不需要微分等其它辅助信息，应用范围更广。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由m 个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传 迷宫机器人路径规划算法研究 算法的运算过程也是一个反复迭代过程，第代群体记做p ( f ) ，经过一代遗传和 进化后，得到第f + l 代群体，它们也是由多个个体组成的集合，记做p o + 1 ) 。 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度 较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体 x ，它所对应的表现型x 将达到或接近于问题的最优解。其算法思想可以用图 3 5 更加清晰的表达。 图孓5 ：遗传算法流程图 由图孓5 可以看出，遗传算法的主要步骤如下： ( 1 ) ：制定编码、解码策略，把目标问题的解空间转换为位串结构的 编码空间s ； ( 2 ) ：确定适应值函数八功即目标函数； ( 3 ) ：确定遗传策略，包括确定群体大小m ，选择、交叉、变异等遗传 操作的方法，以及交叉概率p c 。、变异概率砌等遗传参数； ( 4 ) ：随机生成初始群体蜀； ( 5 ) ：对群体中个体位串进行解码，并计算其适应值厂( z ) ； 迷宫机器人路径规划算法研究 ( 6 ) ：按照遗传策略，对群体的个体进行选择、交叉和变异等遗传操作， 形成下一代群体； ( 7 ) ：判断进化过程是否可以结束，如群体性能是否满足某一指标，或 己完成预定的迭代次数，不可结束则返回步骤( 5 ) 。 3 5 2 遗传算法的组成 遗传算法主要由五个部分组成：编码方式、初始群体产生的方法、适应度 函数、遗传操作、算法终止条件、算法参数的设置。要利用遗传算法成功的解决 优化问题，每个部分的设计都非常关键【2 8 】。 3 5 2 1 编码原理 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关 键步骤。编码方法不仅决定个体的染色体排列形式，还决定个体从搜索空间的基 因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算 子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群 体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能会使得 交叉运算、变异运算等遗传操作可以简单地实现和执行；而一个差的编码方法， 却有可能会使得交叉运算、变异运算等遗传操作难以实现，也有可能会产生很多 在可行解集合内无对应可行解的个体，这些个体经解码处理后所表示的解称为无 效解。虽然有时产生一些无效解并不完全都是有害的，但大部分情况下它却是影 响遗传算法运行效率的主要因素之一。 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的 应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套很严 密的指导理论及评价准则能够帮助我们设计编码方案。作为参考，d ej o n g 曾 提出了两条操作性较强的实用编码原则( 又称为编码规则) ： 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问题相 关的且具有低阶、断定以长度模式的编码方案。 编码原则二( 最小字符集编码原则) ：应使用能使问题得到自然表示或描述 的具有最小编码字符集的编码方案。 上述d ej o n g 编码原则仅仅是给出了设计编码方案时的一个指导性大 纲，它并不适合于所有的问题。所以对于实际应用问题，仍必须对编码方法、交 2 3 迷宫机器人路径规划算法研究 叉运算方法、变异运算方法、解码方法等统一考虑，以寻求一种对问题的描述最 为方便、遗传运算效率最高的编码方案。 有意义积木块编码规则要求具有目标问题的先验性知识，然而这一要求对 大多数问题的求解来说是比较苛刻的，不过第二条规则是非常实用的。 通常的编码方法包括： 二进制编码方法 格雷码编码方法 浮点数编码方法 符号编码方法 多参数级联编码方法 ， 多参数交叉编码方法 二进制编码的优点在于编码、解码操作简单，交叉、变异等遗传操作便于 实现，而且便于利用模式定理进行理论分析等；其缺点在于，不便于反映所求问 题的特定知识，对于一些连续函数的优化问题等，也由于遗传算法的随机特性而 使得其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制 编码存在着连续函数离散化时的映射误差，个体编码串较短时，