（控制科学与工程专业论文）多机器人协同探测的任务分配和避碰方法研究.pdf

摘要 机器人技术的发展使得机器人的能力不断提高，其应用的领域和 范围正不断扩展。人们希望多个机器人能完成由单一机器人难以完成 的更加复杂的作业。这些复杂的作业，需要多个机器人相互协调与协 作共同完成，因此对多机器人协调系统的研究就显得非常重要。多机 器人进行目标点探测有着广泛的应用。 文章围绕多机器人协调探测多目标点这一任务进行展开。文中首 先介绍了多机器人的体系结构，并在此基础上重点研究了多机器人任 务分配方法和避碰方法。文章主要工作如下： 对多机器人任务分配方法的研究方面，多目标点探测首先用组合 拍卖的方法来获得有效的目标集合，然后对这些目标集合中各目标点 探测的任务分配方法是用改进的蚁群算法来实现的。所以文中提出了 一种基于改进蚁群算法的多机器人的任务分配方法。该方法通过对蚁 群算法的改进，具体包括：多个机器人同时并行搜索、信息素的更新 和局部搜索算法的改进成功实现了多个机器人进行多目标探测的任 务分配方法。最后仿真实现了多个机器人探测目标点的任务分配方 法。结果表明该方法的有效性和正确性。 在多机器人执行任务的过程中，可能会发生路径的交叉现象。路 径的交叉是导致机器人碰撞发生的原因。为了解决多机器人的避碰问 题，文中提出了一种基于运动规划的多机器人协调避碰方法。该方法 通过问题描述、模型建立、交通规则和优先权设计等来实现了冲突区 域的资源分配，即多机器人的协调避碰方法。最后通过实验验证了该 方法的可行性。 关键字多机器人，蚁群算法，任务分配，避碰 a b s t r a c t w i t ht h ed e v e l o p m e n ti nr o b o t i c ss y s t e m ，t h ec a p a b i l i t yo fr o b o ti s i m p r o v e dc e a s e l e s s l ya n di t sa p p l i c a t i o nf i e l dh a sb e e ne x t e n d e d r o b o t s a r eb e i n ge x p e c t e dt od om o r ec o m p l e xt a s kw h i c hc a l l tb ea c c o m p l i s h e d b yas i n g l er o b o t o b v i o u s l y , t h e s e t a s k sn e e dc o o r d i n a t i o na n d c o o p e r a t i o na m o n gm u l t i p l er o b o t st of i n i s h s o i ti si m p o r t a n tt os t u d y m u l t i r o b o t s c o o p e r a t i o ns y s t e m t h ed e t e c t i n g o fm u l t i - t a r g e t s b y m u l t i r o b o t sh a se x t e n s i v eu s e t h i sd i s s e r t a t i o nt a k e st h et a s ko f d e t e c t i n gm u l t i - t a r g e t s c o o p e r m i v e l y w i t hm u l t i r o b o t sa sc e n t e r f i r s t l y , i n t r o d u c et h e a r c h i t e c t u r eo fm u l t i r o b o ts y s t e m , a n dt h e nm a i n l yr e s e a r c ht h et a s k a l l o c a t i o na n dc o l l i s i o na v o i d a n c em e t h o do fm u l t i - r o b o t s t h em a i n c o n t r i b u t i o na n dw o r ka r ed e s c r i b e da sf o l l o w i n g ： i nt h er e s e a r c ho ft h et a s ka u o c a t i o nm e t h o do fm u l t i - r o b o t s ，f i r s tw e c a nu s et h ec o m b i n a t i o n a la u c t i o nt og a i nt h ee 伍c i e n tt a r g e ts e t s ，u s et h e i m p r o v e da n ts y s t e ma l g o r i t h mt od e t e c tt h o s et a r g e ts e t s s oip r o p o s ea t a s ka l l o c a t i o nm e t h o do fm u l t i r o b o t sb a s e do nt h ei m p r o v e da n ts y s t e m a l g o r i t h m t h ep r o p o s e dm e t h o d si n c l u d em u l t i - r o b o t sp a r a l l e ls e a r c h i n g s i m u l t a n e o u s l y ，r e n e wt h ep h e r o m o n e ，a n di m p r o v et h el o c a ls e a r c h a l g o r i t h m a tl a s t ，r e a l i z e st h et a s ka l l o c a t i o nm e t h o do fm u l t i - t a r g e t s d e t e c t i n gb ym u l t i r o b o t st h r o u g h s i m u l a t i o n t h er e s u l t ss h o wt h e v a l i d i t ya n dc o r r e c n l e s so f t h ep r o p o s e dm e t h o d i nt h ep r o c e s so fr o b o t sp e r f o r mt a s k ，t h e r em a yb ee x i s tt h e p h e n o m e n o no fc r o s s i n gp a t h ，a n dt h ec r o s s i n gp a t hi st h em a i nr e a s o n f o rt h ec o l l i s i o nh a p p e n si nm u l t i r o b o t s i no r d e rt os o l v et h ec o l l i s i o n a v o i d a n c e p r o b l e m o f m u l t i r o b o t s ，t h i s d i s s e r t a t i o n p r o p o s e a c o o r d i n a t i o nc o l l i s i o na v o i d a n c em e t h o do fm u l t i - r o b o t sb a s e do nt h e m o v e m e n t p l a n n i n g b yp r o b l e ms t a t e m e n t ，m o d e lb u i l d i n g ，t h ed e s i g no f t h et r a f f i cr u l e sa n dt h ed e s i g no fp r i o r i t y , e t c ，t or e a l i z et h er e s o u r c e a l l o c a t i o ni nc o n f l i c tr e g i o n t h a ti s ，t h ec o l l i s i o na v o i d a n c ep r o b l e mo f m u l t i r o b o t s t h es i m u l a t i o nr e s u l t ss h o wt h e p r o p o s e dm e t h o d i s f e a s i b l e k e yw o r d sm u l t i r o b o t s ，a n ts y s t e m a l g o r i t h m ，t a s ka l l o c a t i o n ， c o l l i s i o na v o i d a n c e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 _ 十卜一十产 作者签名：盗星日期：盟年上月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：坦年上月上日 硕士学位论文 第一章绪论 1 1研究背景与意义 第一章绪论 随着计算机、通讯、电子、传感器、控制等技术以及人工智能技术的飞速发 展，机器人的开发与应用得到了不断地提高。机器人的发展经历了三个阶段：( 1 ) 可编程的、示教再现型机器人；( 2 ) 带有一定的视觉、触觉，具有一定适应能力 的机器人；( 3 ) 带有多种传感器，具有自适应能力、自学习功能的自主式机器人， 即所谓的“智能化机器人”。智能机器人是多种学科技术的集成，涉及到机构学、 控制工程、计算机技术、人工智能、传感技术、仿生学和其它一些相关的领域， 针对智能机器人，国内外都展开了相关技术的研究【lj 。早在本世纪4 0 年代中期， g w a l t e r 、w i e n e r 和s h a n n o n 在研究其带传感器的龟形机器人时，这些简单机器 人在对相互间运动的反应中已表现出“复杂的群体行为”，在7 0 年代早期，多智 能体间的相互协调和交互作用( 仅限于软件形式的智能体) 在分布式人工智能 ( d a i ) 领域作了大量研究，而在机器人研究领域内进行多机器人协调的研究是到 了8 0 年代末期才兴起的，并在9 0 年代得到迅速发展。同时，研究平台由刚兴起 时的计算机仿真环境向实物形式的机器人平台转变【2 】。与机器人技术的发展相一 致，美、日在多机器入协调的研究上也处于世界领先地位，另外，英、法、德、 韩和加拿大也有一定的发展，而我国在这方面的研究刚刚起步，仍然落后于发达 国家，且受到美国在技术支持上的限制。 随着智能机器人技术的发展，对机器人的研究重点己经转到多智能机器人系 统的研究上。多机器人群体协作系统具备自己的特点1 3 j ： ( 1 ) 空间分布：多个机器人分布在工作空间的各个区域同时作业； ( 2 ) 功能分布：功能不同的机器人或具有不同目标任务的多机器人可以协同 工作； ( 3 ) 时问分布：多个机器人可以在不同时间分布内执行任务。 事实证明，一个相互协调的多个机器人有着单个机器人系统所无法比拟的优 势： ( 1 ) 相互协调的n 个机器人系统的能力可以远大于一个单机器人系统的n 倍， 多机器人系统还可以实现单机器人系统所无法实现的复杂任务； ( 2 ) 当环境或任务极其复杂，需要机器人具有多种能力，而设计这种集所有 能力于一体的单机器人成为不可能时，多机器人系统是最佳解决方案： 硕士学位论文第一章绪论 ( 3 ) 设计和制造多个简单机器人比单个复杂机器人更容易、成本更低； ( 4 ) 使用多机器人系统可以大大节约时间，提高效率； ( 5 ) 多机器人系统的平行性和冗余性可以提高系统的柔性、鲁棒性和容错性， 等等。 然而，多机器人系统也存在单机器人系统所不存在的问题： ( 1 ) 如何在各智能体间表达、描述问题，分解和分配任务； ( 2 ) 如何使智能体间相互通讯和相互作用； ( 3 ) 如何保证各智能体行为协调一致； ( 4 ) 智能体间如何识别和解决冲突，等等。 多机器人协调系统涉及到社会科学( 组织理论、经济学) 、生命科学( 理论生物 学、动物行为学) 和认识科学( 心理学、信息理论、人工智能) 等的学科理论和关键 技术。 多机器人协作进行目标探测有着广泛的应用，可以用在： ( 1 ) 民用领域：清洁机器人可以代替人来执行清扫垃圾和脏物的工作等； ( 2 ) 医学领域：大量的微机器人进入肠道、胃或血管等人体内狭窄部位进行 校查、发现和修补病变； ( 3 ) 军事领域：使用机器人群体进行侦察、巡逻，排雷等： ( 4 ) 航天领域：利用机器人群体进行卫星和空间站的内外维护以及星球探索 等。 “多机器人协作目标探测”任务的实质可认为是通过团队合作来弥补个体的 不足，以协同完成这一复杂任务。这便涉及到了多机器人系统的协同机制。协同 机制包括协作与协调这两方面。在该任务中，由于各机器人的观察角度和范围不 同，以及观察的对象及方式也可能不同，这就存在一个协作的问题，比如首先根 据总体任务进行任务分解，然后根据团队中每个机器人的感知能力及当前位置来 对各个预定探测的目标点进行最优分配。而在各机器人任务已被分配之后，在到 达目标点的过程中，各机器人不但需要具备一定的运动能力，还需要遵循一定的 协调机制，比如发生空间资源冲突时如何避免各机器人之间的互相碰撞等。总之， 协同机制既是连接各个单机器人的枢纽，又是体现多机器人系统整体性能是否优 越的最重要方面。 同时在多机器人协作执行任务运行的过程中，存在着如何协调他们安全快速 的达到目标点并避免相互之间的碰撞( 暂不考虑系统中存在障碍物的情况) 。 所以本论文以“目标探测”这一任务，来研究多机器人系统中协同机制方面 的两个主要的问题( 包括协调和避碰问题) ，以期提高多机器人系统作为一个整 体的反应能力、感知能力和效率。 2 硕士学位论文 第一章绪论 本论文研究内容来源于国家基础研究项目“异质多移动体的协同工作与重构 技术的基础研究( a 1 4 2 0 0 6 0 1 5 9 ) ”。 1 2研究现状 经过二十几年的发展，多机器人系统的研究已在理论和实践方面取得很大进 展，并建立了一些多机器人的仿真系统和实验系统【4 】。目前，国内的多机器人系 统的研究刚刚起步。而国外的研究则比较活跃，欧盟设立专门进行多机器人系统 研究的m a r t h a 课题“用于搬运的多自主机器人系统( m u l t i p l ea u t o n o m o u s r o b o tf o rt r a n s p o r ta n dh a n d l i n ga p p l i c a t i o n ) 。美国海军研究部和能源部也对多机 器人系统的研究进行了资助。但从总体上讲，目前多机器人系统的研究还处于发 展的初期阶段，离实用化还有很远的距离。 一、多机器人协调系统的体系结构 由于智能机器人能够模拟人的智能行为与功能，因此它的体系结构与人的组 织结构系统一样，比较复杂。事实上，任何一个机器人都有自身的体系结构。 目前有两种具有代表性的机器人体系结构，分层递阶式结构【5 】和包容式体系 结构【6 1 。分层递阶式结构较好地解决了智能和控制精度的关系，但是也有一些不 尽人意的地方，如系统可靠性和鲁棒性较差，反应性极差。虽然低层的安排使它 具有一定的实时处理的能力，但是仅限于局部的非智能的反应。因为智能操作被 安排在上层，从传感到动作产生需要由下至上然后自上而下的来回过程，从而失 去了高度智能性的实时反应能力。包容式体系结构构造了多种机器人，这些机器 人确实显示出非常强的智能行为。因此，包容式体系结构在自主智能机器人领域 中产生了极大的影响。不过，仔细分析b r o o k s 的包容式结构思想，它也有一定 的不足之处。它强调了单元的独立、平行工作，缺少全局的指导和协调，虽然在 局部行动上可显示出很灵活的反应能力和鲁棒性，但是对于长远的全局性的目标 跟踪显得缺少主动性，目的性较差，而且人的经验、启发性知识难于加入，限制 了人的知识和应用。 文献【7 】提出了一种具有学习能力的智能机器人体系结构。针对特定的机器 人及所要完成的任务，研究和设计了机器人的软件体系结构。该体系结构包括感 知融合列、动作规划列和学习评价及物理层、感知层、反应层、动作层、规划层 和使命层，一共2 0 个功能模块。 文献【8 】提出了多机器人协作的结构，该结构非常适合于协作来控制任务的 执行。在任何时候，总有个机器人作为l e a d e r ，其它机器入作为f o l l o w e r ，角 色的分配和协调是通过网络协议和控制算法来实现的。在执行任务的过程中，允 许机器人间角色的转换。这种方法的缺点是受网络通信的影响。 3 硕士学位论文 第一章绪论 文献 9 】提出了一种基于行为的机器人的分级结构。这种结构在不影响基于 行为的系统的性能的同时增加了人工智能级的概念，描述了一种分级抽象行为结 构，在基于行为的框架下来描述和执行复杂的、有序的分级结构任务。通过对基 于行为的系统中的概念的行为抽象获得该结构，同时可以使这些结构在不同行为 间可重用。任务分解的基础就是由复杂的、分级的策略编码而成的行为网络结构。 文献 1 0 】提出了一种移动机器人的混合式自适应结构。该结构可以学习怎样 协调由使用强化学习的人工势场方法编码而成的原始行为，此结构的性能由机器 人从一个场地到另一个场地的性能曲线来描述的。我们知道反应式结构从当前机 器人的传感器的信息来直接决定行为，它对未知环境的反应较好；分布式结构由 规划来决定，此任务通过建立一个世界模型，把所以传感器的信息考虑进去，然 后再进行推理，它对机器人的情况有全局的了解，允许定义一个针对全局性能的 行为。混合式结构是结合了前面两个的有点，通过一组规划模块，可以产生一组 反应式行为集合，使它们有序，协调他们的输出或改变它们的内部机制。由于混 合式结构的复杂性，它一般用于纯反应式行为不能满足机器人的需要时的场合。 二、多机器人协调任务分配方法 多机器人目标探测时的协调分配方法属于多机器人任务分配方法。多机器人 系统的任务分配目前主要分为涌现式分配和意图合作分配这两大类【l 。 其中涌现式任务分配的思想来源于自然界中群居生物的社会组织方式，例如 蚂蚁、蜜蜂等生物群体虽然都属于低智能生物，但通过整体协调以及有效分工都 能够很好的完成特定的群体任务。在它们之间，信息交互是通过诸如信息素之类 的元素来进行的一种隐式通信。涌现式任务分配方式便是模拟这种生物群体，通 过机器人相互之间的行为交互以及对环境的影响来实现整体的协调。这种方式比 较适合机器人团队规模较大且任务规模也较大的情形。而在多数情况下，机器人 团队之间是需要进行显示的通信的，因此这种分配模式现今还应用较少。 意图合作任务分配方式是通过机器人之间的显式通信与协商来实现合作与 任务分配的，这种方式相比之涌现式任务分配更接近于人类社会通常的合作与任 务分配方式。意图合作任务分配主要包括以下几种方式： ( 1 ) 集中式任务分配 集中式任务分配就是由中央控制器全权决定任务的分配。在这种分配方式 下，中央控制器具有绝对的支配力，而各机器人只有接受任务和完成任务的义务， 无权利选择任务。 采用集中式分配的多机器人系统其缺点是，随着机器人团队规模的增大，中 央控制器将可能不堪重负，导致通信堵塞，分配速度过慢。一旦中央控制器失效 时，则系统将整个瘫痪。另外，各机器人需要通过通信将当前状态及环境信息传 4 硕士学位论文第一章绪论 递给中央控制器，然后由中央控制器做出处理，再告之机器人做出反应。显然， 这种方式使得系统难以对动态性较高的环境做出及时的处理。但这种系统在算法 设计和实现上较为简单，对于规模较小的系统而言，其任务的优化分配往往易于 实现旧。 ( 2 ) 合同网协议分配 合同网协议是一种典型的基于市场机制的分配方法，其思想来源于经济模型 中的拍卖模型。其特点是每个任务的分配都需进行招标、投标、合同授权和合同 建立这四个过程。 合同网协议分配方式无需预先掌握其他机器人的能力信息，因此较易实现任 务的动态分布式分配。但由于每个任务的分配都需要进行一轮招标、投标、合同 授权和合同建立的过程，因此对机器人的通信要求相对较高。 ( 3 ) 交易员分配 在交易员分配方式中，多机器人系统中的一个或多个机器人将扮演交易员的 角色，以接受中央控制器分派下来的任务并将其分配给适当的机器人执行，以及 接受各机器人提交的任务。 ( 4 ) 熟人网分配 在这种分配方式下，各机器人都保存有一张用于记录完成各个任务所需的能 力以及具备该能力的机器人的技能表，并定时更新和维护。当需要对某个任务进 行分配时，只需查找该表以找出最适合完成该任务的机器人。 三、多机器人系统避碰策略 在多机器人系统中，有时为了共同完成一些任务，这就需要多个机器人之间 相互协调来完成。在执行任务过程中，不但每个机器人成员需要具备良好的个体 行为，而且多个机器人之间需要协调以完成预期的目标或任务。这其中，一个非 常重要而基础的问题就是如何在同一个平台上协调各机器人运动而之间互不相 碰。 为了保证多机器人系统安全可靠地运行，研究人员也开展了大量的关于避碰 方面的工作。在复杂环境下的多机器人避碰规划中，存在着冲突消解等问题。目 前多机器人协调避碰技术概括起来主要有： ( 1 ) 通过组织结构进行协调 最简单的协调方法就是预定义一个组织结构，因为组织结构隐含了机器人所 具有的责任、能力、与其他机器人的相互关系及系统的控制流。它通过定义机器 人的角色、机器人相互之间信息交流的途径、隶属关系提供了一个各机器人之间 协调工作的框架。一般常用的组织结构形式是主从式的组织结构，即由某个主控 机器人为多个从属机器人分配任务和资源。主控机器人对任务进行规划，将规划 5 硕十学位论文 第一章绪论 后形成的子任务分配给从属机器人。从属机器人之间可以存在相互的通信，但都 必须向主控机器人反馈任务完成的进度和结果。主控机器人对于从属机器人是完 全自主的，而从属机器人对于主控机器人而言则是部分自主的。这种策略在具有 主从结构的系统中能够很好地控制从属机器人的行为，乃至整个任务的完成过 程。但从系统的角度来看，这种结构对多个机器人系统的并行性、鲁棒性和可靠 性会产生不利的影响。 ( 2 ) 以合同网协议为基础的协调 通过合同为协议在机器人中进行任务和资源的分配，决定机器人之间的组织 结构。从而达到多机器人之间相互避碰的目的并尽可能安全快速的达到目标点 ( 3 ) 基于多智能体规划的协调 为了避免混乱和冲突的情况，多机器人系统通过详细地考察各机器人将来的 行为和为了完成各自目标所需的相互协调工作，制定一个方案，然后通过不断地 规划、重新规划来得到更好的方案。一般存在以下两类多智能体规划方法。 ( 4 ) 集中式的多智能体规划 在集中式多智能体规划中，通常由一个协调机器人负责接收从各机器人发来 的所有局部规划，使他们成为一个适合于多机器人协调工作的规划，从而避免机 器人之间相互冲突的发生。它与主从式组织结构的协调方法具有许多相似的局限 和问题。 ( 5 ) 分布式的多智能体规划 在分布式的多智能体规划中，每个机器人都可以获得其他机器人规划的模 型。机器人之间可以通过通信来建立和更新它们自己的规划及其所获得的其他机 器人的规划模型。通过不断的重建和更新规划及模型，各机器人之间的冲突问题 最终可以获得解决。 ( 6 ) 磋商法 磋商法是一种最常用的协调机制，上述的几种协调方法都存在某种形式的磋 商。在人工智能中，磋商可定义为，“磋商法是一组智能体为了达成一个相互间 在某种程度上都可以接受的方案( 或规划) 而进行相互交流、通信的过程 。在 磋商法中可以应用许多不同的技术和策略形成各具特色的协调方法和策略。这些 技术和策略包括逻辑的方法、基于案例的推理、基于模型的推理、优化方法、博 弈论、乃至社会学、认知科学的相关理论。对于多机器人系统，所有这些方法和 策略都是值得研究和借鉴的。 在具体策略方面，最简单的一种解决方法是在多机器人系统中设计一个集中 控制规划器，由该控制规划器预先设定每个机器人的行为顺序，这种方法被称为 集中行为控制法【1 3 】。显然，这种方法赋与了集中控制规划器过多的任务，而各机 6 硕士学位论文第一章绪论 器人的自主性却大大降低，从而无法适应实际环境的变化。 因此，更多的非集中控制方案被提出来。如主从控制式，即一个机器人团队 中有一个主机器人，当发生冲突时，由它向其他机器人发出行动指令。另一种是 基于交通规则的分布式避碰方法，该方法应用于将环境建模成交通道路网式的系 统中，各机器人通过遵循一定的交通规则来约束自己的运动，从而避免碰撞与死 锁【l4 1 。基于p e t r in e t 的运动规划方法由l i u 等人提出，通过p e t r in e t ，建立起多 机器人路径上的交叉路口模型，在此基础上来解决交叉路口的冲突问题。 s h i l l 于1 9 9 3 年提出了速度障碍物的概念，用以解决机器人对于动态障碍物 的避碰问题。随着多机器人系统的研究发展，该方法后来被许多学者引用到多机 器人避碰策略中来。文献 1 5 a p 在此基础上提出了一种基于加速度空间的避碰策 略。 文献【1 6 】从个体层、协作层、传播层这三个层次来解决避碰问题。其中，个 体层用来对预测到碰撞的机器人进行速度调整，协调层使各避碰机器人以一种同 步方式来调整自己的速度；在传播层，那些系统中未涉及碰撞的机器人也将采取 速度调整策略，来协调自己与各避碰机器人的避碰行为。该避碰策略较适用于在 工厂、机场等环境下运动的大规模机器人团队。 文献【1 7 】提出了一种多机器人避碰及死锁预防算法。将机器人的运行环境形 式化地描述为初等运动集、冲突图、总任务集及机器人作业集，利用集合论、图 论的相关方法实现了多机器人之间的避碰行为。该避碰算法的一大特点是算法在 运行过程中同时预防了死锁的发生，而无须另行对死锁问题进行单独解决。 文献【l8 】通过结合智能控制和神经网络技术，提出了一种分级策略来实现多 机器人协调避碰。在该文中，将多机器人系统分为上下两层，上层包括了一个基 于知识的协调器( k n o w l e d g eb a s e dc o o r d i n a t o r ) 和一个基于神经网络的预测器 ( n n b a s e dp r e d i c t o r ) ，下层则由系统中各机器人组成。其中，上层协调器通过 预测器来预测来自下层各机器人相关输入信息的影响作用，并调整该信息将其反 馈给下层机器人，以实现多机器人的互相避碰。 文献【1 9 】采用集中分布相结合的规划方法，根据系统的拓扑结构为每个机器 人规划路径。在冲突区域内采用优先级策略对机器人的运动特征进行分布式规 划。 在文献 2 0 】中，将机器人的行为分为奔向目标行为、避免碰撞行为和协商行 为，并提出了意愿强度的概念，以对单机器人的几种行为进行合理的综合。各机 器人以意愿强度为基础同其他机器人进行协商，以决定自身的速度调节值，从而 实现避碰。但该文中并未具体讨论多机器人避碰死锁的问题。 文献【2 l 】对“巴别塔”问题( t h et o w e ro f b a b e l ) 设计了一种有效的多机器 7 硕士学位论文第一章绪论 人避碰机制，以保证机器人在无碰撞的情况下( 包括避开静态障碍物和其他机器 人) 到达各自的目标点。文巾，定义了机器人的“可取方向”，用来引导机器人 驶向目标点，并采用了一种链结构米记忆必需的环境信息。另外，设计了协调器 来解决多机器人避碰死锁问题。在协调器中，通过将当前运动决策为停止等待的 机器人逐个加入到一个停止等待机器人队列中，来动态调整各机器人的运动权 值，并最终使各机器人按照协调器的指令逐个顺序运动，从而解决死锁问题。 1 3 机器人平台介绍 中南移动体二号( 以下简称m o r c si i ) 是由中南大学智能控制研究所课题 组成员在a c t i v em e d i a 公司生产的第- - r 机器人a m i g o 机器人平台上改造而成 如图1 1 。在保留了a m i g o 机器人原有的特点的基础上，改变了机器人和计算机 之间通信方式，为机器人建立了自身的操作系统，使机器人成为一个真正意义上 的智能体，也为本课题的研究提供了强有力的技术支持。 ( a ) a m i g o 机器人 1 3 1 硬件部分 图1 - 1 机器人平台 a m i g o 机器人的尺寸是2 8 x 3 3 1 3 c m ，包括电池在内的重量大约3 6 k g 。底部 装有三个直径为1 0 c m 的轮子，其中一个是万向转动轮，轮子由一个1 2 v 的可逆 直流电动机驱动。机器人内部传感系统以及机器人的驱动的供电均是由一个主频 为2 0 m h z 单片机系统控制，该单片机有1 6 k r a m 和6 4 k f l a s h 的片上存储单 元，1 m 的外部f l a s h 。机器人有三个r s 2 3 2 串口，8 个i o 总线，包括4 个片 选，3 个地址和读写线；6 个数字时间i o 口，4 个a d 口，一个p w m 线，一 个可供给1 2 v 和1 5 v 直流电源。m o r c si i 是在a m i g o 的基础上增加了一个嵌 入式板，通过一个s a p h i r a 客户端程序来连接和控制机器人。改造后的m o r c s i i 有自己的操作系统，可通过无线网络和控制台联系，使功能更多，操作更灵活 方便。 硕士学位论文第一章绪论 1 3 2 软件部分 根据a m i g o 系统自身提供的方便的软件控制接口，又进一步进行了相应的 研究。由中南大学智能控制研究所自行开发的m o r c si i 平台，主要包括服务器 端和客户端。其中服务器端主要有p l a t f o r m 类定义了平台中的一些菜单和对话 框等；m a p u t i l 2 类定义了平台中的坐标，栅格、地图等数据结构；s o c k e t q u e u e 类主要用于设置和客户端连接的网络端口等。客户端主要有r o b o t c l i e n t 类定义 了机器人的一些属性和仿真或连接实际机器人；s o c k e t q u e u e 类用来和服务器端 相互通信，从而在控制台可以控制多台机器人来执行相应的命令；g r i d m a p 定义 了栅格地图的一些信息等等。 另外，每个研究人员根据自己的研究内容再进一步的开发相应的类来实现相 应的功能。 1 4 论文主要研究内容及组织结构 1 4 1 主要研究内容 文章围绕多机器人协调探测多目标点这一任务进行展开。文中首先介绍了多 机器人的体系结构，并在此基础上重点研究了多机器人任务分配方法和避碰方 法。文章主要工作如下： 对于多目标点探测首先用组合拍卖的方法来获得有效的目标集合，然后对这 些目标集合中各目标点探测的任务分配方法是用改进的蚁群算法来实现的。 文中提出了一种基于改进蚁群算法的多机器人的任务分配方法。该方法通过 对蚁群算法的改进，具体包括：多个机器人同时并行搜索、信息素的更新和局部 搜索算法的改进。最后仿真实现了多个机器人探测目标点的任务分配方法。结果 表明该方法的有效性和正确性。 在多机器人执行任务的过程中，为了避免碰撞，文中提出了一种基于运动规 划的多机器人协调避碰方法。该方法通过问题描述、模型建立、交通规则和优先 权设计等来实现了冲突区域的资源分配。即多机器人的协调避碰方法。最后通过 实验验证了该方法的可行性。 1 4 2 论文的组织结构 文章围绕多机器人协调探测多目标点这一任务进行展开。介绍了一种多机器 人体系结构并重点研究了多机器人执行任务时的任务分配和避碰方法。论文的组 9 硕士学位论文 第一章绪论 织结构如下： 第一章为绪论，主要介绍了论文课题的研究背景与意义、现状，以及论文的 研究内容和重点，并给出了本论文的组织结构。 第二章介绍了多机器人系统体系结构，并介绍了一种集中式与分布式混合的 智能控制系统。 第三章研究了多机器人目标探测时的任务分配方法，提出一种基于改进蚁群 算法的多机器人任务分配方法，并实验仿真了该方法。 第四章研究多机器人执行任务的过程中协调避碰策略，提出一种基于运动规 划的多机器人避碰方法，并通过实验验证了该方法。 第五章为总结和展望，对本论文的研究内容和创新点进行了总结，分析了论 文中的缺陷和不足，最后对今后的研究发展方向进行了展望。 1 0 硕士学位论文第二章多机器人系统体系结构及协作策略 第二章多机器人系统体系结构及协作策略 2 1引言 多移动机器人体系结构是多机器人研究的关键问题之一，它主要是研究如何 组织和控制多机器人系统完成所需任务。 体系结构通常分为群体体系结构和个体体系结构两部分。群体体系结构是多 机器人个体间的组织形式。多机器人之间的协作机制就是通过它来体现的，它决 定了多机器人系统在任务分解、分配、规划、决策及执行等过程中的运行机制及 系统各机器人个体所担当的角色。每个机器人个体通过系统体系结构能够获得关 于系统整体行为的高级观点，从而有利于引导局部控制实现协作，增强系统的全 局一致性。 研究机器人个体控制结构也非常重要。由于多机器人系统是机器人个体组 成，因此，机器人个体的控制性能对于多机器人系统中的协调能力有着决定作用。 多机器系统在全局上，应该是面向所要实现的任务；在局部上，机器人个体也应 该具有一定的灵活性，机器人个体可以在短期内对自己的行为做出规划，以应对 随时出现的紧急情况，也可以通过通讯实现与其它机器人的协商。另外，机器人 个体可以进行对环境感知的同时，反馈局部信息，影响下一步多机器入系统的任 务规划。 从系统设计的角度而言，体系结构要有利于个体能力最大程度的发挥和任务 的高效完成。 2 2机器人个体体系结构 2 2 1几种机器人个体体系结构 从人工智能的角度来看，当前机器人控制体系结构主要有四类，一类是基于 慎思式智能的功能分解体系结构；一类是基于反应式智能的行为分解体系结构； 一类是基于分布式智能的多智能体体系结构，还有一些综合前面两者或三者的混 合式体系结构。这里主要介绍和分析前面三类主要体系结构思想的优点与不足之 处。 ( 1 ) 基于功能分解的体系结构。基于功能分解的体系结构在人工智能上属于 硕士学位论文第二章多机器人系统体系结构及协作策略 传统的慎思式智能，在结构上体现为串行分布，在执行方式上属于异步执行，即 按照“感知规划一行动”的模式进行信息处理和控制实现。以美国国家航天局 和美国国家标准局所提出的n a s r a m 为典型代表。这种体系结构的优点是系统 的功能明了，层次清晰，实现简单。但是串行的处理方式大大延长了系统对外部 事件的响应时间，环境的改变导致必须重新规划，从而降低了执行效率。因此只 适合在已知的结构化环境下完成比较复杂的工作。 ( 2 ) 基于行为分解的体系结构。基于行为分解的体系结构在人工智能上属于 现代的反应式智能，在结构上体现为并行( 包容) 分布，在执行方式上属于同步执 行，即按照“感知一行动”的模式并行进行信息处理和控制。是一种自底而上的 控制结构。用行为封装了机器人控制中具备的感知、探索、避障、规划和执行任 务等能力，各行为是由传感器到驱动器的局部映射，而系统得全局目标任务通过 各行为之间的相互作用实现。它具有很强的实时性和鲁棒性。基于行为分解的体 系结构以麻省理工的r a b r o o k s 所提出的行为分层的包容式体系结构【2 副( c s u b s u m p t i o na r c h i t e c t u r e ) 和a r k i n 提出的基于m o t o rs c h e m a 的结构1 2 3 j 为典型代 表。其主要优点就是执行时间短，效率高，机动能力强。但是由于缺乏整体的管 理，很难适应于各种情况。因此只适用于在未知环境下执行比较简单的任务。 ( 3 ) 基于智能分布的体系结构。基于智能分布的体系结构在人工智能上属于 最新的分布式智能，在结构上体现为分散分布，在执行上属于协同执行，既可以 单独完成各自的局部问题求解，又能通过协作求解单个或多个全局问题。以基于 多智能体【2 4 】的体系结构为典型代表。这种体系结构的优点是既具有“智能分布” 的特点，又有统一的协调机制。但是如何在各个智能体之间合理的划分和协调仍 然需要大量的研究和实践。该体系结构在许多大型的智能信息处理系统上有着广 泛的应用。 2 2 2 单机器人反应式控制结构 除以上三类主要的体系结构之外，还有一些改进的混合式体系结构，如带反 馈环节的行为分解模式、基于分布式智能的分层体系结构、基于功能分解的多智 能体结构等等。随着机器人体系结构的复杂化，单个机器人虽然获得了较高的智 能，但在组成多机器人系统时会导致响应缓慢，不利于多机器人协同工作。尤其 考虑到实时环境下，机器人面对的是动态、复杂、非结构化环境，采用复杂的机 器人个体控制结构，会降低机器人的响应速度。 综上考虑，在机器人控制结构的选择中，考虑了机器人在实际环境中对环境 建模的困难，为提高多移动机器人协作系统的鲁棒性和快速响应能力，采用基于 行为的反应式控制体系结构( 如图2 1 ) ，该结构把机器人传感器与机器人运动结 硕士学位论文 第二章多机器人系统体系结构及协作策略 合起来，实现了对环境变化的快速响应。将多机器人协作建立在机器人个体的反 应式控制机构之上，加快了多机器人系统对外界的响应，避免了复杂的推理，从 而提高了系统的实时性。 图2 - 1 反应式控制结构 反应式控制器的总体输出是所有处于激活状态的基本行为输出的矢量加权 和，如公式2 - 1 ，其中，亏为综合行为输出，互为行为i 的矢量输出，彬为行为f 拥 有的权值。 雪= ，形互江1 2 堋 ( 2 - 1 ) 2 3多机器人系统体系结构 多机器人系统体系结构是系统中机器人之间逻辑上和物理上的信息关系和 控制关系，以及问题求解能力的分布模式，它是多移动机器人协作行为的基础。 现有的许多文献提出了多种体系结构，从不同的角度可以分不同的结构形式。 2 3 1多机器人系统组织结构 多机器人协调系统的组织结构为整个系统执行协调合作任务提供基础，决定 了系统的能力和局限性。现有文献提出了许多种系统结构，从不同的角度可以分 不同的结构形式： a ) 集中式b ) 分散式 c ) 分布式 图2 - 2 控制结构 ( 1 ) 从控制结构分有集中式c e n t r a l i z e d 、分散式d e c e n t r a l i z e d 和分布式 1 3 硕+ 学位论文第二章多机器人系统体系结构及协作策略 d i s t r i b u t e d 三种。c e n t r a l i z e d 控制结构【2 4 】由一个机器人集中控制整个系统，它是 一种规划与决策的自上而下t o p d o w n 式的层次控制结构，其层的数量和复杂性 决定了系统响应所需的时间和行为决策的质量，如图2 2 ( a ) 。系统的协调性较好， 但实时性、动态性较差，对环境变化响应能力差。当机器人数目增多时，系统将 变得复杂而难以控制。d e c e n t r a l i z e d 控制结构【2 5 】的多机器人协调系统中，各机器 人具有高度自主自治能力，各机器人自行处理信息、自行规划与决策、自行执行 自己的任务，如图2 2 ( b ) ，与其它机器人相互通讯以协调各自行为而没有任何集 中控制单元。这种结构有较好的容错能力和可扩展性，但对通讯要求较高，且多 边协商效率较低，无法保证全局目标的实现。d i s t r i b u t e d 控制方式【1 1 为刀j 介于两 者之间，是一种全局上各机器人等同的自主分布式分层结构而局部集中的结构方 式，如图2 - 2 ( c ) 。这种结构方式是分散式的水平交互和集中式的垂直控制相结合 的产物，既提高了协调效率，又不影响系统的实时性、动态性、容错性和可扩展 性。系统具有更多的灵活性和更强的鲁棒性，每个机器人的行为由自己的规则决 定。 ( 2 ) 从通讯方式分又有三种组织结构。一是系统的各机器人间没有精确的通 讯或相互作用，仅仅是在共享环境( 实际上是共享内存) 的基础上以环境为媒体作 最简单、最有限的相互作用。二是基于传感器信息的机器人间相互作用，也就是 说，机器人间同样地没有精确的通讯，而是通过传感器的相互检测获取对方信息， 产生局部的相互反应，它要求机器人能识别其它个体，并区别于环境中的其它物 体。这种方法多用于诸如f l o c k i n g 、p a t t e mf o r m a t i o n 的集体行为。三是机器人间 存在精确通讯，用点对点、b l a c k b o a r d 或b r o a d c a s t 式传递m e s s a g e 。这种通讯结 构类似于网络，因此涉及到许多标准的网络问题，加网络拓扑结构和通讯协议的 设计等 2 8 1 。 ( 3 ) 从个体差异性分有同质个体和异质个体两种结构。同质个体结构系统的 各机器人的能力是等同的，而异质结构则不同。一般地，异质结构由于各个体具 有不同的能力，使得系统任务分配更复杂，个体之间的通讯或建模更困难。因此， 大多数多机器人协调系统的研究是建立在同质结构上，如s w a r m 2 8 结构。也有 一些优秀的结构处理异质个体，如a c t r e s s 2 9 j 和a l l