2009-8-20 史忠植 高级人工智能 1
高级人工智能第十章 分布式人工智能史忠植中国科学院计算技术所
2009-8-20 史忠植 高级人工智能 2
内容
10.1 概述
10.2 分布式问题求解
10.3 主体
10.4 主体理论
10.5 主体结构
10.6 主体通信
10.7 主体的协调与协作
10.8 多主体环境 MAGE
2009-8-20 史忠植 高级人工智能 3
10.1 概述分布式人工智能主要研究在逻辑上或物理上分散的智能系统如何并行的、相互协作地实现问题求解。
两种解决问题的方法:
自顶向下:分布式问题求解
自底向上:基于主体的方法
2009-8-20 史忠植 高级人工智能 4
分布式人工智能系统的特色
1) 系统中的数据、知识,以及控制不但在逻辑上,而且在物理上是分布的,既没有全局控制,也没有全局的数据存储。
2) 各个求解机构由计算机网络互连,在问题求解过程中,通信代价要比求解问题的代价低得多。
3) 系统中诸机构能够相互协作,来求解单个机构难以解决,甚至不能解决的任务。
2009-8-20 史忠植 高级人工智能 5
分布式人工智能系统的主要优点
1) 提高问题求解能力。
2) 提高问题求解效率。
3) 扩大应用范围。
4) 降低软件的复杂性。
2009-8-20 史忠植 高级人工智能 6
10.2 分布式问题求解特点:
数据、知识、控制均分布在系统的各节点上,既无全局控制,也无全局数据和知识存储。
两种协作方式:
任务分担
结果共享
2009-8-20 史忠植 高级人工智能 7
10.2.1 分布式问题求解系统分类根据组织结构,分布式问题求解系统可以分为三类:
层次结构类
平行结构类
混合结构类
2009-8-20 史忠植 高级人工智能 8
10.2.2 分布式问题求解过程分布式问题求解过程可以分为四步:
任务分解
任务分配
子问题求解
结果综合
2009-8-20 史忠植 高级人工智能 9
分布式问题求解系统中协作的分类按节点间协作量的多少,协作分为三类:
全协作系统
无协作系统
半协作系统常用的通信方式有:
共享全局存储器
信息传递
黑板模型
2009-8-20 史忠植 高级人工智能 10
10.3 主体多主体系统主要研究在逻辑上或物理上分离的多个主体协调其智能行为,即知识、目标、意图及规划等,实现问题求解。可以看作是一种由底向上设计的系统。
2009-8-20 史忠植 高级人工智能 11
主体的思想智能主体的几个典型的实例:
Microsoft的 Office助手
计算机病毒 ( 破坏主体 )
计算机游戏或模拟中的智能角色
贸易和谈判主体 ( 如 Ebay的拍卖主体 )
网络蜘蛛 Web Spider( 搜索引擎中的数据搜集和索引主体,如 Google)
2009-8-20 史忠植 高级人工智能 12
主体概念的出现面向过程的方法面向实体的方法面向对象的方法面向主体的方法软件开发方法的进化
2009-8-20 史忠植 高级人工智能 13
主体的定义在计算机和人工智能领域中,主体可以看作是一个实体,它通过传感器感知环境,通过效应器作用于环境。
2009-8-20 史忠植 高级人工智能 14
主体的特性主体弱概念:
自治性、社会能力(可通信性)、反应能力、自发行为主体强概念:
知识、信念、意图、承诺等心智状态其它属性:
长寿性、移动性、推理能力、规划能力、学习和适应能力、诚实、善意、
理性
2009-8-20 史忠植 高级人工智能 15
10.4 主体理论智能主体的理论模型研究主要从逻辑、
行为、心理、社会等角度出发,对智能主体的本质进行描述,为智能主体系统创建奠定基础。
2009-8-20 史忠植 高级人工智能 16
10.4.1 理性主体( BDI主体)
Belief——信念,主体对环境的基本看法。
Desire——愿望,主体想要实现的状态,
即目标。
Intention——意图,目标的子集。
2009-8-20 史忠植 高级人工智能 17
10.4.2 BDI主体模型
BDI主体模型可以通过下列要素描述:
一组关于世界的信念;
主体当前打算达到的一组目标;
一个规划库,描述怎样达到目标和怎样改变信念;
一个意图结构,描述主体当前怎样达到它的目标和改变信念。
2009-8-20 史忠植 高级人工智能 18
BDI解释器
BDI-Interpreter
initialize-state();
do
options,= option-generator(event-queue,B,G,I);
selected-options,= deliberate(options,B,G,I);
update-intentions(selected-options,I);
execute(I);
get-new-external-events();
drop-successful-attitudes(B,G,I);
drop-impossible-attitudes(B,G,I);
until quit
2009-8-20 史忠植 高级人工智能 19
10.4.3 RAO逻辑框架目标:以一种自然的方式描述多主体系统中关于别的主体的状态的推理过程。
系统的分类:由于多主体系统太复杂,
建立一种通用的推理模式的想法是不现实的,有必要对系统分类以便区别对待。
常识的获得:和单个主体情形一样,常识问题是阻碍推理的大难题。
2009-8-20 史忠植 高级人工智能 20
10.4.4 换位推理
)()( 212121 BBBBBB
基本思想:为了对某个主体 j的状况和行为进行推理,推理者假想自己正处于主体 j所处的环境,然后推理者把他自己在那种环境下的将要处于的状况和行为作为推理者对于主体 j的状况和行为的推理结果。
形式化表示:
2009-8-20 史忠植 高级人工智能 21
10.4.5 动作理论情景演算是描述动作的主要的形式框架。
在情景演算中引入了状态和动作的概念,
并利用两条逻辑公理来描述动作与状态的关系。一条公理描述一个动作在满足什么条件的状态之下可能发生,另外一条描述在一个状态之下某个动作发生以后当前状态如何改变。
2009-8-20 史忠植 高级人工智能 22
规划库的形式化表示环境状态:
State = { P1,P2,… Pn }
目标:
Goal=<State,weightiness>
动作模板:
Act_template = <name,roles,preconditions,
effects,resources>
主体能力:
Ability=<Act_template,role,cost>
2009-8-20 史忠植 高级人工智能 23
10.5主体结构主体结构需要解决的问题包括:
主体由那些模块组成,
模块之间如何交互信息,
主体感知到的信息如何影响它的行为和内部状态,
如何将这些模块用软件或硬件的方式组合起来形成一个有机的整体。
2009-8-20 史忠植 高级人工智能 24
主体基本结构环境 主体感知作用黑箱软件主体
2009-8-20 史忠植 高级人工智能 25
智能主体的工作过程环境交互信息融合信息处理作用交互感知作用
2009-8-20 史忠植 高级人工智能 26
主体骨架程序
function Skeleton-Agent(percept) return action
static,memory /* 主体的世界记忆 */
memory ← Update -Memory(memory,percept)
action ← Choose -Best-Action(memory)
memory ← Update -Memory(memory,action)
return action
2009-8-20 史忠植 高级人工智能 27
主体的分类根据人类思维的层次模型,可以将主体分成四类:
反应主体
形象思维主体
抽象思维主体
复合式主体形象思维主体和抽象思维主体也可以合称为认知主体
2009-8-20 史忠植 高级人工智能 28
10.5.1 反应主体环境当前世界传感器动 作效应器条件 -动作规则主体
2009-8-20 史忠植 高级人工智能 29
反应主体程序
function Reactive-Agent(percept) returns action
static,rules,/* 一组条件 -动作规则 */
state ← Interpret -Input(percept)
rule ← Rule -Match(state,rules)
action ← Rule -Action[rule]
return action
2009-8-20 史忠植 高级人工智能 30
10.5.2 认知主体环境信息融合传感器动 作效应器主体规 划知识库目标内部状态
2009-8-20 史忠植 高级人工智能 31
认知主体程序
function Cognitive-Agent(percept) returns action
static,environment,/* 描述当前世界环境 */
kb,/* 知识库 */
environment ← Update -World-Model(environment,percept)
state ← Update -Mental-State(environment,state)
action ← Decision -Making(state,kb)
environment ← Update -World-Model(environment,action)
return action
2009-8-20 史忠植 高级人工智能 32
BDI结构知识信念规划意 图目 标愿 望
2009-8-20 史忠植 高级人工智能 33
10.5.3 复合式主体决策生成规 划反 射建 模 通 信感 知 行 动其他智能主体智能主体外部世界预测 协作与协商动作请求或应答信息一般情况紧急情况和简单情况
2009-8-20 史忠植 高级人工智能 34
规划模块世界的模型
(包括其他主体的模型)
经 验 库 目标集合局 部 规 划 器决 策 生 成重新规划 规划规划目标
2009-8-20 史忠植 高级人工智能 35
建模模块世界的模型
(包括其他主体的模型)模 型 库模 型 生 成 和 维 护 预 测规划决策生成感 知 通 信建模
2009-8-20 史忠植 高级人工智能 36
通信模块词 法 库 语 法 库 词 义 库 物理通信语言生成语言理解 通信
2009-8-20 史忠植 高级人工智能 37
10.6 主体通信策 略对 话消 息黑 板协 议通信协作 协 议
2009-8-20 史忠植 高级人工智能 38
主体通信中的主要问题
语义:全部有关的主体必须知道通信语言的语义,消息的语义内容知识是分布式问题求解的核心部分。
言语行为:通信语言也是一种动作,说话是为了使世界的状态发生改变。
交互协议:主体之间消息交换的典型模式
通信语言:传递消息的标准语法。
Foundation for Intelligent Physical Agents
http://www.fipa.org
2009-8-20 史忠植 高级人工智能 39
主体间的消息传递消息发送 /传输服务器转换到传输格式 从传输格式转换消息 M
言语行为意图 I
目标 G
Agent i
消息 M
Agent i
2009-8-20 史忠植 高级人工智能 40
本体论本体论是概念化的明确的表示和描述。
对某一领域中的概念有共同理解,可以提高交流和协作的效率,从而提高了软件的重用性。
2009-8-20 史忠植 高级人工智能 41
言语行为
有关言语行为理论的研究主要集中在如何划分不同类型的言语行为。
在主体通信语言的研究中,言语行为理论主要用来考虑主体之间可以交互的信息类型。
2009-8-20 史忠植 高级人工智能 42
FIPA通信动作库
Accept Proposal 接受提议
Agree 同意
Cancel 取消
Call for Proposal 要求提议
Confirm 确认
Disconfirm 确认为否定
Failure 失败
Inform 通知
Inform If 通知 是否
Inform Ref 通知 有关对象
Not Understood 不理解
2009-8-20 史忠植 高级人工智能 43
Propagate 传播
Propose 提议
Proxy 代理
Query If 询问 是否
Query Ref 询问 有关对象
Refuse 拒绝 ( 请求 )
Reject Proposal 拒绝提议
Request 请求
Request When 请求 某个条件下执行
Request Whenever 请求 一旦某个条件成立就执行
Subscribe 预定详细说明:
http://www.fipa.org/repository/cas.html
2009-8-20 史忠植 高级人工智能 44
交互协议主体之间的会话常常形成典型模式,这种情况下某些消息序列是可知的,这些消息交换的典型模式称为协议。
主体间交互的理想情况:主体充分地理解消息的含意和意图,然后根据自身的信念、
目标等心智状态,做出相应的回答比较实际的实现:预先规范这些协议,规定好消息的顺序。
2009-8-20 史忠植 高级人工智能 45
FIPA
英国拍卖协议
2009-8-20 史忠植 高级人工智能 46
通信语言
KQML,由美国 ARPA的知识共享计划中提出,规定了消息格式和消息传送系统,为多主体系统通信和协商提供了一种通用框架。
ACL,由 FIPA制定的一种规范。与
KQML非常相似
2009-8-20 史忠植 高级人工智能 47
KQML
一个例子:
(ask-all
,sender A
,receiver B
,in-reply-to ido
,reply-with idl
,language Prolog
,ontology foo
,content,bar (X,Y)”)
2009-8-20 史忠植 高级人工智能 48
FIPA ACL
(inform
,sender agent1
,receiver hpl-auction-server
,content
(price (bid good02) 150)
,in-reply-to round-4
,reply-with bid04
,language s1
,ontology hpl-auction
)
消息结构开始通信动作类型消息参数消息内容表达式参数表达式
2009-8-20 史忠植 高级人工智能 49
XML—eXtensible Markup Language
可扩展标记语言
XML是用于标记电子文件使其具有结构性的标记语言。 XML文件本身只是将文件资料结构化。
例如:下面的 ACL消息
(inform
:sender jklabrou
:receiver grosof
:content (CPU libretto50 pentium)
:ontology laptop
:language kif)
2009-8-20 史忠植 高级人工智能 50
转换为 XML格式后如下:
<?xml version="pre-1.0"?>
<!DOCTYPE fipa_acl SYSTEM "fipa_acl.dtd">
<message>
<messagetype>
inform
</messagetype>
<messageparameter>
<sender link="http://www.cs.umbc.edu/?jklabrou">
jklabrou
</sender>
</messageparameter>
<messageparameter>
<receiver link="http://www.research.ibm.com/people/g/grosof/">
grosof
</receiver>
</messageparameter>
2009-8-20 史忠植 高级人工智能 51
<messageparameter>
<ontology
link="http://www.cs.umbc.edu/?jklabrou/ontology/laptop.html">
laptop
</ontology>
</messageparameter>
<messageparameter>
<content>
(CPU libretto50 pentium)
</content>
</messageparameter>
<messageparameter>
<language link="http://www.stanford.edu/kif.html">
kif
</language>
</messageparameter>
</message>
2009-8-20 史忠植 高级人工智能 52
10.7主体的协调与协作协调 (coordination)与协作 (cooperation)是多主体研究的核心问题之一。
协调是指一组智能主体完成一些集体活动时相互作用的性质。
协作是非对抗的主体之间保持行为协调的一个特例。
2009-8-20 史忠植 高级人工智能 53
协调多主体系统中的协调是指多个主体为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望避免主体之间的死锁或活锁。
死锁指多个主体无法进行各自的下一步动作;
活锁指多个主体不断工作却无任何进展。
2009-8-20 史忠植 高级人工智能 54
协作目前针对主体协作的研究大体上可分为两类:
1) 将其它领域研究多实体行为的方法和技术用于主体协作的研究。如对策论和力学研究。
2) 从主体的目标、意图、规划等心智态度出发来研究多主体间的协作。
2009-8-20 史忠植 高级人工智能 55
协作规划协作的动机:
1) 某个主体相信通过协作能带来好处
(如提高效率,完成以往单独无法完成的任务)
2) 多个主体在交流的过程中,发现它们能够通过协作来实现更大的目标。
2009-8-20 史忠植 高级人工智能 56
协作过程
1) 产生需求、确定目标
2) 协作规划、求解协作结构
3) 寻求协作伙伴
4) 选择协作方案
5) 实现目标
6) 评估结果
2009-8-20 史忠植 高级人工智能 57
10.8 多主体环境 MAGE
MAGE的主要特点:
运行于分布式网络环境
用 java编写
使用模块化的能力
通过 ADL来描述并生成主体
主体之间通过 ACL通信
2009-8-20 史忠植 高级人工智能 58
10.9 面向主体的软件技术在面向主体的软件开发方法中,应用程序编写为软件主体,这些主体之间通过主体通信语言可以进行比普通消息传递更规范、更明确的通讯。
2009-8-20 史忠植 高级人工智能 59
主体与对象的异同共同点:
都具有封装性、继承性和多态性。
对象的内部状态映射为主体的心智状态。
互操作。
不同点:
主体具有自治性,对象只能被动的被调用。
主体之间交互使用通信语言,对象之间交互是通过互相调用方法。
2009-8-20 史忠植 高级人工智能 60
AO与 OO
对象是对现实世界中的被动实体的抽象,主体是对主动实体的很好的抽象。
主体支持用于表示智能的结构,如信念、承诺等。
主体支持基于言语行为理论的高级交互,不同于对象之间频繁的消息发送和接收。
对象是通过外部来进行控制的(白箱控制),相反,主体有自治性,不能直接从外部进行控制(黑箱控制)。
2009-8-20 史忠植 高级人工智能 61
主要的基于主体的方法
1) Gaia方法,Wooldridge,Jennings和
Kinny在 1999年提出了面向主体分析与设计的 Gaia方法学。
2)多主体工程方法学,Wood和 DeLoach
提出了多主体工程方法学 MaSE。
3) AUML,Odell等人提出了对 UML语言的扩充 ——主体 UML语言 AUML语言。
2009-8-20 史忠植 高级人工智能 62
Gaia方法
Gaia是一种同时支持微观级(主体结构)和宏观级(主体社会与组织结构)的主体开发的一般方法。
分析过程
第一步是找到系统中的角色,
第二步是对角色之间的交互进行建模。每个角色包含四个属性:责任、许可、活动和协议
设计阶段
第一步是把角色映射到一定的主体类型,然后对不同的主体类型创建适当的主体实例;
第二步是确定一个和多个主体中角色所需要的服务模块;
最后一步是为主体之间的通信表示建立熟人模块。
2009-8-20 史忠植 高级人工智能 63
MaSE
MaSE在一般性及应用领域上类似于 Gaia,
MaSE的目的是引导设计者怎样从初始的系统规范说明到主体系统的实现。
MaSE在逻辑上被分为七段流水线:捕获目标、应用用例、精练角色、创建主体类、构造会话、编译主体类、系统设计。
2009-8-20 史忠植 高级人工智能 64
AUML
Odell,Parunak和 Bauer提出了主体交互协议 AIP的三层表示方法。该方法不仅需要表达语义的修改,而且需要
UML可视化语言的修改。
AUML已经被提交给 UML标准委员会,
作为一个建议包含在 UML2.0中。