（计算机应用技术专业论文）基于pi演算的agent交互模式研究.pdf

太原埋上大学坝士研究生，辛位1 仑) ( 基于pi 一演算的a g e n t 交互模式研究 摘要 随着计算机软硬件和网络技术的迅猛发展，应用软件的规模日益庞大、 系统日趋复杂。如何准确地描述用户需求、有效地开发和管理复杂系统、 有力地支持软件复用成为软件产业发展的关键问题。多a g e n t 技术的出现 为复杂软件系统的开发提供了一种新途径，它非常适于表示那些具有多种 求解方法、多种视图及多个求解实体的问题。多a g e n t 系统( m u l t i - a g e n t s y s t e m ，m a s ) 是由多个问题解决者( a g e n t ) 所构成的松散耦合网络，这 些a g e n t 相互作用从而解决单个a g e n t 由于能力或知识上的不足而无法解决 的问题。m a s 系统和传统软件系统的显著区别在于其自主性、反应性、协 作性、对动态环境的自适应性。这些特点对m a s 的需求分析、系统设计和 程序实现提出了现有软件开发技术所没有的新要求。要想使各种a g e n t 技 术在理论上成熟，从而真正进入实用领域，各种形式化方法将会起到重要 的作用。 本文提出了一种基于p i 一演算的a g e n t 交互模式的定性规约和定量分析 方法。使用p i 一演算规约a g e n t 的行为，给出了m a s 中a g e n t 交互过程的 解析表达式，利用p i 演算的操作语义分析了m a s 运行状态的转移过程， 特别是m a s 的死锁性分析。通过建立交互过程和齐次m a r k o v 链之间的一 一对应关系来应用马尔科夫链中的分析方法去考察m a s 的一些数值特征。 特别地，计算出a g e n t 交互过程的平稳状态分布。该方法的主要优点是在 一个统一的框架下，同时进行定性验证和定量分析。一方面，形式规约抽 象出a g e n t 交互过程中不同角色a g e n t 的功能特征，利于指导m a s 中个体 a g e n t 的处理逻辑实现；另一方面，对a g e n t 交互过程的定量分析，明确了 交互模式中的参数空间，使得系统具有比较好的灵活性和复用性。通过比 较理论分析结果和实验数据，证明了该方法具有一定的可靠性和对实际 m a s 开发的指导作用。 关键词：多a g e n t 系统，p i 一演算，马尔科夫链，交互协议，死锁 太原理工大学坝士研芄生学位论文 r e s e a r c ho na g e n ti n t e r a c t i o n s b a s e do np i c a l c u l u s a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fc o m p u t e r h a r d w a r ea n dn e t w o r k i n g t e c h n o l o g y , a p p l i c a t i o n s o f t w a r eb e c o m e sm o r ea n dm o r e c o m p l e x c o n s e q u e n t l y , a ni m p o r t a n tr e s e a r c ht o p i ci ns o f t w a r ee n g i n e e r i n gi sh o w t o d e s c r i b eu s e rr e q u i r e m e n t sp r e c i s e l y , h o wt od e v e l o p ，m a n a g ec o m p l e xs o f t w a r e s y s t e ma n ds u p p o r ts o f i t w a r er e u s a b i l i t ye f f e c t i v e l y m u l t i a g e n ts y s t e m s ( m a s ) p r o v i d e san e wa p p r o a c ht ot h ed e v e l o p m e n to fc o m p l e xs o f t w a r e ；i ti sv e r y s u i t e dt ot a c k l et h ep r o b l e m sw h i c hh a v ec o m p e t i t i v es o l v i n gm e t h o d s ，m u l t i p l e v i e w - p o i n t sa n dv a r i o u ss o l v e r s t h em a i n d i f f e r e n c eb e t w e e nm a sa n d t r a d i t i o n a ls o f t w a r es y s t e mi st h a tm a sa r em o r ea u t o n o m o u s ，m o r er e a c t i v e ， m o r ec o l l a b o r a t i v ea n dm o r ea d a p t i v et od y n a m i ce n v i r o n m e n t s b e c a u s eo f t h e s ec h a r a c t e r i s t i c s ，t h ed e v e l o p m e n to fm a si sb e y o n dt h ec u r r e n tt e c h n o l o g y ； f o r m a lm e t h o d sw i l lp l a ya ni m p o r t a n tr o l ei nm a k i n gm a sb er i p ei nt h e o r ys o t h a tt h e yc o u l db em o r ea p p l i c a t i v et or e a ll i f e t h i sp a p e rp r e s e n t saf o r m a lm e t h o df o rs p e c i f i c a t i o na n dq u a n t i t a t i v e a n a l y s i s o fa g e n ti n t e r a c t i o n s t h eb e h a v i o r so fa g e n t sa r es p e c i f i e di n p i c a l c u l u s ；a n a l y s e so fv a r i o u sp r o p e r t i e so fr u n t i m et r a n s i t i o np r o c e s s e so f m a s ，s u c ha sd e a d l o c k f l e e ，a r ea c h i e v e du s i n ge x p l i c i tr e p r e s e n t a t i o n so f i i i 太原理工大学硕士研究生学位论文 i n t e r a c t i o np r o c e s s e sa n do p e r a t i o n a ls e m a n t i c so f p i c a l c u l u s b ye s t a b l i s h i n ga o n e t o o n ec o r r e s p o n d e n c eb e t w e e nm a st r a n s i t i o np r o c e s sa n dam a r k o vc h a i n ， s t o c h a s t i ca n a l y s i st e c h n i q u e sa r ea p p l i c a b l e e s p e c i a l l y , s t a t i o n a r yp r o b a b i l i t y d i s t r i b u t i o ni sc o m p u t e d t h ea d v a n t a g eo ft h i sa p p r o a c hi st h a tq u a l i t a t i v e s p e c i f i c a t i o n a n dq u a n t i t a t i v e a n a l y s i so fa g e n t - i n t e r a c t i o n sc a r lb ed o n e u n i f o r m 【l yi nt h es a m ef r a m e w o r k o no n es i d e ，b yc o n s i d e r i n gf u n c t i o n a l c h a r a c t e r i s t i c so fd i f f e r e n ta g e n t sw i t hd i f f e r e n tr o l e s ，f o r m a ls p e c i f i c a t i o nc a n h e l pu si m p l e m e n tp r o c e s sl o g i co fa g e n t ；o n et h eo t h e rs i d e ，q u a n t i t a t i v e a n a l y s i so fa g e n ti n t e r a c t i o nh e l pu sm a k es y s t e mm o r ef l e x i b l ea n dm o r e r e u s a b l e c o m p a r i s o no ft h e o r e t i c a lr e s u l t sa n ds i m u l a t i o nr e s u l t sp r o v e st h a t t h i sa p p r o a c hi sr e l i a b l ea n da p p l i c a b l et or e a ll i f es y s t e m s k e yw o r d s ：m u l t i a g e n ts y s t e m ，p i c a l c u l u s ，m a r k o v - c h a i n ，i n t e r a c t i o n p r o t o c o l s ，d e a d l o c k s i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 4 车堑日期z 翌牢：至垄 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的。 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名： 导师签名： 堑互堡 太原理工大学硕士研究生学位论文 1 1 基于a g e n t 的软件工程 第一章引言 随着计算机软硬件和网络技术的迅猛发展，应用软件的规模日益庞大、系统日趋复 杂。软件系统的分布性、异构性、人机协作性和开放性的增强，特别是用户需求的不确 定性、需求变更周期的缩短和不可预知的快速变化环境对软件系统的适应性、复用性提 出了更高的要求。因此，如何准确地描述用户需求、有效地开发和管理复杂系统、有力 地支持软件复用成为软件产业发展的关键问题。 多a g e n t 技术的出现为复杂软件系统的分析、设计和开发提供了一种新途径，它非 常适于表示那些具有多种求解方法、多种视图及多个求解实体的问题t 。多a g e n t 系统 ( m u l t i a g e n ts y s t e m ，m a s ) 是由多个问题求解者( a g e n t ) 所构成的松散耦合网络， 这些a g e n t 相互作用从而解决单个a g e n t 由于能力或知识上的不足而无法解决的问题。 复杂软件系统是指由许多模块构成并有大量交互行为的系统。通常情况下，这种复 杂性并不是偶然发生的，它是计算机软件用于完成某些任务时固有的特性，这种复杂性 往往表现出某种规律性1 2 ： 复杂性常常表现为一种层次型模式。也就是说，一个软件系统是有一些在 其内部互相关联的子系统构成的，而每一个子系统又是一个独立的层次结 构，即它也由自己的子系统构成。子系统问的这种天然的联系变化万千， 虽然人们发现并总结了它们中较为一般的某些关联方式，比如：客户端一 服务器，点对点，团队等等。然而对于大多数的关联，往往都是动态的， 它们能够并且经常的发生变化。 人们对于系统核心构件的选择往往是武断的，并且常常带有观察者的主观 意愿。这就是说我们为一个软件系统定的基础性构件往往并不是在系统的 复杂交互中真正其基础作用的。我们现有的方法对系统的复杂交互行为并 ) ) 1 2 n 太原理工大学硕士研究生学位论文 ( 3 ) ( 4 ) 不能很好的描述和发现。 层次型系统的发展或者演化要比相同大小的非层次型系统快很多。换言 之，一种有稳定的中间形态的系统从简单系统发展到复杂系统的速度要远 快于没有稳定的中间形态的系统。 复杂软件系统各个子系统间的交互和子系统内部的交互是有区别的。后者 更为频繁，通常不在同一个数量级。然而它的行为却比前者更容易预测， 换句话说，它的大多数行为都是重复性的。这使人们自然会想到复杂系统 是可分解的，但是不幸的是，完全独立的子系统几乎没有，反而子系统间 的交互是复杂而多变的。这导致，虽然在设计阶段我们可以预测一部分子 系统间的交互，但总有不可预测的交互存在。 d 子系统 n 子系统组件 - c o m p o s e do f ( 组成) f r e q u e n ti n t e r a c t i o n ( 经常性交互) 一一i n f r e q u e n ti n t e r a c t i o n ( 非经常性交互) 图i - 1 一种规范的复杂系统视图 f i g 1 - 1v i e wo f ac a n o n i c a lc o m p l e xs y s t e m 从上面的规律性，人们定义了一种规范的复杂系统视图( 图l - 1 ) ，其中软件系统的 层次结构以“c o m p o s e do f ”连接表示，子系统内部的构件用“f r e q u e n ti n t e r a c t i o n ”连接 起来，子系统间的连接被用“i n f r e q u e n ti n t e r a c t i o n ”连接起来。原始构件的可变性体现 在其向整个子系统并发层面上的扩展。 基于以上对复杂软件系统的分析，专家和软件工程师们给出了解决复杂性的很多方 法。这些方法包括【3 】： 2 太原理1 大争颂士研究生学位论文 ( 1 )分解：这是解决大型复杂问题的最基本的方法。把一个大问题分成许多相 互关联但是又相对独立的小块，然后一个个解决。分解能够有效帮助解决 复杂性问题，主要的原因不是分解本身，因为众所周知复杂系统之所以复 杂就是因为交互的繁多，试图从中分解独立的部分几乎是不可能做到的。 分解对于解决复杂性问题最大的贡献是它限制了设计者的行为范围，在任 意紧急时刻设计者都只需面对一个局部问题，而随着对局部问题分析和方 案提出，对整体复杂系统的问题解决起到非常大的推动作用。 ( 2 )抽象：定义一个系统模型，它只强调系统的某些细节或者属性，而忽略其 他属性。同样这种方法也只是在帮助设计者限定自己的工作范围方面起到 好的作用。设计者的注意力可以集中在某些显而易见的系统属性方面而暂 时不需要考虑其他细节。 ， ( 3 )组织：是指标识和管理那些各种各样的问题解决部件之间的内部联系，我 们可以拿它们和前图中的子系统及其联系相比较。这种标明和设定的组织 关系能够帮助设计者从两种途径解决复杂性问题。第一种途径，设计一组 基础组件充当高层分析单元。第二种途径，提供一种描述单元问高层关系 的方法。 基于多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 ，a g e n t 间的交互反映子系统内部中的构件间的“f t e q u e n ti n t e r a c t i o n ”连接，而组织间的结构关 系则表示了各个子系统间的“i n f r e q u e n ti n t e r a c t i o n ”连接。 1 2 多a g e n t 系统 历史上，m a s 是分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a d 的一个 分支1 4 】。d a i 研究的核心问题是如何协调系统中的多个问题求解节点，得出问题的解， 以此将d a i 与分布式系统区别开来，即d a i 不关心一些底层的并行、并发问题，如怎 样将多个进程分配到不同的处理器上己增加系统的吞吐量，如何将集中式算法并行化 等。d a i 的另一个分支是分布式问题求解( d i s t r i b u t e dp r o b l e ms o l v i n g ，d p s ) 。d p s 主 3 太原理- j 人学碘# ：l o f 究生学他论文 要研究分布式问题求解技术，即如何将一个问题分解为一个个相对独立的予问题，如何 将这些子问题分配给各个问题求解节点，如何在多个问题求解节点间共享信息资源和领 域知识以及如何综合子问题的解以得到原始问题的解。也就是说d p s 侧重于针对给定 的问题，找出最佳的分布式求解策略。m a s 是由多个可以相互交互的a g e n t 的计算单 元所组成的系统，这些a g e n t 可以是同构的，也可以是异构的，可以有相同的目标，也 可以有不同的目标。与d p s 不同的是，m a s 所关心的是如何利用现有的自治a g e n t 来 共同完成某个目标。在m a s 中，单个a g e n t 可能由于所掌握的信息不够完整，也可能 由于能力或资源不够的缘故，无法独立完成某项任务，这时a g e n t 必须与其他a g e n t 进 行交互，在能力和资源上相互支持，以最终实现系统的目标。m a s 的主要特点是【5 】： ( 1 ) m a s 中的单个a g e n t 的能力局限性，即单个a g e n t 求解问题的能力，对 环境的感知，信息资源的掌握程度等都是有限的，不足以达到系统的整体 目标： ( 2 )m a s 中没有系统的全局控制机制： ( 3 ) 数据是分散的； ( 4 ) 计算是异步的。 ， 这也是互联网时代软件系统与p c 时代软件系统的重要差别。同时，一方面，传统 的客户机服务器交互模式过于僵硬，要求过于苛刻，而m a s 中的核心概念是a g e n t ， a g e n t 问的灵活的端对端的交互模式( 合作，协作，谈判等) 可以更自然地表达人们对 软件系统的需求；另一方面，m a s 具有与遗留系统的很好的互操作性1 6 , 7 1 。这些特点使 m a s 区别于面向对象系统、分布式系统等其他软件系统，为构造健壮的、数据和系统 控制高度分布的软件系统提供了一个新的范型，m a s 引起了人们的广泛关注，多a g e n t 技术取得了飞速发展。 基于m a s 的软件开发为单a g e n t 联合解决高层眉标提供了有效的技术，但在实际 应用中，m a s 的开发并不容易，不仅需要分布式开发知识，还必须解决a g e n t 之间的 通信问题，另外软件开发过程比较复杂【8 】am a s 系统和传统软件系统的显著区别在于其 自主性、反应性、协作性、对动态环境的自适应性。：这些特点对m a s 的需求分析、系 统设计和程序实现提出了现有软件开发技术所没有的新要求， 为支持m a s 开发，许多学者对面向a g e n t 建模技术和方法学进行了广泛的研究， 大致可以分为如下几类【9 1 ： 4 a 原理上人学坝士训f 氕生学位论义 ( 1 ) 扩充o o 建模技术或方法学的适用性来设计a g e n t 系统【1 0 l 。如m a s e ( m u l t i - a g e n ts y s t e m se n g i n e e r i n g ) 把a g e n t 看作是对象的特例，以同样 的框架处理智能、非智能系统构件。 ( 2 ) 扩充知识工程的方法学和建模技术，为验证基于a g e n t 的系统的结构和功 能提供形式化的建模语言。 ( 3 )利用形式化方法和语言( 如进程代数，z 语言等) 提供定义框架以支持 a g e n t 或a g e n t 系统规范。 ( 4 ) 支持特定的a g e n t 系统开发。如：方法论c a s s i o p e i a 支持基于合同网的 系统设计，已成功用于r o b o ts o c c 一1 。 要想使各种a g e n t 技术在理论上成熟，从而真正地进入实用领域，各种形式化方法 将会起到重要的作用。目前，研究者们提出了多种针对m a s 的规约和分析方法。这些 方法中，有些考虑m a s 中的一些定性属性，如依赖型约束、a g e n t 间交互的一致性和 无死锁性等，有些考虑m a s 中的一些定量属性，如a g e n t 的请求满足率、系统的吞吐 量、系统的可持续性等。这些方法都将m a s 的定性分析和定量分析分开进行。事实上， m a s 的设计过程是其功能属性和质量属性的折衷过程。在该过程中，我们不但要使系 统满足一定的功能，还要使系统达到一定的性能标准。不同的m a s 设计将导致不同的 性能和服务质量，客观地、准确地评估这些设计成为m a s 研究者要解决的主要问题之 一【1 2 1 。 1 3 论文主要内容和组织结构 自治性是a g e n t 的主要特性之一【。自治性使得a g e n t 决策结果具有不确定性，导 致m a s 在运行时整体行为的不确定性，增加了m a s 分析上的困难。但是这种不确定 性并不是完全任意的，往往具有某种概率特征，例如可以根据特定应用领域假设单位时 间内a g e n t 的请求数服从泊松分布。这提示我们使用概率论和随机过程中的技术来对付 这种不确定性。 为解决m a s 规约和分析上的困难，本文提出了一种基于p i 演算的m a s 分析方法。 进程代数是在代数学框架下研究分布式、并发系统的数学基础，不确定性现象是进程代 数中的主要研究对象之一，已经积累了丰富的理论结果。p i 演算作为一种进程代数，更 5 太原理：尺学预十研究g ：学何论文 加强了对交互过程中动态性的研究。由于a g e n t 行为的不确定性和动态性，本文使川p i 演算规约a g e n t 的行为，给出了m a s 中a g e n t 交互过程的解析表达式，利用p i 演算的 操作语义分析了m a s 运行状态的转移过程，特别是交互过程的死锁性分析。为定量分 析a g e n t 交互过程，建立了交互过程和齐次m a r k o v 链之间的一一对应关系。这样，就 可以应用马尔科夫链中的分析方法来考察m a s 的一些数值特征，特别地，我们计算出 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 的功能特征，对m a s 中个体a g e n t 的处理逻辑实现起了很好的指导作用；另一方面，对a g e n t 交互过程的定量分析，明确 了交互模式中的参数空间，使得系统具有比较好的灵活性和重用性，对不同角色的a g e n t 的影响作用的数值刻画也指导我们如何去提高系统的可靠性和健壮性。作为应用，本文 详细分析了f i p a 定义的请求交互协议、b r o k e r 交互协议和m a t c h m a k e r 交互协议，最后， 研制开发了a g e n t 交互模式仿真系统。通过比较理论分析结果和实验数据，证明了该方 法具有一定的准确性和对实际m _ a s 开发的指导作用。 论文内容安排如下：第二章叙述a g e n t 形式规约方法，并验证了f i p a 定义的请求 交互协议的无死锁性；第三章叙述a g e n t 交互过程的定量分析方法，作为应用例子和对 第二章内容的继续，详细分析了f i p a 请求交互协议；第四章给出b r o k e r 交互模式和 m a t c h m a k e r 交互模式的完整形式规约和定量分析过程，并比较了这两种交互模式中不 同角色的a g e n t 对交互结果的影响程度：第五章叙述a g e n t 交互模式仿真系统的设计和 实现，分析实验结果：最后，第六章总结全文，并指出下一步的工作。 6 a 原埋上人学颂士研究生学位论文 第二章a g e n t 行为形式规约 a g e n t 间的交互是m a s 求解问题的主要途径之一。自治性是a g e n t 的主要特点之 一，自治性使a g e m 间的交互行为灵活多变，增强了系统解决问题的能力，同时也增加 了分析a g e m 间交互行为特征的困难。为分析a g e n t 间的交互行为，我们使用一种移动 进程代数_ p i 演算来形式规约a g e n t 的行为。本章首先综述m a s 形式规约中一 些具有代表性的方法和途径，然后叙述本文提出来的使用p i - 演算规约a g e n t 的行为和 定性验证a g e n t 行为特征的方法，最后使用p i - 演算自动化分析工具m w b 详细分析了 f i p a 定义的请求交互协议的一些定性属性。 2 1p i - 演算简介 p i 演算是一种移动进程代数3 1 。在p i 演算中，系统的行为由动作序列来规约，动 作通过一些基本的算子，如并发、非确定性选择、辖域限制等组合起来。下面简要叙述 和本文相关的p i 演算的语法和语义，规定一些记号。关于p i - 演算的原始论文可见文献 【1 4 】，文献【1 5 】和【1 6 】提供了对p i 一演算引论性的介绍。 2 1 1p i - 演算的语法 从1 9 8 9 年的首次提出到今天，p i 演算发展出了很多分支，但其基本定义并没有改 变多少。为统一讨论，我们首先给出p i 演算的语法定义( 表2 - 1 ) ，以此作为本文讨论 的出发点。 表2 1 中各个表达式的语义可直观解释如下： ( 1 ) 零进程0 表示不执行任何动作； ( 2 ) 输出前缀甜p 表示是名字工沿着名字a 送出，然后执行进程尸； ( 3 ) 输入前缀口( x ) p 表示沿名字a 接收一个名字后，然后执行进程p ，其中x 是接收 7 太原理= 1 ：大学硕十研究生学何论文 名字的地方 表2 - 1p i - 演算的语法 t a b l e2 - 1s y n t a xo f p i c a l c u l u s ( 4 ) 隐动作f p 表示该进程不与其它进程进行交互，执行内部动作f ，然后执行进程 p ： ( 5 ) 选择组合户+ q 表示一个可以执行p 或q 的进程； ( 6 ) 并发组合p i q 表示尸和q 并发执行的组合进程； ( 7 ) i 匹i e x = y p 表示如果x 和y 是同一个名字，功b 么执行进程p ，否则，什么都不 做； ( 8 ) 不0 t i g x y e 表示如果工和y 是不同的名字，那么执行进程p ，否则，什么都 一 丕做；。 ( 9 ) 限制( 侬妒表示x 是一个局部名字，不能作为个端口与p 的环境立即交互，但 可以用于p 内部的通信。 8 太原埋j 二大字坝士桫侈i 生学位论文 2 1 2p i - 演算的语义 p i 演算的形式语义可由多种方式给出。这里叙述的方式是先给出进程间的结构同余 关系，再给出进程的操作语义，由此严格定义了p i 演算的形式语义。 定义2 1p i 一演算中的结构同余关系( s t r u c t u r a lc o n g r u e n c e ，) 定义为满足下述 规则( 表2 2 ) 的最小的一个同余关系： 表2 - 2 结构同余关系 t a b l e2 2s t r u c t u r a lc o n g r u e n c e 之所以先引出结构同余关系，再定义p i 演算的操作语义，主要是减少语义规则的 数量，保持其简洁性。p i 演算的操作语义定义如表2 3 所示。 在p i 演算中，进程间交互的基本方式是传递通信连接，通常称之为名字( n a m e ) 。 名字概念是p i 演算的重要概念之一，也是其区别于其它进程代数的特点之一。它既可 以表示进程问通信的信道，又可以表示信道上传递的数据。例如考虑进程p ， 9 太原理1 人学硕t 研究生位论文 尸= ( v a ) ( b a sr ) j6 ( c ) c d q 名字c 在动作前缀6 ( c ) 中是名字6 上传递的数据，但在；d 中又被当作信道用来传递名 字d 。将名字概念和辖域限制算子v 结合起来可以自然地表达进程问的一些交互行为， 同时赋予p i 演算强大的表达能力。 表2 - 3 操作语义 t a b l e2 - 3o p e r a t i o n a ls e m a n t i c s 2 2m a s 形式规约方法 i v l a s 的定性规约方法大体上可分为两种途径：基于形式逻辑的方法和基于进程代 1 0 太原埋上大字硕士研艽生学位论文 数的方法。在基于逻辑的方法中，使用形式逻辑原语来定义a g e n t 的能力，将a g e n t 问 的交互定义为一组逻辑规则，这样，一个m a s 可看成是一个逻辑规则系统，通过逻辑 推理来规约m a s 的整体行为。在基于进程代数的方法中，通常使用进程表达式表示出 m a s 的某些属性，如a g e n t 的行为、a g e n t 间的约束关系等，然后通过进程代数的语义 规则来分析这些属性的一些性质，如等价性、匹配性和死锁性等。由于m a s 固有的动 态性，通常使用p i - 演算来形式规约m a s 。在叙述这些结果时，我们采取的顺序是先讨 论单个a g e n t ，再讨论m a s 。 2 2 1a g e n t 形式规约 基于a g e n 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 n n i n g s 在文献 9 中给出的a g e n t 的强定义 与弱定义。a g e n t 的弱定义是： a g e n t 是具有下列特性的计算机系统： ( 1 ) 最主要的特性就是所谓自治性：a g e n t 具有属于其自身的计算资源和局部 于自身行为控制的机制，能在无外界直接操纵的情况下，根据其内部状态 和感知到的( 外部) 环境信息，决定和控制自身的行为； ( 2 )反应性：感知所处的环境，并对相关事件做出适时反应； ( 3 ) 社会性：可以通过某种a g e n t 通讯语言( a g e n tc o m m u n i c a t i o nl a n g u a g e ， a c l ) 和其他a g e n t ( 包括人类) 进行信息交流； ( 4 ) 能动性：可以主动地做出有目标的行为。 w o o l d r i d g e 称这个定义为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 的形式规约中引入了一 些心理学和人类行为学的概念。一个很有影响的工作来自于1 9 8 7 年d e n n e t t 的“意向系 统”( i n t e n t i o ns y s t e m ) 。在这个系统中，行为被描述成诸如“信念”( b e l i e f ) 、“喜好” ( p r e f e r e n c e ) 和“意向”( i n t e n t i o n ) 之类的心智状态，这些状态在决定a g e n t 行为时 太原理l 大学硕十研究生学位论文 似乎起到了不同的作用。1 9 9 2 年k i s s 把它们分为三类： ( 1 ) 认知的( c o g n i t i v e ) ，如信念和知识等； ( 2 ) 意图的( c o n a t i v e ) ，如意向，承诺和规划等； ( 3 ) 情感的( a f f e c t i v e ) ，如愿望，目标和喜好等。 信念、愿望和意向( b e l i e f , d e s i r e ，i n t e n t i o n ，简称为b d i ) 通常用来作为这三类心智 状态的代表。信念表示一个a g e n t 对环境和自身所持的观点。愿望和意向都是a g e n t 希 望作某事的状态，通常的区别是意向可以作为衡量承诺( c o m m i t m e n t ) 的一个尺度，用 来引导和控制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 去行动，而且引导a g e n t 未来所作的行为。 一些a g e n t 结构模型将意向明确表示出来。这些结构模型的一个子集被称作b d i a g e n t 结构模型( 图2 - 1 ) 。在这些模型里，三元组 在a g e n t 的认知过程中起到了积极的作用，因此通常称其为b d ia g e n t 。 | 姗”l，厂= 沁n 卜加h 蒿刊埘一h 表示函数表示映射 图2 - 1b d ia g e n t 体系结构 f i g 2 1 , r c h i t e c t u r eo f b d ia g e n t 表示数据 在b d ia g e n t 方面展开过广泛的理论和逻辑研究：第一个试图形式化这些概念的是 1 2 太原理工大学硕士伽f 究生学位论义 c o h e n 和l e v e s q u e ，他们以b r a t m a n 的哲学工作为逻辑基础，其研究成果为此后发展起 来的其他形式化理论奠定了基础。一般地说，所有这些理论都试图通过描述b d ia g e n t 之间的相互关系来描述、分析和说明一个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 。其中最具代表性的是r a o 和 g e o r g e f f 的理性b d ia g e n t 结构的逻辑描述【1 9 】。 r a o 和g e o r g e f f 的理性b d ia g e n t 结构逻辑描述包括基础逻辑的定义、信念、愿望 和意图、模态操作符的描述、模态操作符的可能世界语义的定义、b d i 操作符之间关系 定义的公理等。与大多数哲学理论相比，r a o 和g e o r g e f f 把意图作为第一类实体概念， 即与信念和愿望具有相同的地位。在该模型中，世界采用时序结构描述，该结构是以未 来为分支时间、以过去为线性的结构，故称为时间树。有两种公式描述这些时间树逻辑 的改变：状态公式( 考虑在特殊的时间点) 和路径公式( 考虑时间树中一段路径) 。 b d ia g e n t 的语义定义分为三个部分：状态和路径公式的语义、事件的语义以及意 图、信念和目标的语义。如果在所有信念可达的世界中某个公式为真，则称a g e n t 相信 该公式。事件的语义提供了一种定义事件变换时间点到另一点成功或失败的机制。信念、 目标和意图的定义采用可能世界语义。在每个情景中，存在信念可达、目标可达和意图 可达世界的集合，它们分别用于刻划a g e n t 相信可能、想要到达和已承诺要到达。信念 的公理系统基于标准的弱s 5 ( k d 4 5 ) 模态系统，其中k 和d 公理用于目标和意图。这 就是说在蕴含下目标和意图是封闭的，并且它们必须是一致的。 上述c o h e n 和l e v e s q u e 的“意念”理论、r a o 和g e o r g e f t 咱勺b d i a g e n t 都是讨论个体 a g e n t 的思维属性，随之而来的问题就是群体的思维属性问题。在a g e n t 的思维属性中， 承诺的直观含义是a g e n t 有能力完成一个任务或动作，以便实现一个尚未达到的目标， 并准备付诸行动。在m a s 中可以有多种承诺关系，就a g e n t 卟 体而言，最基本的承诺是 内部承诺，a p a g e n t 向 自己承诺执行一个动作或实现一个目标；a g e n t 加入一个组织是对 组织目标的承诺，通过把组织目标加入自己的目标集合中来实现；a g e n t 三l 间的交互是 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 s 对另 一个a g e n t 的社会承诺，并产生与之相关的义务和权利，反映 a g e n t 的社会性特点。张 1 3 太原理i ，人学硕十研究生学位论文 伟和石纯提出了一种至于承诺的a g e n f 的体系结构【2 0 】，如图2 2 所示 社会推理层 规划层 反应层 图2 - 2 基于承诺的a g e n t 的体系结构 f i g 2 2c o m m i t m e n t b a s e da r c h i t e c t u r eo f a g e n t s 在上图中，社会推主层实现a g e n t 之间的交互和a g e n t 个体目标的确定，其思维属 性以承诺为核心；社会在理层中的承诺是a g e n t 组织中a g e n t 个体思维属性和群体思维 属性的桥梁，同时，社会推理层为规划层提供决策目标，由规划层决定要采取的行动。 反应层由动作执行器和环境感知器组成，负责与环境交互。进一步，文献 2 1 给出了承 诺的形式化描述，并用公理的形式给出了组织中各种承诺间的关系；在此基础上，从宏 观和微观两个方面分析了a g e n t 组织的运动规律，初步建立个体思维属性和群体思维属 性的关系。 在a g e n t 行为的形式化方法中，文献【2 2 】提出了一种“目标驱动”的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 、提供服务以及那些与交互无关的 内部行为等五个部分，茅给出了每令部分的p i 演算表示。例如，将向外界提出服务需 求的a g e n t 请求行为定义为 一1 _ 。一 ， 8 ( w ，) = ( v n i d ) r ( w ) w ( h i d ) h i di 。 其中，r 为a g e n t 所请求的服务名，州为获取服务的位置，n d 为服务的指针。在形式规 约t a g e n t 的行为之后，作者进一步分析了a g e n t 间的交互协议，严格定义t a g e n t 行为 与交互协议的一致性概念，并给出了一个交互过程中无死锁的充分条件。 2 2 2m a s 形式规约 基于a g e n t 计算范型中的三个协心概念是a g e n t ，交互和组织脚，但前面所述方法 都是采用“面向a g e n t ”( a g e n t o d e n f e d ) 。的途径，即在描述m a s 时，m a s 设计者主 1 4 太原埋上火学坝士研究生学位论文 要考虑单个a g e n t 独自的个体行为，忽略了对组织的形式规约，认为m a s 中的社会结 构隐含在a g e n t 间的交互中。这种方法论往往还假设a g e n t 的交互行为是其意念、信念、 目标、承诺等内部心智状态的产物。但是，在实际系统的规约中，“面向a g e n t ”方法论 遇到较大的困难，这是由于： ( 1 )a g e n t 通信语言的异构性。虽然支持异构a g e n t 间的互操作是m