（计算机应用技术专业论文）动态环境下四足机器人运动规划和控制.pdf

摘要 摘要 一个“智能”的系统必须能够感知，规划和控制，只有具备了上述能力的系 统才能够完成不平凡的任务。在这篇文章中，我们讨论了这样一个系统：一个在 动态环境中基于自身传感器工作的四足机器人系统。 对于移动机器人而言，运动规划和控制方面的智能是最基本，也是最核心的 问题之一。本文以r o b o c u p 四腿组为背景，对如下问题展开了研究： 1 提出一种新的四足机器人里程计计算方法，该方法通过对机器人腿部建 立参数化模型，以实际运动特征优化模型，使四足机器人的里程计误差仅为对比 方法的5 0 并降低了标定复杂度。 2 在机器人定位误差很大，环境噪声很高的情况下，作者提出一种基于里 程计的运动规划方法，利用a 算法搜索出机器人的参考运动轨迹，将机器人运 动约束融入到a 幸算法搜索过程中，使得该方法能满足路径末端机器人的位姿限 制。 3 由于四足机器人复杂的动力学特性，传统的控制方法难于实现，提出一 种基于模型的运动控制方法。 4 。设计一种适合完成复杂任务的自主机器人控制框架。该框架中使用卡尔 曼滤波器融合视觉传感器信息和自身关节传感器的信息，能够实现对四足机器人 的精确控制，并在r o b 0 c u p 四腿组平台上，使用该方法成功的实现了动态的带 球，这也是整个r c b o c u p 四腿组内的首次实现。 关键字四足机器人，移动机器入，动态环境，里程计，运动规划，运动控 制，机器人足球，卡尔曼滤波器 a b s t r a c t a b s t r a c t a n “i n t e l l i g e n t s y s t e mm u s tb ea b l et os e n s e ，p l a na u l dc o n t r 0 1 o i l l y 、v h e nt 1 1 e s e c a p a b i l j t i e sw o r kt o g e m e ras y s t e mc a ns u c c e s s 如j l ya c c o m p l i s hn o n t r i v i a lt a s k s m u l i st h e s i sw ed i s c u s si s s u e si nm ec o n t e x to fas e n s o r - b a s e dq u 乏帅e dr o b o t 、v h o w o f l ( si i lad y r 姗i ce n v i r o m l l e n t m o t i o n 叫a n n i n ga 1 1 dm o 垃o nc o n t r 引a r et h eb a s i cj n t e 】l i g e n c eo fm o b i j er o b o t u n d e rm eb a c k g r o u n do fr - o b o c u pf o u r - l e g g e dl e a g u e ，“sm e s i sd i s c u s s e s f o l l o 、i n gt o p i c s ： i i h st h e s i sp r e s e n san e w o ( 1 0 m e t 哆c a i c u j a i n ga n dc a i i b a 珏n gm e 毒h o d 南f q u a d m p e dr o b o t t h j sm e t h o ds e t su pa “p a r 锄e t r i cp h y s i c a lm o d e l i n c o 印o r a t i n g v 撕o u sp r o p e f t i e so ft h er o b o ta n de n v i r o 脚e n ts u c ha s 衔c t i o n ，幻e r t i 鸟e t ct 1 1 r o u g h o p t i m i z a t i o nw i t hl o c o m o t o rd a t a t h ee x p e r i m e n t so ns o r l ya i b oe r s 一7r o b o t s s h o w e dt h a tt 1 1 eo d o m e t d re r r o ro fm en e wm e t h o di sg e n e r a l l y0 1 1 l ya ：b o u t5 0 o f t h ee x i s t i n gm e t h o d i i la d d i t i o n ，t h ec a i i b r a t i o nc q m p l e x i t yi sr a t h e rl o w 2 a i m i n ga tr o b o tw o r ki nd y n 啪i ce n v i r o 啪e n t sa i l d 、v i t l ll a r g el o c a l i z a t i o n e r r o r ，a u t h o rp r e s e n t sam o t i o np l a m i n gm e t h o dw 砸c hi sb a s e do no d o m e t q t h e m e t h o df i n dar e f e r e n c et r 面e c t o r ) rb ya 宰a l g o r i t a i l dc o n s i d e rt l l el i l 血t a t i o no f r o b o tm o t i o nb yc o n s 打a 枷n gt h en 0 如铽t e n s i o nm e 也o di na a l g o r i k l ，t h i s m e t h o dc a ns a t i s 匆m er e s t r i c t i o no fr o b o tp o s ew h e nm er o b o tm o v e st ot h e e n d p o i n to fat r 句e c t o d ， 3 b e c a u s eo ft h cc o m p l e x i t yo fd y n a m i co ft h eq u a ( i n l p e dr o b o t ，t h e t r a d i t i o n a lc o n t r o lm e t h o dc a nr l o tw o r kw e l l ；t l l i sm e s i sp r e s e n t sam o d e l - b a s e d m o t i o nc o n t r o lm e t l l o d 4 t h i sm e s i sa l s od e s i g n sar o b o tc o n t r o l 丘a m e w o r kf o rr o b o ta c c o m p l i s i l i n g c o m p i e xt a s k a 隐i m a i l6 i e ri sa d o p e d 凡f 如s j n g h ev j 正o ns e 玎s o f 越地j 西n t s s e n s o r s o nm er 0 b o c u pf o u r - l e g g e dp l a t f o n i l ，t 1 1 i sm e t l l o da c c o m p l i s h e sd y n 锄i c d r i b b l ea n dt 1 1 i si st h e 丘r s tt i m ea c h i e v i n gt h i sg o a li nf d u rl e g g e dl e a 黟l c k e yw o r d sq u a d r u p e dr o b o t ，m o b i l er o b o t ，d ) r i l 锄i ce n v 的眦e 咄o d o m e n y ， m o t j o np i a n ，m o t i o nc o n 仃0 l ，r o b o c n p ，k a l m a n 丘1 t e r 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：互至氆堕 杪鼍年r 月) 口日 1 东 第l 章绪论 对慎思式的机器人来说，与环境交互的过程能分为如下的三个模块( 图 1 2 ) ： f a )附 图i 2自主机器入模块划分及模块之间关系 1 感知( s e n s e ) 。机器人搜集周围环境的必要信息，这些信息可能是地图 参数或者一个命令。对于自主机器人来说，感知过程主要是从搜集各种传感器 信息并处理，构建自身状态和世界模型。这些传感器可能是彩色摄像头，红外 传感器，声纳或者g p s 接收器等。 2 规划( p l a n ) 。获取了必要的信息后，机器人需要找到一种方式去完成 既定的任务。比如一个足球机器人发现了场地上的球，它需要绕过前方阻挡的 机器人，到达球的位置并选择一个处理球的动作，机器人必须首先规划一条路 径，可能需要考虑障碍物，自身动力学特性等。这就是规划过程所要处理的问 题。 3 控制( c o n t r 0 1 ) 。这个过程就是将既定的规划实现的过程。一旦形成了 一个规划，控制部分将负责实现。比如，控制机器人沿规划的路径移动等。控 制通常需要考虑机器人的运动学和动力学特性等。 当处理复杂的任务时，比如机器入足球中的连续带球，不仅需要规划带球 的前进方向，还要控制身体把球踢到合适的位置，而且带球过程中，机器人不 能把目光( 视觉) 一直盯在足球上，还需要注意到周围的障碍物以及球门的方 向。在这样一个复杂的任务中，感知，规划和控制三个模块必须相互交互，如 图1 2 中b 所示的那样。在这幅图中，规划模块不再是被动的从传感器模块接 收信息，而要主动的指示传感器向哪个探测，或者需要哪种信息。同样的，控 制模块也不仅仅负责执行，当它发现执行的规划已经无法完成或者规划已经“过 时 时，也会提醒规划模块；是时候修改规划了。 本文将主要研究规划和控制所面i 临的问题，也是j o h n 总结的机器人导航 2 第l 章绪论 ( n a v i g a t i o n ) 所要处理的三个核心问题：“我在哪里”，“我将要去哪里 和“我 如何到达那里 中的后两个。然而第一个问题作为后两个问题的基础，在处理 后两个问题时，无可避免的需要面对“我在哪里 ，“我移动了多远”的问题。 将移动机器人系统设计为仅仅依赖于其自身的传感器显而易见的拥有很多好 处，另一方面，自主移动机器人往往需要工作在动态环境串，也限制了它们只 能依赖于自身的传感器。所以，机器人不得不容忍传感器信息的误差，获取信 息的局部性以及自身状态的估计误差和世界模型的偏差。特别的，有一些应用 强调机器人执行任务的速度，比如在机器人足球比赛中，几乎没有时间给机器 人停下来扫描地标等标志物以恢复错误的定位，在这样的情况下，机器人仅仅 能依赖一些传感器获得的相对信息，比如自身相对某一个时刻的相对位移，目 标的相对位置，相对速度等。在动态环境中，面对信息的缺失和不确定，本文 将针对这样的情况展开对四足机器人运动规划和控制的研究。首先针对感知过 程，本文提出一种新的里程计算法，改善四足机器人里程计的精度，并且为机 器入的运动控制提供自身状态的反馈，在此基础上，提出一种基于视觉传感器 和里程计的局部运动规划方法，其中使用扩展的卡尔曼滤波器对多传感器的信 息进行融合；对于控制问题，本文将介绍种适用于四足机器人的基于模型的 控制方法，并给出基于该方法的控制框架，最后本文将给出使用这一套方法解 决机器人足球中实际问题的结果。 接下里的文章将这样组织：本章的下段将总结步行机器人里程计和运动 规划研究现状：第二章介绍一种新的四足机器人里程计算法- m b o 方法，并 给出实验以验证该方法的精度；第三章介绍一种考虑枧器人运动特性的运动翅 划算法。第四章介绍一种基于模型的运动控制框架和方法。第五章介绍一个实 际的应用系统：给出了一种能够处理复杂任务的自主机器人系统框架并以机器 人足球为背景，介绍整个系统处理机器人足球问题的成果。第六章将对文章总 结，并指出进一步的工作，结下来是参考文献和附录，附录将介绍自主设计的 实验系统g t m s 系统。 l 。2 。里程计 里程计( o d o m e t 巧) 这个单词源于希腊语中的单词“h d d d s ”( 意为旅行。 行进) 和“m e t r o n ( 意为测量) ，最开始使用在航海中，是指一种通过观测星 空或者其他参考坐标，而计算出自身航行的里程和方向的方法。 在移动机器入领域中里程计通常用来指轮式小车自身位置估计的一种方 法，也用做描述轮式小车自身的位移，包括位置和身体朝向的变化量，通常也 等同于d e a df c 如n i n g ，里程计是用来估计自身裙对某个已幻位置的莛点的 第1 章绪论 相对位置的方法，对于轮式小车来说，里程计就是通过观测轮子转动而获取自 身的相对位移的方法。而在步行机器人中，一般认为里程计是通过本体感受 ( p r o o c e p t i o n ) ，如腿部关节的位置，而获取自身相对位移的方法。 里程计被广泛的应用在移动机器人导航中，是最重要的一种相对定位方法 ( k e l l y ，2 0 0 4 ) 。这是因为里程计具有获取方便，系统开销小，实时性好这些 特点( b o r e n s t e i n ，1 9 9 6 ) ，能够提供高频率的，连续的自身位置变化信息。里 程计的缺点是误差会无边界的积累，随着机器入移动的距离增加，误差也会累 积得越来越大。 对于轮式移动机器人而言，国内外学者已经做了大量研究如何减小里程计 的误差，已有很多的文献资料，这些方法主要包括测定运动学参数( 觚o n e l l i ， 2 0 0 3 ) 和标定误差模型( c h o n g ，1 9 9 7 ) 两种。但是对步行机器人而言，这方 面的研究还非常少( c o b a j l o ，2 0 0 7 ) 。目前对四足机器人里程计的研究，主要集 中在r o b o c u p 的四腿组( 标准平台组，、 ，、 r 、v r o b o c u p o r g ) 中。 t h o m a sr 石f e r ( 2 0 0 4 ) 提出了一种基于接触传感器的里程计计算方法，但 这种方法适用的范围非常有限。g e 硼a j lt e 锄( d n 位r t ，2 0 0 5 ) 通过优化行走引 擎的参数( h e n g s t ，2 0 0 2 ) ，使得行走命令和行走引擎的执行效果实际速度 尽可能的接近，其标定里程计的过程是寻找执行效果和该行走命令最符合的行 走引擎参数。r u n sw i r ( c h e n ，2 0 0 5 ) 通过多项式拟合的技术标定里程计，他 们寻找一条命令和实际速度之间最好拟合的曲线。l i i i 和他的团队( 2 0 0 6 ) 针 对他们的六足机器人，提出了一种通过身体位姿计算里程计的方法。s t r o n g 和 s t o n e ( 2 0 0 5 ) 提出了一种自标定的方法，能够做到完全自动的标定里程计，但 目前未见用该方法标定全方位行走的工作和实验结果。这些方法的不足在于标 定复杂，通常需要标定数量巨大的行走命令，另一个不足在于认为机器人不存 在加( 减) 速过程，其里程计由行走命令或由标定得到的实际速度乘以该命令 的执行时间得到，无法反映机器人速度增加( 减小) 的过程。 近年来，里程计已不仅仅应用于机器人相对定位中，也用于机器人路径规 划，运动控制等其他方面。 1 3 运动规划研究现状 对机器人运动规划的研究是2 0 世纪6 0 年代出现的( n i l s s o n ，1 9 8 4 ) 。1 9 7 8 年l o z a n o p e r e z 和w r e s l e y 首次引入构型空间( c 一空间) 的概念构造规划器，对 于现代的运动规划问题是一次划时代的革命。在c 空间中，每一个位姿代表着 机器人在物理空间中的位置和方位，机器人被当作一个点，运动规划问题就变 成在位姿空间中寻找一条从起始位姿点到目标位姿点的连续路径。1 9 8 7 年，j 4 第l 章绪论 p i 烈曲o n d ( 1 9 9 8 ) 将机械系统中的非完整性引入到机器人运动规划中解决自 动泊车问题。自此，非完整运动规划成为一个新的研究热点一直延续到今天。 移动机器人路径规划可以当作运动规划的一个简单特例。所谓“路径”是指在 位姿空间中机器人位姿的一个特定序列，而不考虑机器人位姿的时间因素；而 “轨迹”与何时到达路径中的每个部分有关，强调了时间性( l a l 】m o n d ，1 9 9 8 ) 。 机器人运动规划就是对“轨迹”的规划，按照环境建模方式和搜索策略的 异同，可将规划方法大致上分成三类，分别是基于自由空间几何构造的规划， 前向图搜索算法和近年兴起的以解决高维姿态空间和复杂环境中运动规划为目 的的基于随机采样的运动规划。 1 3 1 基于自由空间几何构造的规划方法 基于几何构造的规划方法有可视图( o o r l l m e n ，1 9 8 7 ) 、切线图( l i u ，1 9 9 4 ) 、 v o r o n o i 图( c a n n y ，1 9 8 5 ) 以及精确( 近似) 栅格分解( p a r s o l l s ，1 9 9 0 ，c h e n ， 1 9 9 7 ) 等方法。路径规划是搜索的过程( b o n e t ，2 0 0 1 ) 。不管何种规划算法， 最终都将归结到在某个空间中搜索一条满足某准则的连续路径问题。利用几何 构造的手段描述环境的自由空间，一般都会构成图( 栅格被当作一类特殊的图) ， 最终完成轨迹的规划需要图搜索这个很重要的步骤。 基于自由空间几何构造的规划方法基本思想就是构造某种图来描述环境的 自由空间，从图上找到满足某种准则的最优路径。此法一般包括两阶段：第一 阶段构造一个描述自由空间关系图，第二阶段按照一定的准则( 最短距离、最少 时间等) 寻找一条最优路径。其中，图的构造比较重要，搜索算法一般采用 d i i k s 仃a 算法或a 幸算法。 可视图法可视图法是1 9 s 7 年j p l a u m o n d ( 1 9 9 8 ) 提出的， l a t o m b e ( 1 9 9 1 ) 对此进行了详细描述。在c 空间中，以多边形障碍物模型为基础，任 意形状障碍物用近似多边形代替，用直线将机器人运动的起始点q i n i t 和所有c 一 空间障碍物的顶点以及目标点q 酬连接，并保证这些直线段不与c 空间障碍物 相交，形成了一张图，称为可视图。然后采用图搜索算法寻找从起始点到目标 点的最优路径，搜索最优路径就转化为从起始点到目标点经过这些可视直线的 最短距离问题。可视图构造的时间复杂度是0 ( ，1 2l g ) 或者d ( 玎2 ) ，n 代表障碍物 的顶点总数。 v o m n o i 图法计算几何中的很多技术被引用到机器人的运动规划中来， 基于v 0 r o n o i 图的路径规划就是一个典型的例子( c a i l n y ，1 9 8 5 ，) 。在c 空间中， 根据已知的障碍分布情况，取障碍物的顶点、边界构造出c 空间中障碍分布的 v o r o n o i 图，连接机器人运动的起始点q i n i 。以及目标点q g o a l 到已经构造好的 第l 章绪论 v o r o n o i 图上，构成环境中自由空间“骨架”的图，在此基础上，基于图的搜索 算法可以找到连接起点和终点的最短路径。v o r o n o i 图构造的时间复杂度是 d ( 珂l g 刀) ，实时性较好，生成的路径相对比较安全，远离障碍，并且路径比较 平滑，合理性也较好，但是不能保证路径最优。c h o s e t ( 1 9 9 5 ) 等对广义v 0 r o n o i 图( g v g ，g e n e r a l i z e dv o r o n o ig r a p h ) 在基于传感器的路径规划方面进行了深入 研究。 栅格分解法是目前研究最广泛的路径规划方法之一( k 啪b h 锄p a t i ， 1 9 8 6 ) 。该方法将机器人的工作空间分解为多个简单的区域，一般称为栅格。由 这些栅格构成一个显式的连通图，或在搜索过程中形成隐式的连通图，然后在 图上搜索一条从起始栅格到目标栅格的路径。一般，路径只需用栅格的序号表 示。按照栅格划分的方式又分为确切的和不确切的两种。确切的栅格法( p a r s o n s ， 1 9 9 0 ，l a t o m b e ，1 9 9 1 ) 将机器人工作环境分解成一系列固定大小的栅格单元， 环境被量化成具有一定分辨率的栅格序列。赋予每个栅格一个通行因子后，路 径规划问题就变成在栅格图上寻求两个栅格节点间的最优路径问题。在该方法 中，分辨率直接影响着环境信息存储量的大小和规划时间的长短。在不确切的 栅格分解法( c h e n ，1 9 9 7 ，l a t o n l i b e ，1 9 9 1 ) 中，所有的栅格都是预定的形状， 通常为矩形。整个环境被分割成多个较大的矩形，每个矩形间都是连续的。如 果大矩形内部包含障碍物或者边界，则又被分割成4 个小矩形，对所有稍大的 栅格都进行这种划分，然后在划分的最后界限内形成的小栅格间重复执行程序， 直到达到解的界限为止。这种分解的结构称为“四叉树”。c m u 已将这种不确 切的栅格描述法用于越野环境下自主地面车导航，取得很好效果( i a ，1 9 9 8 ) 。 切线图法以多边形障碍物模型为基础，任意形状障碍物用近似多边形替 代，在自由空间中构造切线图。文献( l i u ，1 9 9 4 ) 采用移动线和扫描线相结合 的方法构造切线图。采用“移动线算法”检测障碍物顶点之间的所有公切线， 然后利用一种“扫描线算法”测试已知公切线与障碍物之间是否存在交叉点， 如果存在，滤除这些公切线，剩下的公切线构成的图被称为切线图。构造切线 图在最坏情况下的时间复杂度为d ( 【m + r 】牛+ m 2l g m ) ，其中n 表示障碍物 顶点数，m 表示个点构成的凸曲线的条数，r 表示开凸曲线的滚动数。最后， 搜索最优路径的问题转化为从起始点到目标点经过这些障碍物切线的最短距离 问题。文献( 吴峰光，2 0 0 4 ) 在此基础上，采用跳跃式扫描技术按需扩展搜索 图，使机器人能在行进中构造切线图，可以较好地适应未知和动态环境。 1 3 2 前向图搜索算法 描述地形的图构造出来后，最优路径搜索显得非常重要。下面对图的常用 6 第1 章绪论 搜索算法进行总结。 贪心算法是最简单的图搜索算法( m c k e e v e r ，2 0 0 0 p a p a d a t o s ，1 9 9 6 ) ， 是一种典型的集中考虑局部费用最小化，而忽略全局最优的搜索算法，该算法 不能保证一定收敛到目标节点，就是说，该算法不完备。 d i j k s t r a 算法d i i k s t r a 算法( o r l i n ，1 9 9 3 ，p a p a d a t o s ，1 9 9 6 ) 是最短路径 搜索的经典算法，首次出现在1 9 5 9 年，随后广泛应用在最短路径搜索问题中。 该算法可以在显式图中找到从源节点到任意节点的最短路径，或者从目标节点 到图中任意节点的最短路径。如果该算法在到达目标节点时结束，那么一定可 以找一条从源节点到目标节点的最短路径。算法复杂度是。硒。多年来，研究 者不断改进算法，遗传算法实现d i j l ( s t m 算法的最优时间上界是 d ( i i l i n ( 聊= i g 以，朋l g l g c ，聊+ 疗( 1 9 c ) o 。5 ) ) ) ，其中c 是满足一定属性的常数。 a 矗算法a 枣算法( p a p a d a t o s ，1 9 9 6 ) 是应用极广的隐式图启发式搜索算法， 其距离函数的定义具有启发性，在栅格结构的数据集上性能相当好。其距离函 数的定义一般为厂0 ) = g ( c ) + 磊p ) 。即某个栅格( 节点) c 处的距离c ) 定义为从 起点至c 的距离g ( c ) 与从c 到目标点距离的估计j l z ( c ) 之和。如果启发式估计j i z ( c ) 是真实路径费用的下界，只要该路径存在，a 算法的可接纳性保证它可以得 到一条最优路径。j p e 训等( 1 9 8 0 ) 全面研究了a 牛算法的平均计算量和距离 函数的估计精度之间的关系，得出a 宰的计算量为多项式的充要条件是距离函数 必须具有“对数 阶精度。但在实际应用中这个要求很难达到，a 幸算法基本上 未能克服计算量的指数爆炸困难。已证明对于平面避障问题a 是多项式时间算 法，但当环境复杂、规模较大时是低效率的，经常几乎要扩展整个规划空闻才 能找到目标。针对a 的这一缺陷，人们提出了许多改进措施，如采用并行机制、 分层规划机制等。 d 算法上述的图搜索算法只限于在静态图上的搜索，s t e n t z 发展一种d 幸 算法( p a p a 妣o s ，1 9 9 6 。s t e n t z ，1 9 9 4 ) 可以在动态图上搜索到最短路径。通常， 该算法能够在搜索动态图目标节点的过程中处理变动弧的费用，假设弧的费用 在遇到障碍时可能会发生变化。需要指出，d 母在静态图中的搜索情况将退化为 d i i k s 娩算法，时间复杂度为o ( n 2 ) 。s 话n t z 表示，“若d 宰算法在搜索结果的过 程中，费用参数可以随之改变的情况下，它可以处理任意的路径优化问题 ，“当 参数的变更发生在起始点附近时。算法效率最高”。该算法在c m u 的越野环境 导航实验中取得了很多成果( m j a ，1 9 9 8 ) 。 人工势场法物理学中的场的概念也被引进来描述机器人在空间中的几何 结构，引导机器人向目标行进。这些场包括常见的势场，还有距离场( k i l l u i l e l ， 1 9 9 8 ) 以及来自于水力分析的基于流函数( w a y d o ，2 0 0 3 ) 的规划算法。国内 7 第1 章绪论 对后两种算法研究甚少享天工势场法( h 、啪g ，1 9 9 2 ) 最初由k h a t i b ( 1 9 8 5 ) 提出，其基本思想是引入一个称为势场的数值函数来描述机器人空间的几何结 构，通过搜索势场的下降方向来完成运动规划。势场分为两部分，即目标位姿 产生的吸引势和障碍物产生的排斥势。吸引势使机器人向目标位姿靠近，排斥 势使机器人绕开障碍物，二者的叠加构成机器人运动的虚拟势场，势场的负梯 度作为作用在机器人上的虚拟力，该力“推动”机器人向着目标作无碰运动。 1 3 3 基于随机采样的运动规划方法 前面介绍的规划算法基本上属于相对确定的方法，就是说对于同环境任 意两次不同规划，结果都相同。但是即使一类简单的规划问题，比如一个点机 器入在三维多边形障碍环境中运动，其规划复杂度在j 9 8 8 年就已经被j f c 枷y 证明是n p 复杂度( r e i f 1 9 7 9 ，c a n n y ，1 9 8 8 ) 。通常，规划问题的复杂 度与机器人的自由度成指数关系。与环境中障碍物的规模成多项式关系，规划 问题随着机器人自由度增多会出现“维数灾难( d i m e n s i o nc u r s e ) 问题，因而以 上确定性算法不适合解决高自由度机器人在复杂环境中的实时规划( l a v a i l e ， 2 0 0 4 ，j e a n ，2 0 0 1 ) 。为了解决存在的问题，科学家们采用基于在规划空间( 如位 置空间、姿态空间、状态空间等) 中随机采样的方法，以损失完备性为代价提高 算法的执行效率( o y e r m a r s ，1 9 9 2 ，l i n d e m a l l i l ，2 0 0 4 ) 。 随机路径规划器1 9 9 0 年，b 删u a n d 和l a t o m b e 设计一种随机路径规 划器( r p p ) ( b a r r a q u a n d ，1 9 9 q ) 被认为是基于随机采样的运动规划的开端 ( l i n d e m 觚n ，2 0 0 4 ) 。该算法在人工势场法的基础上通过执行随机步骤使其摆 脱局部极小。定义h ( v ) 代表吸引势和排斥势合成的启发式势函数( 从某节点至目 标点的费用估计) 。对于r p p 规划器来说，定义三种模式：d e s c e n d ，e s c a p e 和b a c k t r a c k 。最初时，规划器处于d e s c e n d 模式，从v i i l i t 开始按照梯度 下降的原则产生新节点。在d e s c e n d 模式下，在图g 中产生一个新节点v 。， 在v 。的邻域内且使得h ( v ) 最小的方向上产生一个新节点v n 作为规划的下一个节 点，如果陷入局部极小，通过梯度下降产生新节点的操作会失败。此时，规划 器转入e s c a p e 模式，试图摆脱局部极小。在e s c a p e 模式下，执行一个随机 步骤创建新节点，结束后转向d e s c e n d 模式。如果在e s c a p e 模式下，一定 步数内，连续随机产生新节点失败，规划器将转入b a c k t r a c k 模式。在此 模式下，在图g 中，从上次产生的最新节点到图g 的起始节点之间随机选择一 个节点，从该节点开始规划器进入e s c a p e 模式。该算法( l a v a i l e ，2 0 0 4 ) 在 陷入局部极小时通过执行随机步骤能有效地克服局部极小的限制，能解决高维 自由度机器入的规划问题，但是该算法的正确运行需要调整很多参数，如果部 第l 章绪论 分参数设置不当，容易导致算法陷入局部极小，如果次数太多，也极大地影响 算法性能。 概率路标算法 自1 9 9 4 年开始，l y d i ak a v m k i 和j e a n c l a u d el a t o m b e 发 表了一系列在位姿空间中随机采样进行预处理的快速路径规划算法，即概率路 标算法( p r m ) ( k a v r a k i ，1 9 9 4 ，k a v r a 嵇，2 0 0 4 ) 。其主要思想是用一个随机路 标图来表示机器人系统运行的自由空间g 切然后在此图中为机器人系统搜索到 一条可行的路径，它是一个多重查询算法。这一随机路标图即是为机器人系统 所建立的地图，该网络中节点代表在c ，胁中为机器人随机选取的位姿节点之间 的连线，即图中的边，代表机器人不同位姿之间的可行路径。p r m 算法因为在 处理狭窄通道处的完备性太差等缺陷，很多学者对其进行改进，产生很多变种， 如m a p i t m ( w i l m a i t h ，l9 9 9 ) ，o b p i 己m ( a m a t o ，l9 9 8 ) ，l a z y - p r m ( b o i d i n ， 2 0 0 0 ) ，v i s i b i l 畸p r m ( n i s s o u x ，2 0 0 0 ) 等等。该算法在动态障碍物、高维状 态空间的环境中的运动规划已经得到广泛的应用( h s u ，1 9 9 9 ) ，但该算法未能 解决移动机器人运动中存在微分约束等问题，导致其结果路径合理性较差 ( l a v a j l e ，2 0 0 4 ) 。 膨胀空间法d h s u 和j c l a t o m b e 等( 1 9 9 9 ) 介绍了一种用于扩展姿态 空间的单一查询规划算法一膨胀空间法( e s t ， e x p a n s i v es p a c e s ) 。e s t 规 划器从初始节点开始生成一棵树，树中每一个节点x 有相应的权值，被定义成 n d ( x ) ，表示以节点x 为中心，d 为半径的邻域内顶点的数目。在每一次迭代过 程中，该树以一定的概率选择一个节点进行扩展。节点x 被选中的概率是l v ( x ) ， w ( x ) 代表权函数。对于给定的节点x ，在其邻域n “x ) 内有k 个节点被采样到， 这样每一个节点的权函数就可以计算出来。每一个新节点y 以概率l w ( x ) 被保 持，并且规划器会试图将每一个被保持的节点连接到x 。这样，该算法试图将 搜索树扩展到自由空间中未被探测到的区域。主要的缺点在于算法需要d 和k 参数，在不同的环境中，对它们的选择受主观因素影响较大( 跏r a l ( i ，1 9 9 6 ) 。 快速随机搜索树算法1 9 9 8 年美国伊利诺斯大学i u c ) 的科学家s ，m l a v a l l e 在最优控制理论、非完整规划和随机路径规划的基础上提出了一种单一 查询的快速随机搜索树算法( i 乇r t ) ( la _ v a l l e ，2 0 0 4 ) 。基本王凇算法是一种增量 式前向搜索算法。为了提高算法的效率和性能，不断对该算法进行改进。如为 了提高搜索效率采用双向搜索树( b i 姗( l a v a l l e ，2 0 0 0 ) ，从起始点和目标点 并行生成两棵i 沁，直至两棵树相遇，算法收敛；i 汕胁e r 和l a v a l l e 又提出 i 冰t - c o l l n e c t ( 2 0 0 0 ) ，使得节点的扩展效率大大提高；运动规划中，距离的定 义非常复杂，p e n gc h e n g ( 2 0 0 1 ) 研究了在耻汀生长过程中距离函数不断学习 的算法以降低距离函数对环境的敏感性；考虑到基本i 凇规划器得到的路径长 9 第1 章绪论 度一般是最优路径的1 3 1 5 倍，英国的j d es m i t h ( 2 0 0 3 ) 研究了变分法技术 使其达到最优。该算法在动态障碍物、高维状态空间和存在运动学、动力学等 微分约束的环境中的运动规划已经得到广泛的应用( u 肌s o n ，2 0 0 2 ) 。 1 3 4 其他智能化规划方法 路径规划是环境模型和搜索算法相结合的一种技术，规划过程既是搜索的 过程，也是推理的过程。人工智能中的很多优化、推理技术也被运用到移动机 器人运动规划中来，如遗传算法、模糊推理以及神经网络等在移动机器人运动 规划中起到很大的作用( 张颖，2 0 0 3 ) 。 遗传算法规划器遗传算法求解路径规划问题是将路径个体表达为路径中 的一系列中途点，并转换为二进制串。首先初始化路径群体，然后进行遗传操 作，如选择、交叉、复制、变异。经过若干代的进化以后，停止进化，输出当 前最优个体作为路径下一个节点。该算法的优点是，路径可以收敛到全局最优 或者近似最优：缺点是进化速度难以控制，难以满足实时需要，需要的经验参 数太多，不利于自动处理。 模糊规划器模糊逻辑( z a d e h ，1 9 6 5 ) 运用近似自然语言方式，可以很好 地处理数据的不确定性和非精确性，克服噪声和误差，实现输入输出之间的映 射关系。模糊规划器利用反射式导航机制( h o w a 帕，2 0 0 1 ，b a g c h i ，1 9 9 2 ) ，将 当前环境障碍信息作为模糊推理机的输入，推理机输出机器人期望的转向角和 速度等。该方法在环境未知或发生变化的情况下，能够快速而准确地规划机器 人局部路径，对于要求有较少路径规划时间的机器人是一种很好的导航方法。 但是，其缺点是当障碍物数目增加时，该方法的计算量较大，影响规划结果， 而且该规划器只利用局部信息作出快速反应，较容易陷入局部极小。 神经网络规划器近年来，科学家一直致力于将机器学习的技术运用到机 器人中来( b r o o k s ，1 9 9 1 ) ，或者说致力于依靠智能机器入技术来推动机器学习 的发展，事实上，它们是密不可分的。神经网络在机器导航中曾经取得过辉煌 的成就( s u k t h a n k a r ，1 9 9 3 ，b a t a v i a ，1 9 9 6 ) ，在机器人运动规划中也有大量的 研究成果( j a n g l o v ，2 0 0 4 ，刘成良，2 0 0 1 ) 。其基本原理是将环境障碍等作为神 经网络的输入层信息，经由神经网络并行处理，神经网络输出层输出期望的转 向角和速度等，引导机器人避障行驶，直至到达目的地。优点是并行处理效率 高，具有学习功能，能收敛到最优路径。 这些智能化推理方法与基于几何构造的方法类似，随着机器人自由度的增 加和环境复杂度增强，都存在效率问题。 1 0 第l 章绪论 1 4 主要研究内容 随着步行机器人的广泛应用和应用水平的提高，如何控制步行机器人使其 具有复杂的技能，这仍然是一个挑战，比如在r 0 b o c u p 中。如何使机器人能够 像入样连续带球，这不仅需要对机器人腿部的运动控制，对机器人自身运动 也需要精确的控制，还需要对机器人运动做出规划。由于受机器人自身传感器 的限制，机器人往往只能获得局部的环境信息，并且在动态环境中。无论是室 内机器人还是室外机器人，通常都很难获得精确的自身定位信息，如对于室外 机器人而言，g p s 信号的精度往往是有限的，传统的运动规划和控制方法在这 种情况下很难适用。 使机器人更加智能是研究的目标，从行为主义的观点看，机器人能越好的 完成复杂的任务，掌握了更加复杂的技能，意为者机器人具有更高的智能。对 于移动机器人而言，运动规划和控制方面的智能是最基本，也是最核心的问题 之一。本文以r 0 b o c u p 四腿组为背景，对如下问题展开了研究： 1 提出一种新的四足机器人里程计计算方法，该方法通过对机器人腿部 建立参数化模型，以实际运动特征优化模型，大幅提高了四足机器人的里程计 精度。 2 在机器人定位误差很大环境噪声很高的情况下作者提出一种基于 里程计的运动规划方法，利用a 奉算法搜索出机器人的参考运动轨迹，将机器人 运动约束融入到a 算法搜索过程中，使得该方法能满足路径末端机器人的位姿 限制。 3 由于四足机器人复杂的动力学特性，传统的控制方法难于实现 ( b i i o d e a u ，1 9 9 8 ) ，提出一种基于模型的运动控制方法。 4 设计一种适合完成复杂任务的自主机器人控制框架，该框架中使用卡 尔曼滤波器融合视觉传感器信息和自身关节传感器的信息，能够实现对四足机 器人的精确控制。并在r 0 b o c u p 四腿组平台上，使用该方法成功的实现了动态 的带球，这也是整个r o b o c u p 四腿组内的首次实现。 第2 章m b 0 里程计计算方法 第2 章船o 里程计计算方法 这一章将介绍一种四足机器人的里程计计算方法，我们把它称作m b o ( 丛o d e l 旦凼e dq d o m e t r y ) 方法。m b o 方法首先建立参数化的腿部物理模型， 这些参数用来反应机器人行走的物理特性，比如打滑等，然后通过机器人实际的 行走数据优化模型参数，基于得到的能实际反应机器人行走情况的参数化模型， m b o 方法通过机器人腿部的运动轨迹分析得到机器人的里程计信息。在舭b o 的实验表明，m b o 方法的误差仅为现有的方法的5 0 ，并且标定的复杂度也大 幅度降低。 这一章按如下组织：首先是前言，将对m b o 方法做整体性的概述和介绍， 接下来介绍m b o 方法的原理，解释a i b o 平台上的腿部参数化模型以及如何优 化该模型。第四小节将进一步讨论m b 0 方法的关键点，第五小节讨论如何从机 器人的腿部运动轨迹中分析得到机器人的里程计。第六小节将展示实验和分析实 验结果，最后是小结本章。 2 1 引言 在第一章中已经提到已有的关于四组机器人的里程计工作，这些工作可以被 分为两类：一类是基于寻找一种直接映射关系的方法，通过寻找行走命令和实际 速度的映射关系来计算和标定里程计，这类方法可以称为“直接标定法 ；另一 类方法是基于本体感受( p r o 面o c e p t i o n ) 的，我们称这类方法为“间接标定法。 直接标定法需要建立一种映射关系，而行走命令和实际速度均在一个三维的 空间中，所以不可避免的需要标定这个舀标空间的很多点，标定复杂度都比较高， 另一方面，机器人的运动状态改变是连续的，而这种映射关系是建立在离散空间 上的，所以精度不能很好的保证。 间接标定法使用传感器信息，而类似于码盘的关节传感器是能以非常高的频 率工作的，通常能提供连续的本体状态，能够避免直接标定法的缺点。 针对四足机器人里程计计算和标定问题，本章提出一个叫做m b o ( 丛o d e l 坦a s e dq d o m e t 巧) 的方法。m b o 首先根据机器人腿部形状，设定一个 描述腿部物理形状特性的参数化模型，由机器入的实际行走特性优化腿部模型。 基于这个优化的腿部模型，根据正运动学计算出腿部运动的轨迹，通过分析腿部 运动轨迹获取里程计。 m b o 方法通过观察腿部的运动状态获得里程计，这样反应的是实时的机器 人运动状态，机器人的加速( 减速) 过程能够在里程计中体现。m b o 方法的精 1 2 第2 章m b 0 里程计计算方法 度取决于腿部模型，标定过程就是优化腿部模型的过程。m b o 方法的标定复杂 度较低，只需标定1 2 个左右的行走命令即可完成整个行走命令空间的标定。 m b 0 在a i b oe r s 7 1 上实现并实验，实验表明，m b o 获取的里程计精度较 现有方法有2 - 4 倍的提高。 2