（控制理论与控制工程专业论文）多机器人系统的协作控制算法设计与实现.pdf

摘要 摘要 多机器入协作与控制研究的基本思想前提就是将多机器人系统看作是一个 群体或一个社会，从组织和系统的角度研究多个机器入之间的协作机制，从而充 分发挥多机器人系统各种内在的优势。 本文将多机器人系统的协作控制分为：全局任务分配，局部协调策略，底层 运动控制三个由高到低的层面，其中：全局任务分配规定了整个系统的工作模式， 制定了全局任务执行方式的框架；局部协调策略则是遵循整体框架的前提下，有 效组织多个机器人合作，使得某个任务的执行变得科学、有效；底层运动控制则 是运用控制理论的成果合理驱动机器人，它决定了上层策略能否最终得以实现。 这三者分别起到了：统领全局，承上启下和功能实现的作用，他们相互影响，相 互制约，也因此成为了贯穿本文对多机器人系统协作控制问题研究的主线。本文 分别针对这三个方面，进行相关的理论研究、解决方案设计及实验分析，主要包 括以下内容： 首先，研究了多机器人协作搜集、搬箱子问题。介绍了任务分配的方法和任 务的类型，建立了用混杂自动机模型描述的基于动态角色分配的任务分配机制， 借鉴了蚁群算法的任务分配方法，进行了大量的仿真，统计了实验结果，分析比 较了不同的任务分配策略的优劣特性。 其次，研究了机器人围捕问题。调研分析了q 学习作为解决围捕问题的理 论依据的可行性。独创性的以围捕队形作为学习状态的划分依据，并依其优劣特 性表现出的数学规律，设计了评价函数。最终通过仿真验证其有效性。 再次，研究了移动机器人领航跟随运动系统的控制问题。研习了精确线性 化的理论知识，对非完整约束的跟随运动系统建立了运动学模型，推导证明了控 制律，制定了基于x m l 格式的通讯协议，实现了两车的实时数据通讯。 最后，研究了仿真软件作为算法有效性验证工具的问题。分析了m u r o s 开 源软件的系统构架，扩充了基础功能类库，添加了模拟控制函数，最终图解了几 个主要的全文中提到的仿真实验。 关键词：混杂模型；蚁群算法；q 学习；队形矩阵；精确线性化 a b s t r a c t a b s t r a c t c o n s i d e r i n gm u l t i r o b o ts y s t e ma sac o l o n yo rc o m m u n i t yi nt h ev i e wo fg r o u p o rs y s t e m ，i sau s u a lw a yt os o l v et h ep r o b l e mo fc o o p e r a t i o n , w h i c hw i l le n l a r g et h e a d v a n t a g eo fm u l t is y s t e m i ti sc o n s i d e r e di nt h i sp a p e rt h a tt h em u l t i r o b o tc o n t r o l p r o b l e mf r o mt h r e ea s p e c t s ：g l o b a lt a s ka l l o c a t i o n ，l o c a lc o o r d i n a t e ，a c t i o nc o n t r 0 1 t h et a s ka l l o c a t i o ne s t a b l i s ht h ef r a m e w o r kt ob ee x e c u t e d l o c a lc o o r d i n a t et r yt o m a k es u r et h a te v e r ym e m b e rw o r kt o g e t h e re f f e c t i v ea n dr e a s o n a b l e m o t i o nc o n t r o l e n f o r c ee a c hm e m b e rt oa c h i e v et h eo u t p u td e s i r e db yt h es y s t e mi nt h eh e l po f c o n t r o lt h e o r y t h e s ea r ec o n d i t i o n a la n dr e a c t i v eb e t w e e ne a c ho t h e r , w h i c hm a k e t h e mt h ec o r eo ft h er e s e a r c ho fm u l t i - r o b o ts y s t e mi nt h i sa r t i c l e w er e s e a r c ht h e s e t h e r ea s p e c t sb yt h e o r ys t u d y , s o l u t i o nd e s i g na n ds i m u l a t i o nr e s u l ta n a l y s i s t h em a i n w o r k sa r ea sf o l l o w s ： f i r s t l y , r e s e a r c ht h eo b j e c tm o v i n gp r o b l e m i n t r o d u c et h ew a y t ot a s ka l l o c a t i o n a n dt a s k t y p e e s t a b l i s h i n gt h er o l ea s s i g n m e n tm o d e lu n d e r ah y b r i ds y s t e m f r a m e w o r k ，a n da n o t h e rm o d e l 谢t 1 1t h ei d e ao fa n tc o l o n ya l g o r i t h m ab i ga m o u n to f e x p e r i m e n th a sb e e nc a r r i e do u t t h er e s u l t sw e r es h o wa n da n a l y s i sw a sg i v e n s e c o n d l y , r e s e a r c h t h eh u n t i n gp r o b l e m g i v et h ef e a s i b i l i t yr e s e a r c ho f q l e a r n i n gt os o l v eh u n t i n gp r o b l e m p r o p o s e san e w m e t h o dt oi n d i c a t eaf o r m a t i o n b yi n t r o d u c i n gf o r m a t i o nm a t r i x e sw h i c he f f e c t i v e l yr e d u c et h ed i m e n s i o n so ft h e l e a r n i n gs t a t e s m o r e o v e ra ne v a l u a t i o nf u n c t i o ni sp r e s e n t e db yt h ec h a r a c t e r i s t i c so f m a t r i x e sw i t ht h ed i f f e r e n tf o r m a t i o n s t h e n ，r e s e a r c ht h el e a d e r - f o l l o w e rm o b i l ec o n t r o lp r o b l e m s t u d yt h ef e e d b a c k l i n e a r i z a t i o nc o n t r 0 1 e s t a b l i s ht h ea c t i o nm o d e lc o n s i d e r i n gt h en o n h o l o n o m i c c o n s t r a i n t c o n t r o ll a wa n ds t a b l ed e m o n s t r a t i o na r eg i v e n e s t a b l i s h i n gt h e c o m m u n i c a t i o np r o t o c o lb a s e do nx m l ，w h i c hh a sb e e nr e a l i z e dt h ed a t at r a n s f e ri n r e a l t i m eb e t w e e nt w om o b i l er o b o t s m o r e o v e r , r e s e a r c ht h es i m u l a t i o ns o f t w a r e d e s c r i b i n gt h es y s t e mf r a m ea n d w o r k i n gp r o c e s s i n go f t h es i m u l a t o r i n t r o d u c i n gt h ec l a s sa n d f u n c t i o nr e i n f o r c e m e n t s a m em i s s i o nr e s e a r c h e di nt h i sa r t i c l ew a ss h o wa n di l l u s t r a t e db ys i m u l a t i o ns n a p s h o t k e yw o r d ：h y b r i dm o d e l ；a n tc o l o n y ；ol e a r n i n g ；f o r m a t i o nm a t r i x ；f e e d b a c k l i n e a r i z a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即；学校有权保留送交 论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影 印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 耋地 导师签名： 日期：! 笠丛笙 本论文工作得到国家自然科学基金( n o 6 0 7 7 4 0 3 7 ) 项目资助。 第1 章绪论 1 1 引言 第1 章绪论 在机器人研究的早期，机器人的结构、运动学、控制和信息处理是研究的重 点。随着机器人技术的发展，单个机器人的能力、鲁棒性、可靠性、效率等都有 很大的提升。但面对一些复杂的、需要高效率的、并行完成的任务时，单个机器 人则难以胜任。为了解决这类问题，一方面可以进一步开发智能更高、能力更强、 柔性更好的机器人，或者叫“超级机器人”；另一方面设想如果能够通过多个简单、 低成本机器人之间的协调工作，来完成更为复杂的任务，将也会是一种有效的解 决途径，多机器人系统的研究由此而产生。 多机器人系统作为一种人工系统，实际上是对自然界和人类社会中群体系统 的一种模拟。它不是物理意义上纯粹的单个机器入的代数相加，其作用效果也不 是单个机器人作用的线性求和，它应该还包括一个“线性和”之外的基于个体之 间相互作用的增量。如果多个机器人之间没有好的协作，只是简单的多个机器人 的堆砌，不但不能实现多机器人系统的优势，反而可能导致多机器入的冲突与对 抗，甚至无法完成预定的任务。因此，“协作 是多机器人系统要解决的核心问 题。 1 2 多机器人系统的研究开发近况 1 2 1 硬件系统 ( 1 ) 群智能机器人系统 群体机器入系统是由许多无差别的自治机器人组成的分布式系统，它主要研 究如何使能力有限的个体机器人通过交互产生群体智能。 在自然界的蚂蚁、蜜蜂等昆虫群体中，个体能力有限，但从他们的交互中却 呈现出了智能行为。这种行为对于生态群体中的个体的生存是必要的。通过人工 模拟昆虫社会，有助于群智能机器人系统的研究。加拿大的a l b e r t a 大学开发的 c o l l e c t i v er o b o t i c s 实验系统【l 】是一个典型例子。该系统将许多简单的机器人组成 一个团体来完成一些有意义的工作。另一个有代表性的的系统是美国的u s c 大 学开发的t h en e r dh e r d 系统1 2 。 。 圈11c o l l e c t i v er o b o t i c s 系统 f i g u r ei 1c o l l e c t i v er o b o t i c s 圈12t h e n e r d h e r d 实验系统 f 1 9 u m12 t h e n e r d h e r d 它由2 0 个机器人组成，机器人上装有用于抓取、堆放物品的装手，抓手上 装有红外传奇、感器和接触传感器。机器人本题l 装有碰撞传感器、无声声纳 定位系统及通信系统。该系统可用于大规模机器人群行为实验。 ( 2 ) 自重构机器人系统 自重构机器人系统( s e l f - r e e o r d l g u r a b l er o b o t i cs y s t e m s ，s r r s ) 以- - 些具有不同 功能的标准模块为组件，根据目标任务的需要对这些模块进行相应的组合，进 而形成具有不同功能的系统。日本n a g o y a 大学的t f u k u d a 教授领导的研究小组 在生物细胞结构的启发下研究的c e b o t 3 , 4 , s , 6 1 系统就是一个典型的示例。 c e b o t 系统将系统中众多相同或不同功能的机器人视为细胞元，这些细胞 元机器人可以移动、寻找和组合。根据任务或环境的变化，这些细胞元机器人可 以自组织成器官化机器人，多个器官化机器人可匕l 进一步自组织形成功能更加复 杂的机器人系统。细胞结构机器人系统强调的是单元体的组合如何根据任务的和 环境要求动态重构。因此，系统具有多变的构型，可以具体学习和适应的群智能 并具有分布式的体系结构。 ( 3 ) 协作机器人系统 图13c e b o t 系统示意图 f i g u r ei3 c e b o t 协作机器人系统是由多个具有一定智能的自治机器人组成，机器人之间通过 通信实现相互间的协作己完成复杂的任务。 美国o a k r i a g e 国家实验室的l y n n c ep a r k e r 及其研究小组建立了实验平台 ( c e s a r e m p e r o r 和c e s a r n o m a d s 机器人系统) 进行理论的验证n 前者用于户 外，在机器人上安装激光测距仪摄像头、声纳传感器以及无线以太网等；后者用 于室内应用，机器人上安装多种传感器，包括测距仪、接触传感器、声纳、红外、 视觉、罗盘以及基于激光的2 d 定位系统，机器人还装有无线以太网以实现机器 人之间的通信以及机器人和工作站之间的通信。 ( a ) c e s a r 唧哪r ( b ) c e s a r n o r o a d s 图14c e s a r 实验系统 f i g u r e1 , 4c e s a r 中科院沈阳自动化研究所以制造环境应用多机器人装配为背景，建立了一个 多机器人协作装配系统( m d t i r o b o t c o o p e r a t i v ea s s e m b l ys y s t c n l , m r c a s ) s , 9 , t 0 i 。该 系统采用集中与分散相结合的分层体系结构，分为合作组织级和协调作业级。合 作组织级的协作控制h o s t 由一台p c 机构成，协调作业级则由p u m a 5 6 2 ， p u m a 7 6 0 ，a d e p t1 和全方位移动车o d v 组成。利用m r c a s 进行多机器人协 作装配工件的实验结果表明：m r c a s 系统为深入研究多机器人协作理论与方法 提供了一个很好的实验平台，并对多机器人协作系统的实际窿用具有参考价值。 1 2 2 软件系统 ( 1 ) m o b i l e s i r a 由美国a c f i v e m e d i ar o b o t i c s 公司开发的与其系列硬件产品相配套的移动机 嚣人控制软件。其向用户提供了一套用c 抖语言编写的开源控制开发包a r i a ，既 是一种为移动机器人设计的面向对象的机器人程序类库。它实现了对机器人底层 的驱动封装，支持对机器人所有硬件和运动的控制，还包括串口通讯、包的发送、 线程管理、附加件控制等。用户可以直接根据需要编写高层的控制程序。在 m o b i l e s i m 上实现的控制程序可直接控制该公司的移动机器人。 汹 f 2 ) t e a m b o t s 仿真系统 图l5m o b i l e s i m 仿真系统 f i g u r e1 5m o b i l e s i m 图16 t e a m b o t s 仿真系统 f i g u r e1 6 t e a m b o t _ s 由g e o r g i ai n s t i t u t eo f t e c h n o l o g y 和c m u 共同开发完成的川。该仿真系统采 用j a v a 语言编写，在w i n d o w s 、l i n u x 和s o l a r i s 等操作系统上均可运行系统， 源代码公开，在遵守一些协议的条件下可以修改其代码，通用性较好，与实际机 器人有接口。 ( 3 ) s o c c e rs e r v e r 图17s o c c e r s e r v e r 仿真机器人足球 f i g u r e l 7s o c c e r s 口v 盱 是比较著名的多机器人仿真软件“2 1 ”拥有大量的用户。它较少地考虑环境 的几何要素，而更多地考虑机器人之间的交互对抗。该软件由r o b o t c u p 委员会 提供，是一个允许参赛者使用各种程序语言进行仿真足球比赛的系统。它提供一 个虚拟的场地，并对比赛双方的全部队员和足球运动进行仿真。在仿真模型里面， 考虑了真实世界的很多复杂特性，诸如感知信息和执行机构的不确定性，通信的 限制等。该软件是机器人足球的专用软件，难以进行足球比赛以外的仿真试验。 1 3 多机器人主要研究问题及任务 1 3 1 主要研究问题 由多台自主移动机器人构成的，而且具有协作行为的多机器人系统，目前还 根少有实际应用的报道，除了技术、工艺、硬设备的限制之外，支持多机器人合 作的理论也处于研究阶段。在这些研究中，面向多机器人系统的体系结构，机器 人运动中的自主定位，资源争用问题，协调协作的产生，学习问题，几何问题等 一直是研究的主线 1 4 1 。下面分别对这几个问题进行介绍。 f 1 1 体系结构 多机器人系统依靠几个机器人的简单组合并不能充分发挥其优势，只有通过 某种形式的合作才能实现其对复杂任务的处理。多个机器人要实现相互间的合作 就必须确定机器人之间逻辑上和物理上的信息关系和控制关系，以及问题求解能 力如何分布等问题。针对这些问题而进行的群体体系结构研究可以将多机器人系 统的结构与控制有机的结合起来，保证多机器人系统中信息流与控制流的畅通， 为机器人之间的活动。交互作用提供框架。群体结构可分为集中式和分散式两种。 分散式又可进一步划分为分层式和分布式【1 5 】。 北京工业大学工学硕士学位论文 集中式结构中，通常是一个主控单元掌握全部环境信息及各受控机器人的信 息，运用规划算法和优化算法，主控单元对任务进行分解分配，像个受控单元发 布命令，并组织多个受控机器人共同完成任务。分布式结构中没有主控单元。个 机器人之间的关系是平等的，个机器人均能通过通信等手段与其他机器人进行信 息交流，自主的进行决策。分层式相对于分布式存在局部集中，是介于集中时结 构与分布式结构之间的一种混合结构。 ( 2 ) 通信 通信是机器人之间进行交互和组织的基础。通过通信，多机器人系统中个机 器入了解其他机器人的意图、目标和动作以及当前环境状态等信息，进而进行有 效的磋商，协作完成任务。一般来说，机器人之间的通信可分为隐式通信和显式 通信。 使用隐式通信的多机器人系统通过外界环境和自身传感器来获取所需的信 息并实现相互之间的协作，机器人之间没有通过某种共有的规则和方式进行数据 转移和信息交换来实现特定含义信息的传递【16 ，1 7 1 。使用显式通信的多机器人系统 利用特定的通信介质，通过某种共有的规则和方式实现特定含义信息的传递，因 而可以快速、有效地完成个机器人间数据、信息的转移和交换【1 8 , 1 9 , 2 0 。 利用显式通信进行少量的机器人之间的上层协作，通过隐式通信进行大量的 机器人之间的底层协调，在出现隐式通信无法解决的冲突死锁时，再利用显式通 信进行少量的协调工作加以解决。这样的通信结构既可以增强系统的协作能力、 容错能力，又可以减少通信量，避免通信中的瓶颈效应。 ( 3 ) 学习 机器学习的研究是人工智能研究的一个重要方向，其研究成果对于多机器人 系统学习方法的研究有很大帮助 2 1 1 。 按学习的过程划分，学习可以分为两种形式：独立学习和交互学习。独立学 习只单个机器人独立进行的学习过程，不依赖与其他机器人。交互学习指多个机 器人共同进行的学习过程。交互学习算法中，a c e 算法和d f g 算法是两种较好 的分布式增强学习算法圈，可以帮助多机器人系统实现相互之间协调协作地学 习，乃至整个组织结构的调整。 按学习的反馈类型来划分，学习可以分为：监督式学习、增强式学习、和无 监督式学习。多机器人系统作为一个群体进行学习时，依据不同的学习目的其内 部存在几种学习类型：机器人某种特定类型的学习；对群体组合特性的学习；对 任务模式的学习；对环境特性学习。 6 第1 荦绪论 n 一 一i i l - 皇曼曼鼍鼍 多机器入学习一般分为三个阶段：学习开始前的数据收集阶段；学习进行中， 单个机器人以来局部数据进行学习，同时通过通信将部分学习结果与其他机器人 共享的阶段；局部学习完成后，各机器入共享并综合其学习所得的数据和知识， 形成最终学习结果的阶段。 在动态过程中，多机器人系统出了需要选取适当的学习算法外，还需要在恰 当的时候决定是否开始学习、停止学习等。所以多机器人系统的学习算法及其相 关知识的研究对多机器人系统都是重要和具有现实意义的。 ( 4 ) 协调协作机制 如引言所属，多机器人系统研究中一个重要问题就是如何实现个机器人之间 的协调与协作【2 3 1 。多机器人的协调协作机制与系统的体系结构、个体体系结构、 通信、学习等方面研究密切相关。文献【2 4 】对协作的概念、意义、方式以及实际 物理系统、化学系统、生物系统的自组织协作等问题进行了较全面的论述，并结 合多机器人系统的各方面研究讨论了协调协作问题。 对于多机器人系统协调协作，现在还没有一个统一的定义。总体上讲，协调 与协作反映了在多机器人系统不同层次上对系统控制与交互提出的不同要求。 a r a u s c h 等在研究中提出了多机器人系统不同层次的协调协作2 5 1 ，其中提到了： 异步协作关系、同步协作关系。 “ 对于异步协作关系的机器人，机器人之间的协调协作主要解决的是完成各自 在目标过程中产生的冲突和死锁。这些问题的发生通常存在不确定性，无法事先 准确地预知，这就需要在系统动态运行过程中采用一些方法来处理，包括：磋商 法、协作规则、优先级等。 对于同步协作关系的机器人，多个机器人要共同完成一个任务就必须解决任 务的分解、分配，资源的利用，冲突和死锁的处理等问题。在人工智能中，解决 类似问题的规划研究已取得大量成果，并成功应用于多机器入系统规划问题的研 究：通过经验知识，运用p e t r in e t 2 6 】等方法进行任务的分解；采用多智能体模型 2 7 1 、合同网、熟人模型、搜索算法等方法进行实时分配和最优分配；运用协作规 则、协议等方法进行实时的冲突、死锁监测及处理。 1 3 2 常见任务分类 2 0 世纪8 0 年代后期，多机器人系统的快速发展体现为三个方面的相互影响： 问题、系统和理论。为解决一个给定的问题，想象出一个系统，然后进行仿真、 构建，借用别的领域的理论进行协作。将这些实际应用中多机器人合作所面临的 任务加以抽象，列出了一些代表性的任务，这些任务可分以下几类： 7 北京工业大学工学硕士学位论文 - - = = = = i 曼曼皇曼曼曼曼曼曼曼皇曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼! ! 皇曼曼 ( 1 ) 交通控制 当多个机器人运行在同一环境中时，它们要努力避碰。从根本上说，这可以 看作是资源冲突的问题，这可以通过引进如交通规则【2 8 】、优先权或通信结构等来 解决。从另一个角度来看，进行路径规划必须考虑其它机器人和全局环境。这种 多机器人规划本质上是配置空间一时间中的几何问题。本课题中采用基于势场原 理的避碰规则口9 】，使机器人具备基本的避碰能力，不是研究的重点。 ( 2 ) 推箱子协作操作 许多工作是讨论推箱子问题的。有的集中在任务分配、容错和强化学习上， 而有的则研究通信协议和硬件。协作操作较大的物体也非常令人感兴趣，因为即 使机器人之间相互不知道对方的存在也可以实现协作行为。 ( 3 ) 搜集 它要求一群机器人去捡起散落在环境中的物体。这可以联想到有毒废物清 除，收割，搜寻和营救等。搜集任务是协作机器人学的规范的试验床。一方面这 种任务可以由单个机器人来完成，另一方面可以从生物学获得灵感来研究协作机 器入系统。解决方案有最简单的随机运动拾捡，还有将机器入沿着目标排成链型 队形将目标传递到目的地。在研究这类问题时，群体的体系结构和学习也是主要 的研究主题。 ( 4 ) 环境构建 一个很现实的问题，既是个体机器入对工作空间并不是预先就知道的。其中 一些任务可能需要机器人对环境进行有效的探测，构建出环境地图或者边构建地 图边执行任务，这就带来了多机器人系统环境，探测环境构建问题。 ( 5 ) 编队 队形的实现可以使得多机器人系统更加有效地完成任务。其包括队形形成和 队形控制两部分。队形形成主要研究如何使系统从一个杂乱无章的状态最终形成 一个整体具有规律性或者符合设计者要求的稳定状态 3 0 , 3 1 1 。而队形控制【3 2 ，3 3 , 3 4 1 主 要研究在机器人系统朝着目的地行进的过程中，既要遵循一定的队形约束，又要 适应当前工作环境约束( 如障碍物或空间物理限制) 的控制技术。是多机器人系统 典型性和代表性的研究问题之一。 ( 6 ) 围捕 该类问题也是目前很热的研究问题，它是由原先的队形控制问题中延伸出来 的。多机器人系统要完成的任务是在动态环境下利用机器人上的安装的有限能力 8 第1 荦绪论 ! ! 一 i i - - , , 曼曼曼曼曼量曼曼曼曼曼曼曼蔓曼皇曼曼皇量皇曼 的传感器进行无碰撞的搜索，最终实现对具有一定智能的动态未知对象的围捕 3 5 】。这对多个机器人的协作控制提出了很高的要求。 ( 7 ) 机器人足球赛 以上多机器人任务中，机器人之间的关系是合作的，互助的。而在机器人足 球赛中，不同球队的机器人之间的关系是对抗的、竞争的；同队的机器人之间则 是合作的，互助的。由于机器人足球赛的对抗性强，对个体间协作的实时性要求 高，因而是一个极具挑战性的课题【3 6 】。 1 4 多机器人系统有待解决的难题 由于多机器人系统的研究涉及到多个领域和学科，因此其发展也受到相关 学科和技术发展的限制除了感知能力、控制系统实现等硬件方面上的限制之外， 多机器人系统的一些问题在理论上也还没有得到很好的解决多机器人系统作为 一个研究领域，其理论框架和实现方法均需要得到进一步完善。目前多移动机器 人系统研究中有待解决的几个主要闯题如下： ( 1 ) 基于多机器人信息融合的环境感知与任务规划 多机器人系统可以利用分布式控制的特点，较好地解决单台机器人无法完 整地感知自身所处环境的问题但是，因为系统中每一台机器人自身的环境感知 能力仍然有限，因此，如何构建合理的信息框架，对各个机器人所感知到的环境 信息进行合理融合，并在此基础上进行任务规划和运动规划，是多机器人系统必 须解决的重要问题。 ( 2 ) 二l l z 完整运动约束对运动规划的影响 在实际应用中，大多数移动机器人具有非完整运动约束特性因此，机器人的 运动轨迹控制将受到限制，而不可能像进行计算机仿真时那样使机器人按照任 意给定的轨迹运动因此，当多机器人系统中存在具有非完整运动约束特性的移 动机器人时，必须充分考虑机器人自身的运动学特性对任务规划和运动规划带 来的影响和限制，并在此基础上找到最佳方案。 ( 3 ) 协调控制策略的选择 移动机器人的控制策略可以分为反应式和慎思式两种类型反应式控制方式 具有较好的实时性，但难以完成复杂任务慎思式控制方式可以完成复杂任务，但 往往实时性较差而对于多机器入系统来说，因为在大多数情况下系统中各个机 器人处于不同环境，如果仅仅依靠反应式控制方式，各机器人之间很容易出现相 互冲突的情况因此如何根据任务的具体特点，将反应式和慎思式这两种控制方 9 北京工业大学工学硕士学位论文 m l 式进行合理结合，并在此基础上进行任务规划和运动规划，将是多机器人系统研 究必须解决的重要问题。 ( 4 ) 多机器人系统的遥操作控制 由于机器人自身的智能程度难以达到完成复杂任务的水平，因此，对于许多 复杂任务来说，采用遥操作控制方式将是一种很好的选择虽然单机器人的遥操 作控制问题已经取得了许多研究成果，但是，对于多机器人系统来说，由同样数 量的操作人员同时进行操作显然不是一种很好的控制方式虽然在某些情况下可 以由多个操作人员同时进行操作因此如何解决由一个或儿个操作人员对多机器 人系统进行遥操作控制，使其能够很好地完成给定任务也是一个重要问题。 ( 5 ) 降低系统对通信速度的依赖 高性能多移动机器人系统应当具有良好的内部通信能力理想的情况是，系 统中所有的机器人之间都可以实现实时通信，从而使每台机器人都可以根据自 身和其它机器入的信息实时进行任务规划和运动规划但是，虽然近年来无线通 讯技术己经得到很好发展，但在目前的技术条件下，在多机器人系统中实现所有 机器人之间的点对点实时通讯还有较大困难这也是大多数多机器人系统仍然采 用集中通讯方式的主要原因因此，如何降低多机器人系统对通信速度的依赖程 度也是一个非常重要的问题。 ( 6 ) 基于实际系统的协调控制策略验证 多机器人系统协调控制策略理论研究方面已经得到了许多研究成果由于实 验条件的限制，许多理论和算法难以通过实际的多机器人系统进行验证因此，研 究人员往往在自己提出的假设条件下，通过计算机仿真对所提方法进行验证但 是，由于这些假设往往过于理想，在目前的技术条件下，实际的机器人系统很难 满足这些假设因此，如何根据机器人的实际情况，有效地利用已有的多机器人系 统理论和算法，也是一个急待解决的重要问题。 1 5 本文的主要研究内容及结构 1 5 i 主要研究内容 本文将多机器人系统协作控制算法设计分为了：任务分配、协调策略、运动 控制三个层面，认为协作策略制定是多机器人系统的研究核心。三个层面的问题 均通过具体的多机器人群体协作任务来展开研究：首先进行任务分析，随后研习、 借鉴相关的控制理论或数学方法，将其针对具体问题做了适当改进，最后通过仿 1 0 第1 苹绪论 真实验来验证算法的有效性。本文将用三章内容分别陈述这三个层面相关的研究 工作。另外，在多机器人仿真平台的设计开发方面也做了一个章节的内容描述。 1 5 2 论文内容安排 文章的结构是： 第一章：介绍了多机器人系统的主要特点和国内外发展状况，对多机器人系 统的研究内容及面临的难题做了相关的概述，最后简述了文章内容。 第二章：研究分析了多机器人的任务分类及分配机制，并结合角色切换以及 蚁群算法的思想，借助混杂自动机的描述形式，设计了任务分配机制，用以解决 多机器人系统搜集和搬箱子问题，并做了大量仿真实验和统计分析。 第三章：研究分析了q 学习在多机器人围捕任务中的应用价值，针对围捕 任务提出了新的学习空间的状态划分方法：队形矩阵划分法，大大缩小了学习空 间的维数，并据此设计了奖惩函数。最后做了相关的仿真实验及分析。 第四章：研究分析了非线性控制理论反馈线性化法在解决移动机器人跟随控 制系统中的解决途径。对于小脚轮在前驱动轮在后的，考虑非完整运动约束的移 动车跟随运动，建立了运动学模型，推导了控制律并证明其收敛性。随后制定了 一套基于x m l 描述语言格式的通讯协议用于实现移动车辆之间的数据传输。 第五章：分析介绍了c h 叫弋码编写的m u r o s 多机器人仿真软件的系统结构 和程序运行流程。概述了主要模拟控制函数，及根据任务需要扩充类库的方法。 北京工业大学工学硕士学位论文 第2 章多移动机器人系统的任务分配 多机器人系统在执行任务过程中首要解决的是任务的分配问题，也就是决定 将任务分配给某个或几个机器人去完成的问题。任务分配是整个多机器人系统运 行的基础，关系到系统如何完成任务，机器人之间怎样进行协调等问题，对系统 目标或性能等方面有决定性影响。合理的任务分配机制作，可以有效的解决完成 任务过程中可能出现的冲突、死锁等问题。 本文针对几个典型的多机器人协作任务问题，借鉴了混杂自动机的描述模型 和蚁群算法的思想，做了相关仿真和统计分析工作。 2 1 任务分配 2 1 1 任务分配的分类 根据实际问题条件不同，可以从不同角度对多机器系统任务分配问题进行 分类。文【3 7 , 3 8 , 3 9 从多个角度对多机器系统任务分配问题进行分类讨论。文 4 0 l 按多 机器系统任务是否能以直接、确定的方式完成将其分成简单任务分配和复杂任务 分配；根据系统中机器人功能结构的不同，可将机器系统任务分配分为同构系统 【4 1 4 2 4 3 1 和异构系统 4 4 , 4 5 , 4 6 , 4 7 1 任务分配；根据多机器人合作的动机，多机器系统任 务分配可分为涌现式和意图合作式两大类；目前研究比较多的是意图合作式任务 分配，意图合作式任务分配又可分为集中式任务分配和分布式任务分配：集中式 分配的多机器人系统中有一个机器人节点作为中央规划器，负责对其他机器人 进行任务分配；分布式系统通常没有全局规划器，没有全局c p u ，与集中式任务 分配相比，分布式任务分配在动态环境下更快、鲁棒性更强、更能适应环境的变 化。 2 1 2 任务分配的主要方法 机器人研究领域的学者们采用组合优化法、基于阈值的方法、基于市场机制 的方法、黑板模型法等对多机器人任务分配进行了研究。 ( 1 ) 组合优化法 简单的任务和机器人之间的组合优化问题用组合优化法就能解决，应用于 多机器人任务分配的组合优化法包括的线性规划法，匈牙利算法【4 8 】等， c a b e r e r t o n 采用线性规划方法解决多机器人协作探索中的任务分配 4 9 1 。 1 2 第2 犟多移动机器人系统的任务分配 ( 2 ) 基于阈值的动态分配 基于阈值的任务分配是一种用涌现式任务分配，该方法中每个机器人对每 个任务都有一个阈值，用激素反映任务的紧迫性和重要性，机器入不断感知任务 发出的激素。当感知的激素值超过对应的阈值，机器人执行该任务，而当感知的 激素值降低到低于阈值时( 如任务完成) ，机器人停止执行。该方法可用于大量功 能简单的机器人系统的任务分配，通信要求低，但效率不高。a g a g e 提出一种依 据情绪的雇佣方法来解决多机器人的任务分配问题 5 0 l ，每个机器人都有一定的 情绪值，用来表征其对任务的热情程度。初始时较低，当机器人接收到其他机器 人发布的任务时，检查自身情绪值，若高于设定阈值则响应该任务，否则不响应 该任务，但对该任务的情绪值增加，发布任务的机器人如果在一定时间内没有收 到响应消息，则再次发布任务，直到某个机器人响应该任务，该方法的优点是节 省通信带宽，甚至只需要单向通信，但其响应速度较慢，难以适应动态要求较高 的环境。 ( 3 ) 基于市场机制的任务分配 目前研究最多的基于市场机制的任务分配方法，该方法的基本思想是通过 合同协商实现任务分配，系统中的m a n a g e r 将任务分解成多个子任务，寻找合适 的c o n t r a c t o r 完成各项子任务。c o n t r a c t o r 依据自身能力作出评价，向m a n a g e r 提交标书，m a n a g e r 依据特定的仲裁机制( 通常为拍卖协议) 确定中标者，与其建立 合同关系，由其完成招标的子任务。这是一种典型的意图式任务分配方法，系统 中各个子系统以自私的方式，以子系统的局部指标最大化为目标进行优化控制。 市场算法最大的优点是计算简单，适合大量或未知数量的自私子系统之间协调 其交互活施子系统的任意增删对系统的控制都很方便【5 1 1 ，但其对通信的要求 较高。基于市场机制的任务分配中拍卖的任务可以是单任务也可以是多任务组 2 0 g ：l o ( 4 ) 黑板模型法 黑板的概念最早由n e w e l l 提出，2 0 世纪7 0 年代初期，c a r n e g i e m e l l o n 大学 提出黑板问题求解模型，并研制了一个黑板系统h e a r s a y i i 。黑板是一个共享 的工作空间，存在机器人需要的信息和执行任务过程中的环境状态数据，有时也 存放控制数据，在执行任务过程中，机器人不断的修改黑板，机器人之间的交互 只能通过黑板进行。 ( 5 ) 其他任务分配方法 很多学者针对不同领域任务分配特点，应用人工智能技术和智能计算方法 提出了一些颇具特色的任务分配方法。 1 3 北京工业大学工学硕士学位论文 l u i z 和m a r i o 等提出了基于动态角色切换的任务分配方式【5 2 1 。其在混杂系统 框架下建立了一个角色分配模型，用混杂自动机标识了角色、状态转变、连续控 制器等。在任务的执行过程中，个体机器人根据“黑板 消息，及个人意愿阈值 等决定是否切换角色执行相关角色任务。 丁滢颖 5 3 】等，则采用将蚁群算法用于解决搬箱子任务分配，任务中几个能 力相同的机器人( 同构) 独自搬动轻的物体，或引入“信息素 诱使队友合作搬动 重的物体。并针对任务执行过程中出现的“任务死锁”现象，提出了衰减因子， 防止了死锁的发生。 2 2 任务类型 机器人的任务可以从多个角度来分，其中从子任务的耦合程度角度来看，就 可以分为紧耦合和松耦合任务两种。 2 2 1 紧耦合任务 紧耦合任务由一个机器人无法完成，要求有多个机器人协作才能完成。为了 完成紧耦合任务，个体机器人通常得通过显式或隐式的通信方式知道队友的状态 和行动来实现最终的协作。任何一个机器人都是完成任务的关键，因为任何个体 机器入的失败都将导致任务的无法完成。紧耦合任务可以分为两类任务： ( 1 ) 不可分紧耦合任务 任务无法分解为由单个机器人完成的一串子任务的称为不可分紧耦合任务， 其必须通过多个机器人一起完成。多机器人合作搬箱子就是一个典型的不可分紧 耦合任务。在这个任务中所有机器人都只有一个共同的任务，就是将重物搬至目 标区域。 ( 2 ) 可分紧耦合任务 如果任务可以分解为一个个子任务，且各自任务之间有内部的关联，则称为 可分紧耦合任务。这些子任务不是相互独立的，是相互依赖的。一个典型的可分 紧耦合任务是m u r p h y 等人描述的博物馆派发铅笔任务【5 4 1 。在这个任务中，共有 两个机器人，其中一个承担服务员角色，另一个承担加料员角色。服务员和加料 员之间存在循环关联，服务员要依赖加料员的工作才能开展自己的工作，同样加 料员也要依赖服务员的工作才能开展自己的工作，具体表现为资源的传递，即任 何一个机器人必须等待其所需资源从另一个机器人传递过来才能继续自己的任 务。 1 4 第2 章多移动机器人系统的任务分配 2 2 2 松耦合任务 松耦合任务则是可以由一个机器人独立完成，但是在群体合作的情况下完成 的会更好。在执行松耦合任务过程中，个体机器人相互之间独立，并没有严格的 群体协作要求。也可大致分为两类： ( 1 ) 有内部顺序关联的任务 有内部顺序关联是指任务中两个或多个子任务在执行顺序上有先后关系，有 的子任务必须在其它子任务完成或达到一定进度后才能开始。从卡车上卸货任务 就属于有内部顺序关联任务。卡车卸货任务可以分为两个子任务：卸货和搬运。 搬运机器人必须等货物卸下以后才能搬运，如果地上没有货物，则搬运工作必须 等待，所以卸货任务和搬运任务有顺序上的关联，先卸货再搬运。 ( 2 ) 无内部顺序关联的任务 这类任务比较常见，它们的特点是任务可以分解成许多子任务，子任务之间 完全独立，执行子任务的机器人不需要任何配合，也不需要知道其他子任务的进 展。如多机器人看门、多机器人边界了望、多机器人搜集等等。这类任务基本上 有一个共同点，就是每个机器人的子任务其实就是全局任务的同比例缩小。此类 任务在现实当中非常普遍，它们将成为多机器人系统今后应用的一个主要领域。 2 3 实验设计与统计分析 本文针对两种任务类型，参照动态角色切换和蚁群算法制定任务分配机制。 为验证算法的可行性做了实验和分析。 2 3 1 任务描述 在多机器人搜集任务中机器人搜索整个环境寻找物品，并将物品送到指定的 目标区域( l u i z 5 5 】，d r o g o u l 和f e r b e r 5 6 】等学者对于这个任务做过相关研究) 。我 们假设有台搬运机器人和m 个物品随机的分布在一个