一种基于协调知识水平的协调问题描述方法

　2005年7月系统工程理论与实践第7期　文章编号:100026788(2005) 0720087206

一种基于协调知识水平的协调问题描述方法

马巧云, 陈学广, 洪　流

(华中科技大学系统工程研究所, 湖北武汉430074)

摘要:　从协调的本质出发, 提出基于协调知识水平的协调理论研究框架, 用活动、资源、相互依赖和协

调机制等刻画协调知识水平. 在此基础上, 按照分析活动→判断资源→分清依赖的顺序对协调问题进行

抽象, 进而通过三元组(A ,D ,R ) 对其进行形式化的描述, 将协调问题的求解过程简化为对三种基本相互

依赖的处理过程, 为利用计算机处理协调问题打下了基础.

关键词:　协调; 协调知识水平; 依赖

中图分类号:　TP30114　　　　　　　　文献标识码:　A 　　　

A Method for Describing C oordination Problem Based

on C oordination K nowledge Level

MA Qiao 2yun , CHE N Xue 2guang , HONGLiu

(Institute of Systems Engineering , Huazhong University of Science and T echnology , Wuhan 430074,China )

Abstract :　Describing coordination problem is a base for coordination theory. According to the nature of

coordination , we present a research scheme of coordination theory based on coordination knowledge level , which can

be expressed by the coordination elements , such as activity , res ource , interdependence and coordination mechanism.

Furtherm ore , we abstract the general coordination problem following the three steps of analyzing activities , checking

res ources and identifying interdependences , and then express it by a triple (A ,D , R ) . In this way , it reduces the

coordination process to the management of three basic interdependences and als o provides a base for further study on

general coordination theory by computer.

K ey w ords :　coordination ; coordination knowledge level ; interdependence

1　引言

协调作为一个重要的概念广泛地出现在多个学科和社会经济领域, 成为共同关注的一个研究课题. 近年来, 关于协调已有大量的研究成果, 例如组织理论中的基于角色的任务分派

的优化模型[2][3][1], 运筹学中关于资源分配, 分布式开放系统中支持软件集成的软件平台Middleware 等. 然而, 这些研究成果与具体的应用领域密切相关, 可移植性差, 不利于协调理论及其应用的进一步发展. 因此, 人们致力于探索通用的协

[4]调理论, 采用的方法多是建立协调模型和协调语言, 例如合同网模型、黑板模型、G PG P (通用部分全局规

划) 模型以及Linda 、Manifold 、C OO L 等协调语言

通用性的问题.

我们认为研究通用的协调理论的前提是对各种不同的协调问题有一个统一的描述和形式化表述. 为

[7]此, 本文基于Malone 和Crowston (1994) 对协调的定义, 从协调是管理活动间的相互依赖的观点, 提出一种

基于协调知识水平的协调理论研究框架. 将活动、资源、相互依赖和协调机制作为协调的基本要素, 用以刻画协调知识水平. 在此基础上, 对协调问题进行一般化的描述, 并提出一种基于协调知识水平的协调问题

收稿日期:2004206223

资助项目:国家自然科学基金(60274065)

　　作者简介:马巧云(1968-) , 女, 河南新密人, 讲师, 博士研究生, 主要研究方向:协调及其可计算化表达. 电话:[1**********]9,E 2mail :maqiaoyun@163. com. [5,6]. 但是这些协调模型和协调语言大都是针对某一类特定的协调问题或协调环境构建, 在使用的过程中常常受到问题本身和所处环境等条件的限制, 依然没有解决

的形式化表达方法. 该方法一方面可为建立覆盖大范围应用的协调模型和协调语言打下坚实的基础, 推动协调研究的进一步发展. 另一方面, 可方便地将活动间的各种相互依赖及其相应的协调机理固化为一个协调模块, 针对不同的问题映射到具体的应用领域, 加快以协调为主要功能的各类决策支持系统(DSS ) 的构建, 提高软件的可重用性.

2　协调知识水平

划分知识水平是理论研究中常用的研究手段之一. 在一定的知识水平上研究协调问题已有大量的工

[8]作, 例如Newell (1982) 提出了知识水平协作的概念, 对合作问题求解中的协调问题进行了探讨;

[9]McG uinness (2000) 利用本体来统一描述与特定领域相关的基本概念, 保证开放的异构系统间的协调, 也

是基于一定的知识水平进行的;Barbuceanu 和F ox (1996) 提出组织水平, 使用组织理论的概念(角色、能力

[10]等) 来描述组织水平, 在不同的结构层次上研究了组织协调中的相关问题;Jennings (1996) 提出合作知识

水平的概念, 将社会交互的知识与个体问题求解的知识分离, 有助于产生问题求解中涉及社会交互的规则、理论和方法.

一般地, 知识水平的划分有两种方法:一是纵向的划分方法, 即将知识划分为元知识、基础知识和应用知识等不同层次; 二是横向的划分方法, 即将知识划分为领域知识及问题中独立于具体领域的公共的抽象知识, 进而在独立于具体领域的公共抽象知识基础上建立相应的理论. 上文中提到的关于协调知识水平的研究, 多是从纵向划分知识水平, 这样并没有从根本上解决通用性问题. 本文拟采用横向划分知识水平的方法, 如图1所示, 将协调知识与领域知识分离, 并在协调知识水平上开展协调问题的研究

.

按照这一思路, 可以将协调知识定义为关于协调过程的知识, 而将

领域知识定义为与具体应用领域相关的知识. 显然, 领域知识随着应用

领域的不同而不同, 而协调知识则可由协调环境和协调机制的类型决

定, 是独立于具体应用的, 这就表明协调知识相对于领域知识具有相当

程度的稳定性. 从某种意义上讲, 这里的协调知识和数学知识是可以进

行类比的. 数学知识广布于各个应用领域, 但却可以从各个具体的应用

图1　知识水平的划分中抽象分离出来. 这更使我们坚信协调知识与领域知识是可分离的, 从而可在协调知识水平上来描述协调问题.

然而, 人们关于协调的知识同领域知识并非自然分离, 要寻求一种适于任何决策环境的最一般的协调知识是很困难的. 不过, 根据Malone 和Crowston (1994) 提出的协调定义, 即认为协调是管理活动间的相互

[7]依赖, 我们不难得知协调问题中包含的基本知识主要有:活动间相互依赖的知识和管理这些依赖的知识. 其中, 对依赖的管理主要表现为协调机制, 它可以看成协调问题的解; 而活动间的相互依赖可反映在活动的多个描述属性上, 如活动的目标、执行者、所需资源、执行时间等, 但这些属性无不通过活动的输入或输出加以体现. 如果我们将活动的输入集和输出集的元素统一表述为一种广义的资源, 那么活动间的相互依赖就表现为活动关于这种广义资源的相互依赖. (下文中如无特别声明, 提到的资源均为广义资源)

综上, 我们就可以用活动、资源、相互依赖和协调机制来描述协调知识水平. 其中, 活动可看成任务执行中不能再分解的一个过程, 资源可看成活动的输入或输出条件, 相互依赖刻画活动基于资源的相互关系, 协调机制是对活动基于资源相互依赖的管理, 可理解为协调问题的解. 在这一研究框架下, 首先必须解决的问题就是协调问题的统一描述. [11]

3　基于协调知识水平的协调问题描述

在上述基于协调知识水平的协调问题研究框架下, 协调的本质体现在管理活动间的相互依赖. 因此, 对协调问题的描述必须从分析活动间的相互依赖入手.

311　活动间的相互依赖

关于活动间相互依赖的研究已有相当长的历史. 有的从活动的执行者方面讨论依赖, 如Thom ps on (1967) 在其组织理论中基于组织单元间的相互依赖, 提出汇聚(pooled ) 、序列(sequential ) 和交互(reciprocal )

[12]三种相互依赖; 也有的从活动执行的时间方面来讨论依赖, 如Allen (1984) 提出活动基于时间的before 、

[13]meet 、overlap 、start 、end 、during 、equal 等七种基本相互依赖; 还有的从活动执行所耗用的资源出发来研究

活动间的相互依赖, 如Malone 和Crowston 提出基于资源的三种基本相互依赖, 即流依赖(flow ) , 共享依赖(sharing ) , 共同依赖(fit ) [14]. Rapos o (2001) 等将活动间的依赖分为时态依赖和资源依赖两种类型, 分别从活

[15]动的执行级和对象级两个层次上加以讨论, 定义任务间的相互依赖框架, 虽然其关于资源和时间的相

互依赖是独立的, 但其综合活动多属性的思路给了我们启示, 如何去统一这些从不同属性方面描述的各种依赖, 鉴于我们将活动的所有属性统一为广义的资源, 所以只要讨论活动间基于广义资源的相互依赖即可.

31111　活动间关于资源的基本相互依赖

因为任何活动间关于资源的相互依赖都可以分解为一系列两个活动关于一种资源的相互依赖, 所以我们将两个活动关于一种资源的相互依赖叫做活动间关于资源的基本相互依赖.

Malone (1999) 从与多个活动相关的资源出发, 提出了三种基本相互依赖:流依赖(flow ) , 共享依赖(sharing ) 和共同依赖(fit ) [14]. 如图2, 其中(a ) 流依赖是指一个活动发生所需要的资源由另一个活动产生, 如流水线作业中相邻的两个活动间的关系; (b ) 共享依赖是指多个活动的发生需要相同的资源, 如两个活动都需要使用同一台机器或同一个人完成; (c ) 共同依赖是指多个活动共同产生某种资源, 如对于汽车这种资源, 是由生产零部件和组装等活动共同产生

.

图2　活动间的基本依赖　

事实上, 我们也可从活动的输入和输出角度来考虑活动间关于资

源的基本相互依赖. 如图3, 设有两个活动a 1和a 2, 其输入输出分别为

Φ) ∨(X 1∩Y 2X 1, X 2, Y 1, Y 2. 这两个活动若发生关系, 则有(X 1∩X 2≠

Φ) ∨(Y 1∩X 2≠Φ) ∨(Y 1∩Y 2≠Φ) 为真. 因这里考虑的是关于一种≠

Φ(或X 1∩Y 2≠Φ) 时, 说明活动a 2的输入是活动a 1的输出资源的相互依赖, 这就意味着:当Y 1∩X 2≠

(或活动a 1的输入是活动a 2的输出) , 也即活动a 2发生所需要的资源由活动a 1产生(或活动a 1发生所图3　活动的输入输出

Φ时, 活动a 1和a 2有相同的输入, 也即活动a 1和需要的资源由活动a 2产生) , 如图2(a ) ; 当X 1∩X 2≠

Φ时, 活动a 1和a 2有相同的输出, 也即活动a 1和a 2a 2的发生需要相同的资源, 如图2(b ) ; 当Y 1∩Y 2≠

共同产生某种资源, 如图2(c ) .

综上, 我们认为活动间基于资源的基本相互依赖有且只有三种, 即流依赖(flow ) , 共享依赖(sharing ) 和共同依赖(fit ) .

31112　活动间关于资源的复合相互依赖

活动间的相互依赖不仅反映在两个活动间关于一种资源的相互依赖, 更多地反映在多个活动关于多个资源的相互依赖. 但这些依赖都可以分解为一系列的基本相互依赖, 因此将多个活动关于多个资源的相互依赖称为活动间复合的相互依赖.

显然, 两个活动关于n 种资源的相互依赖可以是n 个流依赖(如图4(a ) ) , n 个共享依赖(如图4(b ) ) , n 个共同依赖(如图4(c ) ) , 或是这三种依赖的复合.

m 个活动关于一种资源的相互依赖则表现为以下情况:

(a ) 可看成C 2

m 个共享依赖的复合(如图5(a ) ) ;

(b ) 可看成m -1个流依赖与C 2

m -1个共同依赖的复合(如图5(b ) ) ;

(c ) 可看成m -1个流依赖与C 2

m -1个共享依赖的复合(如图5(c ) ) ;

(d ) 可看成C 2

m 个共同依赖的复合(如图5(d ) ) ;

22(e ) ks 个流依赖、C k 个共同依赖与C s 个共享依赖

的复合(如图5(e ) ) , 其中k , s 均不小于2, 且k +s =

m .

m 个活动关于n 种资源的相互依赖可从每个资源

图4　两个活动基于n 个资源的相互依赖出发考虑活动间的相互依赖, 即可看成n 个多活动关于一种资源的相互依赖的复合, 当然它也是基本相互

依赖的复合

.

图5　m 个活动关于一种资源的依赖

　

由于协调的本质是管理活动间的相互依赖, 而活动间的相互依赖又统一为其关于资源的依赖, 所以要管理这些依赖, 就必须考虑资源的可用性, 讨论决定资源可用性的一些主要特征.

312　资源的特征

鉴于本文提到的资源包含了活动的输入和输出中的所有元素, 它可以是物质材料, 资金, 人的能力等等. 这些资源千差万别, 有的是可分的, 即可通过分割使用而不改变其功用, 如大多食品和资金等; 有的是并发的, 即不用分割就可满足多活动的使用, 如数据、信息等; 有的则是可重用的, 即可在活动中反复使用, 如可重用的软件等

资源的可用性.

资源的时间特性反映在其生命周期上. 几乎每种资源都有其生命周期, 或用起止时间区间表示, 或用初始时间加上有效期限表示. 但在现实中考虑资源的可用性时, 人们关注更多的是到期时间(即终止有效时间) 和现在时间的比较, 于是我们采用资源的到期时间来描述资源的时间特性.

资源的位置特性用来描述资源在合适的地方可用. 合适的地方不仅意味着资源在绝对的空间位置上, 更要考虑到该资源的并发操作, 如处在一定位置上的某大型耗能机器或库房等, 通常要求多个活动同时操作时才可用, 同时还会受到负荷限制, 限制最大的并发操作数. 所以, 资源的位置属性可用并发操作数的限制描述, 即可用区间[n 1, n 2]表示, 其中, n 1, n 2为自然数, 且n 1≤n 2, n 1为该资源限制的最小并发操作数, n 2为该资源限制的最大并发操作数. 特别地, 当资源不在可用的绝对位置上时, 该资源的位置属性规定为[15]. 但是无论哪种资源, 都有其存在的时间、位置、质量和数量等属性, 它们直接决定了∞.

资源的质量是个抽象的概念, 它可以是产品的规格、等级, 也可是人的能力等, 统一用q 表示, 主要用于与实际操作需求的质量进行比较.

资源的数量是指时间、位置、质量属性完全相同的资源的总和. 随着资源的类型不同, 可有不同的度量单位, 但对同种资源要保持计量单位一致, 尤其是在与实际操作需求的资源数量进行比较时, 更要保持计量单位一致.

这样, 就可用资源的上述属性刻画资源的可用性. 若资源r 对活动a 可用, 当且仅当这四个属性都满足要求.

313　协调问题的形式化描述

就协调问题的描述来说, 目前采用较多的是通过协调模型和协调语言来表达. 由于这些描述都不是从协调涉及的基本要素出发进行的, 往往只适于一些特定的情景, 这就不便于给出协调问题的统一化描述.

为此, 本文从协调的本质出发, 通过对协调涉及的基本要素进行分析, 在协调知识水平上建立协调问题的统一化表达.

从上述的分析可知, 协调问题涉及的基本要素有活动、资源和相互依赖, 为给出协调问题的形式化表达, 特引进符号R 、A 和D , 其含义如下:

R 为资源集, 它可随着环境的变化和活动的完成而实时地更新, 记为R ={r 1, r 2, …, r m }.其中的每个资源r i 通过时间、位置、质量和数量四种属性来刻画, 若资源r i 的到期时间(due time ) 为dt i , 位置特征为p i , p i =[n i 1, n i 2], 质量为m i , 数量为q i , 则记为r i =(name i ,d t i , p i , m i , q i ) . 对任意资源x =(name x ,d t x , p x , m x , q x ) , 其中p x =[n x 1, n x 2], 则x ∈R 当且仅当存在r i =(name i ,d t i ,[n i 1, n i 2], m i , q i ) , r i ∈R , 且name i =name x ,d t i >d t x (即资源r i 的到期时间晚于资源x 的到期时间) ,[n i 1, n i 2]Β[n x 1, n x 2], m i q x ;

A 为一系列不可分解的基本活动集, 可随着环境和目标的变化而更新, 记为A ={a 1, a 2, …, a n }, 其中每个活动a i 有其特定的输入集X i 和输出集Y i , X i ={x i 1, x i 2, …, x im i }, Y i ={y i 1, y i 2, …, y in i }, x ij , y ij 均为资源, a i 执行的必要条件是X i ΑR ;

D 为活动间的相互依赖集, 随着环境的变化和活动的执行而更新, 它有一系列的基本依赖构成, 记为D ={D 1, D 2, D 3}, 其中D 1, D 2, D 3分别表示流依赖、共享依赖和共同依赖.

ΠR ∈{D 1, D 2, D 3}, R ΑA ×A 描述了活动集上的一个二元关系, 若用R (a i , a j ) 表示活动a i 和a j 间的基本依赖, 结合前述关于基本依赖的定义, 有

D 1(a i , a j ) ≡(Y i ∩X j ≠

D 2(a i , a j ) ≡X i ∩X j ≠

D 3(a i , a j ) ≡Y i ∩Y j ≠

　　这样, 一般的协调问题就可用一个三元组(A , D , R ) 描述出来, 其中活动间的相互依赖D 是协调的必要条件, 而资源R 和活动A 是依赖存在的基础.

需要说明的是:有时尽管活动间存在相互依赖, 但在资源充足情况下是不需要协调的, 这时我们可认为该协调问题总有解, 是平凡的. 然而, 非平凡的协调问题通常以资源不足为前提. 活动a i 资源不足是指X i 中至少有一种资源不在R 中, 即X i ⁄R . 当系统中至少有一个活动资源不足时, 称系统资源不足. 显然, 当活动a i 资源不足, 且不依赖于其它活动时, 是无法协调的. 换言之, 该协调问题是无解的.

一般地, 为揭示协调问题, 我们可以按下列步骤进行:

(1) 检查系统中每个活动a i 的资源集X i 是否可用, 即判断X i ΑR (i =1,2, …, n ) 是否成立. 若对所有的活动都有X i ΑR , 则转(2) (3) , 否则转(4) .

(2) 检查满足X i ∩X j ≠

(3) 检查满足Y i ∩Y j ≠

(4) 对所有满足X i ⁄R 的活动a i , 通过搜索Y j (j ≠i ) , 找出满足X i ∩Y j ≠

综上, 我们可以按照分析活动→判断资源→分清依赖的顺序, 来对各种协调问题进行抽象, 进而通过三元组(A , D , R ) 对其进行形式化的描述. 这样对协调问题的求解过程, 就简化为对三种基本依赖的处理过程. 同时, 由于文中对协调问题的表述是形式化的, 所以为进一步通过计算机来求解协调问题打下了基础.

4　结束语

本文通过挖掘协调问题的本质特征, 采用横向划分知识水平的方法并对协调知识水平进行建模, 提出了一种基于协调知识水平的协调问题描述方法, 为探索通用的可计算化的协调模型提供了新思路.

基于协调知识水平的协调问题的统一描述是研究通用可计算化的协调模型的第一步. 后面需要进一步研究的工作包括:(1) 进一步研究活动间的三种基本依赖的形式化描述, 并针对各种依赖研究其相应的

协调机制; (2) 在研究各种依赖及其协调机制的基础上建立统一的形式化协调模型; (3) 利用形式化协调模型解释现有的各种协调模型; (4) 建立一套实现形式化协调模型向可计算化的协调模型转化的结构化方法.

参考文献:

[1]　Carley K M , G asser L. C omputational organization theory[A].G. Weiss Multiagent Systems[C].Massachusetts , M A :The MIT

Press , 1999. 299-330.

[2]　钱颂迪. 运筹学[M].第2版. 北京:清华大学出版社,1990. 216-227.

Qian S D. Operational Research[M].2nd Edition. Beijing :QinghuaUniversity Press ,1990:216-227.

[3]　Lind L. M ASSI VE:S oftware engineering for multiagent systems[D].PhD thesis , University of the Saarland , 2000. http Π:Πw w w.

agentlab. de Πdocuments.

[4]　Antonio Brogi ,Jean 2Marie Jacquet. On the expressiveness of coordination via shared dataspaces [J ].Science of C omputer

Programming , 2003, 46(1-2) :71-98.

[5]　Oss owski S. C oordination in Artificial Agent S ocieties :S ocial S tructures and Its Implications for Autonom ous Problem S olving Agents

[M].Lecture notes in artificial intelligence LNAI 1535,1999,31-63.

[6]　Arbab F. C oordination and its relevance [A ].Database and Expert Systems Applications[C].Ninth International W orkshop on ,

1998,26-28,529-535.

[7]　Malone T W ,Crowston K. The interdisciplinary study of coordination[J].AC M C omputing Surveys , 1994, 26(1) :87-119.

[8]　A. Newell. The knowledge level[J].Artificial Intelligence , 1982,18:87-127.

[9]　McG uinness D L. C onceptual m odeling for distributed ontology environments[A].Proceedings of the 8th International C on ference

on C onceptual S tructures Logical , Linguistic , and C omputational Issues (ICCS ) [C].Darmstadt , G ermany. August , 2000. 14-18.

[10]　Barbuceanu M , F ox M S. Capturing and m odeling coordination knowledge for multiagent systems [J].International Journal of

C ooperative In formation Systems , 1996, 5(2-3) :275-314.

[11]　Jennings N R. T owards a cooperation knowledge level for collaborative problem s olving [A ].Proceedings of 10th European

C on ference on AI[C].Vienna ,Austria , 1992:224-228.

[12]　Thomps on J D. Organizations in Action :S ocial Science Bases of Administrative Theory[M].McG raw 2Hill , New Y ork. 1967.

[13]　Allen J F. T owards a general theory of action and time[J].Artificial Intelligence ,1984,23:123-154.

[14]　Malone T W , Crowston K,et al. T ools for inventing organizations :toward a handbook of organizational processes[J].Management

Science , 1999,45(3) :425-443.

[15]　Rapos o A B , Magalhaes L P , Ricarte I L M. C oordination of collaborative activities 2a framew ork for the definition of tasks

interdependencies[A].Proceedings Seventh International W orkshop on G roupuare[C]., 2001,6-8:170-179.