（精密仪器及机械专业论文）多机器人编队的运动规则.pdf

摘要 摘要 在过去二十年内，多机器人系统在诸多应用领域中受到了广泛关注，如机械 制造，监控巡逻，空间探索等领域的应用。在许多实际应用中，要求机器人组成 并保持特殊的队形以完成复杂的任务，如大型货物物体的搬运，地图探测，目标 搜寻，和营救任务。在多机器人编队研究中，运动规划是一个重要的问题，其必 然受到多机器人编队的各种几何运动约束。 首先，为了解决在动态环境和有限环境信息下的编队问题，我们提出了一种 分布式的多机器人运动规划方法。我们设计了一种改进式的随机生成树路径规划 器，该路径规划器将对每个机器人进行在线的运动规划。当机器人到达编队目标 位置时，机器人之间会互相制约产生运动冲突或矛盾。具体来讲，就是先到达编 队理想位置的机器人可能会阻碍其他机器人到达预定目标。这种运动上的冲突和 矛盾可能会造成机器人到达目标位置时的运行混乱甚至卡死现象。为了克服这种 冲突矛盾，我们提出了一种动态优先级的策略，用以规范组成编队时的次序。并 且，为了验证所提出的各种方法，我们在一组移动式机器人上进行了仿真和实验。 实验的结果证实了所提出的新路径规划器可有效地实时更新每个机器人的运动 规划，而通过将动态优先级策略嵌入至运动规划方法中，可以更快速有效的完成 编队组成的问题。 其次，在此文中，我们进一步讨论和解决了多移动式机器人在设定路线上的 编队运动规划问题。在这个问题中，机器人不仅要求沿着设定路线前进，而且， 在运动过程中需要完成一些编队任务。通过将运动规划中的编队关系建模为速度 的函数，我们将此运动规划问题转化为一个速度优化问题。另外，为了使规划的 速度曲线符合机器人的运动规律，我们还考虑了机器人的速度和加速度的边界约 束。我们将描述的编队关系进行综合并考虑各种速度约束，最终建立了以维持编 队关系为目标的优化函数。通过使用非线性规划器l i n g o ，我们可以离线地得到 了该速度优化的结果。为了能解决一些突发情况，如对一些运动物体进行壁障， 我们提出一种策略来在线调整所得的优化结果。在策略中，当有移动障碍物靠近 机器人编队时，机器人需要对其产生判断和响应，包括停止运行或者沿原运动规 划进行倒退。机器人在壁障之后，仍然能按照原来的运动规划继续运行。为了证 实此方法的有效性，我们用一组机器人进行了仿真和实验。 本论文对多机器人的编队运动规划方法进行了研究，提出了新的方法并予以 证实。现有文献中较少涉及到此类方法内容。此研究结果将会对机器人领域尤其 是近年来的多机器人编队研究做出贡献。 摘要 关键词：多机器人编队机器人路径规划速度优化优先级策略 a b s t r a c t a b s t r a c t o v e rt h ep a s tf e wd e c a d e s ，m u l t i r o b o ts y s t e m sh a v eb e e ns t u d i e dc o n s i d e r a b l y , d u e t ot h e i rw i d ea p p l i c a t i o n si ns u c hf i e l d sa sm a n u f a c t u r i n g ，s u r v e i l l a n c e ，a n ds p a c e e x p l o r a t i o n i nm a n ya p p l i c a t i o n s ，r o b o t sm u s tf o r ma n dm a i n t a i nf o r m a t i o n st o a c c o m p l i s hs u c hc o m p l e xt a s k sa st r a n s p o r t a t i o no fl a r g ea w k w a r do b j e c t s ，m a p p i n g ， s e a r c h ，a n dr e s c u e m o t i o np l a n n i n g ，w h i c hi so n eo ft h em o s ti m p o r t a n ti s s u e si n m u l t i r o b o tf o r m a t i o n s ，i ss i g n i f i c a n t l ya f f e c t e db yt h eg e o m e t r i c a lc o n s t r a i n t so ft h e f o r m a t i o n s t h i st h e s i sa i m st od e v e l o pas e to fn e wm o t i o np l a n n i n gm e t h o d o l o g i e sf o r m u l t i p l em o b i l er o b o t si nf o r m a t i o n - f o r m i n ga n df o r m a t i o n - m a i n t a i n i n gt a s k s s t u d i e s h a v eb e e np e r f o r m e dm a i n l yi nt h ef o l l o w i n gt w o c a t e g o r i e s f i r s t ，ad e c e n t r a l i z e dm u l t i r o b o tm o t i o np l a n n i n gf r a m e w o r ki sd e v e l o p e dt os o l v e t h ef o r m a t i o n - f o r m i n gp r o b l e mi nad y n a m i ce n v i r o n m e n t 、析ml i m i t e de n v i r o n m e n t i n f o r m a t i o n a ni m p r o v e dr r t ( r a p i d l y - e x p l o r i n gr a n d o mt r e e s ) b a s e dp a t h p l a n n e ri sd e s i g n e dt ou p d a t et h em o t i o np l a n n i n gf o re a c hr o b o to n l i n e w h e nr o b o t s e n t e rt h et a r g e tf o r m a t i o n ，t h e ym a yc o n s t r a i ne a c ho t h e r ：t h er o b o tf i r s ta r r i v i n ga tt h e d e s i r e dp o s i t i o ni nt h ef o r m a t i o nm a yb l o c kt h eo t h e rr o b o t sf r o me n t e r i n gt h e f o r m a t i o n t h i st h e s i sr e f e r st ot h i s s i t u a t i o n a sm o t i o nc o n f l i c ti n t h e f o r m a t i o n - f o r m i n gp r o b l e m s u c hc o n f l i c tm a yc a u s ed i s o r d e ra m o n gt h er o b o t so r e v e nd e a d l o c kt h e mw h e nt h e ye n t e rt h ef o r m a t i o n t oo v e r c o m et h i sp r o b l e m ，a d y n a m i cp r i o r i t ys t r a t e g yi sp r o p o s e dt or e g u l a t et h ef o r m a t i o n f o r m i n ga c t i o ni n p r o p e ro r d e r s i m u l a t i o n sa n de x p e r i m e n t sw e r ep e r f o r m e do nag r o u po fm o b i l e r o b o t s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e dn e wp a t hp l a n n e rc a n e f f e c t i v e l yu p d a t em o t i o np l a n n i n gf o re a c hr o b o to n l i n e b ya d d i n gad y n a m i c p r i o r i t ys t r a t e g y t ot h ed e c e n t r a l i z e dm o t i o n p l a n n i n g f r a m e w o r k ，t h e f o r m a t i o n f o r m i n gg o a lc a nb ea c h i e v e de f f i c i e n t l y s e c o n d ，t h i st h e s i sa d d r e s s e st h ec o o r d i n a t e dm o t i o np l a n n i n gp r o b l e mo fm u l t i p l e m o b i l er o b o t sm o v i n ga l o n gd e s i g n e dp a t h sw h i l em e e t i n gf o r m a t i o nr e q u i r e m e n t s t h i sp r o b l e mi sf o r m u l a t e da sav e l o c i t yo p t i m i z a t i o np r o b l e m ，a f t e rm o d e l l i n gt h e f o r m a t i o nr e l a t i o n s h i pt ob ev e l o c i t y - d e p e n d e n t t h ev e l o c i t ya n da c c e l e r a t i o nb o u n d s a r ec o n s i d e r e ds ot h a tt h eg e n e r a t e dv e l o c i t yp r o f i l ef o re a c hr o b o ti sd y n a m i c a l l y f e a s i b l e a no b j e c t i v ef u n c t i o ni se s t a b l i s h e dt oi n t e g r a t ea l lt h ec o o r d i n a t i o n i i i a b s t r a c t r e q u i r e m e n t sw i t ht h eg o a lo fv e l o c i t yo p t i m i z a t i o n ，s u b j e c tt ov a r i o u sv e l o c i t y c o n s t r a i n t s al i n e a ri n t e r a c t i v ea n dg e n e r a lo p t i m i z e r ( l i n g o ) i su s e dt oo b t a i na n o p t i m a lm o t i o np l a no f f l i n e t h i sp l a nc a nb ef u r t h e ra d j u s t e do n l i n et od e a lw i t h s o m ee m e r g e n tc a s e s ，s u c ha sa v o i d i n ga s u d d e n l ya p p e a r i n gm o v i n go b s t a c l et h a ti s d i f f i c u l tt op r e d i c t w h e nt h em o v i n go b s t a c l eg e t sc l o s ee n o u g ht ot h er o b o tg r o u p ， t h er o b o t sn e e dt or e s p o n db ye i t h e rs t o p p i n gt ol e tt h eo b s t a c l ep a s so rr e t r e a t i n g a l o n gt h ep r e v i o u sm o v i n gt r a j e c t o r i e s as t r a t e g yi sd e v e l o p e dt og u i d et h er o b o t st o r e s u m et h e o r i g i n a lm o t i o np l a na f t e rc o l l i s i o na v o i d a n c e s i m u l a t i o n sa n d e x p e r i m e n t sw e r ep e r f o r m e do nag r o u po fm o b i l er o b o t st ov e r i f yt h ee f f e c t i v e n e s so f t h ep r o p o s e da p p r o a c h t h i sr e s e a r c hp r o v i d e sap r o o f - o f - c o n c e p td e m o n s t r a t i o no fn e wa n di n n o v a t i v e m o t i o np l a n n i n gm e t h o d o l o g i e sf o rm u l t i p l er o b o t si nf o r m a t i o n s f e ws t u d i e sh a v e b e e nr e p o r t e di nt h el i t e r a t u r er e g a r d i n gt h i st o p i c t h er e s e a r c ho u t c o m e sw i l lb e n e f i t t h er o b o t i c s s o c i e t y , e s p e c i a l l y f o ri n f r a s t r u c t u r en e t w o r k st h a th a v er e c e i v e d c o n s i d e r a b l ea t t e n t i o ni nr e c e n ty e a r s k e yw o r d s ：m u l t i - r o b o tf o r m a t i o n s ，m o b i l er o b o tp a t h p l a n n i n g ，v e l o c i t y o p t i m i z a t i o n ，p r i o r i t ys t r a t e g y i v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：埘 签字日期：! 塑：竺：三! 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 导师签名：堡止 签字日期：丝! ! ：? ：!签字日期：丝! ! ：! ：兰 第1 章绪论 1 1 背景 第1 章绪论 多机器人系统对于许多实际问题提供了独特的解决方法。自主式多机器人系 统可以在众多领域中完成各种协作任务，如工业制造，监控巡逻，空间探索等领 域。在许多的多机器人系统应用中，机器人需要组成特殊的编队来完成诸如大型 物件搬运，定位制图，搜索和营救等工作。图11 展示了一组多机器人协同捕获 任务，其中，一些机器人“追赶者”( p u r s u e r s ) 正在试图捕获一组机器人“入 侵者”( e v a d e r s ) ，而任务的活动范固被设定在一个有边界的位置环境中 1 。图 l 2 所展示的则是另一个例子其中，在一个三维的复杂环境中有一组移动式 机器人通过互相协作来完成运输任务 2 。在这些任务中，由于使用多机器人协 作的方法，使得任务的柔韧性与容错性都得到大大提高。 机器人编队研究中最重要的问题之一便是的运动规划。在运动规划中编队 的几何约柬将被引入到机器人的轨迹规划中。机器人编队的运动规划方法也因为 任务的不同而不同，比如，编队责任的分配，编队的组成方法，编队形状的维持 方法，和编队阵型的变换等。现有文献中的运动规划方法则考虑给机器人分配特 定的起点终点，或者仅设定机器人之间的关系，或者考虑区域的覆盖控制问题 ( c o v e r a g ec o n t r 0 1 ) 。 第l 章绪论 凹ll l v u g v 追击八侵者任务( i r s u l te v a s i o ng a m e ) 图12 三维复杂环境f 多机器人协同搬运 1 2 问题阐述 本篇论文对多机器人编队组成的运动规划做了深入研究。在该问题中，每个 机器人仅能感知其周围的局部信息，而其他机器人的运动规划也并不知晓。这就 要求每个机器人都能根据其周围的局部环境，目标的位置和周围机器人位置进行 自我规划。图1 3 展示这样一个例子其中一组机器人被设置于包含有障碍物的 复杂环境中，机器人仅能感知其周围的局部信息。运动规划的目标是为每个机器 人规划运动轨迹，并且使其能顺利的移动至目标位置从而组成所要求的编队形 状。 第1 章绪论 图1 3 多机器人编队组成的运动规划问题 首先，为了解决多机器人编队组成的运动规划问题，我们要求每个机器人能 根据其局部环境信息，目标位置和周围机器人位置，对各自的路径进行规划。现 有的机器人编队路径规划方法多是根据所有机器人的编队信息进行规划的，这就 必须要求已知所有机器人的运动规划，因此不能直接应用于此。一些基于行为的 方法( b e h a v i o r b a s e d ) 和一些群体机器人( s w a r mr o b o t ) 的方法则强调机器 人在群体中的关系而没有特定的编队目标。在仅使用局部信息的情况下，最为可 行的方法是基于传感器( s e n s o r - b a s e d ) 的运动规划方法。在典型的基于传感器 的方法中，机器人仅仅根据传感器所提供的信息进行判断，而机器人之间没有相 互通讯交流。这些机器人根据某种特定的交通规则( t r a f f i cr u l e s ) 或启发式 的策略方法来进行协调和壁障然而，此类方法过多依赖于传感器系统和复杂的 启发式策略，而很难应用于编队的特殊任务上。在某种意义上来说，多机器人运 动规划是单机器人动态运动规划的延伸。换句话说，对于每个机器人而言，都相 当于一个动态运动规划问题。现有的机器人动态运动规划方法可以处理动态环境 下的规划问题，但是多数要求已知运动障碍物的完整轨迹，也就是要求了解其他 机器人的运动轨迹。由于在本文中，机器人仅能感知周围机器人的位置信息而不 知道其具体的轨迹，所以这类动态运动规划方法都不能应用在本文的问题中。因 此，我们需要一种可以做出快速反应的路径规划器，并可以在机器人运动过程中 3 第1 章绪论 不断根据变化的环境来更新路径。 第二，为了组成目标编队，机器人必须进行相互协调。一种常见的多机器人 协调壁障的方法就是给每个机器人分配优先级，然后根据设定的优先级对机器人 的速度进行调节来互相协调壁障。然而，多数现有的优先级策略多是静态的 3 ， 即在运动开始前分配好优先级而这些优先级在运动过程中保持不变。此类静态优 先级( s t a t i cp r i o r i t y ) 策略都是基于全局环境信息已知的条件下的。另一方 面，目前普遍可以接受的关点是，优先级应根据实际情况进行动态分配。在文献 4 中，有作者提出了一种动态优先级方法。每个机器人根据其所在空间的拥挤 程度来决定自身的优先级，即机器人所处空间越拥挤其优先级会变的越高，进而 达到壁障和提高运动规划效率的目的。这种动态优先级策略并不需要其他机器人 的运动轨迹，而仅仅要求机器人在互相靠近时能交换优先级信息，因而可适用于 本文所提问题。不同于文献 4 的是，在我们的研究中，当机器人接近其编队目 标位置时可能会出现运动混乱甚至卡死现象。就其原因主要是，先到达编队位置 的机器人可能将其他机器人的路径堵塞，使得其他的机器人不得不重新规划路径 而造成混乱和卡死。因此，我们需要一种新的动态优先级策略来完成机器人编队 组成问题。 第三，本文对多机器人编队在设定路径上的优化运动问题也做了研究。该问 题在很多应用中有中具有重要意义，如大型物体的搬运等。尤其在任务需要反复 重复或资源受限的情况下，运动的优化性更为重要。在文献e 5 3 中，该作者提出 了一种同步控制( s y n c h r o n i z a t i o nc o n t r 0 1 ) 的方法来解决类似的问题。然而， 文献中各个机器人的最优轨迹已知，该方法只是解决了如何沿着最优轨迹运行的 问题。在文献 6 中，多机器人运动规划被建模为一个整数混合非线性规划问题。 在文献 7 中，该问题又被进一步扩展，并且考虑了通讯约束。然而，现有方法 的优化目标多为减少任务完成时间，壁障，和保持通讯联络等，而没有考虑编队 需求。因此，我们需要一种包含维持编队阵型的最优运动规划方法。 1 3 研究目标 博士论文工作的研究目标如下： 1 ) 提出一种新的高效路径规划器 为使各个机器人能穿过复杂的未知环境移动到各自的目标位置，本文提出了 一种有效的路径规划器。因为机器人运行过程中只可以获知其局部信息，所以该 路径规划器必须能够实时更新机器人的路径。并且，该规划器所生成的路径必须 4 第1 章绪论 能应用于移动式机器人。 2 ) 提出一种新的动态优先级策略 本文将提出一种新的动态优先级策略用以协调多机器人的编队任务。该策略 需要根据编队任务的具体情况来动态计算机器人的优先级，使得编队任务能顺利 进行并时间最短，并且无碰撞和卡死产生。 3 ) 在设定路径上的多机器人编队的优化运动 当机器人沿着设定路径运行以完成机器人编队任务时，应优化其速度曲线， 使其能最好的维持编队阵列，完成编队任务。 4 ) 在实验中证明所提方法 我们将在实验室环境下使用三台轮式移动机器人进行实验，证明所提出运动 规划方法的有效性，包括编队组成任务和设定路径下的运动规划。 1 4 方法论及其意义 我们提出以下方法用来解决以上提出的问题 1 4 1 提出一种改进式的基于r r t ( r a p i d l ye x p l o r i n gr a n d o mt r e e s ， 快速生成树) 的路径规划器 由于机器人编队全局信息未知，并且只有局部环境信息已知，我们采用分布 式运动规划方法。该方法中，每个机器人独自规划运动路径并调节速度来避免可 能的冲突矛盾。 我们根据快速随机生成树( r r t ) 算法设计了一种高效的路径规划器。快速 随机生成树算法可以简单，快速地探索高维构型空间，并且具有随机完整性 ( p r o b a b i l i s t i c a l l yc o m p l e t e ) 。该算法可很好的应用于移动式机器人路径规 划中。然而，多数基于随机生成树的路径规划器仅仅考虑点机器人( p o i n tr o b o t ) 模型来生成路径，并需要进一步平滑才能使用。本文对基本的快速随机生成树路 径规划器进行改进，通过在路径生成过程中考虑机器人的运动学约束使得生成的 路径更加平滑。该改进方法可嵌入到其他快速随机生成树路径规划器的改进算法 中，从而得到更有效的方法。为了减少完成时间和避免互相碰撞，机器人根据其 于目标点的距离和与其他机器人的距离来调节速度。 1 4 2 用于编队组成的动态优先级策略 第1 章绪论 为了完成编队组成任务，我们进一步提出一种有效的动态优先级策略。优先 级策略在多机器人路径规划领域非常常见。现有的优先级策略多为静态优先级策 略，并基于机器人编队的全局信息。在本文，机器人编队全局信息未知，而每个 机器人只能局部地感知周围机器人的位置信息。因此，在我们所提出的动态优先 级策略中，每个机器人需要根据其局部信息不断的计算优先级并通知周围的机器 人。该策略并不需要了解其他机器人的运动轨迹，而只需要机器人彼此靠近时能 交换优先级信息。 在没有机器人编队的运动信息的情况下，机器人在其接近目标编队位置时可 能产生运动混乱甚至卡死，即首先到达编队期望目标位置的机器人可能会阻碍其 他机器人的路径，导致很多机器人必须重新规划路径从而造成混乱。本文研究分 析了该矛盾冲突，并将所有此类冲突表述为一个矛盾冲突图( c o n f l i c tn e t ) 。 通过研究此矛盾冲突图的特点，我们发现应该将其中一些机器人设定较高的优先 级使得其不会阻碍其他机器人到达目标编队位置。借助此矛盾冲突图我们提出了 一种新颖的优先级计算方法。根据该优先级计算方法，机器人调节其速度来协同 完成编队组成的任务。 1 4 3 通过速度优化对多机器人编队运动进行规划 作为多机器人编队组成问题的延伸，我们进一步解决了多机器人在设定路径 上的运动规划问题。在该问题中，我们必须为每个机器人设计优化速度曲线，使 机器人能沿着设定路径以维持要求的编队阵型，并避免与任何障碍物碰撞。 我们将此问题转化为一个速度优化问题，其中的编队约束被建模为速度的函 数。在速度优化中，我们考虑了速度和加速度的边界约束，从而产生实际可行的 速度曲线。我们建立了一个优化函数以表示该编队约束和速度边界约束。之后， 使用优化器l i n g o e s 对该速度优化问题进行求解，最终得到优化的速度曲线。该 运动规划可进一步在线调节以应付突发情况，比如躲避未能预先得知的移动障碍 物。当移动障碍物靠近机器人编队时，机器人应做出相应响应，如立刻停止运行 等待障碍物通过或者沿着运行轨迹逆行以躲避障碍物。我们进一步提出方法使机 器人能在避障后继续沿着原运动规划运行。 以上方法的重要意义如下： 1 ) 通过使用所提出的高效路径规划器，编队组成可在未知环境中进行。并且， 所生成的路径比一般随机生成树路径规划器的平滑。 2 ) 通过使用所提出的动态优先级策略，在机器人接近目标编队位置时可以得到 一个适当的顺序。从而，缩短了任务完成时间并且避免了卡死现象。 6 第1 章绪论 3 ) 通过对速度进行优化，机器人可在设定路径下维持编队，并在不同编队阵型 之间变化。通过所提出饿在线调整方法，机器人编队可躲避未知的移动障碍物。 1 5 结论 本章讨论了机器人编队运动规划的研究背景，研究目标及我们所提出的方 法。研究的重点集中在发展一种新的多机器人编队组成的运动规划方法。我们提 出一种分布式多机器人路径规划方法，该方法仅利用局部信息来完成复杂环境中 的编队组成问题。我们还提出了一种改进式的快速随机生成树路径规划器来更新 每个机器人的运动轨迹。另外，我们研究了编队组成任务中的运动约束，并针对 其中多机器人之间的运动冲突提出一种动态优先级策略，从而使多机器人在组成 编队时获得一个适当的顺序。作为该问题的延伸，我们进一步研究了多机器人在 设定路径上的编队运动优化问题。最终我们在实验室环境下进行了机器人实验来 验证所提出方法的有效性。 本文的其他内容如下：第二章将对现有多机器人运动规划方法进行回顾。第 三章，我们将展示分布式的多机器人运动规划方法，然后，在第四章，我们会介 绍多机器人编队组成中的动态优先级策略。第五章介绍了多机器人编队在设定路 径上的优化运动问题。最终，我们给出本文的结论和未来工作。 7 第2 章国内外研究现状 第2 章国内外研究现状 随着分布式机器人系统的研究发展，多机器人系统越来越多的方面得到拓 展。它的研究领域可分为：与生物学有关的研究( b i o l o g i c a li n s p i r a t i o n ) ， 通讯问题，体系结构问题，定位和制图，探索问题，物体搬运，工业制造，运动 协调，和重构机器人( r e c o n f i g u r a t i o nr o b o t s ) 9 - 1 7 。其中最热门的研究内 容之一便是运动协调问题。该领域已得到充分的拓展，包括多机器人路径规划 1 8 ，交通控制( t r a f f i cc o n t r 0 1 ) 1 9 ，编队生成 2 0 - 2 2 ，和编队维持 2 3 - 2 4 。 本章文献调研主要对多机器人运动规划做进一步总结。 文献调研工作将按如下组织：将现存的多机器人系统运动规划方法分为耦合 式和解耦式的方法( c o u p l e do rd e c o u p l e d ) ，而解耦式方法又可进步分为基 于集中式构架的解耦式方法和基于分布式构架的解耦式方法。其中本章的重点将 落在基于分布式构架的解耦式方法上，之后还将给出一些关于多机器人编队方法 的简单总结和快速随机生成树方法的介绍。 2 1 多机器人运动规划 现有的多机器人运动规划可分为两类，耦合式方法与解耦式方法( c o u p l e d o rd e c o u p l e d ) 2 5 2 6 。在耦合式方法中，各个独立机器人的构型空间被结合 为一个复合构型空间，然后在该复合空间内搜寻可行路径。相反，解耦式方法首 先为每个机器人设计路径然后再解决其可能产生的矛盾问题。 2 1 1 耦合式多机器人运动规划 在一个耦合式规划方法中，多机器人运动规划的解是从所有机器人的构型空间的 笛卡尔积中搜索得到的。通过将各个机器人的状态空间组合为一个复合系统的状 态空间，我们可以从中搜寻出一系列的状态变化。这一系列的状态变化可以使所 有机器人从其起点运动到终点。使用完整式搜寻算法，例如a 星算法【2 7 】，耦合 式方法可以得到完整解和最优解。 耦合式方法可依赖集中式构架，在这种构架结构中，存在一个中央规划器来 处理所有机器人的状态信息。这种方法便于将所有机器人信息融合，结构简单， 但是该类方法的主要局限在于高维空间搜索的复杂度会随着机器人的数量的增 加而剧增。直接使用a 星算法可以保证得到的解具有分辨率完整性 9 第2 章国内外研究现状 ( r e s o l u t i o n - c o m p l e t e ) 。然而，由于复合空间的尺寸随机器人数量增加而呈指数 上升【叭) 对于r 个机器人】，a 星算法的复杂度也将随之以指数上升而最终无 法计算。h o p c r o f i 等人也证明了一般的多机器人运动规划问题是p s p a c e 难度的 2 8 。因此，在实际应用中，使用者往往不得不使用一些启发式方法来应对如此 巨大的节点空间搜索问题。 为了解决这个复杂的问题，有些作者提出了一些方法，如人工势场法 2 9 】。 由于人工势场方法存在局部极值点的问题，很多学者对此提出了各种不同的解决 方法。在b a r r a q u a n d 的文章 3 0 1 中，该作者使用一种随机搜索的方法同人工势场 法进行结合，然后集中式地规划数个移动机器人路径。 另外，还有一类用来降低搜索空间大小的方法叫做随机路径方法 ( p r o b a b i l i s t i cr o a d m a p ) ，该方法通过在整个环境内生成随机路径以减少搜索空 间的大d x 3 1 3 3 】，这种基于随机路径的方法具有概率完整性( p r o b a b i l i s t i c a l l y c o m p l e t e ) ，即当规划时间足够长时，算法趋于完整。这种方法通常至多可用于5 个机器人的路径规划。 另外一种方法是将大的地图分解为数个子图，在子图之间进行路径规划，然 后再在子图内进行路径规划从而降低搜索难度【3 4 】。 2 1 2 解耦式多机器人规划 在解耦式多机器人规划方法中，路径规划器为每个机器人分别规划路径，而 非将其视为一个复合的整体来规划。解耦式规划方法可使用集中式的构架结构或 者分布式的( c e n t r a l i z e do rd e c e n t r a l i z e d ) 。在集中式构架结构中，存在一个中央 规划器，其负责每个机器人的路径规划，和分析每个机器人的信息。在分布式的 构架结构中，每个机器人都有一个运动规划器。机器人之间的信息可通过通讯或 者机器人网络 3 5 1 来进行共享和交换。分布式的构架结构不能整合全部机器人信 息但是计算的并行性非常容易实现。 2 1 2 1 基于集中式构架的多机器人解耦式运动规划 在基于集中式构架的多机器人解耦式运动规划中，规划处理器将问题解耦为 每个机器人寻找无碰路径的问题和调节机器人运行速度用以避障的问题 3 6 - 3 7 。此类方法被发展为“路径一速度 分解方法，即首先只考虑静态障碍物， 为每个机器人设计路径，然后调节各个机器人在其路径上的速度来避免机器人之 间的碰撞和躲避移动的障碍物。 一种较流行的解耦式方法是构建机器人的“时间一构型空间 ( c o n f i g u r a t i o n t i m e s p a c e ) 3 8 ，其构成方法是将时间信息加入到机器人状态中，即每一点状 1 0 第2 章国内外研究现状 态信息除了包含机器人位置和方向外还包括时间。由此时间一构型空间的概念衍 生出了一系列的规划方法，被统称为优先级规划方法( p r i o r i t i z e dp l a n n i n g ) 3 9 。此类方法首先分配给机器人优先级，然后按照次序在时间一构型空间中规 划每个机器人的路径。其中，先被规划的机器人路径存在于这个时间一构型空间 中，被其他机器人视为这个空间中的障碍物。 这种依次规划机器人路径的规划方法，引出了一个新的问题，就是按照怎样 的词语来规划机器人的路径，也就是如何分配优先级的问题。由此，产生了各种 不同的分配方式。文献 4 0 中的方法采用固定的优先级然后应用人工势场法在时 间一构型空间中搜索路径。在文献 1 8 描述的方法中也使用了固定的优先级并使 用随机绕路的方法让低优先级的机器人躲避高优先级的机器人。在文献 4 1 中， 该作者采用一种启发式的策略，尽量使得可以走直线运动的机器人的优先级高些 从而提高效率。在文献 4 2 中，该作者将所有的优先级分配方法全部考虑。由于 其复杂度限制，该方法仅限于不超过三个机器人的应用。在文献 4 3 中，该作者 具体就解耦式路径规划方法中的优先级分配做了讨论，并提出一种在优先级空间 中随机搜索的方法，从而，可以找到一个可行的优先级分配解和一个效果最好的 解。在文献 3 6 中，该作者使用一种全局评价指标来衡量不同优先级分配情况下 的机器人运动规划，然后选择最优的一个。 另外一种解耦式规划方法叫做路径协调方法( p a t hc o o r d i n a t i o n ) ，该方法 在文献 4 4 中被首先提出。在路径协调问题中，每个机器人的路径已预先设计好， 然后路径处理器通过协调机器人在其设定路径上的运动来避免碰撞 4 5 。其中， 机器人可以前进，停止或者后退。在文献 4 6 - 4 8 ，该作者采用协调表格的技术 ( c o o r d i n a t i o n - d i a g r a m ) 来解决路径协调方法。还有其他一些解决方法如下。 在文献 4 9 中，该问题被约束在随机路径上，通过靠每个机器人的优化指标进行 最优规划。文献 3 6 中的方法则利用全局衡量函数来评价机器人小组的运动状 态。在文献 6 中，路径协调问题被建模规划为一个整数混合非线性规划问题， 并使用数学优化器a m p l 5 0 和c p l e x 5 1 进行了求解。其他作者对路径协调问题 又进行了扩展，如考虑任务完成时间和通讯约束等 7 。 解耦式运动规划方法大大降低了多机器人运动规划的计算复杂度。然而，在 集中式构架结构中，所有的路径规划都在一个处理器上完成，所有计算量仍然会 随着机器人数量的增加而显著增加，因而较难实现计算的并行性。 2 1 2 2 分布式多机器人运动规划 在分布式多机器人路径规划中，不存在中央处理器，每个机器人必须独立完 成路径规划任务，并根据各自的局部信息进行判断 5 2 。分布式路径规划方法的 第2 章国内外研究现状 优势在于其计算复杂度与机器人数量无关，并且可更好地利用现有的单机器人运 动规划方法。但是由于没有集中的机器人信息，很难进行机器人之间的协调运行， 于是，存在各种用于机器人之间协调的方法。 一种分布式的运动规划方法是在运动协调时应用交通规则 1 9 。然而，该类 方法多要求环境被建模为路径网( r o u t en e t w o r k ) 的形式 5 3 ，并且机器人需 要通过通讯了解互相的运动来使用交通规则。 最纯粹的分布式规划方法是基于传感器信息的方法 5 4 - 5 5 3 ，这类方法完全 依靠传感器信息进行运动判断而不进行通讯。机器人的协调工作完全有机器人自 身来判断。这种方法通常使用迷宫搜索( m a z es e a r c h i n g ) 的方法 5 6 或者人工 势场法 5 7 来进行协调。 在多机器人运动中，如果将其他机器人看做为移动的障碍物，则多机器人运 动规划为题可退化为单机器人在动态环境下的运动规划问题，但是此问题本身仍 然是非常复杂的。此类方法也可根据其运动是否受限而划分，在文献 5 6 中，机 器人的运动没有受限，而在文献 5 7 3 中，机器人的运动限制在了与静态障碍物无 碰撞的路径上。而在文献 1 1 中介绍的方法则是将机器人的运动限制在了路径网 ( r o a d m a p ) 上。 许多分布式多机器人运动规划方法是由动态运动规划方法发展而来。在文献 5 8 ，该作者提出一种动态环境下的文时多机器人导航方法。作者使用了一种室 内i g p s ( i n d o o rg l o b a lp o s i t i o n i n gs y s t e m ) 对所有工作空间内的机器人和障 碍物的位置姿态信息进行在线检测和更新，利用这些信息，机器人的全局路径被 不断更新。 在文献 5 9 ，该作者提出一种基于已知信息的基因算法( k n o w l e d g eb a s e d g a ) 应用于动态环境下的运动规划。每一个机器人都使用基因算法而把其他机器 人视为突然出现或消失的障碍物。该基因算法使用一种简单而独特的路径表示方 法，并使用整数代替实数来表示每一个节点，其中障碍物可以为任意形状而非限 制在栅格之中。 文献 6 0 的作者则提出一种用于实时生成机器人路径的高效动态系统。该文 章将目标位置的距离信息传播在整个机器人工作空间，并且每一次都逐个栅格的 传播距离信息直到其到达机器人位置，该算法可以应对不断改变的环境，包括改 变的障碍物和移动的目标。该方法可以被利用来处理多机器人路劲该规划问题， 其中其他机器人被视为移动障碍物，而目标位置为固定位置。 在文献 6 1 中，该作者提出了一种基于人工势场法的多机器人路劲规划方 法。其他机器人不再被视为障碍物，而当两个机器人互相进入到传感器探测范围 时，机器人根据彼此的优先级进行协调。低优先级的机器人会停止前进等待高优 1 2 第2 章国内外研究现状 先级机器人通过，该方法简单并且不需要全局环境信息。 路径变形技术( p a t hd e f o r m a t i o n ) 可应用于动态环境的运动规划 6 2 - 6 3 。 机器人应用该技术对遇到的动态障碍物做出响应，并对已生成的路径进行实时变 形来适应动态环境的变化。 文献 6 4 提出一种利用相对速度解决动态运动规划的方法。该方法利用速度 转换，将动态的环境转化为静态，从而将问题简化为一个更容易处理的问题。其 工作被拓展为在机器人速度空间内建立明确的速度障碍物的方法。这类方法最初 限定障碍物为直线路径运行，后来发展为任意非直线路径运行 6 5 - 6 6 。 然而，如上所述的大多数动态运动规划方法都必须已知移动物体的具体运动 轨迹，或者至少已知其速度。然而，在真实的动态环境中，移动障碍物的运动是 随意的，而且通常很难预测。因此，在这种情况下，这些基于已知移动障碍物轨 迹的方法都很难使用，而本文将采用不断对环境检测并更新路径的方法。这就需 要一个快速高效的路径规划器，如文献 6 7