多Agent学习

1.Multi-Agent Learning

1.1 算法特点

Multi-Agent Learning是多Agent系统的学习算法,是一个在AI里比较年轻而重要
的课题.一方面,单个Agent的局限性是很大的,就象单个的人,其能力也是有限的多
个Agent的组合,包括合作与协调将会大大地提高系统的智能:正所谓"三个臭皮匠,
顶一个诸葛亮".另一方面,随着Internet的逐渐普及与迅速扩大,Agent一下上升到
一个具有战略意义的地位.网络上的Agent自然地形成一个多Agent系统.因此,研究
基于多Agent的学习算法显得分外迫切。
研究者对此进行了大量的研究，其中相关的国际会议(WorkShop)有：Learning
,Interaction and Organizations in Multi-Agent Environments, ICMAS′96
。相关的杂志有：JETAI(Journal of Experimental and Theoretical Artifical
Intelligence)杂志的专刊：Learning in Distributed Artificial
Intelligence Systems；Machine Learning杂志的专刊：Multi-Agent Learning
。专门的书作有Gerhard Weiss& Sandip Sen的<Adaption and Learning in
Multi-Agent Systems> (Springer-Verlag出版社，3/20/1996)。另外，哥伦比亚
的JAM计划，就是试图在基于网络的信息系统上用基于Jave的Learning Agent进行
学习，学习过的Agent称为"classify agents "。这些Agen可以在网络上迁移，以
获得别的Agent的知识。

Multi-Agent Learning与一般的学习算法有所不同，它们具有如下特点：
1它基于,甚至要求多个Agent之间的相互作用,以建立整个系统的协调,学习,智能
化.也就是说,它强调的是对多个Agent组成的环境变化的及时反应和考虑相互间的
合作与协调。
2学习策略是有针对性的，对于不同的环境和问题，有不同的算法。
3 Multi-Agents系统很可能中有不同质的Agents，算法必须考虑异质Agent的特点。
4 Multi-Agent System中每个Agent的看法都会带有偏见，就是说只是局部最优。
学习算法必须从整体着想，设法从局部最优达到全局最优。

1.2.1分布式事例学习(Distributed Case-Based Learning )

基于事例推力(Case-Based Reasoning，CBR)由于拥有广泛的应用，近来受到了很
高的重视。M V Nagendra等人对此作出了深入的研究。他们目前的主要工作是"合
作恢复"(Cooperative Retrieval)。也就是说在Multi-Agent System中，把分布
在各个Agent的子事例抽取并且组合成一个新的事例。在这样一个系统中，每个
Agent都会有偏见和对解决问题的不完美的看法。这导致了这样一个需求：各个
Agents互相合作，抽取他们的事例以得到"最优子事例"，这些"最优子事例"以固
定的方式组合成一个对问题求解有用的完整的事例。每个Agent的视野是局部的，
这个偏见会导致它抽取的是"局部最优子事例"，而这些"局部最优子事例"如果以
全局的标准来衡量的话，则不一定是最优的。所以这要求各个Agents合作地抽取
他们的事例，以恢复和组装出一个好的组合例子。

目前，M V Nagendra等人已经实现了一个基于多Agent的路径计划(Path
Planning)系统，其中应用了分布式事例学习。

1.2.2异质多Agent系统中结构角色的学习(Learning Organizational Roles in a
Heterogeous Multi-Agent System)

L-TEAM是一个为支持在合作化分布式搜索领域中的异质可重用Agent的TEAM的扩展
。多Agent的参数设计是合作搜索的一种形式，其变量的值的范围是在一个已知的
值域中。初始化是由一些有能力的Agent根据问题描述来对参数进行设置，当然，
这种设置会带有偏见。然后其他Agent就对初始设置进行扩展和评价，直到设置完
整并且所有参与的Agent都相互满意。

每个Agent在L-TEAM的搜索过程中扮演着一些结构角色。一个角色定义了在一个解
答中的一个或者一组任务。在L-TEAM中，一个可能的角色是：初始化参数设置，
扩展一个已经存在的部分参数设置和评价一个已经存在的设置。而有结果表明，
角色的分配影响了整个搜索的进程和最终的结果。这其中的原因可以追溯到特定
的Agent能够提供或者使用从其他Agent反馈的信息的能力。争决定了特定的角色
分配的优化。因此，学习技术被运用于以下的任务中：在使用参与的Agent中分配
角色，以各尽其才，在功能和效率上达到比较高的水平。
1.2.3协调学习策略(Learning Coordination Strategies)

在很多真实世界中的应用领域，例如网络控制和诊断，合作机器人，办公室自动
化中的合作分布式问题求解(cooperative distributed problem solving，
CDPS). 虽然协调性是CDPS中的基本技术要求，但是很多高级的、复杂的策略却不
能在所有的情形下有效地求解问题。人们寻求一种学习方法，能够在特定的问题
求解中协调。这种学习是通过记录和分析问题求解结果的推理。这种分析标识了
那些不好的状态：不合适的协调导致了冗余的动作或者及时地执行重要的动作，
因此导致系统功能下降。这种分析也常被用于建立特定状态下的协调策略，使用
关于网络动作的非局部的额外的信息，加到系统上以补救问题缺陷。这些策略能
够决定：(1) 局部和非局部的动作的优先级, (2)消息的优先级 (3)协调行为所
需要的非局部信息。这些策略同样能够把不同层次的协调引入到系统中，也就是
说，系统能决定何时使用协调，何时由它自治处理。这一课题应用在一个现实的
、分布问题求解中，例如计算机网络监控和诊断系统。

可参阅的文献有：
Sugawara, T. and Lesser, V. "On-Line Learning of Coordination Plans,"
Computer Science Technical Report 93-27, University of Massachusetts,
Amherst, 1993. (This is an extended version of a paper that appeared in
the Twelfth International Workshop on Distributed Artificial
Intelligence.).

Sugawara, T. and Lesser, V. "Learning Coordination Plans in Distributed
Problem-Solving Environments," Revised and Shortened version of
Computer Science Technical Report 93-27, University of Massachusetts,
Amherst, 1993. (Also appeared in the Twelfth International Workshop on
Distributed Artificial Intelligence, 1993).

Sugawara, T. and Murakami, K. "A Multiagent Diagnostic System for
Internetwork Problems," Proceedings of INET′92, Kobe, Japan, 1992.

Sugawara, T. "Cooperation in Multiagent Systems by Hypothesis-Based
Preceding Reasoning," Proceedings of the AAAI Eleventh International
Workshop on DAI, 1992.

1.2.4自利Agent的学习算法(Learning among self-interested agents )

在一群自利的Agent中，它们之间存在相互作用，它们能在一定的环境(包括对手)
进行学习，并且各有各的策略。下面1.3会详细分析在多Agent中如何运用强化学
习(Reinforcement Learning)中的Q-learning算法。

强化学习(RL) 的基本思想是：加强那些能产生良好效果的行为，减弱那些效果不
佳的行为。Q-learning当前的强化学习中一种不需要为环境建立模型的算法，能
够在线地使用。因此它非常适用于那些可重复的、对手未知的游戏中。很多强化
学习的研究者被限制在单一Agent或那种报酬是绝对正面(如团队问题)或绝对反面
( zero-sum游戏)的多Agent系统中。在3.1中我们将详细介绍在可重复的囚徒困境
问题(iterated prisoner′s dilemma，IPD)中,如何运用强化学习策略。在这个问
题中，报酬并非是明显的正或反，因此强化学习在这一问题中的运用是比较困难
的。于是我们使用Q-learning agents来参与可重复的囚徒困境游戏，来对付那些
未知的对手。在某些实验中，对手使用针锋相对的策略，而在令一些实验中，对
手也是一个用Q-learning作为学习算法的Agent(Q-Learner)。所有的Q-learner能
学到对付"针锋相对"Agent的最佳策略，而对付同是Q-learner则比较困难。正是
因为其它Q-Learner在不断的学习而导致环境不断变化。而且，没有关于IPD的元
知识以鼓励其它Q-Learner进行合作。

这些Q-Learner的学习可以从三个角度进行改变：作为上下文的历史长度；使用
得内存类型(基于有限历史的查找表或理论上能反映任何深度的历史的可循环网络
)；搜索策略。虽然所有的Q-Learner在于Q-Learner进行这个游戏时，它们都要面
对很大的困难，但是历史记录越长，内存类型是查找表和长久的搜索进化的
Q-Learner在游戏中获益最大。

可参阅的文献有：
Sandholm, T. and Crites, R. 1995. Multiagent Reinforcement Learning in
the Iterated Prisoner′s Dilemma. Biosystems 37: 147-166, Special Issue
on the Prisoner′s Dilemma.

Sandholm, T. and Crites, R. 1995. On Multiagent Q-Learning in a
Semi-competitive Domain. 14th International Joint Conference on
Artificial Intelligence (IJCAI-95), Workshop on Adaptation and Learning
in Multiagent Systems, Montreal, Canada, pp. 71-77.

Sandholm, T. and Crites, R. 1996. On Multiagent Q-Learning in a
Semi-competitive Domain. In LECTURE NOTES IN ARTIFICIAL INTELLIGENCE of
LECTURE NOTES IN COMPUTER SCIENCE, Springer-Verlag.

Berkman, N. and Sandholm, T. 1995. What should be minimized in a
decision tree: A re-examination. University of Massachusetts at
Amherst, Computer Science Technical Report TR 95-20.
1.2.5特定情况下的协调学习(Learning Situation-Specific Coordination)

要在Multi-Agent系统中获得有效的协调是一个困难的问题。原因是很多的：首先
，一个Agent的决定，是建立在它对整个问题的局部视野中的，这样会导致在下列
行为的不合适的决定：下一步应该怎样做，应该把什么结果传递给其它Agent，应
该要求其它Agent产生什么结果。当然，如果一个Agent对整个问题有全局的了解
，它就能作出更合适的决定。然而，即使有这些元知识，对任务的结果和对系统
的未来的任务还是存在不确定性的，这体现在Agent之间不紧密的行为上。这些在
为获得有效协调的困难会加重，原因是一个Agent为了得到问题的全局，会耗费很
多系统资源。这个代价包括了通讯延迟，在产生合适的形式提供信息以及Agent运
用这些信息来产生局部决定。因此，在特定的问题求解中，由于Agent固有的行为
不确定性和元知识处理处理的代价，我们可能不需要去获得其它Agent的活动情况
。复杂的协调策略并不能在所有的问庵杏行敌校砸残碓市碓谀承┎愦紊?br />存在非协调的行为可能更加有效。在这种情况下，局部问题求解会更有效，它不
需要额外的开销进行协调。

通用部分-全局规划(Genalized Partial Global Planning ,GPGP) 就是为迎合这
一需求而提出的。它建立了适当的协调策略，以服务于一些特殊的任务环境。它
的结构是一组可扩展的模块集合，模块对应各种协调策略，因此人们可以根据需
要使用里面的任意子集。实验结果证明对于某些特定问题环境，子集的效果比运
用整个集合即全部协调技术要好。当前的工作就是赋予Agent对应不同问题自动选
择协调策略子集的能力。

可参阅的文献有：

M V Nagendra Prasad, and Victor R Lesser "Off-line Learning of
Coordination in Functionally Structured Agents for Distributed Data
Processing," submitted.

M V Nagendra Prasad, Keith Decker, Alan Garvey, and Victor Lesser.
"Exploring Organizational Designs with TAEMS: A Case Study of
Distributed Data Processing", ICMAS-96.

M V Nagendra Prasad , and Victor R Lesser Learning Situation-specific
Coordination in Generalized Partial Global Planning to be presented at
the 1996 AAAI Spring Symposium on Adaptation, Co-evolution and
Learning in Multiagent Systems, Stanford, CA.

Decker, K. and Lesser, V., "Designing a Family of Coordination
Algorithms," In Proceedings of the First International Conference on
Multi-Agent Systems. This link is to the more detailed UMASS Technical
Report 94-14, updated April 1995.

Dcker, K., "Environment Centered Analysis and Design of Coordination
Mechanisms". Ph.D. Thesis, Department of Computer Science, University
of Massachusetts, Amherst, May 1995.
1.2.6 联盟学习(Federated Learning)

在Agent中的合作学习，就是在全球范围进行通讯和学习。当前的研究有：
分布式的基于事例学习(Distributed Case-based Reasoning，DistCBR)
集中式的基于事例学习( Collective Case-based Reasoning，ColCBR)
迁移的 CBR Agents (MigCBR)
分类任务中可迁移的推理学习者(Migratory Inductive Learners for
Classification Tasks，MILC)

联盟学习：动机和框架

多Agent框架中的问题求解对学习研究提出了新的挑战。我们认为在合作性的基于
Agent的问题求解系统中比集成式的多策略学习(Integrated multistrategy
learning，IMSL)要求更高的灵活性。为此我们提出了联盟学习。

联盟学习与其它IMSL的学习方法的不同之处在于：其它学习方法拥有关于何时和
怎样进行硬连线的知识，而联盟学习没有这种固定的知识。一个联盟学习得Agent
所要做的是去寻找它所不知道的。缺少固定行动策略的知识，这样使得Agent之间
的合作更灵活，解决新问题的能力更强，更大地提高性能。

联盟学习得研究是在之前的工作上扩展的。之前人们研究了在反射结果里的学习
的内在进程。(可参阅ANALOG项目). 我可以总结出联盟学习是之前工作的在Agent
关系中的自然延续，也就是说，它具有以下特点：

个体的独立的内存和经验；
公共的外部语言描述知识；
联盟学习Agent的合作性和特殊性；
查找，发掘信息之源，与其它Agent进行磋商。

从问题求解系统的角度上看，学习扩展了可正确解决问题的范围并且提高了系统
性能。在多Agent中联盟学习提高了Agent得整体求解问题的能力。这里意味着我
们已经假设系统存在合作行为，而不适合在竞争式的多Agent系统中。.
1.2.7 分层学习(Layered Learning)-机器人足球

机器人踢足球无疑是很具娱乐性的，除此以外，它也成为人工智能，包括多Agent
系统，机器学习，实时规划的重要研究领域之一。研究者以这一领域作为测试床
，运用了分层学习以产生复杂的多Agent。这里不将详述。

1.2.8 基于事例推理的Agent的合作(Cooperation Among Case-based Reasoning
Agents)

这里我们将介绍三种合作的模式。在基于事例的推理的Agent解决问题和学习过程
中存在推理。它们是：

DistCBR - 分布式基于事例推理的Agent系统，Distributed Case-based Reasoning
Agents
ColCBR - 集中式基于事例推理的Agent系统，Collective Case-based Reasoning
Agents
froactive Learning -Learning Agent′s Competence Models

[align=right][此贴子已经被作者于2006-5-31 11:08:52编辑过][/align]