《1 引言》

1 引言

在多Agent系统中, 如果给定的目标和环境包含有不确定性, 则Agent就无法更好地执行正确的行为。这种不确定性与不确定的环境、其他Agent的行为及智能Agent的行为密切相关。虽然有许多学者试图解决这一问题, 如他们提出的可信任度因子法、主观贝叶斯方法及Dempster-Shafer的证据理论, 但是他们基本上都是采用概率和统计的方法[1], 而这些方法常采用不确定知识的经验模型, 因而不具有逻辑系统所具有的直观语义;并且这些方法无法表示由自然语言组成的用户目标, 例如人类语言中有一类常用来表示事物的势态、人的情态以及过程变迁的词。像“大、中、小”, “必然、可能”, “知道、认可” 等是无法采用概率和统计的方法来描述的。并且多Agent系统中用于描述和解决现实世界问题的知识常常带有不确定性;因而Agent系统应能体现和反映知识的这种不确定性, 即能适当地表示不确定知识, 利用不确定知识的推理是非单调的、次协调的[1]。只有如此, Agent才能在不确定的环境中, 采取适当的行动来解决给定的问题, 或得到优化的解决方案。

由于模态逻辑通过引入模态词较好地解决了现实世界中的含糊性, 有关专家提出了利用模态逻辑来对含糊进行形式化描述, 如文献[2]提出的“上下文方法”, 但仅限于单个Agent的情况, 不适合于上述的多Agent系统, 于是笔者提出了基于Kripke结构[3] 的多Agent系统的信息处理方法。

《2 具有含糊性的多Agent系统》

2 具有含糊性的多Agent系统

假设在1个有n个Agent构成的组中, 每个成员了解外界和其他Agent的有关情况, 并且每个Agent所采取的唯一行动是告诉同组中其他成员它所知道的事情。并且, 还假设它仅告诉它所认为正确的事情, 且其他成员对它的话不产生怀疑。为了表述简单, 认为Agent之间的知识是不冲突的。

为了对Agent的信息状态进行处理, 采用了赋值的Kripke结构[4]

(Μ,w,V):Μ=W,{Ri}iA,A,wW

V是评价函数, V: WP2 , P2是命题变量P的幂集, W是可能世界的集合, A表示一个有限的Agent集, {Ri}iA 表示对于每个属于A的Agent i在世界中所能可达的关系。并且, 只有Agengt i在世界w中认为世界w′可能时, 可以说wRiw′。另外, 用模态运算集{Ki}iA 来表示知识, 其中 (M, w) |=Kiφ, 并且当对所有满足wRiw′的w′都有 (M, w) |=∧iG成立。以下将省略下面的结论 (因为它是上式的特殊情况) : (M, w) |=φ, 当且仅当对于任意的V都有 (M, w, V) |=φ成立。

在文献[4]的基础上, 定义了群体知识E和常识C:

(M, w) |= EGφ, 当且仅当有

(M, w) |=∧iGKiφ成立;

(M, w) |=CGφ, 当且仅当有

(M, w) |=∧iGEiφ成立。

此信息结构满足自反性和串行性, 即它们满足KD45, 对所有的wWiA满足以下性质:

(D) (M, w) |=Ki⊥, (串行性)

(4) (M, w) |=KiKiKiφ, (正自反)

(5) (M, w) |=KiφKiKiφ, (反自反)

Agent被赋予非常有限的通信能力, 即它们唯一通信行为的形式为tell (i, G, S) , 其定义如下:

定义1 tell。

tell是一个从赋值Kripke结构到另一个Kripke结构的函数, 它可以看作一个更新函数, 并且tell有3个参数 (i, G, S) , 其中i表示说话的Agent, GAi}表示听话的Agent, S是表示属于某一特定语言段Lspec上的自然语言句。虽然在模型中允许多于2个的tell行为同时发生, 但是当2个tell行为同时发生时, 将需要系统并行更新。为了描述方便, 考虑1次只允许1个tell行为发生。

1个从Lspec到命题逻辑Lpl0的函数τ将产生1个可能的代表S的语义, 实际上τ (S) 返回的是等价知识类的集合。并且那些等价的知识属于相同的类, 用 [φ] 表示φ的等价类。

事实上S在语义上含糊并不意味着说话者和听话者认为S是含糊的[5], 下面将看到如何形式化地定义语义含糊 (semantic ambiguity) 和感觉含糊 (perceived ambiguity) 之间的差别。

《3 语义含糊与感觉含糊定义2 语义含糊。》

3 语义含糊与感觉含糊定义2 语义含糊。

如果SLspec, 于是说S在语义上是含糊的, 当且仅当有|τ (S) |>1成立;也即是至少存在2种不等价的方式来表示S的语义。

根据Pinkal在文献[6]中的解释可知:一个句子在语义上是含糊的, 当且仅当在一定的条件下, 尽管有足够的相关事实, 但是仍然无法把true或者false作为它的真值。

例如, 句子“奥迪是一种快车”中所包含的修饰词“快”, 当解释为“对现代车而言是快车”时, 这个句子的真值为false;但是, 当把“快”解释为“对它同时代的车而言是快车”时, 这个句子的真值取决于和奥迪相比的车的类型。

于是可以得出如下结论:令pq表示2个命题, 命题pq更加准确 (相对含糊而言) , 当且仅当满足如下2个条件:在q为true (false) 的状态世界中, p也一定为true (false) ; 在q真值不确定的一定环境下, p的真值可能为true也可能为false。

定义3 感觉含糊。

假设S表示一个语义上含糊的句子, 正如定义2所示, 于是有tell (i, G, S) (M, w, V) = (M′, w′, V′) 成立, 并且下面的条件也成立:

(Μ,w,V)|=-C{i}Gφ(Μ,w,V)|=E{i}G([φ]τ(S)C{i}Gφ)

于是可以说S是感觉含糊的。

感觉含糊的解释如下:令AB表示在一次谈话中的2个参与者, 在谈话环境D下, A讲给B的言语UB认为在环境D中是含糊的, 需要满足的条件是BD下处理U时获得的结果不同于AU的解释。

语义含糊与感觉含糊之间的区别:语义含糊是属于语言语法的一部分, 句子在语义上是含糊的, 可能不被听话者所注意, 事实上它往往是由语言研究者所发现的;而感觉含糊是由理解 (interpretation) 的过程所导致的结果 (从本质上讲是无效的 (defeasible) 结果) , 因而可能会在错误传达 (miscommunication) 信息的情况下导致多种解释。另外, Poesio在文献[7]中认为, 语义含糊着重于描述多重感觉 (multiplicity of sense) 的理论模型, 而感觉含糊着重于描述有关推理。

《4 处理含糊性的准则》

4 处理含糊性的准则

对多agent通信行为的执行做以下约束, 这些约束是在Grice原理的基础上进行的, 可以看作是Grice原理在多 Agent系统中的部分应用[8]

令一个给定的形如 (M, w, V) 的赋值Kripke结构表示当前的信息状态。下面准则是对tell应用的约束, 如果有tell (i, G, S) (M, w, V) = (M′, w′, V′) , 则有 ∃[φ]∈τ (S) 满足如下准则:

1) (M, w , V ) |= Kiφ

定性准则:不要认为你缺少足够的证据。这一点是通过要求说话者至少知道一条S的知识为真。

2) (M, w , V) |=KiC{i}

定量准则:为当前的信息交换贡献出你的知识。Agent i知道至少一条知识S不是公共知识。

3) ∀[Ψ]∈τ (S) [φ]} (M, w , V ) =Ki (C{i}∪GΨC{i}∪GΨ)

行为准则:避免含糊。Agent i知道说话者和听话者之间的公共知识是属于S的所有知识Ψ且[Ψ]≠[φ]) , 并且其值的真假是确定的。

4) (M′, w′, V′) |=C{i}∪Gφ

评价准则:告诉完S后, φ成为听话者和说话者i的公共知识。

同文献[9]的规定相同, 条件分为前件 (pre-condition) 和后件 (post-condition) 。前件指的是通信行为执行之前 (也就是在更新原始的Kripke模型之前) 必须成立的条件, 后件指的是通信行为结束后那些必须成立的结果。

准则1至准则3 是把 tell应用到赋值Kripke结构时的前件, 而准则4是其后件, 也就是把说话者的贡献加入到公共知识中。详见文献[10]

在对多agent系统进行更新时, 当把前件 (1—3) 作为强行约束时, 将产生一个满足后件 (4) 的一个状态。也就是说:虽然Agent 能够和语义上含糊的句子进行通信, 但是这样的句子被听话者认为是含糊的情况不可能发生。

另一方面, 如果前件 (1—3) 被作为缺省约束应用时, 如说话者违反行为准则时, 则就不能保证评价准则成立。

同样在构建智能系统时, 检测含糊性也是十分重要的, 因为它能够通知系统去实现修补策略。同时也说明了含糊和析取之间的区别, 如果处理1个含糊句Sm个知识的析取∨Kmk=1φk 的方式相同, 这将导致更加弱的、形如 (M′, w′, V′) =C{i}∪Gk=1mφk的后件。

定义4 信息递增。

假设{Ki}*iA表示有限个元素{Ki}iA的串联集合, 其中也包括空序列ε

如果Κ{Κi}iA*并且 (M, w, V) =Κφ, 则有tell(i,G,S)(Μ,w,V)|=Κφ成立。

这里的信息递增的定义是建立在文献[11]中Groeneveld的“描述信息递增”的基础上进行的。

《5 含糊知识的更新》

5 含糊知识的更新

图1和图2的Kripke结构分别代表了Agent 1和Agent 2的信息状态。考虑有2个命题变量pq, Agent 1知道p成立, 但它无法确定q的真值。另外, Agent 1不知道Agent 2是否知道pq; 或者Agent 2不知道Agent 1是否知道pq

《图1》

图1 表示agent 1信息状态的Kripke结构Fig.1 Kripke structure representing information state of agent 1

图1 表示agent 1信息状态的Kripke结构Fig.1 Kripke structure representing information state of agent 1  

《图2》

图2 表示agent 2信息状态的Kripke结构Fig.2 Kripke structure representing information state of agent 2

图2 表示agent 2信息状态的Kripke结构Fig.2 Kripke structure representing information state of agent 2  

由图1可知, 实际上下列条件成立:

(Μ,w,V)|=Κ1p-Κ1q(Μ,w,V)|=-Κ1Κ2(C{1,2}pC{1,2}q)

由图2可知Agent 2认为下列条件成立:

(Μ,w,V)|=Κ2pq)(Μ,w,V)|=(Κ2(Κ1pΚ1q)

如果Agent 1告诉Agent 2有关S的情况是:τ (S) ={p, q}, 于是图1和图2中的模型必须用tell (1, {2}, S) 更新, 这样更新后的Agent 1和Agent 2的信息状态如图3和图4所示。

《图3》

图3 用S更新后的agent 1的信息状态Fig.3 Information states of agent 1 after updating with S

图3 用S更新后的agent 1的信息状态Fig.3 Information states of agent 1 after updating with S  

《图4》

图4 用S更新后的agent 2的信息状态Fig.4 Information state of agent 2 after updating with S

图4 用S更新后的agent 2的信息状态Fig.4 Information state of agent 2 after updating with S  

决定Agent 2的结果信息是十分复杂的。在多大程度上Agent 2遵循合作准则, 知道Agent 1违反了行为准则, 但是Agent 1没有感觉到这一点。为了简明起见, 假设说话者充分信任听话者, 也就是说, 他们认为听话者都遵循合作准则。

对于图4而言, 存在4种可能。对于每个S的知识有2个:S的知识之一是Agent 2认为Agent 1的认为p为真, 这是因为它不能确定q的真值, 或者由于它知道q不为真;另一个S的知识, 对于q来说, 情况同上, 这里不再重述。

可见通过tell函数对基于Kripke结构的多agent系统的更新, 使系统能够正确地把含糊子句传递的信息中语义含糊和感觉含糊区分开来。

《6 实例分析》

6 实例分析

例如, 为了证明 (ABA) , 其中τ (A) ={a1, a2}, B是不含糊的。必须证明下列4种情况都成立:

|=(a1B)a1|=(a1B)a2|=(a2B)a1|=(a2B)a2

下面给出每一种情况的证明树, 如图5所示。

《图5》

图5 4种情况分别对应的证明树

图5 4种情况分别对应的证明树  

Fig.5 Proof trees corresponding to four case

实际上, 图5中的证明树在结构上是相同的, 与它们是否包含含糊信息无关, 这表明了一种策略:可以延迟那些不含含糊的信息, 而合并它们相同的证明树。于是上述4种情况可以用带标号的紧凑证明树表示, 如图6所示。

《图6》

图6 紧凑的带标号证明树

图6 紧凑的带标号证明树  

Fig.6 Compact labeled proof tree

由于A是含糊的, 因而不符合提出的含糊性处理规则, 故在图6中的 (3) 和 (4) 不能合成1个分支。通过对图5和图6的比较可见, 所提出的含糊性处理方法的结构简单, 处理方便。

《7 相关工作分析》

7 相关工作分析

处理含糊性的一般方法是基于多值逻辑, 尤其是Zadeh提出的模糊逻辑 (被认为是泛化的多值逻辑) 倍受重视[12]。虽然用模糊逻辑对连续的观测值和模糊量词之间的关系进行建模是一种较好的形式化方法, 但是它不适合于形式化的逻辑推理。于是Fine提出了运用超值 (supervaluation) 来处理含糊性的方法[13]。近来Williamson把含糊认为是一种认知 (epistemic) 现象, 并提出了一种不同于Fine的处理含糊性的方法[14], 是一种基于模态逻辑的方法, 并且还融合和扩展了前人处理含糊性的有关方法。但是这些方法主要关注含糊的哲学含义, 而没有提出如何在AI知识库中对含糊性进行管理。笔者提出基于赋值Kripke结构的多agent系统中含糊性处理方法, 着重对语义含糊和感觉含糊进行了比较, 提出处理含糊性的有关准则, 并用具体实例说明对含糊性知识的处理, 这对于研究多agent系统有一定的实用价值。

《8 结语》

8 结语

在多Agent系统中含糊性可以在一定程度上利用Kripke结构加以处理, 但是由于多Agent系统的复杂性, 笔者对一些复杂情况做了简化处理, 给出一个在多Agent系统中如何形式化定义和解决含糊性的大致轮廓。笔者所建立的方法只是初步的, 还有许多问题需要解决, 像如何把此方法扩展到一阶 (动态) 逻辑?哪些经验公式在此方法中可以继续应用?这些都是下一步应该着重研究的目标。