（计算机应用技术专业论文）基于强化学习的多机器人协作机制研究.pdf

摘要 基于强化学习的多机器人协作机制研究 摘要 机器人技术的发展使机器人的能力不断提高，机器人应用领域和 范围不断扩大。从自动化的装配工作到深海探测乃至火星探测等任务 都有机器人的身影。对于有些任务来说，单个机器人的能力是有限的， 因此必须把多个机器人组织起来才能完成特定的任务。对于由大量自 主机器人组成的群体，如果采用由设计者提供合适的控制参数使之形 成期望的协作行为，那是非常困难的。因此，整个机器人群体及群体 中的每个机器人都必须具有学习能力，从而优化系统性能，适应环境 变化。 强化学习是近几十年来迅速发展起来的一类机器学习算法。强化 学习不需要有先验知识，而是通过与环境的不断交互获得知识，改进 行为策略，具有自学习的能力。强化学习由于自身特点，在自主机器 人研究领域中受到了国内外越来越多的重视。 基于马尔科夫过程的强化学习作为一种在线学习方式，能够很好 地应用于单智能体环境中。由于强化学习理论的限制，在多智能体系 统中马尔科夫过程模型不再适用，因此不能把强化学习直接用于多智 能体的协作学习问题。本文提出了多智能体协作的分布式两层强化学 习方法。该方法主要通过在单个智能体中构筑两层强化学习单元来实 现，第一层强化学习单元负责学习智能体的联合任务协作策略，第二 层强化学习单元负责学习在本智能体看来是最有效的行动策略。最后 用3 个智能体协作抬起圆形物体的实验来验证该方法，实验结果表明 所提出方法比集中式强化学习方法更好。 在基于强化学习的多智能体环境下，评价一个智能体行为的效果 和其他智能体的行为是密切相关的，如果每个智能体都能够通过预测 其他智能体的行为再来采取自己的行为，则必将大大促进整个系统的 协作。在传统强化学习方式中引入组合动作的基础上，本文提出了一 种基于行为预测的多智能体强化学习方法，研究了对其他智能体行为 进行预测的几种可行方法。实验结果表明，引入组合动作的传统强化 学习方法是收敛的，行为预测方法能有效促进协作。 关键词：强化学习，多智能体，协作，行为预测 l i 英文摘要 r e s a r c ho n t i r o b o tc o o p e r t l 0 n 匝c h a n i s mb a s e do nr e i n f o r c e m 匝n tl e a r n i n g a b s t r a c t w i t ht h ed e v e l o p m e n to fr o b o t i c s ，t h ec a p a b i l i t yo far o b o ti sb e c o m i n gm o r e p o w e r f u l t h ea p p l i c a t i o n o fr o b o t i c sh a se x t e n d e di n t o m a n yd o m a i n s ，f r o m a u t o m a t i ca s s e m b l yt od e e ps e ae x p l o r a t i o n ，m a r se x p l o r a t i o na n ds oo n t h e r ea r e s o m es p e c i a l i z e dt a s k sw h i c hs i n g l er o b o th a sn o te n o u g hp o w e rt oc o m p l e t e ，b u t m u l t i p l er o b o t sc a nb eo r g a n i z e dt oc o m p l e t e ri sv e r yd i f f i c u l tf o rt h ed e s i g n e rt o p r o v i d ep r o p e rc o n t r o lp a r a m e t e r sw h i c h c a l lb eu s e dt oh e l pt h em u l t i r o b o ts y s t e m c o n s i s t i n go fm a n ya u t o n o m o u sr o b o t sw o r kc o o p e r a t i v e l y t h e r e f o r e ，i ti sh i g h l y d e s i r a b l ef o rm u l t i r o b o ts y s t e ma n de a c hr o b o tt ob ea b l et ol e a r nc o n t r o lp a r a m e t e r v a l u e si no r d e rt o o p t i m i z e t h e i rt a s k p e r f o r m a n c e ，a n dt oa d a p t t o d y n a m i c e n v i r o n m e n t r e i n f o r c e m e n tl e a r n i n g ，ak i n do fm a c h i n el e a r n i n ga l g o r i t h m ，h a sr e c e i e v e d m u c ha t t e n t i o ni nr e c e n tt e ny e a r s r e i n f o r c e m e n tl e a r n i n gd o e sn o tn e e dp r i o r i k n o w l e d g e a n d i m p r o v e s i t sb e h a v i o r p o l i c yw i t hk n o w l e d g e o b t a i n e db yi n t e r a c t i o n w i t ht h ee n v i r o n m e n t s or e i n f o r c e m e n t l e a r n i n gh a s t h ea b i l i t yo f s d f t e a m i n g r e i n f o r c e m e n t l e a r n i n g h a sb e e n a p p l i e d t o s i n g l ea g e n t e n v i r o n m e n t s u c c e s s f u l l y d u e t ot h et h e o r e t i c a ll i m i t a t i o nt h a ti ta s s u l l l e st h a ta ne n v i r o n m e n ti s m a r k o v i a n ，t r a d i t i o n a lr e i n f o r c e m e n t l e a r n i n ga l g o r i t h m sc a n n o tb ea p p l i e dd i r e c t l yt o m u l t i a g e n ts y s t e m i n t h i s p a p e r ，t w o l a y e rr e i n f o r c e m e n tl e a r n i n g m e t h o df o r m u l t i a g e n tc o o p e r a t i o ni sp r e s e n t e d t h i sm e t h o di s r e a l i z e db ya d d i n gt w o l a y e r r e i n f o r c e m e n tl e a r n i n gu n i tt oe v e r ya g e n t t h ef i r s tl a y e ri sf o rl e a r n i n gg l o b a l 1 1 1 英文摘要 c o o p e r a t i o ng a m e ，a n dt h es e c o n dl a y e ri sf o rl e a r n i n ge f f i c i e n ta c t i o ng a m ei ni t s o w nv i e w a ne x p e r i m e n tt h a tt h r e e a g e n t sr a i s ear o u n do b j e c tb yc o o p e r a t i o ni s m a d et ot e s tt h e e f f i c a c yo f t h em e t h o d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e a g e n t s u s i n g t h i sm e t h o dc o o p e r a t eb e t t e rt h a nt h e a g e n t su s i n g c e n t e rr e i n f o r c e m e n t l e a r n i n g i nm u l t i a g e n ts y s t e mb a s e do nr e i n f o r c e m e n tl e a r n i n g ，t h ee v a l u a t i o nt ot h e b e h a v i o ro far o b o t d e p e n d s o nt h eo t h e r a g e n t s b e h a v i o r sc l o s e l y i fe a c ha g e n tt a k e s i t sa c t i o na f t e ri tp 蒯c t st h eo t h e ra g e n t s a c t i o n ss e l f - c o n s c i o u s l y ，t h ep e r f o r m a n c e o ft h ew h o l es y s t e mw i l lb eb e t t e r i nt h i s p a p e r ，m t r o d u c m gj o i n t - a c t i o nt o t h e t r a d i t i o n a lr e i n f o r c e m e n t l e a r n i n g ，a n e w m u l t i - a g e n t r e i n f o r c e m e n t l e a r n i n g a l g o r i t h m b a s e do nb e h a v i o r p r e d i c t i o n i s p r e s e n t e d a n ds e v e r a lm e t h o d sf o r p r e d i c t i n go t h e ra g e n t s b e h a v i o r sa r ed i s c u s s e d t h ee x p e r i m e n tr e s u l t ss h o wt h a t j o i n t a c t i o ni sa p p l i e di nt h et r a d i t i o n a lm i n f o r c e m e n tl e a r n i n gs u c c e s s f u l l ya n dt h e c o o p e r a t i o np r o c e s s c a nb e s p e e d e db y b e h a v i o r p r e d i c t i o n k e y w o r d s ：r e i n f o r c e m e n t l e a r n i n g ，m u l t i - a g e n t ，c o o p e r a t i o n ， b e h a v i o r p r e d i c t i o n 第一章绪论 1 1 研究背景 第一章绪论 机器人技术集机械、材料、计算机、人工智能、传感器、信息处理和通信等 技术于一体，是最新科技水平的重要标志之一。机器人学的研究工作经历了从简 单到复杂，功能单一到功能多样，从工业制造领域扩展到军事侦察、核工业、航 空航天、服务业、医疗器械、基因工程等各个领域的过程。国内外对机器人技术 广泛深入的研究，不但是由于机器人具有广阔的应用领域，而且是这一研究可以 带动和促进相关技术的全面进步。 多机器人技术是机器人研究中的一个重要领域，它在计算机集成制造系统、 柔性制造系统、具有繁重、复杂装配作业的系统和自动化工厂中有十分广泛的应 用前景，它是新一代制造系统一智能制造( 蛆) 系统中的关键技术之一。 自主机器人组成的多机器人群体协作行为( c o o p e r a t i v eb e h a v i o r ) 的研究越来 越受到关注，因为对某些任务，用一台机器人去完成显然过于复杂，甚至不能 实现，通过多个机器人协作则可以顺利地完成任务：用多机器人协作完成任务， 还可以简化机器人个体的设计，方便制造，降低机器人个体价格；多机器人系 统还具有更大的柔性、可扩展性和容错能力。与单个机器人相比，多机器人集 群具有更灵活的组织结构，具有可重组性和自适应性等显著特点，在执行动态 环境下的复杂任务时，协作的自主式机器人群体较传统的单个复杂机器人系统 具有更大的优越性，而且有的时候开发单个复杂机器人往往比开发多个简单机 器人组成的系统更加困难和昂贵。同时，随着机器人生产线的出现及柔性加工 工厂的需要，使多机器人系统进行自主作业的愿望越来越强烈。 自主多机器人协作的主要研究内容和方向。1 为：多机器人群体的体系结构 ( g r o u pa r c h i t e c t u r e ) ，资源冲突( r e s o u r c ec o n f l i c t ) ，协作根源( o r i g i n o f c o o p e r a t i o n ) ，学( l e a r n i n g ) ，几何问题( g e o m e t r i cp r o b l e m ) 等。其中如何组织多 第一章绪论 个机器人群体，在群体中如何实现多机器人的协作( c o o p e m t i o n ) 是当前多机器人 学研究领域的前沿和新课题，具有重要的理论和现实意义。 近年来，通过自学习来达到多机器人群体的协作已成为新的研究热点。这个 研究方向的关键问题是要用学习技术增强机器人的群体智能，改善机器人的行为 策略，来达成协作。在许多学习方法中，强化学习方法得到了广泛关注。近年来， 关于强化学习的课题得到了美国国家科学基金、美国国防部及美国海军、空军研 究办公室的资助。另外，日本、德国、澳大利亚和韩国等国都在开展有关强化学 习的理论和应用研究。本文将对利用强化学习来达成多智能体机器人的协作展开 研究。 1 2 多智能体机器人协作的研究综述 当前，国内外在多机器人系统的研究中，普遍借鉴了人工智能领域中的多智 能体系统( m u l t i a g e n ts y s t e m ，m a s ) 理论，其基本思想是积聚多智能体系统的特 性组织控制多个机器人，使系统具有能协作完成任务的能力，其要点是把系统中 的每机器人看作独立的智能体。因为机器人的行为( 能力) 是由它具有分析决策 能力的“大脑”软智能体( 即机器人a g e n t ) 决定的，多机器人的协作策略 也存在于各机器人的“大脑”中，多机器人系统本质上由多机器人智能体系统驱 动，因而多机器人智能体系统可以与m a s 有非常类似的拓扑结构、组织方式和 运行机制，只不过是二者的a g e n t 的行为方式不一样。所以在一定程度上，我 们可以把单个智能体( a g e n t ) 和单个机器人等同起来。 多智能体系统理论是一种抽象层次较高的普遍理论，它可追溯到7 0 年代的 分布式人工智能及以后的分布式问题求解，其概念、体系结构、协调与合作方式 和策略等的研究已取得了大量成果，但大部分都是在抽象层次上。尽管如此，多 智能体系统理论的核心是把整个系统分成若干智能、自治的子系统，它们在物理 和地理上可以分散，可独立地执行任务，同时又可通过通信交换信息，相互协调， 从而共同完成整体任务，这无疑对完成大规模和复杂的任务是富有吸引力的，因 而很快在军事、通信及其他应用领域得到了广泛的重视。 8 0 年代以来，多机器人协调作为一种新的机器人应用形式日益引起国内外 2 第一章绪论 学术界的兴趣与关注，1 9 8 7 年在美国圣地亚哥召开的多机器人协调研讨会上， 提出了多机器人协调研究的主要问题。在过去的1 0 多年里，人们对多机器人协 调控制中的协调和集中、负载分配、运动分解、避碰轨迹规划、操作柔性体等问 题进行了大量的研究。 到目前，多机器人系统的研究大致可以划分为传统多机器人系统和仿生多 机器人系统。传统多机器人系统的主要特点是机器人在高度结构化的环境下执 行预先规划的动作序列“1 ，体系结构有集中型和分散型。集中型多机器人系统一 般都有一个集中规划器，根据各机器人和环境信息进行各机器人行为规划5 1 ，其 缺点是集中规划器要对每一机器人的行为进行规划，计算任务繁重，往往无法 在线规划；当环境变化或有某一机器人发生故障时，所有机器人的行为必须重 新规划；获取准确的环境信息困难。为克服集中规划的缺点，提出了分布型多 机器人系统嘲，但所提出的系统结构不能随环境的改变而变化。 自7 0 年代以来，分布式人工智能对多智能体协调和相互作用进行了积极研 究；8 0 年代末开始，随着c e b o t 、s w a r m 、a c t r e s s 和g o f e r 等项目的展 开，协作机器人学的研究更加活跃，出现了仿生机器人系统。仿生机器人的研 究主要沿着两个方向：机器人群体中个体结构的可重构仿生进化设计和多机器 人系统协作行为的进化研究。在机器人个体的进化设计方面。日本名古屋大学 的f u k u d a 进行了十多年的研究；美国马萨诸塞州布兰代斯大学的l i p s o n h 等发 表于自然杂志的论文”1 代表该领域研究的最新、最高水平。1 9 9 6 年我国自 然科学基金项目指南高技术探索第1 2 主题中也曾列上“仿生机构的基本原理研 究与探索”。但是，由于仿生机机器入需要研究的问题太多，难度太大，国外的 研究也没有取得期望的进展：我国自然科学基金项目指南中，自1 9 9 7 年开始已 删去了这一主题。 但是，基于生物进化原理，对机器人个体不是仿生进化设计的多自主机器 人群体协作行为的研究却随着分布式人工智能、多智能体协作等研究的新进展 而受到更大的关注。我国2 0 0 1 年国家自然科学基金指南已将“机器学习与进化 机器人”列为鼓励研究领域。 多机器人系统的群体体系结构是研究多机器人协作行为的基础，它决定了多 机器人系统的整体性能，决定了一个机器人识别和建模其它机器人的能力，决定 第一章绪论 了机器人问相互通信的结构。群体体系结构是指系统结构是集中的还是分散的； 若是分散的，则是分层的还是分布的；还有各机器人是同构的还是异构的等等。 在分布结构中，所有机器人相对于控制是平等的；而分层结构是局部集中的，存 在局部控制智能体。集中式系统协作效率比较高，但实时性、动态特性差：分散 式系统中，个体高度自治，容错能力、可靠性和可扩展性好，但协作较困难。根 据单个机器人结构的划分是否服从笛卡尔方法，分为基于行为和基于功能的体系 结构。基于行为的结构有灵活的反应能力，有利于完成实时任务，但几乎没有智 能”1 ；基于功能的结构对外界反应不够灵敏，反应速度慢，但规划和推理能力强。 多机器人群体中机器人间的通信联系是实现多机器人群体协作行为的必要 条件。智能体机器人间相互作用的通信结构主要有无明显通信机制模式和有明显 通信机制模式。基于共享存储器的“无通信协作”州，智能体间通过传感器进行 局部相互作用的“亲戚辨认”( k i nr e c o g i l m o l l ) 方法“，基于视觉传感的相互作用 实现方法等是无明显通信机制的方法。通过明显的通信机制实现相互作用是最活 跃的研究方法之一，w a n g 等做了系列研究工作3 。 自从研究者将人工智能中的多智能体理论应用到多机器人系统的研究中后， 展开了多机器人系统理论研究的新局面。但无论是国际上还是国内，对多机器人 系统的研究很多还依赖于建立某种复杂的体系结构或者数学模型，然后基于这种 对问题的精确定义来实现机器人群体的协作行为。由于环境中存在着许多的随机 因素，这些随机因素对机器人影响很大，所以这种复杂而精确的系统定义必然由 于忽视随机因素的存在而导致系统的难以设计和实现，以及在鲁棒性、柔性、自 适应性等方面的欠缺。近年来国内外的很多学者都意识到了这个问题，转而尝试 应用人工神经网络、遗传算法、以及强化学习等非精确性的随机学习方法来获得 系统的满意解，这些基于计算智能的方法无需建立精确的数学模型“”，允许机器 人通过学习进化自己找到一个能够满足实际需要的解决问题的方法，并可以记住 己获得的经验进行学习，从而实现系统的鲁棒性、柔性、自适应性以及通用性， 成为机器人学的新研究点。 学习机制问题已经成为多机器人协作的一个重要问题。对于由大量自主机器 人组成的群体，如果采用由设计者提供合适的控制参数使之形成期望的协作行 为，那是非常困难的。因此，整个机器人群体及群体中的每个机器人都必须具有 4 第一章绪论 学习能力，从而优化系统性能，适应环境变化。强化学习为多机器人群体行为的 研究提供了一条新途径“”。除多机器人协作的强化学习“，两个机器人推箱 f b o x p u s h i n g ) 的强化学习“”，简单的人工机器人语言的强化学习“”等研究工作 外，w i n f r i e di 等采用强化学习使六足昆虫机器人学习六条腿的协调动作“。 此外，欧洲一些大学及研究机构的机器人学者也在对多机器人协作系统进行 研究。在协作机器人研究中，目前以移动机器人为背景进行研究的文献“8 。1 比较 多，包括规划、避碰、行进编队、推箱问题、搜索问题等，而基于系统全局的高 层组织及协作机制等实际应用方面的文献较为少见。可见，协作机器人要真正走 向人类的生产和生活还有很长的一段路要走。 1 3 强化学习的发展与应用概况 1 3 1 强化学习的发展历史 强化学习是人工智能领域中既崭新又古老的课题，它是从动物学习、参数扰 动自适应控制等理论发展而来。其研究历史可划分为两个阶段：第一阶段是5 0 年代至6 0 年代，可以称为强化学习的形成阶段；第二阶段是8 0 年代以后，可称 为强化学习的发展阶段。 在第一阶段，“强化”和“强化学习”这些术语由m i n s k y 首次提出并出现在 工程文献上1 。当时数学心理学家探索了各种计算模型以解释动物和人类的学习 行为。他们认为学习是随机进行的，并发展了所谓的随机学习模型。”。w i d r o w ， h o f f 年nr o s e n b l a t t 这些神经网络先驱们，以及心理学家b u s h 和m o s t e l l e r 等都研 究过强化学习。他们利用了“奖励”和“惩罚”这样的术语，但他们的研究系统 越来越趋向于监督学习。“”2 ”。在控制理论中，由w a l t z 和付京孙于1 9 6 5 年分 别独立提出这一概念o “。在应用方面，最早的应用例子是s a m u e l 的下棋程序， 该程序采用类似值迭代、瞬时差分和q 学习的训练机制，来学习用线性函数表 示的值函数。”。w i d r o w 及其同事们在研究监督学习时，认识到监督学习和强化 学习之间的不同，并于1 9 7 3 年w i d r o w ，g u p t a 和m a i t r a 改正了w i d r o w h o f f 监 督学习规则( 常称为l m s 规则) 。新规则可实现强化学习，即根据成功和失败的 第一章绪论 信号进行学习，代替原来的使用训练样本进行学习。他们用“有评价的学习”一 词代替“有教师的学习”1 。s a r i d i s 把强化控制系统的控制器看成一个随机自动 机”1 ，首次系统地提出了采用强化学习来解决随机控制系统的学习控制问题的方 法。 在六七十年代，强化学习研究进展比较缓慢，对强化学习的研究与监督学习 混淆在一起，强化学习的研究进入低谷。进入8 0 年代以后，随着人们对人工神 经网络的研究不断地取得进展，以及计算机技术的进步，人们对强化学习的研究 又出现了高潮，逐渐成为机器学习研究中的活跃领域。 b a r t o 于1 9 8 3 年介绍了强化学习在实际控制系统中的应用情况，他采用了两 个单元a s e ( a s s o c i a t i v es e a r c he l e m e n t ) 及a c e ( a d a p t i v e c r i t i ce l e m e n t ) ，构成了一 个评价控制系统，经过反复学习，使倒摆维持较长的时间。实际上这一思想就是 强化学习中的a h c ( a d a p t i v eh e u r i s t i cc r i t i c ) 算法的早期形式“。之后，s u t t o n 于 1 9 8 4 年，在他的博士论文中提出了a h c 算法，比较系统的介绍了a h c 思想。 文中采用两个神经元形式，对不同的算法进行了大量实验。1 。另外，s u t t o n 于 1 9 8 8 年在 m a c h i n el e a r n i n g ) ) 上发表了题为“l e a r n i n g t op r e d i c tb yt h em e t h o d s o f t e m p o r a ld i f f e r e n c e s ”著名论文啪1 ，可以说这是一篇经典之作。文中提出了瞬 时差分t d ( t e m p o r a ld i f f e r e n c e s ) 方法，解决了强化学习中根据时间序列进行预测 的问题，并且在一些简化条件下证明了t d 方法的收敛性。d a y a n 对t d 方法的 收敛性作了进一步的证明。“。许多学者对t d 法进行了分析和改进。2 。“1 。 在强化学习方法中，另一个比较著名的算法，就是w a t k i n s 等人提出了的q l e a r n i n g ”。w a t k i n s 对ql e a r n i n g 方法的收敛性进行了证明这被称为是强化 学习理论发展的一个里程碑。j i n g p e n g 及w l i l i a m s 等人提出了多步的q l e a r n i n g 方法；s z e p e s v a r 在一定条件下证明了q 学习的收敛速度汹1 。s i n g h 提出了替 ( r e p l a c i n ge l i g i b i l i t yt r a c e s ) 计算方法并对替换迹进行了理论分析，证明了 替换迹具有学习速度快而且也比较可靠的特点“。s c h w a r t z 、m a h a d e v a n 等采用 非折扣性能评价的方法来选择动作策略，并提出了平均奖赏值的方法r l e a r n i n g 的方法m t “3 。t a d e p a l i 等提出了基于模型及平均强化值的hl e a r n i n g 方法，通过 对自主导引车的试验研究，表明该算法收敛较快，也具有较好的鲁棒性”。 国际期刊m a c h i n el e a r n i n g ) ) 分别在1 9 9 2 年和1 9 9 6 年出版了强化学习的 6 第一章绪论 专辑，登载了数篇强化学习的理论研究论文，其中黜c h a r ds u t t o n 于1 9 9 2 年编辑 的第一个专刊标志着强化学习发展成为机器学习领域的一个重要组成部分。 r o b o t i c sa n da u t o n o m o u ss y s t e m ) ) 在1 9 9 5 年也出版了强化学习的专辑，主要 介绍关于强化学习在智能机器人上的应用情况。 从国内情况看，强化学习己处于发展应用阶段。t 9 9 6 年，阖平凡在信息 与控制上发表综述文章，论述了强化学习的原理、算法及其在智能控制中的应 用。他还提出了基于可靠度优先的强化学习算法，并研究了其在过程控制上的 应用。杨璐采用强化学习中的t d 算法对经济领域的预测问题进行研究“”。蔡自 兴采用强化学习方法对非线性系统控制问题进行了仿真试验“”。张汝波对基于强 化学习的智能机器人避障行为的学习方法进行研究“钉。蒋国飞将q 一学习应用于 蓟摆控制系统，并通过对连续空桶的离散化，证明了在满足一定条件下q 一学习 的收敛性。张健沛等对连续动作的强化学习方法进行了研究，并把它应用到机 器人避碰行为中去“”。李春贵等为求解大状态空间的强化学习问题，把状态聚类 的方法引入到强化学习率。 1 3 2 强化学习的应用现状 强化学习已在机器人的学习、自动控制系统、游戏比赛、调度管理等领域中 得到了广泛的应用，而且正日益受到重视。 1 在控制系统中的应用 倒摆控制系统是强化学习在控制中的应用的典型实例。倒摆控制是一个非线 性不稳定系统，许多强化学习的文章都把这一控制系统作为验证各种强化学习算 法的实验系统嘲_ ”，”1 。当倒摆保持平衡时，得到奖励，倒摆失败时，得到惩罚a 例如在b a r t o 的实验系统中，a s e 、a c e 两个神经元，通过多次的反复实验学习 使得倒摆的平衡时间达到几十分钟；w i l l i a m s 等人采用q 学习算法对倒摆系统进 行实验研究，并与a h c 方法进行了比较分析嘲1 。强化学习另一个应用领域是在 过程控制方面，采用强化学习方法不需要外部环境的数学模型，而是把控制系统 的性能指标要求直接转化为一种评价指标，当系统性能指标满足要求时，所施控 7 第一章绪论 制动作得到奖励，否则，得到惩罚。控制器通过本身的学习，最终得到最优的控 制动作。文献1 5 6 】以d y n a q 学习结合b p 神经网络给出了一个生物反应控制 实例；文献 5 7 】以二自由度的机械手控制为例，研究了强化学习在非线性系统自 适应控制上的实用方法；文献 5 8 】采用硬件实现一种动作评价随机学习方法，成 功地完成了插栓入孑l 任务和小球平衡器的控制任务。 2 在游戏比赛中的应用 游戏比赛在人工智能领域中始终是一个研究的问题，许多学者也正研究把强 化学习理论应用到游戏比赛中。如动物觅食游戏。”等。在应用方面，最早应用的 例子是s a m u e l 的下棋程序，近来，t e s a u r o 把瞬时差分法应用于b a c k g a m m o n 这 就是著名的t dg a m m o m 。b a c k g a m m o n 大约有1 0 2 。个状态，t e s a u r o 采用三层 b p 神经网络把棋盘上的棋子位置与棋手的获胜率联系起来，通过训练取得在4 0 盘比赛中负l 盘的战绩呱“3 。 3 在调度管理中的应用 调度是一个随机优化控制问题的例子，具有很大的经济价值。c r i t c s 和b a r t o 将强化学习算法用于一个4 个电梯、1 0 层楼的系统中。每一个电梯都有各自 的位置、方向、速度和一系列表示乘客要离开的位置状态。这个系统的状态集合 将超过1 0 z z 个，用传统的动态规划方法( 如值迭代方法) 很难管理。即使每回溯一 个状态只要一秒钟，回溯集合中的所有状态也需约1 0 0 0 年的时问。c r i t e s 和b a r t o 采用平均等待时间的平方作为电梯调度算法的性能，用反传算法训练表示q 函 数的神经网络，与其他算法相比较，强化学习更加优越。另外，强化学习在蜂窝 电话系统中动态信道分配”及机器调度问题上都有应用。 4 在机器人行为学习中的应用 强化学习作为一种在线学习方法，目前应用最多，也比较合适的在于机器人 领域，近年来国际上兴起了把强化学习应用到智能机器人行为学习的领域，其中 包括单个自主机器人行为的学习和多个机器人群体行为的学习。本文将在下一节 详细讨论强化学习在多智能体机器人领域中的研究情况。 第一章绪论 1 4 强化学习在多智能体领域的应用情况 通过学习实现多智能体系统的协作，在当前人工智能领域里正日益受到关 注。强化学习已成为在多智能体系统中协调各智能体行为的通用手段。由于强化 学习的鲁棒性和通用性，该技术已经广泛用于智能控制领域等。在机器人方面， 一方面可以采用强化学习实现智能机器人底层的基础控制：另一方面，也可以采 用强化学习实现自主机器人的高层的行为学习，如机器人的路径规划、动作学习 等，同样，可以采用强化学习用于多智能体机器人的协作学习。 1 4 1 强化学习在多智畿体机器入中的研究现状 强化学习在多智能体环境中的应用的研究已经引起了越来越多的关注，近年 来，在其理论、方法和技术方面进行了全面的研究。例如，m a t a r i c 在多机器人 中使用了强化学习，通过行为和它们关联的条件最小化状态空间，形成了具有利 用专门领域知识的不同强化函数和进度估计的强化学习，并通过4 个协作觅食的 移动机器人得到验证“”。w i n f r i e d 等采用强化学习使六足昆虫机器人学习六条腿 的协调动作“”。s a c h i y oa m i 和k a t i as y c a r a 在基于利益共享的多智能体系统中 引入强化学习来解决动态环境中的规划和资源冲突问题，使得多智能体系统达到 平衡阳1 。y a s u o 等通过在智能体内部对其他智能体的行为建模，提出了两个智能 体的协作方法1 。 从强化学习在多智能体中的应用研究情况来看，国内对强化学习的应用还是 比较多的。王立春等在2 0 0 1 年把强化学习用于智能体协商过程，使得系统能够 获得动态协商环境下的最优协商解。罗青等研究了在机器人足球这样的复杂、 动态的环境中使用强化学习的方式与问题，阐述了强化学习的实现及如何处理机 器学习中的常见问题，即延迟奖赏、探索与利用、不完整信息等，同时探讨了减 少复杂性的若干措施“。高阳等对基于m a r k o v 对策的多智能体强化学习模型进 行了研究，提出了元对策强化学习的学习模型和元对策q 算法1 。蔡庆生等对 基于智能体团队的强化学习模型和应用进行了研究，引入了主导智能体的概念， 9 第一章绪论 用主导智能体作为团队学习的主角，并通过主导智能体的角色变换实现了整个团 队的学习呐1 。孟伟等研究了强化学习在机器人足球中的应用，实现了多智能体在 对抗环境下的协同工作”。李晓萌等研究了基于强化学习的多智能体系统，提出 了改进的q 学习算法用于协调学习“。顾国昌在多智能体群体强化学习方法中 引入了预测方法，大大缩小了空间存储规模”。 1 4 2 有待解决的问题 从国内外的研究状况看，强化学习在研究多智能体机器人协作行为时存在以 下几个方面的问题： 1 1 组合爆炸和学习速度的问题。强化学习收敛速度较慢，尤其在搜索空间 较大时更为明显。强化学习的目的是在状态空间和动作空间中找到优化的映射关 系。在有多个机器人组成一个协作群体时，由于学习空间的规模是智能体个数的 指数函数，则智能体个数略多就会使得学习速度慢得不能忍受，这就是组合爆炸 的问题。 2 ) 非马尔可夫问题。传统的强化学习算法基于环境是一个马尔可夫决策过 程的假设。而在多智能体环境中，在单个智能体看来包含了其他智能体的环境是 非马尔可夫过程，使得强化学习算法的学习效果不好，甚至不收敛。 3 ) 连续状态和连续动作问题。通常研究的强化学习系统，其状态和动作都 认为是有限的集合。而在实际问题中，其状态和动作往往是连续的，而连续空间 的强化学习问题，目前还没有一个很好的解决方法。 1 4 3 解决问题的途径 近年来，围绕上述问题学者们展开了一系列的研究工作，提出了多种解决方 法。例如，m a t a r i c 在多机器人中使用了强化学习，通过行为和它们关联的条件 最小化状态空间，形成了具有利用专门领域知识的不同强化函数和进度估计的强 化学习，并通过4 个协作觅食的移动机器人得到验证“”。p i a o 等通过引入动作选 择优先级和规则集的方法，大大减少了机器人动作空间的大小，提高了学习的速 1 0 第一章绪论 度”“。l i t t m a n 运用马尔科夫对策( m a r k o v g a m e s ) 第一个提出了群体强化学习方法 ( r e i n f o m e m e n tl e a r n i n gi ng r o u p s ，r l o ) 3 ，该方法通过把对策论( g a m et h e o r y ) 引入到强化学习中，使强化学习能应用于准马尔科夫( m d p 1 i k e ) 环境，并于1 9 9 6 证明了此算法的收敛性。此后有很多研究者围绕这方面的问题展开了研究，但是 都偏重于考虑非合作的智能体间的交互。顾国昌等在r l g 算法中引入了预测的 方法，大大减小了r l g 学习空间的维数口2 1 。有一些研究者利用神经网络的泛化 能力来简化状态空间到动作空间的映射关系，加快学习。例如，t o u z e t 采用自组 织映射网络来改进q 学习算法，减少了空间存储，并在自主机器人的避障实验 中取得成功的应用”。 1 5 本文研究内容及论文安排 1 5 1 研究内容 本文研究的课题来自省基金项目，主要研究把强化学习方法应用于多个自主 机器人使之形成协作，从而来解决一些单个机器人无法完成而只能由多个自主机 器人协作完成的任务。具体的协作任务是3 个机器人协作抬起一个圆形物体。提 出的方法经过实验表明是有效的，有实际应用的前景。 1 5 2 论文安排 本论文共分六章，按如下方式组织： 第一章绪论，介绍了本研究课题的目的和意义，综述了多智能体机器人系 统研究现状，着重分析了强化学习在多智能体机器人中的应用现状，最后提出了 论文的主要工作内容。 第二章多智能体系统基本理论，介绍了智能体的基本定义和体系结构，分 析了多智能体的组织方式，讨论了几种有代表性的多智能体系统协作方法。 第三章强化学习理论及算法，阐述了强化学习的基本原理和模型，分析了 第一章绪论 强化学习的特点，给出了强化学习的组成要素，并讨论了几种代表性的强化学习 算法。 第四章多智能体分布式两层强化学习协作方法，在分析目前存在问题的基 础上，提出了多智能体协作的两层强化学习方法，详细给出了该方法的实现，并 用实验验证了实际性能。 第五章基于行为预测的多智能体强化学习协作方法，提出了基于行为预测 的多智能体强化学习协作方法，比较了预测最大型、等概率预测型和基于分布律 假设检验的最大预测型等三种行为预测方法。 第六章结束语，总结了本论文的工作，并对进一步的研究方向作了展望。 第二章多智能体系统基本理论 第二章多智能体系统基本理论 2 1 智能体( a g e n t ) 的定义 “a g e n t 这一术语已在诸多研究领域被广泛使用，但是时至今日人们也难以 给出一个能被普遍接受的定义。著名学者h e w i t t 曾指出：“什么是a g e n t ”对于 基于a g e n t 的计算来说是个尴尬的问题，就像在人工智能主流研究中“什么是智 能”这个问题一样。著名a g e n t 理论研究者w o o l d r i d g e 和j e r m i n g s “在总结了前 人在a g e n t 领域的一些工作后认为，可以从广义和狭义，也就是所谓的a g e n t 的“弱定义”和“强定义”这两个方面去理解a g e n t 的特性。 2 1 1 a g e n t 的弱定义 这是从广义的角度来理解a g e n t 的特点。一般地，可以把一个具有一定目的， 能够在分布式环境中独立自主、持续运行的计算实体称为a g e n t 。通常情况下， a g e n t 都具有以下几个主要特点“”： ( 1 ) 自治性( a u t o n o m y ) ：a g e n t 一般都具有自己的资源和局部于自身的控制机 制，能够在没有外界直接操纵下，根据自身的内部状态以及感知的外部环境信息， 决定和控制自身的行为。 ( 2 ) 社会性( s o c i a l i t y ) ：a g e n t 能够通过某种a g e n t 通信语言与其他a g e n t 进 行各种各样的交互，也能和其他各类a g e n t 一起有效地完成各种层次的协同工 作。 ( 3 ) ) 觥( r e a c t i v i t y ) ：a g e n t 能够及时地感知其所在外部环境的变化，并能 够针对一些特定的时间做出相应的反应。无论智能体生存在现实的世界中( 如机 器人，i n t e r n e t 上的通讯智能体、用户界面智能体等) 还是虚拟的世界中( 如虚拟商 场中的智能体、交互式游戏中的智能体等) ，他们都应该可以感知它们所处的环 境，并通过行为改变环境。一个不能对环境变化作出影响的物体不能被称为智能 体。 第二章多智能体系统基本理论 ( 4 ) 主动性( a c t i v i t y ) ：a g e n t 能够遵循其承诺采取主动行动，表现出面向目标 ( 包括静态目标和动态目标) 的行为。传统的应用程序是被动地由用户来运行，并 机械地完成用户的指令，而a g e n t 的行为应该是主动的，或者说自发的。智能体 感知周围环境的变化，并做出有意图的行为( g o a l - d i r e c t e db e h a v i o r ) 。 在a g e n t 弱定义下，最简单的a g e n t 就是具有上述特性的一个计算机进程。 这个进程可以简单到只是一个具有智能的程序，它能够与别的a g e n t 交换消息。 a g e n t 弱定义使的a g e n t 不仅仅只应用到人工智能领域，而且广泛地应用在诸如 通信、软件工程”“7 ”、搜索引擎、