（机械电子工程专业论文）复杂动态环境下移动机器人的全局路径规划算法研究.pdf

北京邮电大学硕士学位论文 复杂动态环境下移动机器人的全局路径规划 算法研究 摘要 路径规划是月面巡视探测器行进过程中运动控制的依据，是巡视 器研究与开发的核心内容之一。月面巡视探测器是一种工作在月面复 杂动态环境下的特殊移动机器人，因此，研究复杂动态环境下移动机 器人的路径规划对于巡视器的路径规划研究具有重要的意义。本文以 国防科工委正在开展的月球探测二、三期工程论证工作为背景，对移 动机器人的传统全局路径规划算法、复杂动态环境下的全局路径规划 算法、模拟月面巡视探测器的路径规划过程、路径成本评估等开展了 研究，论文的主要内容包括： 首先，分析实现了移动机器人的两种传统全局路径规划算法a 与d l i t e 。针对工程约束，将转向角度和转折次数引入算法的评估函 数，提出一种基于a 算法的全局路径规划算法a 觚g l e ，使得规划出 的路径更平滑，更节省能量，在搭建的m a t l a b 仿真平台上对算法进 行了仿真验证。 其次，针对传统算法应用于三维复杂动态环境下时带来的一些问 题，提出了一种新的三维建模的方法，提出了一种新的基于方向的三 维通行性判断方法，并学习工业预测原理和滚动原理，对传统全局路 径规划算法d t i t e 进行了修改，使之可以用于三维复杂未知动态环境， 最后对算法进行了仿真验证。 再次，针对我国月面巡视探测器“遥操作+ 半自主 的工作模式， 分析实现了行星巡视探测器典型局部避障算法m o r p h i n ，并和全局路 径规划算法d 。l i t e 结合起来，在m a t l a b 仿真平台上模拟了月面巡视 探测器的路径规划过程。 最后，在对上述评估函数修改的基础上，针对目前的全局路径规 划算法基本上是以路径最短作为路径最优的标准，提出一种对路径进 行综合评价的方法，综合考虑了移动机器人直线行走代价、转向代价 和机构调整代价。将这些代价综合为功耗和时耗，从而为整体评价路 径的性能提供了一种参考标准。 关键宇：全局路径规划算法； 算法；月面巡视探测器路径规划； 评估函数；三维通行性；局部避障 路径评估 摘要 r e s e a r c ho ng l o b a ll ，a t hp l a n n i n g a l g o i u t h mo fm o b i l er o b o t i nco m p l e xa n dd y n a m i ce n r o n m e n t a b s t r a c t p a t hp l a n n i n gp r o v i d e st h ei n f o r m a t i o no ft h el u n a rr o v e rt ot h e m o t i o nc o n t r o ld u r i n gm o v i n g ，w h i c hi so n eo ft h ek e ye l e m e n t so f s t u d y i n ga n dd e v e l o p i n go ft h ew h o l el u n a rr o v e rs y s t e m l u n a rr o v e r i sa l s oas p e c i a lm o b i l er o b o tw o r k i n gi nt h ec o m p l e xl u n a re n v i r o n m e n t t h e r e f o r e , r e s e a r c h e so nt h ep a t hp l a n n i n go fm o b i l er o b o ti nc o m p l e x a n dd y n a m i ce n v i r o n m e n ta r ev e r yi m p o r t a n tt ot h es t u d yo ft h ep a t h p l a n n i n go fl u n a rr o v e r w i t ht h eb a c k g r o u n dt h a tp r o j e c tp h a s ei ia n d p h a s e o fl u n a re x p l o r a t i o n sd e m o n s t r a t i o nd e v e l o p e db yc o m m i s s i o n o fs c i e n c et e c h n o l o g ya n di n d u s t r yf o rn a t i o n a ld e f e n s e ，t h i sp a p e r r e s e a r c h e st h em o b i l er o b o t st r a d i t i o n a lg l o b a lp a t hp l a n n i n ga l g o r i t h m s ， g l o b a lp a t h p l a n n i n ga l g o r i t h m si nt h ec o m p l e xa n dd y n a m i ce n v i r o n m e n t , s i m u l a t e sl u n a rr o v e r sp a t hp l a n n i n gp r o c e s s i n g ，a n dt h ec o s te v a l u a t i o n o fp a t hp l a n n i n g t h em a i nc o n t e n to ft h i s p a p e ri s l i s t e da st h e f o l l o w i n g s ： a tf i r s t , t h et w ot r a d i t i o n a lm o b i l er o b o t sg l o b a lp a t h p l a n n i n g a l g o r i t h ma a n dd l i t ew e r ec a r r i e do u t a i m e da te n g i n e e r i n g c o n s t r a i n t s ，t h i sp a p e ri n t r o d u c e dt h es t e e r i n ga n g l ea n dt u r n i n gf r e q u e n c y i n t ot h ee v a l u a t i o nf u n c t i o na n d b r o u g h tu paa 。a l g o r i t h m - b a s e dg l o b a l p a t hp l a n n i n ga l g o r i t h ma a n g l ew h i c hm a d et h ep l a n n i n gp a t hs m o o t h e r , m o r ee f f e c t i v e a t1 a s t ，t h en e wa l g o r i t h mw a ss i m u l a t e do nt h e m a t l a bs i m u l a t i o np l a t f o r m s e c o n d l y , a i m e da ts o m ep r o b l e m sc a u s e db yt h et r a d i t i o n a l a l g o r i t h m sw h e nt h e yw e r eu s e di nt h et h r e e d i m e n s i o n a lc o m p l e xa n d d y n a m i ce n v i r o n m e n t ，t h i sp 印e rp r o p o s e dan e wm e t h o do f t h r e e - d i m e n s i o n a lm o d e l i n ga n dd i r e c t i o n a lt h r e e d i m e n s i o n a lt e r r a i n j u d g i n gm e t h o d s ，s t u d i e dt h ei n d u s t r i a lp r i n c i p l e sa n dp r e d i c t i o nr o l l i n g i i 北京邮电大学硕士学位论文 p r i n c i p l ea n da m e n d e dt h et r a d i t i o n a lg l o b a lp a t hp l a n n i n ga l g o r i t h md l i t e s ot h a ti tc o u l db eu s e di nt h et h r e e - d i m e n s i o n a lc o m p l e xa n d d y n a m i ce n v i r o n m e n t t h i r d l y ，a i m e da tt h e “s e m i - a u t o n o m o u sa n dt e l e o p e r a t i o n w o r k i n g m o d eo fo u rc o u n t r y sl u n a rr o v e r , t h i sp a p e rc a r d e do u tt h et y p i c a l l o c a lo b s t a c l ea v o i d a n c ea l g o r i t h mm o r p h i na n dc o m b i n e d 、析m9 1 0 b a l p a t hp l a n n i n ga l g o r i t h md l i t et os i m u l a t el u n a rr o v e r sp a t hp l a n n i n g p r o c e s s i n go nt h em 已订l a bs i m u l a t i o np l a t f o r m l a s t l y , b a s e do nt h em o d i f i c a t i o no ft h ee v a l u a t i o nf u n c t i o n ，t h i s p a p e rp r e s e n t e dac o m p r e h e n s i v ee v a l u a t i o nm e t h o do ft h ep a t h si n s t e a d o ft h et r a d i t i o n a lc r i t e r i o nw h i c ho n l yt o o kt h ep a t hl e n g t hi n t oa c c o u n t t h i sn e wc r i t e r i o nc o n s i d e r e dt h ec o s to fm o b i l er o b o tt ow a l k s t r a i g h t , t h ec o s to ft u m i n ga n d a d j u s t m e n t t h e s ec o s t sw i l lb ei n t e g r a t e df o r p o w e rc o n s u m p t i o na n dt i m e - c o n s u m i n ga n dp r o v i d e da s t a n d a r df o rt h e p e r f o r m a n c eo ft h ep a t h s 一k e yw o r d s ：g l o b a lp a t hp l a n n i n ga l g o r i t h m ；e v a l u a t i o nf u n c t i o n ； t h r e e - d i m e n s i o n a lt r a v c r s a b i l i t y ；l o c a lo b s t a c l ea v o i d a n c ea l g o r i t h m ； l u n a rr o v e r sp a t hp l a n n i n g ；p a t he v a l u a t i o n i i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：! 叁堡! 兰日期：婴：墨：! 曼 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 夺倍他 日期： 日期： 加7 、夏f 弓 互学- 4 _ 一 北京邮电大学硕士学位论文 1 1 课题来源 第一章绪论 本课题来源于国防科工委正在开展的月球探测二、三期工程论证工作，其中 月面巡视探测器方案论证课题目前正在开展原理样机研制。路径规划是月面巡视 探测器导航与控制系统的重要工作内容，是月面巡视探测器的关键技术之一。月 面巡视探测器既是一种特殊航天器，也是一种工作在月面未知环境下的特殊移动 机器人，因此本课题移动机器人在复杂动态环境下的全局路径规划是解决月面巡 视探测器路径问题的基础和前提，该问题的解决对月面巡视探测器的方案确定具 有重要的意义。 1 2 研究背景及意义 机器人作为人类2 0 世纪最伟大的发明之一，发展机器人技术己成为高技术 领域中具有代表性的战略目标之一。随着计算机技术、信息技术、通讯技术、微 电子技术等技术的发展，正如人类活动范围和探索的空间是人类进步的标志一样， 机器人的智能同样体现在运动空间的大小上。为了获得更大的独立性，人们也对 机器人的灵活性及智能提出更高的要求，要求机器人能够在一定范围内安全运动， 完成特定的任务，增强机器人对环境的适应能力。因此，近年来，移动机器人成为机 器人研究领域的中心之一。 移动机器人是一种在复杂环境下工作的具有自规划、自组织、自适应能力的 智能机器人。在移动机器人相关技术的研究中，导航技术是其核心，而路径规划 是导航研究的一个重要环节和课题。例如，在执行装配、焊接及抢险救灾等任务 时，采用良好的机器人路径规划技术可以节省大量机器人作业时间、减少机器人 磨损，同时也可以节约人力资源，减小资金投入，为机器人在多种行业中的应用奠 定良好的基础。因此移动机器人路径规划作为机器人应用中的一项重要技术，具 有深远的研究意义。 目前，对于移动机器人路径规划技术的研究已经取得了大量的成果，许多路径 规划方法在完全已知环境中能得到令人满意的结果，但在未知环境特别是存在各 种未知或动态障碍的三维复杂环境中，却很可能失去效用。移动机器人在复杂环 第一章绪论 境下行走的路径规划问题一直是一个没能妥善解决的难题。如何快速有效地完成 移动机器人在复杂环境中的路径规划问题仍将是今后研究的重点之一。 尤其在今天，人类开始进行外太空深度探测，月球由于其独特的空间位置和 潜在资源，成为人类开展深空探测的首选目标，也是人类向外层空间发展的理想 基地和前哨战。国外从2 0 世纪6 0 年代开始研制月球探测车，其中美国和前苏联 在月球及行星探测器的研究方面处于世界领先地位。登月计划和深空探测计划促 进了美国、前苏联航天技术的发展，对国家经济产生了重大的影响。我国月球探 测的近期目标( 2 0 0 0 年 - 2 0 0 7 年) 为发射月球探测卫星，中长期( 2 0 0 5 年 - - 2 0 2 0 年或稍后) 目标为2 0 1 2 年左右实施月球软着陆和自动巡视勘察探测( 简称月球探 测二期工程) ，2 0 1 7 年前后实施月球样品自动采样返回( 简称月球探测三期工 程) 。目前，月球探测一期工程已进入工程研制阶段，二期工程开始进行预先研 究和关键技术攻关【1 1 。在月球探测二期工程中，将由月面巡视探测器实施月面巡 视勘查。在着陆器着陆月面之前，月面巡视探测器是着陆器的有效载荷；在着陆 器着陆月面之后，月面巡视探测器即与着陆器分离，成为相对独立、完整、可在 月面移动的载体，具体完成以下任务：承载科学仪器，并为科学仪器提供正常工 作环境；接收指令，在月面自主行走并进行科学勘测；将科学探测数据传输回地 面接收站。 月面巡视探测器既是一种特殊航天器，也是一种工作在月面未知环境下的特 殊移动机器人，因此，借由研究复杂未知月球环境下的移动机器人路径规划，来 探索月面巡视探测器的路径规划和运动控制问题，可以对我国探月工程二期月面 巡视探测器的工程实施提供实现技术参考，为开发具有我国自主知识产权的月面 巡视探测器自主智能控制系统奠定重要的理论和实践基础。 1 3 移动机器人路径规划研究现状 移动机器人路径规划是指在有障碍物的工作环境中，按照某一性能指标( 如 距离、时间、能量等) 搜索一条从起始状态到目标状态的最优或次优路径使机器 人在运动过程中能安全、无碰地绕过所有障碍物【2 】。路径规划主要涉及的问题包 括： ( 1 ) 利用获得的移动机器人环境信息建立较为合理的模型，再用某种算法寻 找一条从起始状态到目标状态的最优或近似最优的无碰撞路径。 ( 2 ) 能够处理环境模型中的不确定因素和路径跟踪中出现的误差，使外界物 体对机器人的影响降到最小。 ( 3 ) 如何利用已知的所有信息来引导机器人的动作，从而得到相对更优的行 2 北京邮电大学硕士学位论文 为决策。 围绕着月球、火星探测任务，国外在移动机器人的路径规划方面开展大量的 研究工作，包括环境建模、路径的评估函数、路径搜索、典型行星巡视探测器路 径规划算法等。 1 3 1 环境建模 机器人所在的环境是实际的物理环境，而进行路径规划需要将物理环境抽象 成为能被计算机理解和表达的环境模型，即需要环境建模。所谓环境建模，就是 指根据已知的环境信息，通过提取和分析相关特征，将其转换成机器入可以理解 的特征空间。对于路径规划问题来说，环境建模就是要建立一张可供搜索的连通 图，即地图创建( m a p - b u i l d i n g ) 。 目前各国研究者已经提出了多种表示方法，如可视图法- - g r a p h ) 、切线图 法和v o r o n o i 图法、自由空间法( f r e es p a c ea p p r o a c h ) 、拓扑法和栅格法( o d d s ) 。 可视图法【3 】视移动机器人为一点，将机器人、目标点和多边形障碍物的各顶 点进行组合连接，并保证这些直线均不与障碍物相交，这就形成了一张图，称为 可视图。由于任意两直线的顶点都是可见的，从起点沿着这些直线到达目标点的 所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标 点经过这些可视直线的最短距离问题。运用优化算法，可删除一些不必要的连线 以简化可视图，缩短搜索时间。该法能够求得最短路径，但假设忽略移动机器人 的尺寸大小，使得机器人通过障碍物顶点时离障碍物太近甚至接触，并且搜索时 间长。 切线图法和v o r o n o i 图法【4 】对可视图法进行了改造。切线图( 如图1 1 ) 用 障碍物的切线表示弧，因此是从起始点到目标点的最短路径的图，即移动机器人 必须几乎接近障碍物行走。其缺点是如果控制过程中产生位置误差，移动机器人 碰撞的可能性会很高。图1 2 用尽可能远离障碍物和墙壁的路径表示弧。由此， 从起始节点到目标节点的路径将会增长，但采用这种控制方式时，即使产生位置 误差，移动机器人也不会碰到障碍物。 图1 1 切线图图1 2v o r o n o i 图 自由空间法应用于移动机器人路径规划，采用预先定义的如广义锥形和凸多 边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来 进行路径规划。自由空间的构造方法【5 1 是：从障碍物的一个顶点开始，依次作其 3 第一章绪论 它顶点的链接线，删除不必要的链接线，使得链接线与障碍物边界所围成的每一 个自由空间都是面积最大的凸多边形；连接各链接线的中点形成的网络图即为机 器人可自由运动的路线。其优点是比较灵活，起始点和目标点的改变不会造成连 通图的重构，缺点是复杂程度与障碍物的多少成正比，且有时无法获得最短路径。 拓扑刚6 】也是一种紧凑的地图表示方法，特别在环境大而简单时，这种方法 将环境表示为一张拓扑意义中的图( g r a p h ) ，图中的节点对应于环境中的一个特征 状态、地点( 由感知决定) ，如果节点间存在直接连接的路径则相当于图中连接节 点的弧。拓扑图的分辨率决定于环境的复杂度。这种表示方法可以实现快速的路 径规划，也为人机交互下达指令提供了一种更为自然的接口。由于拓扑图通常不 需要机器人准确的位置信息，对于机器人的位置误差也就有了更好的鲁棒性。但 当环境中存在两个很相似的地方时，拓扑图的方法将很难确定这是否为同一节点 ( 特别是机器人从不同的路径到达这些节点时) 。 基于栅格法【7 】的地图表示方法即将整个环境分为若干相同大小的栅格，对于 每个栅格指出其中是否存在障碍物。这种方法最早由e l f e s 和m o r a v e s 提出 8 1 ， 并在许多机器人系统中得到应用，是使用较为成功的一种方法。栅格地图很容易 创建和维护，机器人所了解的每个栅格的信息直接与环境中某区域对应，使用声 纳这样的廉价传感器即可获得创建地图的信息并加入地图中，借助于该地图，可 以完成方便地进行自定位和路径规划。使用栅格表示地图的缺点是：当栅格数量 增大时( 在大规模环境或对环境划分比较详细时) ，对于地图的维护行为所占用的 内存和c p u 时间迅速增长，使计算机的实时处理变得很困难。 1 3 2 路径规划的评估函数 路径规划算法的目的是搜索某种测度下巡视探测器的最优路径。但采用的测 度标准不同，规划出的路径就会有不同；即使在相同的测度标准下，不同的路径 规划算法也会产生不同的路径。为此首先需要确定路径规划的评估函数，以比较 不同路径的优劣。 距离是最常用的评估标准。由于距离在一定意义上代表了行走的时间和需要 的能量等代价，所以多数路径规划算法都以搜索最短路径为目标。 此外还可以将测度标准确定为时间和能耗。s h i l l e r 等【9 】将b o b r o w 等【1 0 】应用 于机械臂的路径规划方法应用于移动机器人，首先规划得到数条最短路径，然后 为每条路径进行速度轮廓优化。这也说明最短路径不一定是时间最优路径。 针对能耗的路径规划，r i c h b o u r g 】提出了一种基于光线折射理论的能耗路 径规划方法，该方法需要根据地形属性划分成不同的各向同性区域，机器人在不 同属性区域间移动时遵循光线折射定理( s n e l l sl a w ) ，依据此计算移动能耗并 寻找能耗最优路径。 4 北京邮电大学硕士学位论文 上述针对时间或能耗的路径规划，都是结合具体的算法，没有提出通用的具 有一般性的路径评估函数。 t o m p o k i n s 1 2 1 针对路径评估，提出了路径长度因子瓜、避障因子 、时耗 及徘徊因子兀来对路径进行评价。该评价方法基本与算法无关，但该评价方法仍 显得相对复杂。 1 3 3 路径规划的搜索算法 根据工作的环境，移动机器人路径规划可分为局部路径规划和全局路径规 划。基于传感器的局部路径规划，作业环境信息全部未知或部分未知，又称动态 或在线路径规划；基于模型的全局路径规划，作业环境的全部信息已知，又称静 态或离线路径规划。 局部路径规划和全局路径规划并没有本质区别，只是一个相对的概念。例如 在一定的精度下，作业环境中的信息都可以看成是全部已知的。本课题就是基于 这样的认识开展的，即在一定精度下，把当前的复杂环境当成是完全已知的环境 进行路径规划，机器人行走过程中遇到原先未知的或动态的障碍物时，在当前点 重新进行二次规划，就可以找到一条全局规划路径。注意，这里的二次规划并不 等于局部规划，传统的局部规划是碰到障碍物后，局部修改全局规划路径，而并 不是拟定一条新的路径。用于全局路径规划的方法经过改进都可以用于局部路径 规划，而适用于局部路径规划的方法都可以适用于全局路径规划。 全局路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的主 要方法都是基于上章的方法。路径搜索策略主要有：a 算法、d 系列算法等。局 部路径搜索算法包括人工势场法、模糊逻辑算法、m o r p h i n 算法等。 1 3 2 1 全局路径搜索算法 一般是依赖事先建立的全局地图，解决的是机器人从起点到终点应经过哪些 路径的问题。它根据先验的环境模型，在全局地图中找出一条从起始位置到目标 位置的与障碍物无碰撞的优化路径。 1 a 幸算法 a + 【1 3 】和d + 【1 4 】是一个通用的路径最优搜索算法，在具有网格的算法模型中都 可以使用。a 。算法是n i l s s o n l 9 8 0 年提出，属于启发式搜索中的最佳优先搜索方 法，是一种基于面积的全局规划算法。a 算法是在图中给定节点间动作成本根据 估价函数搜寻最优路径的方法，使用可接受启发式概念用最小的步骤寻找最优的 路径。但a 。既没考虑全局约束满足，也没有有效的二次规划。a b c 算法推广了 a + 算法，使之能适应多种约束。但由于约束是和每一状态相关而且没有主要路径 是不变的，所以算法很复杂，不适合在线编程。 5 第一章绪论 2 d 幸系列算法 d 系列算法包括有b a s i cd 、f o c u s e dd + 、c d + 、d l i t e 及f i e l dd 算法。 ( 1 ) b a s i c d l l 5 j 传统的全局路径规划只考虑一次规划，当环境变化时需要重新进行新的规 划，没有利用上次规划的信息。针对环境部分已知或者动态环境下的全局路径规 划问题，c m u 的s t e n t z 于1 9 9 3 年提出了b a s i cd 方法，当检测到环境变化时， b d + 只对产生变化的局部节点进行修改，从而避免对整个图的修改，从而提高了 搜索效率。但b a s i cd 。基于d i j k s t r a 算法，初次规划效率很低。 ( 2 ) f o c u s e dd 。【1 6 j 针对b a s i cd + 的初次规划低效率问题，s t e n t z 对其进行了修改，使其基于a ， 从而提高了初次规划的效率。f o c u s e dd 也就是现在常说的d 。( d y n a m i c a ) 。 ( 3 ) c d + ( c o n s t r a i n e dd 。) 【1 7 】 在移动机器人进行路径规划时，在搜索最优路径的同时应该满足一些约束条 件，如能源限制等。针对这种带全局约束的路径规划问题，s t e n t z 提出了 c o n s t r a i n e dd 算法。c d 使用权重因子最优代价和可行性( 全局约束) ，通过二元 搜索权重因子寻找在全局限制下权重空间的最优路径。在二次规划时仍需搜索合 适的权重因子，但权重改变相当于重新指定图中所有代价，从而不能体现d + 的 优势。 ( 4 ) d + l i t e 【1 8 】 s t e n t z 的d 算法在二次路径规划方面得到了广泛应用。但d + 算法的二次规 划实现比较复杂，原理上不易理解。为此，s k o e i n g 和m l i k h a c h e v 在l p a 算 法基础上提出了d l i t e 算法来实现动态环境下的二次规划，其原理和实现都比 d + 简单。 ( 5 ) f i e i dd 吐1 9 】 基于栅格的路径规划方法，由于其8 邻域移动准则的限制，其搜索的路径不 能达到最优。为使路径最优就必须打破8 邻域移动。为此d f e r g u s o n 和a s t e n t z 基于d 提出了f i e l dd + 算法。f i e l dd 算法打破了栅格8 邻域移动准则，可以减 小路径转向代价，从而使路径更为平滑。 1 3 2 2 局部路径搜索算法 一般是依赖当前时刻通过传感器获得的机器人附近一个小范围的局部信息， 解决的是机器人在当前时刻根据前方道路情况保持行驶在道路上，并避开障碍物 的问题。局部路径规划是依赖于传感器实时获取环境信息的在线规划，常用于全 局环境信息未知的情况或是对全局路径规划的补充。局部路径搜索算法包括人工 势场法、遗传算法、m o r p h i n 算法等。 6 北京邮电大学硕士学位论文 1 人工势场法 人工势场法是由k h a t i b 提出的一种虚拟力法。其基本思想是将机器人在环 境中的运动视为一种虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目 标点产生引力，引力和斥力的合力作为机器人的加速力，来控制机器人的运动方 向和计算机器人的位置。该法结构简单，便于低层的实时控制，在实时避障和 平滑的轨迹控制方面，得到了广泛的应用，但对存在局部最优解的问题，容易产 生死锁现象( d e a dl o c k ) t z u l , 因而可能使机器人在到达目标点之前就停留在局部 最优点。为解决局部极小值问题，已经研究出一些改进算法，如s a t o 提出的 l a p l a c e 势场法。改进算法是通过数学上合理定义势场方程，来保证势场中不存 在局部极值。 2 遗传算法 j h o l l a n d 在6 0 年代初提出了遗传算法l 二，以自然遗传机制和自然选择等 生物进化理论为基础，构造了一类随机化搜索算法。它利用选择、交叉和变异来 培养控制机构的计算程序，在某种程度上对生物进化过程做数学方式的模拟。它 不要求适应度函数是可导或连续的，而只要求适应度函数为正，同时作为并行算 法，它的隐并行性适用于全局搜索。多数优化算法都是单点搜索算法，很容易陷 入局部最优，而遗传算法却是一种多点搜索算法，因而更有可能搜索到全局最优 解。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息，所以解决了一 些其它优化算法无法解决的问题。但遗传算法运算速度不快，进化众多的规划要 占据较大的存储空间和运算时间。 3 m o r p h i n 算法 m o r p h i n 算法m 卅是一种基于栅格的局部地形可穿越性分析的局部避障算法， 其最初的形式是c a r n e g i em e l l o n 大学用于无人高速越野车辆导航系统的r a n g e r 规划算法，经过不断改进和地面样车r a f t e r 、b u l l w i n k l e 、n o m a d 的实验，m o r p h i n 算法目前正用于m e r 的局部避障中，称之为g e s t a l t m 川。 m o r p h i n 算法实质是通过对探测器局部地形进行统计分析，确定适宜行进的 路径，而不是简单的避开障碍，它不仅能较好地处理来自环境建模的不确定性( 如 立体视觉得到的三维地形图、激光测距仪的误差等) 和定位误差，而且能和全局 规划算法比较好地结合，共同决策巡视探测器的底层运动行为。 m o r p h i n 算法的主要过程是： ( 1 ) 地形的适宜度 把三维地形图分割成两种级别栅格，用最小二乘拟合栅格平面，拟合残差归 一化后分别用于表示行进于该地形时的横倾、纵倾和地形粗糙度的度量，三个度 量的最小值代表该栅格的适宜度。由各个栅格的适宜度值形成该地形的适宜度 7 第一章绪论 图。 ( 2 ) 地形的置信度 根据栅格内的数据点数和点的分布计算该地形的置信度。 ( 3 ) 地形适宜图的拼接 随着探测器的行进，得到地形的适宜度图序列，在m o r p h i n 算法中采用一种 具有与距离相关的“记忆”方法对地形适宜度图进行拼接。 ( 4 ) 路径的可穿越性分析 在地形适宜度图上，对给定的弧段进行可穿越性分析，每一弧段代表待选的 轨迹，弧段的可穿越度定义为弧段的适宜度和弧段置信度的乘积，分别是弧段所 经过的栅格的适宜度和置信度的加权平均值。 路径的可穿越性度量用于和全局路径规划的结果共同确定车的底层轨迹指 令。 1 3 4 典型行星巡视探测器路径规划算法 各国在探测计划论证期间和巡视探测器工程研制任务的前期，开展了大量的 先期研究工作，研制了各种类型的地面样机，取得了巡视探测器设计的宝贵经验， 为飞行试验提供了技术储备，r o c k y 7 、f i d o 、m a r s o k h o d 是3 个最为典型的 地面样机；美国的火星探测计划则将行星表面巡视探测器推向实用化，s o j o u r n e r ， m e r 是两个成功的应用实例。 对于行星探测器的路径规划，目前主要有两种不同的研究思路。 一种是基- ：t a n g e n tb u g 的反应式搜索算法【2 4 】【2 5 】【2 6 】。如s o j o u r n e r 火星探测器 应用了一种类 以t a n g e n tb u g 的反应式算法g ot ow a y p o i n t 算法；另外还有s l l a ub a c h 等人根据t a n g e n tb u g 算法改进的基于传感器的w e d g eb u g 反应式算法， 其在r o c k y 7 _ a l _ 进行了实验验证。这类算法的优点是只依赖于巡游探测器上的传感 器信息，算法简单，运算量小。但仍存在一些问题：例如在算法中将探测器视为 一个点的局限性以及对障碍物边界检测的困难性，都给算法的实际应用带来一定 的困难。 另外一种思路是基于栅格地形图的启发式搜索算法，研究最广泛的是s t e n t z 的d + ( d y n a m i ca + ) 搜索算法，其改进算法，如t e r r yh u n t s b e r g e r 提出的的 r a d m a p 算法。d + 算法是在启发式搜索算法a 上改进而来的，解决了重新规划 路径的时间问题：r a d m a p 算法在火星车地面样机f i f o 上进行了应用试验， 效果比较理想。 国内针对于行星探测器路径规划的研究尚少，而且多偏重理论仿真。居鹤华等人 提出了行为控制月球车路经规划方法，该方法在t a n g e n tb u g 切线法基础上引 入一组自适应行为来构造切线拓扑图，进而进行路经搜索规划【2 7 】。刘方湖等人提 8 北京邮电大学硕士学位论文 出了基于五轮铰接式月球车的基于虚拟传感器的双向全路径规划方法和降维法， 并进行了仿真分析【2 引。 索杰纳( s o j o u r n e r ) 由美国j p l 研制，在火星探路者的可视范围内( 半径 2 0 m ) 进行科学实验。通过地面操作人员对车体位置更新与航位推算结合的方式 实现定位，在路径选择上，s o j o u r n e r 根据避碰传感器的状态，利用简单的转向逻 辑完成。 r a f t e r ( r o b o t i ca l lt e r r a i nl u n a re x p l o r a t i o nr o v e r ) 【2 9 】用于发展在月球任 务中应用的遥驱动技术。r a t l e r 的路径规划基于“安全防护遥操作”思想，即：地 面操作者负责引导月球车的行驶方向，并由车载的安全防护系统负责月球车行驶 过程中的局部避障，由命令仲裁器将两者结合产生安全可靠的导航。路径规划的 核心技术是感知和反映地形特征的车载安全防护系统，主要包括两个方面：基于 立体视觉的局部避障和基于激光测距仪的障碍检测。 n o m a d 【3 0 】由c m u 大学研制，其主要目的是开发，评估和验证能长时间工作 的自主探测车，试验环境类似于月球和火星的表面，既有自主控制又有几千里外 的人工遥操作。n o m a d 使用一种称为适宜图( g o o d n e s sm a p ) 的地图结构为穿越环 境建模。适宜图由若干栅格组成，每个栅格包含两个数据：一是适宜度，表示车 体在该处的适应性；一是可信度，表示适宜度的可靠程度。n o m a d 通过立体相 机和激光系统分别根据其测量信息生成适宜图，在避障模块中使用的适宜图就是 对其进行加权计算后得到的结果。 n d o 是n a s a 为m e r ( “勇气号”和“机遇号”) 设计的地面样机，其主要任 务是：( 1 ) 远距离运行与科学探测；( 2 ) 岩石和土壤的采样返回；( 3 ) 两辆探测 车的集合和样本转送。f i d o 上采用了一种称为r o a m a n ( r o a dm a pn a v i g a t i o n ) 的导航算法，结合了c 空间算法( c s p a c er e p r e s e n t a t i o no f t h ee n v i r o n m e n t ) 对环 境描述的简洁性和d 搜索算法的高效性，在f i d o 上经过多次验证。f i d o 的路径 规划和避障是由安装在桅杆上的宽基线( b a s e l i n e ) 、- r _ 体相机对和安装在车体上的 窄基线立体相机对完成的。由装在桅杆上的宽基线立体相机对采集的图像实现长 距离路径规划，由装在车体上的窄基线立体相机对采集的图像实现局部路径规 划，两者结合实现自主的长距离穿越。 r o c k y 系列探测车是j p l 开发的地面样机，其中以r o c k y7 最为成熟，它 在s o j o u r n e r 的基础上作了一些改进，主要用来验证为了在火星表面行走更长距 离( 5 0 k m ) 所需的新技术应用情况。r o c k y7 路径规划是基于复合架构的。包括 在着陆器控制范围内的路径规划和脱离着陆器的远距离路径规划。 9 蚺一帝绪论 囤1 - 3 索杰纳示意图圄1 4r a t l 日示意图图1 5 n o m a d 示意图 图1 6f i d o 示意田图1 7r 。c k v7 示童囤 1 4 论文研究内容及组织结构 1 4l 研究思路及方法 在本文研究过程中，将采用以下研究思路和研究方法： ( 1 ) 本文研究工作将在充分研究国内外相关成果的基础卜开展，尤其是美国 相关的巡视探测器路径规划研究成果，以及机器人路径规划的相关成果，保证本 文工作在较高的水平上开展。并结合正在开展的月球巡视探测的课题背景，循序 渐进，从静态到动态，逐步研究课题背景下的复杂未知环境中移动机器人的全局 路径规划问题。 ( 2 ) 从系统仿真研究入手，考虑月球环境的复杂未知性和地月通讯的丈延时 性，进行路径规划研究工作。包括几种传统全局路径规划算法实现及改进、模拟 月面环境的三维建模、三维复杂动态环境下的全局路径规划算法研究，在此基础 上开展仿真验证，提高研究工作效率。 北京邮电大学硕士学位论文 1 4 2 主要研究内容及组织结构 月面巡视探测器有遥控、遥操作、遥操作+ 半自主和自主多种工作方式。由 于地月通讯的大时延特性，月面巡视探测器必须具有一定的自主工作能力。但同 时由于我国首次进行月面巡视探测，不确知因素较多，因此依赖月面巡视探测器 自主完成全部任务，可靠性和安全性都难以保障，且目前的技术水平尚不具备实 现月面巡视探测器全自主控制的条件；另一方面，若依赖于地面遥操作，则操作 效率将受限于地月间的通讯时延和带宽，也导致操作人员的工作量和复杂程度提 高。因此为综合提高月面巡视探测器的工作效率和安全性，月面巡视探测器需要 结合遥操作和自主运行，才能保证探测任务的有效完成。 基于上述论述，月面巡视探测器的路径规划功能分为两层：远距离全局路径 规划模块和近距离局部路径规划模块。全局路径规划模块获取大范围低分辨率的 d e m 地形图，并为局部路径规划模块指明起始方向和初始路径，由地面遥控完 成；局部路径规划模块获取小范围高分辨率的d e m 地形图，实时响应传感器信 息，规划局部路径，修正全局路径，由月面巡视探测器自主完成，全局和局部路 径规划结合起来解决月面巡视探测器的路径规划问题。 针对上述路径规划执行方案，本文运用理论研究、仿真建模计算等手段，循 序渐进，从静态到动态，逐步研究月面巡视探测背景下的复杂动态环境下的移动 机器人的全局路径规划算法。在对传统全局路径规划算法原理学习的基础上，进 行了软件实现和仿真验证，分析实现了几种传统全局路径规划算法，提出了一种 评估函数的修改方法；针对传统算法用于三维复杂动态环境下的路径规划存在的 问题，提出了一种新的三维地形建模的方法，提出了新的通行性判断标准，利用 工业预测和滚动规划策略将动态障碍物处理成静态障碍物，对算法进行了改进， 使之能够应用于三维复杂动态的模拟月面环境。接着基于我国月面巡视探测器 “遥操作+ 半自主的控制模式需要，研究了局部避障算法，将全局路径规划算 法和局部避障算法结合起来，模拟演示了月面巡视探测器的路径规划过程。最后 针对路径评估方法出现的问题，提出了一种新的全局规划路径的评估方法。 本学位论文总共六章，各章节安排如下： 第一章一绪论。介绍了课题来源背景与研究意义，从环境建模、路径的评 估函数、路径规划的搜索算法、典型行星巡视探测器路径规划算法四个方面分析 研究了移动机器人路径规划技术国内外发展现状，最后概述了本文的研究内容和 组织结构。 第二章传统全局路径规划算法研究。研究了静态环境下常用的全局路径 搜索算法a 算法和复杂动态环境下用于二次规划的d 4