第六章 DAI与MAS 第一节分布式人工智能(DAI) 一、基本概念 研究在逻辑上或物理上分散的智能系统如何并行地、相互协作地实现问题求解。

Presentation on theme: "第六章 DAI与MAS 第一节分布式人工智能(DAI) 一、基本概念 研究在逻辑上或物理上分散的智能系统如何并行地、相互协作地实现问题求解。"— Presentation transcript:

1 第六章 DAI与MAS 第一节分布式人工智能(DAI) 一、基本概念 研究在逻辑上或物理上分散的智能系统如何并行地、相互协作地实现问题求解。

2 第六章 DAI与MAS 第一节 分布式人工智能(DAI) 二、特点
B)各个求解机构由计算机网络互连，在问题求解过程中，通信代价要比求解问题的代价低得多。 C)系统中诸机构能够相互协作，来求解单个机构难以解决，甚至不能解决的任务。 注：DAI的实现可克服原有专家系统、学习系统等弱点，极大提高知识系统的性能，可提高问题求解能力和效率，扩大应用范围、降低软件复杂性。

3 第六章 DAI与MAS 第一节分布式人工智能(DAI) 三、主要内容 分布式问题求解(DPS)和多Agent系统(MAS)。
A)分布式问题求解(DPS) 主要考虑怎样将一个特殊问题求解工作在多个合作的、知识共享的模块或结点之间划分。 B)多Agent系统(MAS) 主要研究自主的智能Agent之间智能行为的协调，为了一个共同的全局目标，也可能是关于各自的不同目标，共享有关问题和求解方法的知识，协作进行问题求解。 注：基于Agent的计算将成为软件开发的下一个重要的突破口。

4 第六章 DAI与MAS 第二节 分布式问题求解(DPS) 一、协作方式
任务分担(task sharing)和结果共享(results sharing) 二、求解过程 1、任务分解 2、任务分配 3、子问题求解 4、结果综合 注：1)典型的任务分解和任务分配的方法有：合同网络(类似于“招标”)、动态层次控制、自然分解、固定分解、部分全局规划； 2)在DPS中常用的通信方式有：共享全局存储器、消息传递及二者的结合。 3)黑板模型是DPS中使用较多的框架结构。

5 第六章 DAI与MAS 第三节 Agent及多Agent系统 一、Agent
二、简单分类 1、软件Agent 2、智能Agent 3、移动Agent 4、WebAgent

6 第六章 DAI与MAS 第三节 Agent及多Agent系统 三、Agent特性 1、自治性 对自己的行为和内部状态有一定的控制权。
2、社会性或称可通信性 能够通过某种Agent通信语言与其它Agent进行信息交换。 注：任务的承接、多Agent的协作、协商等均以通信为基础。 3、交互性 对环境的感知，并通过行为改变环境。 4、主动性 主动感知周围环境的变化，并作出基于目标的行为。

7 第六章 DAI与MAS 第三节 Agent及多Agent系统 三、Agent特性 5、协作性 通过协作提高多Agent系统的性能。
6、持久性 在“相当长”的时间内连续运行。 7、自适应性 根据过去的经验积累知识，并且修改其行为以适应新的环境。 8、情态特性 具有信念、意图、愿望等情态。 9、可推理性 可根据当前知识和经验，以理性的方式进行推理或预测。

8 第六章 DAI与MAS 第三节 Agent及多Agent系统 三、Agent特性 10、可移动性
可从一个地方移动到另一个地方而保持其内部状态不变。 注：Agent可以携带数据，且可在远处执行智能指令。 11、诚实性 不会故意提供错误信息。 12、友善性 Agent之间不存在互相冲突的目标，总是尽力帮助其它Agent。 13、理性 总是尽力实现自己的目标。

9 第六章 DAI与MAS 第三节 Agent及多Agent系统 四、主要研究内容 1、微观
2、宏观 Agent与环境及其它Agent的关系，包括，多Agent系统体系结构、Agent通信语言、Agent交互与协商、Agent协作与合作、多Agent知识交互与信息共享、多Agent学习。

10 第六章 DAI与MAS 第三节 Agent及多Agent系统 五、Agent理论 1、理性Agent
只有保持信念(Belief)、愿望(Desire)和意图(Intention)的理性平衡，才能有效地解决问题，使理性Agent的行为符合环境的特性。其中环境特性不仅仅指环境的客观条件，同时也包含环境中的社会团体因素。 所谓理性Agent是指：对于每种可能的感知序列，在所提供的证据和Agent内部知识的基础上，应该做的动作是使该Agent的性能测度(效用，utility)为最大。

11 第六章 DAI与MAS 第三节 Agent及多Agent系统 五、Agent理论 2、BDI Agent模型 3、动作理论
情景演算(Situation Calculus)是主要的描述动作的形式逻辑框架，其中主要是使用状态和动作两个概念，并有两条公理来描述动作与状态的关系(动作在满足什么条件的状态下可能发生，在一个状态下某个动作发生以后当前状态如何改变)。

12 第六章 DAI与MAS 第三节 Agent及多Agent系统 五、Agent理论 4、基于演算的Agent模型
演算是一种基于命名概念的并发计算模型，可很自然地表示具有动态结构的进程内及进程间的交互，是一种刻划通信系统的进程演算。 引入演算可用于描述Agent行为的并发性 5、次协调理论 为了克服“逻辑全知”，同时又保留合理的推理能力。

13 第六章 DAI与MAS 第三节 Agent及多Agent系统 六、Agent结构 1、反应Agent(Reactive Agent)
只是简单地对外部刺激产生反应，没有任何内部状态。 2、认知Agent(Cognitive Agent) 是具有内部状态的主动软件，与具体的领域知识不同，具有知识表示、问题求解表示、环境表示、具体通信协议等。 注：认知Agent是一种基于知识的系统，可包括环境描述和丰富的智能行为的逻辑推理能力。 3、混合结构

14 第六章 DAI与MAS 第三节 Agent及多Agent系统 七、Agent通信 1、KQML(知识查询与处理语言)和KIF(知识交互格式)
KQML定义了一种Agent之间传递消息的标准语法以及一些“动作表达式”，如，Tell、Perform、Reply等。 KIF则给信息的内容提供一种语法。 2、ACL 通过Agent的情态来描述Agent的抽象特性，即没有预先规定任何具体的Agent执行模式和认知结构。 具体地，可包括传递的消息格式及类型含义描述和交互协议描述。

15 第六章 DAI与MAS 第三节 Agent及多Agent系统 七、Agent通信 3、Speech Acts
一个Agent通过交互影响另一Agent的动作并改变相应Agent的认知结构，称为Speech Act理论。这相当于一个在说，另一个在听，其中有一个Agent称为Speaker，另一个称为Listener。其种类有：命题、命令、承诺、表达、描述。 注：1)Speech Act总是假设对Listener的知识有影响 2)可将Speech Act看成Listener的动作 Tell(, ) (是Listener) 前提：Next_to()   K(, ) 删除： K(, ) 增加： K(, )

16 第六章 DAI与MAS 第三节 Agent及多Agent系统 八、Agent的协调与协作 1、协调
注：1)协调是对环境的适应 2)协调一般会改变Agent的意图 3)协调的原因是由于其它Agent的意图存在 4)协调是为了解决冲突

17 第六章 DAI与MAS 第三节 Agent及多Agent系统 八、Agent的协调与协作 2、协作
4)协作可分为协作型、自私型、完全自私型、完全协作型和协作与自私结合型。

18 第六章 DAI与MAS 第三节 Agent及多Agent系统 八、Agent的协调与协作 3、基于计算生态学的协作
计算生态学是研究关于开放系统中决定计算结点的行为与资源使用的交互过程的学科。

19 第六章 DAI与MAS 第三节 Agent及多Agent系统 九、协商 1、协商

20 第六章 DAI与MAS 第三节 Agent及多Agent系统 九、协商 1、协商
6)协商协议要提供可能的协商形式的基本规则、协商过程和通信基础。 7)协商策略取决于具体的Agent. 8)一个策略的好坏，环境因素是一个主要的评价指标

21 第六章 DAI与MAS 第三节 Agent及多Agent系统 九、协商 2、协商过程 两个Agent x和y之间的协商过程如下：
2）y评价该提议，若满意则接受，否则设计出一个新的提议给x； 3）x重复2)的过程，直到双方满意或达到约定时间为止。 注：1)在协商过程中，时间、代价(协商过程中的资源开销)和对方的行为是影响协商的因素；2)协商机制要保证单调性(逐步作出让步)、收敛性、理性(协商的结果对于Agent而言是有利的)

22 第六章 DAI与MAS 第三节 Agent及多Agent系统 九、协商 3、协商方法 A)基于对策论的协商方法 以效用集为基础。
B)面向领域的协商方法 若存在双方满意的效用分配，则可得到一个联合规划。 C)最佳平衡协商方法 所有Agent均使用最佳平衡策略。 D)集中式协商方法 用一个“master agent”或组投票机制以达成协议。 E)基于意图的协商 F)基于范例推理的合同网协商

23 第六章 DAI与MAS 第三节 Agent及多Agent系统 九、协商 3、协商方法 G)基于劝说的协商

24 第六章 DAI与MAS 第三节 Agent及多Agent系统 十、移动Agent
是传统的C/S分布计算的扩展方式，可以在执行过程中，有目的地、自治地在网络中移动，利用与分布资源的局部交互而完成分布任务的软件实体。 注：1)移动Agent是代码、数据及执行环境的软件包；2)移动Agent在称为位置(place)的执行环境中移动，位置提供了移动Agent执行的语境，这个语境提供了诸如访问控制和资源限制这样的功能； 3)Telescript是比较著名的移动Agent系统。 4)便携性与安全性是对移动Agent系统的最基本的要求，实现方案基本是利用虚拟机。

25 第六章 DAI与MAS 第三节 Agent及多Agent系统 十一、Agent应用 １、工作流和业务过程管理Agent
9、机器人足球赛

26 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 一、WebAgent
二、应用方式 1、比较 价格、产品等比较 2、学习 3、协商 4、协作 5、搜索

27 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 三、应用实例 1、协作过滤/搜索Agent
如，FastSearch，Google，NorthernLight 2、Web接口Agent 3、移动Agent 4、信息/Internet Agent 如，Dogpile，MetaCrawler，TotalNEWS 5、事件Agent 如，Mind-it，javElink，CyberAlert，Enfish tracker，Eomonitor，MorningPaper

28 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 四、IBM Web Browser Intelligence
1、基本框架 (d)alert user User E The Web (a)monitor web access (e)lists of new pages M G A (b)cluster & extract keyword User model Web search A ©search for new pages E：EDIT Agent， M：Monitor Agent ,G：Generator Agent A：Autonomous(independent of Request-Response stream) Agent，

29 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 四、IBM Web Browser Intelligence
2、商务应用 a)系统和网络管理 在更高抽象层次进行过滤和动作的自动执行，对系统行为模式进行检测和响应。 B)移动访问/管理 驻留在网络中，并在数据源端进行数据处理，只将压缩的结果传递给用户。 C)Mail和Messaging 以一定的组织方式访问邮件，而不是只访问个人电子邮件。(Mail Agent) d)信息访问和管理 搜索、过滤、分类、协作共享信息、注解、有选择的信息传递

30 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 四、IBM Web Browser Intelligence
2、商务应用 e)协作 为资源共享和组工作模式建立和管理协作组 f)工作流和监督管理 计算机/电话服务集成 g)电子商贸 买方和卖方匹配、客户支持、决策支持(E-bay、Price、Time)等 h)自适应的用户接口 学习用户的习惯和偏爱，适应特定人员(个性化)

31 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用
五、Personal Comparison Shopping Agent User Personal Shopper Agent Directory A1 A2 An Mailbox Communicate needs 1 2 3 4 5 6 Collect

32 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 六、Agents and E-Brokers 1、E-Brokers
2、消费者的需要处理 消费者可以设置与购买决策相关的产品或服务需求，如，价格、服务、配送时间、质量。 3、Agent处理需求的方法 使用约束满足问题求解方法。对于约束可有硬约束(如，“我想购买一张价格不超过700元到北京的机票”)和软约束(如，“我想要12月25日的机票，但时间比日期更重要”)。

33 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 七、Agent-Mediated Commerce Seller
Buyer Matchmaker Search Engine Auctioneer Negotiator Time Planner :individual :software agent

34 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 八、基于Agent的电子商贸
在商贸活动中，买卖双方可以直接接触，进行商贸活动，但为了提高效率和效益，还需要有中间人，如，中介公司、超市。此时，就会涉及到三方：买方、卖方和中介。基于Agent的电子商贸应用系统就是一个多Agent系统或一个Agent社会，其中每个Agent要不断监察其环境，并根据相应用户的需求进行工作。对于需要买卖货物的用户可以创建具有自己策略倾向的Agent，并将它连接到相应Agent社会中。买卖Agent采用的策略可包括贪心策略(非常慢地改变自己的价格)、着急策略(非常快地改变自己的价格)和冷静策略(适当改变自己的价格)。对于中介Agent，主要工作就是寻找匹配可能的买者和卖者，并根据相应买卖双方的要求进行协商。

35 第六章 DAI与MAS 第四节 WebAgent技术在电子商务中的应用 九、Agent与个性化

36

37 强化学习模型 i: input r: reward s: state a: action Agent 环境 状态 si 奖励 ri
动作 ai a0 a1 a2 s0 s1 s2 s3 ri+1 环境 si+1 i: input r: reward s: state a: action

38 Policy Reward Value Model of environment

39 Q-learning Q (a,i) Direct approach (ADP) would require learning a model Q-learning does not: Do this update after each state transition:

40 三种观点 问题空间 主要方法 算法准则 合作多agent 强化学习 基于平衡解 多agent强化学习 最佳响应 分布、同构、 合作环境
交换状态 提高学习收敛速度 交换经验 交换策略 交换建议 基于平衡解 多agent强化学习 同构或异构、 合作或竞争环境 极小极大-Q 理性和收敛性 NASH-Q CE-Q WoLF 最佳响应 异构、竞争环境 PHC 收敛性和不遗憾性 IGA GIGA GIGA-WoLF

41 思考题 分布式问题求解的基本机制是什么？其应用关键点是什么？ 如何认识Agent的基本特性及其应用？