（模式识别与智能系统专业论文）部分环境信息已知的智能机器人路径规划方法研究.pdf

南京理工大学硕士学位论文部分环境信息已知的智能机器人路径规划方法研究 摘要 智能移动机器人是机器人研究领域的一个重要分支，有着巨大的应用潜力， 因此当前对智能移动机器人和无人自主车领域的研究吸引着众多学者的注意。路 径规划问题是智能移动机器人开发的重要环节。 本文从全局规划和局部信息相结合的角度重点研究了基于部分环境信息的智 能移动机器人的路径规划问题。主要进行了如下工作： 首先对国内外智能移动机器人路径规划的研究现状，研究方法等进行了系统 的归纳和总结，分析了其各自优点和不足之处，为本论文的研究工作奠定了重要 的基础。 其次，本文重点讨论了在部分环境信息己知情况下，基于动态a 算法( 算 法) 的路径规划方法。并且详细讨论了这种情况下相应的环境表达方式。文章首 先介绍了一般的栅格表示法，以及应用广泛的四叉树表示法，并且将一种简单、 有效的方法应用到了四叉树邻居查找过程。而后本文研究了一种新的带边框四叉 树表示法，并应用到了规划算法当中。 最后，针对所研究的规划方法和环境的表达，本文在v c 环境下进行了仿真。 分析了仿真得到的数据，证明了所讨论算法的正确性和有效性。并且本文将所研究 的算法应用到了实际的地形图中，取得了良好的效果。 总体来说，本文参考了路径规划技术的最新成果，具有一定的实用价值。 关键词：路径规划，智能移动机器人，全局规划，动态a + ( d ) ，带边框四叉树 仿真 a b s t r a c t 硕士论文 a b s t r a c t i n t e l l i g e n tm o b i l er o b o ti sa ni m p o r t a n tb r a n c ho fr o b o ld u et oi t s g r e a t a p p l i c a t i o np o t e n t i a l ，c u r r e n tr e s e a r c ha n dd e v e l o p m e n to fi n t e l l i g e n tm o b i l er o b o ta n d a u t o n o m o u sl a n dv 曲i c l eh a v ea t t r a c t e dt h ea t t e n t i o no fal o to fr e s e a r c h e r s t h e p r o b l e mo fp a t hp l a n n i n gi sav e r yi m p o r t a n tp a r to ft h es t u d yo fi n t e l l i g e n tm o b i l e r o b o t ， f r o mt h ep o i n to fc o m b i n i n gg l o b a lp l a nw i t hl o c a li n f o r m a t i o n ，t h i st h e s i s r e s e a r c h e st h ep a t h p l a n n i n gp r o b l e mo ft h ei n t e l l i g e n tm o b i l er o b o tb a s e do u p a r t i a l l y k n o w ne n v i r o n m e n t si n f o r m a t i o n t h ef o l l o w i n gi st h en l a i nw o r k s ： f i r s t l y ，t h i sp a p e ri n t r o d u c e st h ec o i m n o nu s e dp l a n n i n ga l g o r i t h m sf o ri n t e l f i g e n t m o b i l er o b o ti nt h ec o u n t r ya n da b r o a d ，a n dt h er e s e a r c h i n gs i t u a t i o ni se l a b o r a t e da n d s u m m a r i z e d ，i ta l s oa n a l y z i n ga d v a n t a g e sa n dd e f a u l t so fe a c ha l g o r i t h mw h i c hm a d e a l l i m p o r t a n tb a s i sf o rt h er 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 u gi nt h et h e s i s s e c o n d l nt h i st h e s i sd i s c u s s e st h em e t h o do fp a t hp l a n n i n gb a s e do nt h ed y n a m i c a a l g o r i t h m ( d a l g o r i t h m ) a n dt h ep a r t i a l l y 。k n o w ne n v i r o n m e n t s t h ep a p e ra l s o d i s c u s s e st h er e p r e s e n t a t i o no ft h ee n v i r o n m e n tc o r r e s p o n d i n gt ot h em e t h o d f r o m r e g u l a rc e l lr e p r e s e n t a t i o nt ot h ec o m m o nu s e dq u a d t r e er e p r e s e n t a t i o n ，a n df i n a l l ya k i n do fn e wr e p r e s e n t a t i o no ff a r m e d - q u a d t r e e as i m p l ea n de f f i c i e n tm e t h o du s e df o r f i n d i n gq u a d - t r e en e i g h b o ri sa l s oi n t r o d u c e di nt h ep a p e r f i n a l l y , t h ea u t h o rh a sd e s i g n e dt h es i m u l a t i o ns y s t e m su n d e rv c f o rt h em e t h o do f p a t hp l a n n i n ga n dr e p r e s e n t a t i o no ft h ee n v i r o n m e n t t h ed a t ao ft h es i m u l a t i o ni sa l s o a n a l y z e dt op r o v et h ec o r r e c t n e s sa n dv a f i d i t yo fi t t h ea l g o r i t h mi s a l s ou s e di nt h e t e r r a i nm a po ft h er e a lw o r l d i nc o n c l u s i o n ，t h i st h e s i sr e f e r st ot h el a t e s tf r u i to np a t hp l a n n i n gt e c h n i q u e ，a n d h a sp r a c t i c a l i t i e si ns o m ew a y s k e y w o r d s ：p a t hp l a n n i n g ，i n t e l l i g e n tm o b i l er o b o t ，g l o b a lp l a n ，d y n a m i ca + ( d 4 ) f r a m e d - q u a d - t r e e ，s i m u l a t i o n 声疆 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：益整z 口眸多月目 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上薅公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：塑2 。u 年f 月日 南京理工大学硕士学位论文部分环境信息已知的智熊机器人路径规划方法研究 1 绪论 1 1 本课爱的研究意义和国内外研究现状 随着当代计算机技术、控制理论、能源技术等的发展，机器人技术在短短的几十 年间发生了日新月异的变化。机器人作为人类2 0 世纪最伟大的发明之一，其技术的 发展代表着人类技术发展的最前沿，并将对人类社会的生产和生活产生深远的影响。 特别是作为高级形态的智能机器人已经在制造业中占有不可取代的地位。 始于上世纪6 0 年代末的智能移动机器人研究，是机器人研究领域中重要的研究方 向。本文所讨论的路径规划方法主要是针对地面智能移动机器人，是无人地面自主车 的一种，是指在道路网、野外等环境中，无需人工干预就可以自主完成行驶任务的车 辆，属于智能机器人研究领域中的一项高技术。由于智能移动机器人具有在无人驾驶 情况下的自主移动性能，因此可以应用到核电站、军事、宇宙探索，以及海洋开发等 危险环境下环境探索，并且正在逐步进入交通运输，社会服务业领域。所以世界各国 对于智能机器人的研究都十分的重视。 当前，移动机器人的研究成果主要集中在军事和航天探索领域。八十年代初，美 国国防高级研究计划署( d a r p a ) 的主持下，卡内基梅隆大学( c m u ) 、斯坦福 大学和麻省理工学院( m r r ) 等开展了对a g v ( a u t o n o m o u sg r o u n dv e h i d e ) 或者是 u g v ( u n m a n n e dg r o u n dv c 帕c i e ) 的研究，并且开展了u g v d e m o 系列项目。特别 是2 0 0 4 年3 月1 3 日，作为研制无人驾驶作战车计划的一部分，d a r p a 在美国西部 的莫哈维沙漠组织了首次无人驾驶车赛，其中c m u 的基于h m m w v 【1 ( 类似于j e 印， 由悍马车改造) 的n a v l a b 移动机器人系统取得了最好的成绩，在越野环境下自主 行驶了7 4 英里，它还配备了扫描雷达、立体影像系统、扫描测距雷达系统、地图绘 制工具、方位评估系统以及强大的计算系统。其路径规划系统正是针对野外环境下环 境信息不完全，甚至完全未知的情况设计的。 图1 1c m u 的基于h m m v w s ( 类似于j e e p ) 的原型自主车 除了军事上的应用，移动机器人在外部空间探索中也大有用武之地，如美国航空 1 绪论硕士论文 航天局( n a s a ) 的火星探测车 2 j ，也是个自主式的移动地面车辆，其中路径探测和 规划也是其重要部分。 国内从八五期间开始了这方面的研究，有多所高校联合研制了室外移动机器入， 其某些关键技术达到了国际先进水平，清华大学计算机系自主开发了t 蹦r _ i i 型机 器人【3 ，行动决策与规划技术达到了国际领先水平。 自主式地面移动机器人系统可从上到下大致分为感知、规划和控制三丈部分，其 中规划部分是个体现机器人“智能”的重要环节。规划问题源于计算几何学的传统 研究课题。事实上，不光是自主移动机器人，在各种机器人的研究领域中规划问题都 是一个关键的问题。由于规划问题的复杂性，不同研究者从不同的角度研究某一方面 的问题，对具体问题的提法也就不完全相同。例如，八十年代初，s c h w a r t z 提出的搬 钢琴问题( p i a n om o v e r s p r o b l e m ) f 4 i 就是典型的规划问题，而一般制造机器人机械 臂在空间中的运动也是是个规划闷题。但是从根本上来说，规划就是当机器人接收到 上层动作命令时告诉机器人怎样移动的过程碡】，运动规划或者轨迹规划描述的就是这 一类问题。 而本文所研究讨论的智能移动机器人的路径规划问题可以看作是机器人运动规 划的一个部分。就移动机器人来说，路径规划闯题可以表示为在有障碍物的工作环境 中，如何为机器人寻找一条恰当的从起始状态到目标状态的运动路径，使机器人在运 动过程中能安全、无碰撞地绕过所有的障碍物。 综上所述，路径规划系统是地面智自8 移动机器人系统中的关键部分。本文所讨论 的规划方法正是以智能机器人为应用背景，基于国外学者针对路径规划在地面移动机 器人上的最新应用成果( c m u 的自主车的规划系统、火星探测车的规划算法) 而进行 的研究，具有一定的实用价值。 1 2 部分环境信息已知的路径规划嗣囊概述 1 2 1 援划问曩的分类和结构 如前所述，对于不同的研究角度，路径规划的定义有所不同。对于移动机器人来 说路径可以描述成是连接起来的、通向目标的自由空间单元( 非障礴物区域单元) 组 成的序列，这些自由空闻单元可以是大小各异的、形状不同的自由区域，或者是规则 的嘲格：也可以认为，路径是在规划区域中，出发点和目标点之间的点序列，这些点 及相邻两点之间的连线必须与障碍物保持一定的距离。 路径规划问题主要包括三个方丽的问题，规划的方法、环境的表达以及规划结果 的执行。规划的方法就是指如何根据已知的信息找到可供机器人利用的可通行的路 径。环境的表达主要是指怎样把现实世界的环境合理的表达为规划的方法所能利用的 环境信息，以产生最好的规划效果。不同的环境有不同的环境表达方式，同对不同的 2 南京理工大学硕士学位论文部分环境信息己知的智能机器人路径规划方法研究 环境表达方式对应不同的规划方法，反过来也可以根据不同的环境制定不同的规划方 法。规划结果的执行则侧重于控制机器人按照规划好的路径运动，它与底层的控制机 构相关联，根据各种不同的约束控制不同的机器人【曰。 先看规划的方法。一般情况下，现有的路径规划方法按照规划的层次分为三种类 型，全局规划、局部规划、全局局部相结合的规划【6 】。 全局规划f 7 】【8 】【9 】主要是指在规划环境和机器人模型已经充分了解的情况下依据 己获取的全局环境信息，给机器人规划出一条从起点至终点的运动路径。全局规划是 基于先验的环境信息的，其规划的精确度取决于获取环境信息的准确程度。其优点在 于在已知信息基础之上可以获得起点至终点的最优路径。并且，环境中的任意两点之 间如果存在路径的话都可以通过规划找到一条可通行路径。其缺点在于它依赖先验 的、精确的环境信息，而这一点往往是办不到的。而且一般来说全局规划的计算量比 较大，对于环境信息的改变反应较慢，实时性较差，不适合动态的不确定的环境。 局部规划【0 1 1 f 1 1 4 则主要依靠机器人对周围环境的感知来获得所需的环境信息， 比如依靠机器人的视觉系统，各种传感器等来获得信息。这是一种反射式的对环境的 适应过程。它的优点在于可以对环境的改变做出及时反应，对动态的环境有较强的适 应能力，在多变环境下能控制机器人做出避障动作。由于只对一定范围内的信息感知， 所以局部规划具有较强的实时性。但是正是由于信息的局部性，它不能保证路径的最 优性，同时会发生死锁现象，即不能保证机器人能够顺利的到达目标。 全局和局部相结合的规划方法 1 4 】这种方法提出的目的在于结合全局规划和局部 规划的优点，克服各自的不足。首先可以利用已有的环境信息进行全局的规划，把全 局规划的结果作为局部规划的子目标，在局部利用局部规划的方法感知周围的环境信 息进行避障。这种方法克服了全局规划不适应环境的改变，同时又避免，完全依赖局 部规划而造成的死锁。在机器人行进过程中根据局部的环境信息不断修正全局的路 径，弥补了全局规划中由环境信息的偏差而造成的路径的偏差。在大型的越野环境当 中尤其需要全局和局部相结合。 根据环境中障碍物的状态来分，规划的方法又可以分为静态规划和动态规划。静 态规划指障碍物在机器人运动过程当中是静止的。动态规划中障碍物的位置或者它的 一些性质在机器人的运动过程当中是变化的。而根据环境信息的已知程度又分为全部 环境信息已知，环境信息完全未知，和部分环境信息已知。 按照信息获取的方式分类的话，路径规划方法可分为基于模型的路径规划和基于 传感器的路径规划。基于模型的路径规划中，环境信息被预先存储下来，是一种离线 的规划方式；基于传感器的路径规划利用实时收到的传感器信息和指定的任务来进行 在线的路径规划。 3 1 绪论硕士论文 1 2 2 部分环境信息已知的路径规划 在实际的智能移动机器人规划系统当中，最常遇到的情况是环境信息部分己知。 首先，环境信息完全已知的情况是不太现实的。环境表达的偏差、障碍物状态的改变 等因素都会造成已知信息的不完整。其次，环境信息在规划之前完全未知的情况也是 比较少的，大多数系统都有基于全局的环境地图。可见动态的、环境信息部分己知的 规划是需要主要考虑的，这也就要求了全局规划和局部规划的结合。 由上述内容可以知道。一般情况下，路径规划可以按照下面的层次结构来进行： 子目 运动 目标驱动的全局规划 际点等信息 局部规划( 避障) ? 向等信息i 路径执行控制机构 图1 2 1 一般情况下的规划结构 图1 2 1 中全局规划部分首先根据已有信息规划出全局路径，然后将结果交给局部 规划部分，局部规划部分不断探测环境得到局部环境信息，结合全局规划结果和避障 要求给出机器人的运动方向等信息。这种结构在得到局部信息之后只做出避障反应， 而没有反应到全局的路径，往往造成机器人局部的死锁等现象。于是针对部分环境信 息已知的情况，可以考虑下面这种规划的结构。 全局规划部分 ( 寻找金局路径) 目标驱动的1 运动方向信息 子目标点等信息 局部规划部分 ( 避障) 二震薹境乏, i 刭蕊j t j 信息的差异避惮明 同1 i 思 运动方向决燕 匮 上运动方向信息 4 南京理工大学硕士学位论文部分环境信息已知的智能机器人路径规划方法研究 路径无法通过而必须重新进行的规划。按照重规划与原规划的起点相同与否可以划分 为完全重规划与不完全重规划。所谓完全重规划，是指重规划路径的起点与原规划的 起点相同，而不完全重规划或部分重规划则是指重规划路径的起点与原规划的起点不 同。本文所讨论的方法虽然是不完全的重规划，但是利用了原有的规划信息，在一定 程度上实现了最优性和实时性的结合。 针对这种部分信息已知的、全局和局部相结合的、需要重规划过程的情况，前人 提出了很多方法。s t e n t z 【l 纠利用已知的环境信息构建一条“全局”的路径，然后避过 传感器探测到的障碍物，如果事先规划的路径被完全阻塞，那么再重新全局规划。 l u m e i s k y j f n s t e p a n o v u 4 l 先假设环境中全无障碍，让机器人直接向目标方向移动。如果 一个障碍物阻塞了路径，那么机器人沿着障碍物的周长搜索，直到在障碍物周长上找 到最靠近目标的一点。然后机器人沿着这点继续直接向目标方向行进，过程中让机器 人记住环境中某些特殊点，用一个全局收敛准则来保证收敛性。p i r z a d e h i ”】采用了一 种策略使机器人在环境中漫游，直到找到目标为止。机器人不断的移动到具有最小路 径花费位置的邻近位置，并且机器人每访问一个位置就增加一个位置的路径花费值， 使得下次再次到达同一位置的可能性降低。k o i o - 利用一幅初始地图来估计每个状态 到目标的路径花赞并且当机器人在环境中行进的时候有效的更新回退的花费。 但是可以看到这些方法都没有充分的利用到机器人已有的两点信息，全局的环境 信息和探测器所能感知到的信息。动态的a + ( d 4 ) 算法【4 q 充分的利用了这两点，做 到全局规划和局部信息相结合、离线的规划和在线的规划相结合，正是本文研究的重 点。 1 3 本文的组织结构 本文针对部分环境信息已知这种规划情况，研究了相应的规划方法和环境的表达 方式，结构安排如下： 第一章绪论 本章主要介绍了移动机器人及其路径规划系统的研究现状和研究意义，其分类和 组织结构，简述了本文所研究的问题在整体系统中的位置和作用。 第二章移动机器人规划方法和相应的环境表达方式 本章基于绪论的分类方法和组织结构，重点讨论了移动机器人路径规划系统中已 知的一些规划方法及其相应的环境表达方法。为后两誊打下基础。 第三章部分环境信息己知情况下的路径规划方法 这一章针对部分环境信息已知的情况，详细讨论了适合于这种情况的路径规划力 法。重点研究t d + 算法的原理和实现，并和普通的基于a + 算法的规划方法进行比较。 是全文的重要部分。 1 绪论 硕士论文 第四章相应的环境表达方式 针对第三章的规划方法有相应合适的环境表达方式，这一章就详细讨论了适合于 此种规划情况的环境表达方式。从规则的栅格表示，到四叉树的表示，最后是一种带 边框的四叉树的表达方式和它们相应的实现方法。此章也是全文重点。 第五章仿真实验及结果分析 对第三章和第四章所讨论的方法进行仿真实验，并分析其结果，最终证明所用方 法的正确性和有效性。并且在实际的结构化地形图和越野地形图中进行了实验，进一 步验证了所讨论规划算法的实用性。 南京理工大学硕士学位论文 部分环境信息已知的智能机器人路径规划方法研究 2 智能机器人规划方法和相应的环境表达 2 1 引言 正如绪论中所述，规划问题是智能机器人领域的关键问题。其中1 9 7 8 年 l o z a n o p e f e z 和w e s l e y 【1 7 提出的位姿空间( c o n f i g u r a t i o ns p a c e ，简称c 一空间) 的概念对于路径规划而言具有里程碑式的意义。其实质是根据运动物体( 机器人) 的大 小和姿态，把周围的障碍物向外扩展一定的距离，即相应的“膨胀”，变成扩展障碍。 与此同时，运动物体缩为个点( 运动物体位姿的描述简化为位姿空间中的一个点) ， 于是得到一个新的空闻，称为位姿空间。化为位姿空间的主要目的有三个，l ，将机 器人表达为此空间中的一个点。2 ，空间中主要信息是障碍物。3 ，将物体的规划问题 转变为点的规划问题。这实际上构造了一个虚拟的空间，把运动物体、障碍物及其几 何约束关系做了等效变换。由于将许多规划情况变为点的规划问题，因此得到了广泛 的运用。本章所要介绍的一些环境的表达方式都可以建立在位姿空间中的自由空间 ( c 。) 的基础之上，一些规划方法也可以在此空间中描述，可见其重要性。 本章在绪论的基础上详细介绍了一些规划方法和环境的表达方式。 2 2 规划方法 2 2 1 圈搜索 一种最常见的路径规划方法，这种方法建立在自由空间( c 。) 的基础上，将环 境变为一幅连通的代价图，然后利用人工智能中的搜索策略来找到最终的路径。这里 对经典的最短路径搜索策略在栅格表示的基础上进行介绍。 d i j k s i r a 算法”8 1 ，可以说是最经典、应用最广泛的最短路径搜索方法，1 9 5 9 年最 早提出。该算法可以找到图g 中从初始结点到图中任意结点的最短路径，或者从目标 结点到图中任意结点的最短路径。如果该算法在到达目标结点时结束，那么定可以 找一条从初始结点到目标结点的最短路径。它的主要特点是以初始结点为中一巴、向外层 层扩展，直到扩展到目标结点为止。d i j k s t r a 算法能得出最短路径的最优解，但由于 它遍历计算的结点很多，所以效率低。其算法的时间复杂度是o ( 费) 。图2 2 ，l ( a ) 是 一幅在栅格表示下利用该方法规划的结果图，其中深色的结点是搜索扩展到的结点。 r 算法哗1 ，由n j n i l s s o n1 9 8 0 年提出，是一种应用极为广泛的启发式搜索 算法( h e u r i s t i cs e a r c ha l g o r i t h m ) ，许多研究者对使用a 算法进行路径规划作r 深入的研究。a 算法采用一个评价函数，( n ) ( e v a l u a t i o nf u n c t i o n ) 来指导o p e n 表中扩展结点的选择。 ( 2 2 1 ) 2 智能机器人规划方法和相应的环境表达硕士论文 式中g ( n ) 为从出发点j 到结点n 已发现最优路径的代价， ( n ) 是依赖于问题的启 发信息，反映从”到目标点之间路径代价的估计，在栅格表示中可以为当前点到目标 点的直线几何距离。令h + ( n ) 为从n 到目标点之间的实际最优路径的代价值，a + 算法 要求 ( n ) h + ( n ) 。只要路径存在，a 4 算法可以保证找到一条最优路径( 在给定的代 价函数和环境表示下) 。 由于a 算法加入了启发信息，因此起点终点相同情况下搜索扩展的结点比 d i j k s t r a 算法要少。图2 2 1 ( b ) 是一幅在栅格表示下利用该方法规划的结果图。 a + 算法的实现虽然简单直观，但当环境复杂、规模较大时，它也是低效率的，经常几 乎要扩展整个规划空间才能找到目标。针对这缺陷人们提出了很多改进的机制。 图2 2 1 图搜索 上述两个经典的搜索算法可以在信息完全已知的环境下运用到全局规划当中，而 对绪论中所述的部分环境信息已知的情况则不适合。本文所讨论的规划方法从原理上 说也可以说是图搜索方法，但是适合于部分信息已知的情况。 2 2 2 势垢法 最初由k h a t i b i l 9 1 最早提出，是路径规划的重要方法。这种方法将物理学中场的概 念引入到规划环境的表达当中，其基本思想是引入一个称作人工势场的数值函数来描 述空间结构，通过势场中的力来引导机器人到达目标。势场分为两个部分，即目标位 姿产生的吸引势( a t t r a c t i v ep o t e n t i a l ) 和障碍物产生的排斥势( r e p u l s e p o t e n t i a l ) 。吸引势使机器人向目标位姿靠近，排斥势使机器人绕开障碍物，二者的 叠加构成机器人运动的虚拟势场，势场的负梯度作为作用在机器人上的虚拟力，该力 “推动”机器人向着目标作无碰运动。 例如，在位姿空间当中，势场可以用u ( ) 表示，空间中的一个位姿可以用q 表示， 童塞里三查兰堕圭兰焦堕苎 塑坌墅壁篁垦曼垫竺望墼塑璺查塑丝塑型互鲨竺垄一 目标状态位姿可用以来表示。并定义和目标位姿吼相关联的吸引势u 。一( q ) 以及和障 碍物c 。楣关联的排斥势u 。( 譬) 。那么位姿空间中某一位姿的场可以表示为下式： u ( 口) = u 。( q ) + u 。( g ) ( 2 2 2 ) 又规定对于c 。中的每一个位姿u ( g ) 都必须是可微分的。那么机器人( 这是已是 位姿空间中的点) 所受到的虚拟力为目标位姿的吸引力和障碍物的斥力的合力，如下 式所示： f ( q ) = 一v u ( q ) = 一v u 。( q ) 一v u 。( q ) ( 2 2 。3 ) 其中v u ( q ) 表示u 在q 处的梯度，它是一个向量，其方向是位姿q 处场变化率最大的方 向。那么对于二维空间中的位姿q = ( 五y ) 来说，有： r a u l i v u ( 口) = 1 3 u la ) ，j 对于场u 0 的定义方式可以有很多中，例如对于吸引势u 。( g ) ， 以为： u 。( 口) = 晏勃；( q ) 其中以( g ) = 怕一1 l 是从心到q 的欧氏距离， 最终的吸引力为： 声删。( q ) = j 可u 硝( q ) = 一善( 鼋一q 。) 同样的道理可以定义排斥势为： f ( 2 2 4 ) 最常用的定义可 ( 2 2 5 ) 亭是正的比例系数。那么由“式2 2 3 ” ( 2 2 6 ) 矸( 南一舳) 铂 0 p ( q ) p 。 由“式2 2 2 ”可知最终的排斥力为 ( 2 2 7 ) 扎= 野( 斋一爿( 南 v 眦， ( 2 2 8 ) 最后可以计算出合力来引导机器人向目标行进达到避免碰撞的效果。 常用的有以下几种势场：虚g a j 3 $ b ( v i r t u a lf o r c ef i e l d ) 、牛顿型势场、圆形 对称势场、超四次方势场( s u p e rq u a d r i c ) 以及调和场( h 珊o n i c p o t e n t i a l ) 。势场 法实际上是试图使障碍物的分布情况及其形状等信息反映在环境每一点的势场值当 9 2 智能机器人规划方法和相应的环境衰达 硕士论文 中，机器人依次决定行进方向。它的优点在于计算量较小，适合于实时的在线局部避 障控制。其最大问题在于会在搜索时发生“局部最小”的情况，就是说机器人在某一 处所受力为零，因此会停止不动。许多学者针对这一问题进行了研究1 2 u ，文献悼现 通过引入统一的势能函数来解决这一问题；随机势场法2 卸采用随机运动逃脱局部最小 点。总体来说，势场法是建立在场概念表达环境的基础之上的，适合予局部规划问题。 对规划问题的研究可以说是人工智能与算法理论的结合，因此许多人工智能中的 优化、推理技术也被运用到移动机器人的规划问题当中，如遗传算法、神经网络以及 模糊推理等。这些方法在移动机器入规划问题中起到很大的作用，这里作简要介绍。 遗传算法，是由j o h ni l o l a n d 在7 0 年代早期发展起来的一种基于自然选择和群 体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖，交配和突 变现象。它将每个可能的解看作是群体( 所有可能解) 中的一个个体，并将每个个体编 码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适合值。开 始时总是随机地产生些个体( 即候选解) ，根据这些个体的符合度利用遗传算予( 选 择、交叉、变异) 对这些个体进行交叉组合，得到一个新的个体。这一群新的个体由 于继承了上一代的一些优良性状，因而明显优于上一代，这样逐步朝着更优解的方向 进化r 6 1 。作为一类重要的进化算法在移动机器人运动规划方压的应用获得了大量的成 果【2 4 j - 1 2 7 1 。遗传算法求解路径规划问题的基本思想是：将路径个体表达为路径中的一 系列中途点，并转换为二进制串。首先初始化路径群体，然后进行遗传操作，如选 择、交叉、复制、变异。经过若干代的进化以后，停止进化，输出当前最优个体作为 路径下一个结点。该算法的优点是，路径可以收敛到全局最优或者近似最优；缺点是 进化速度难以控制，难以满足实时需要，需要的经验参数太多，不利于自动处理。 基于神经网络的方法。许多学者致力于将机器学习的技术运用到机器人研究当 中，基于神经网络的方法在规划阉题中也有大量的研究成果f 2 8 】f 2 9 j f3 。1 。其基本原理是 将环境障碍等作为神经网络的输入层信息，经由神经网络并行处理，神经网络输出层 输出期望的转向角和速度等，引导机器人避障行驶，直至到达目的地。其优点是并行 处理效率高，具有学习功能，能收敛到最优路径。 基于模糊逻辑 3 1 j 的方法。由于模糊逻辑运用近似自然语言方式，可以很好的处理 数据的不确定性和非精确性，克服噪声和误差实现输入输出之间的映射关系，因此可 以运用到规划问题当中。这种规划方法将当前环境障碍信息作为模糊推理机的输入， 推理机输出机器人期望转向角和速度等 3 2 3 3 1 。该方法在环境未知或发生变化的情况 下，能够快速而准确地规划机器人局部路径，对于要求有较少路径规划时间的机器人 是一种很好的导航方法。但是，其缺点是当障碍物数目增加对，该方法的计算量较大， 1 0 南京理工大学硕士学位论文部分环境信息已知的智能机器人路径规划方法研究 影响规划结果，而且该规划方法只利用局部信息做出快速反应，容易造成局部的死锁。 2 2 4 其他方法 1 9 8 8 年j f c a n n y 就已证明，一个点机器人在三维多边形障碍环境中运动， 其规划复杂度是n p 复杂度3 4 。规划问题随着机器人自由度增多会出现“维数灾难 ( d i m e n s i o nc u r s e ) ”问题，因此国外学者提出了在规划空间中随机采样的方法，以 损失完备性为代价提高算法的执行效率。这类基于随机采样的方法有很多，典型的有 随机路径规划器( r a n d o m i z e dp a t hp l a n n e r ，简称r p p ) 【”l 、概率路标算法 ( p r o b a b i l i s t i cr o a dm a p ，简称p r m ) 3 6 1 、a r i a d n e 线索法( a r i a d n e sc l e w a l g o r i t h m ) 、膨胀空间法( e x p a n s i v es p a c e s ，简称f _ s t ) 1 3 8 以及快速随机搜索树算法 ( r a p i d l y - e x p l o r i n gr a n d o mt r e e ，简称r r t ) p 螂等，这些方法掀起了一股新的对 机器人运动规划研究的热潮。 当然不同的需求有不同的方法，还有许多规划方法在这里就不做介绍了。 2 3 环境的表选 不同的规划方法对其规划环境都有不同的要求。比如，势场法是基于场的环境表 达，而那些智能规划方法则需要其相应的表达。在这里本文主要介绍在前文所述自由 空间( c 。) 下利用不同的几何方法来构造的不同规划环境。 2 3 1 橱格分解法 可以说栅格表示法是研究最广泛的环境表示方法之。该方法将机器人的工作宅 间分解为多个简单的区域，一般称为栅格( c e l l ) ，然后构造成一个无方向的图，这个 图代表了栅格相邻( 如果在两个栅格之间可以直接移动，则称为相邻) 的关系称为连 通图( c o n n e c t i v i t yg r a p h ) 。在此图上，再利用搜索算法求得一条由连通图中的结点 组成“通道”( c h a n n e ) ，最后基于这个“通道”得到最后得路径【d 。栅格分解法又 分为精确的栅格分解法( e x a c tc e l ld e c o m p o s i t i o n ) 和近似的栅格分解法 ( a p p r o x i m a t ec e l ld e c o m p o s i t i o n ) 。下面分别进行介绍。 精确的栅格分解法。这种方法利用不规则形状的栅格将位姿空间精确的分为障碍 物和自由空问( c 。) ，也就是说按照此法划分完毕之后，栅格所包含的区域就是自 由空间。这种方法划分的栅格有不规则的边界，比较复杂。例如图2 3 1 ( b ) 就是对 图2 3 1 ( a ) 的精确栅格分解图。 2 智能机器人规划方法和相应的环境表达硕士论文 ( a ) 1 0 ( b ) 图2 3 1 精确栅格分解 图2 3 1 ( b ) 中的序号代表栅格在连通图中的结点序号。这种分解的方法分解过 程比较复杂，需要考虑到障碍物的形状。同时连通图中每个栅格结点的大小边界都不 规则，因此计算路径还是比较复杂的。 近似的栅格分解法。这种方法当中利用形状相对固定的栅格来近似的覆盖自由空 间，也就是说划分之后每个栅格都有规则的边界。由于栅格的形状很简单，因此分解 的过程很简单。图2 3 2 就是一个典型的近似栅格分解： 图2 3 2 近似的栅格分解法 这种方法的优点就在于分解栅格过程很简单，分解的栅格很规则，很容易实现。 著且可以根据不同的要求来改变最小的分辨率，从而有很强的适应性。其缺点在于当 1 2 南京理工大学硕士学位论文部分环境信息己知的智能机器人路径规划方法研究 环境很大，精确度要求很高时那么这个方法所需的存储空间比较大。当然具体的分解 方法有很多种，例如本文第四章中的表达方式都是基于此种方法的。 2 3 2 可视图 这是一种在1 9 8 7 年就被提出，且被广泛应用的环境表达i 4 “。它的基本思想是在位 姿空间中，以多边形障碍物模型为基础，任意形状障碍物用近似多边形代替，而后用 直线将机器人运动的起始点q ；。和所有空间中的障碍物的顶点以及目标点q 删连接， 并保证这些直线段不和c 一空间障碍物相交，就形成了一张图，称之为可视图 ( v i s i b i l i t yg r a p h ) ( 如图2 3 3 所示) 。然后采用搜索算法寻找从起始点到目标点 的最优路径，这时寻找路径的问题就转化为寻找从起始点到目标点，经过这些可视直 线的最短距离问题。可视图构造的时间复杂度是o ( n 2 l o g n ) 或者是o ( n 2 ) 。其优点是 概念直观，实现简单。但是这种表示方法缺乏灵活性，即一旦机器人的起始点和目标 点发生改变，就要重新构造可视图，因此算法的复杂性和障碍物的数量成正比，且不 是任何时候都可以获得最优路径。 图2 3 3 可视图 2 3 3v o r o n o i 图 环境表示中运用到了许多计算几何中的技术，v o r o n o i 图表示就是一个典型的例 子2 4 2 ；。其实质是在位姿空间中，根据己知的障碍分布情况，取障碍物的顶点、边界构 造出c 空间中障碍分布的v o r o n o i 图。连接机器人运动的起始点q 。以及目标点q 。 到已经构造好的v o r o n o i 图上，构成如图2 ，3 4 所示的表达环境中自由空间“骨架” 的图。v o r o n o i 图构造的时间复杂度是o ( n l o g h ) ，实时性较好，生成的路径相对比 较安全，远离障碍，并且路径比较平滑，合理性也较好，但是不能保证路径最优。 2 智能机器人规划方法和相应的环境表达硕士论文 图2 3 4v o r o n o i 图 2 3 4 切线圈 这种方法以多边形障碍物模型为基础，任意形状障碍物用近似多边形替代，在自 由空间中进行构造。例如可以用移动线和扫描线相结合的方法构造切线图 4 3 】。首先， 采用“移动线算法”检测障碍物顶点之间的所有公切线，然后利用一种“扫描线算法” 测试已知公切线与障碍物之间是否存在交叉点，如存在，滤除这些公切线，剩下的公 切线构成的图被称为切线图( t a n g e n tg r a p h ) 。构造切线图在最坏情况下的时间复杂 度为0 ( 【m + r n + m2 l o g m ) ，其中n 表示障碍物顶点数，m 表示n 个点构成的凸曲 线的条数，r 表示开凸曲线的滚动数( r o l l i n gn u m b e r ) 。 2 4 本章小结 本章在绪论的基础上详细讨论了图搜索、势场法和智能规划方法等应用广泛的规 划方法。并且以位姿空间为基础详细讨论了栅格分解、可视图、v o r o n o i 图和切线图 等环境表达的方式，为后面两章的内容做了铺垫，是后文的基础。 1 4 南京理工大学硕士学位论文部分环境信息己知的智能机器人路径规划方法研究 3 部分环境信息已知情况下的路径规划方法 3 1 引育 前文对移动机器人的规划方法进行了分类介绍和讨论，本章主要讨论在部分信息 已知的环境中，实现移动机器人全局路径规划的一些方法。从第二章所描述的规划分 类来看，这一章所讨论的算法是可以用在图1 2 2 所示的规划系统的结构当中的，并 且这里所讨论的算法没有考虑机器人的大小、形状以及行驶约束等非完整约束机制， 所以这里的算法是全局意义上的规划，但是利用了局部的信息，是针对部分环境信息 已知的规划情况的。对于相应的局部的规划方法在这种情况下有很多选择，例如可以 利用势场法。需要注意的是局部规划器此时需要返回给全局规划一些信息，包括全局 地图相应状态的可通行率的改变，障碍物的位置移动或者消失等。 3 2 基于a + 搜索算法的规划方法 由第二章的叙述可以知道，经典的a ( a s t a r ) 算法是一种静态环境中求解最短路 径的一种最有效的方法。这里也可以利用这个已有的图搜索算法来实现部分环境信息 己知情况下的路径规划。其基本思想是用已有的环境信息构建一条全局的路径，然后 在局部避过传感器探测到的障碍物，如果规划的路径被完全阻塞，那么再重新进行金 局上的规划。 在规则栅格表示的环境当中进行这种规划，a 的估价函数是很好确定的。“n ) 是 结点n 从初始点到目标点的估价函数，g ( n ) 是在状态空间中从初始结点到n 结点的 实际代价，h 4 ( n ) 是从n 到目标结点最佳路径的代价，而h ( n ) 是从n 到目标结点最佳路 径的估计代价，则f ( n ) = g ( n ) + h ( n ) 。在实际规划当中，h ( ) - - d o c x 删) 2 + ( 匕1 0 ) 2 、 g ( n ) 也为实际环境中结点n 到初始结点的几何距离。显然，h ( n ) 是h 。( n ) 的下界，所以 由 4 4 】的叙述可以知道，这是满足a + 算法的定义的。 在动态的环境当中，首先根据己知的环境信g n 用。算法来规划一条从起始点 到目标点的路径，然后机器人沿着这条路径行进，当装备在机器人上的探测器检测到 实际的环境和己知的环境信息存在差异时，则更新原有的环境地图信息。此时，可以 采取的策略有两个，第一，采用局部的避障方法绕过所检测到的障碍( 此时探测器还 在不断探测周围环境) ：第二，根据更新的环境信息重新规划一条从机器入当前所在 位置到目标点的新的路径。如果采用第一种方法机器人的行进路线完全被障碍物所阻 挡的时候，再重新规划全局的路径。在不同的环境当中两种策略各有好处，如果在障 碍物稀