对话(dialogue)是群体解决复杂问题的一个重要手段^[1].对话模型是对群体对话过程的形式化描述,它不仅是从修辞学角度研究群体对话规律的工具,还是计算机辅助群体研讨支持系统^[2]和基于辩论的多Agent交互系统^[3]的理论基础.一个好的对话模型不仅能刻画日常对话实际,还能很好地支持对话过程引导和共识提取.Walton和Krabbe^[4]从对话初始状态、群体共同目标和个体目标三个因素将对话分为信息索取(information seeking)^[5-6]、问询(inquiry)^[7]、劝说(persuasion)^[8]、谈判(negotiation)^[9-11]和协商(deliberation)^[12]等五种.目前对前四种对话建模的研究已有很多,但对协商对话建模的研究很少^[13].协商对话的目标是探寻群体共同行动方案,如“我们一起到哪里旅游?”、“面对气候变暖,我们的对策是什么?”等.群体成员在协商对话过程中利益目标一致,责任共担,不存在谈判对话中的利益分割问题.协商对话一般要经过确定问题、提出方案和对方案进行论证等三个阶段,其中提出方案是群体发散思维,而对方案进行论证是群体收敛思维.在协商对话之初,个体思维有限,有的还没有形成自己的方案,通过协商对话可以激活思维,促进方案的形成;而在协商对话后期,则要对众多方案进行论证,促进思维收敛,以便形成最终的为群体共同接受的方案.在协商对话过程中,参与者都是以谨慎、探寻和反省的态度与其他参与者交换意见^[14],而不是以击败对手为目标,在发言中往往会用“肯定”、“可能”、“不可能”等模态词,因而协商对话中存在一些不确定性信息.协商对话中每个主体虽然没有自己的个体目标,但有自己的信念,因而在协商过程中仍然存在矛盾和冲突,即在协商对话过程中会引发劝说对话^[15],通过辩论推理使问题得到论证^[8].因此,协商对话模型需要描述从发散到收敛的群体思维过程,并引入不确定性推理及辩论推理方法,其内容包括发言信息结构化分解、对话推演过程表示及争议评价算法等.

现有辩论模型大多只描述了协商对话过程中的某个阶段或某部分信息,没有提供对协商对话过程的全面刻画.例如Toulmin模型^[16]重在对论证结构的描述,但没有描述对话交互过程.基于问题的信息系统(Issue-based Information System, IBIS)模型^[17]描述了针对问题提出方案并给出方案的理由的决策过程,但没有表示对方案的多层论证结构.Dung的抽象辩论框架^[18]描述了争议之间的攻击关系,但它把争议抽象为一个节点而忽略争议的文本内容或内部结构,且没有考虑争议之间的攻击强度,不能反映日常协商对话的全部内容.目前协商对话模型大多建立在以上模型的基础之上,或对它们进行整合,或对它们进行扩展.如Carneades模型^[19]对Dung的抽象辩论框架进行扩展,采用Toulmin模型对争议进行结构化分解,但它没有描述协商对话过程中的提出方案阶段,只适合于对劝说对话的建模.Gordon等^[20]提出的Zeno模型是一个完整可计算IBIS模型,它允许对问题进行特化和泛化,并通过增加对争议节点的优先序关系确定争议的可接受性,但没有考虑针对方案的多层论证结构.Karacapilidis等^[21]的HERMES系统、Baroni等^[22-23]的QuAD模型、Liu等^[24-25]的基于模糊集的协商模型都是建立在IBIS模型基础之上,它们一方面对IBIS模型进行简化,不考虑对问题的特化和泛化等衍生处理,同时增加对方案的多层论证结构和争议评价量化计算,但它们都没有对争议进行结构化分解,不能反映协商对话的完整逻辑关系.目前针对多Agent协商对话的研究也有一些,但这些研究大多针对对话协议,而对争议的量化及评价没有提出相应方法^[14-15].在国内,谭俊峰等^[26]提出了树型研讨信息组织模型,该模型描述了发言节点间的语义关系,但没有描述节点之间反对或支持的强度.陈俊良等^[27]以IBIS模型和Toulmin模型为基础,建立了一种可对发言进行评价的研讨模型,并提出了一种基于语言加权集结(LWA)算子和节点归约的发言节点评价方法,其工作是对Liu等^[24-25]的基于模糊集的协商模型的改进,以语言评价代替模糊数,但并没有克服Liu等^[24-25]的方法存在的问题.

针对以上问题,本文提出一种基于IBIS模型的协商对话框架(Deliberation Dialogue Framwork, DDF),先对IBIS模型进行简化处理,不考虑对问题的特化、泛化等衍生处理,然后用可信度因子表示争议前提的不确定性和争议的论证强度.为了确定方案可信度值,提出一种基于模糊Petri网的共识评价方法,用模糊Petri网对DDF进行重构,将模糊争议映射为变迁,将争议前提和结论映射为库所,用托肯值表示陈述的可信度值,通过矩阵迭代运算求解各库所的托肯值,得出最终的协商对话结果.

IBIS模型^[28]由Horst Rittel提出,主要目的是用图形化方法对采用对话式论证方法求解结构不良问题的过程进行描述,在工程设计、城市规划、政治决策等领域有广泛应用.IBIS模型的基本元素有3种节点和9种边.3种节点分别是问题(Issue)、方案(Position)和争议(Argument). 9种边分别是：方案对问题的响应(Responds-to),争议针对方案支持(Supports-to)或反对(Objects-to);一个问题针对另一个问题的泛化(Generalize)或特化(Specialize)或替换(Replaces),一个问题针对另一个问题或方案或争议的质问(Question)或被建议(Be-suggested-by)、作为回避机制的与其他节点的链接(Other)等,如图 1所示.另外还有主题、事实和模型等3个其他元素.一个基于IBIS模型的完整辩论系统则由问题库、事实库、模型库、主题列表、问题论证映射和文件系统等组成.

IBIS模型的论证过程如下:

(1)参与者针对主题提出问题,并标识问题与方案的管理指标;

(2)编辑问题,并确定与其他问题的联系;

(3)提出解决问题的方案,并为每个方案提供一个争议表,这些争议来自于提出者与其反对者之间的争论;

(4)从文件系统中检索出针对问题的证据和意见,并将新找到的文献添加到文件系统中;

(5)更新问题-方案-争议映射图;

(6)问题要么通过产生一个可接受方案得到解决,要么需要从专家那里得更多的证据,要么方案受到质问和被建议而引发一个新的问题.

IBIS模型是对复杂问题决策过程的全面刻画,既考虑了针对方案的论证,又考虑了问题的泛化、特化和替换等处理,并对决策过程中需要的数据和支撑资料提供支持.IBIS模型主要针对政策决策问题,早期采用手动方式组织和管理决策.但它存在以下问题:一是没有提出方案可接受性的标准,不能自动得出协商结果;二是没有考虑发言信息的可信度,也没有考虑争议的论证强度;三是由于允许对问题进行泛化、特化、替换等多种处理,同时允许针对问题、方案和争议通过质问和被建议而衍生出新的问题,而且对问题的衍生没有限制,增加了问题的组织和管理难度.这些不足使IBIS模型在计算机系统中的实现面临困难.

协商对话框架建立在IBIS基础之上,即对IBIS模型进行约简、扩展和量化.约简是指只针对单一问题进行协商,不考虑问题的泛化、特化和替换等处理,这样处理的目的是使该模型便于在计算机系统中实现.扩展是指增加对争议的结构化表示,并增加针对方案的多层论证结构.为了体现协商对话的特点,增加对争议前提不确定性和争议论证强度的量化表示.

协商是通过对话进行的^[4],对话的基本单元是发言.按照发言的目的,可以把发言分为以下4种类型: 1)针对问题提出方案; 2)对方案或其他发言进行论证; 3)提出质询; 4)回答质询等.其中提出质询不增加任何决策信息,而回答质询可以看作是对前一发言的补充.除此之外,协商对话模型中不考虑与决策无关的其他发言信息.这样所有发言都应该是针对问题或之前的其他发言的响应,整个协商对话将形成一棵以问题为根的树形结构.

定义1 (Statement)  陈述是对事物的肯定性描述,它是发言的基本组成单位.设有两陈述$h_1$、$h_2$,如果它们逻辑上相同,则记为$h_1=h_2$,如果它们逻辑上相反,则记为$h_1=\lnot h_2$.所有陈述的集合记为${\cal L}$.

定义2 (Issue)  问题是协商对话的对象,整个协商对话只针对一个问题,记为$t$.问题一般是用陈述表述的,因此有$t\in {\cal L}$.

本定义是对IBIS模型进行简化,即不考虑由问题、方案和争议衍生出来的其他问题.

定义3 (Position)  方案是问题求解的备选答案,所有方案的集合记为${\cal P}$.方案也是用陈述表述的,因此有${\cal P} \subseteq {\cal L}$.

定义4 (Argument)  有明确主张和相应根据的发言称为争议.争议可以表示为一个二元组$A=\langle H, h\rangle $,其中$H=\{h_1, \cdots, h_n\}$称为争议的前提集, $h_i \in {\cal L}(i\in \{1, 2, \cdots, n\})$称为争议的前提, $h\in {\cal L}$称为争议的结论,且满足当$h_1, \cdots, h_n$都成立时,结论$h$成立.所有争议的集合记为${\cal A}$.

如果一个争议只有一个前提$p$,且$h=t$,则称为方案争议(Position Argument),记为$A_p=\langle \{p\}, t\rangle $,其中$p\in {\cal P}$表示一个方案, $t$是协商对话的问题.在某一时刻,如果一个争议没有受到其他争议的响应,则称为叶子争议(Leaf Argument).如果一个争议没有前提,即$H= \Phi $,表示为$\langle -, h\rangle$, $h\neq t$,则称为表决争议.表决争议的作用是对方案或其他争议的前提表明态度,其他争议无法对其进行响应.

争议可以转换成产生式规则:

ⅰ)只有一个前提的争议:$A=\langle\{h_0\}, h\rangle$,其产生式规则为:

$R:if\ h_0\ then\ h. $

ⅱ)有多个前提的争议：$A=\langle\{h_1, \cdots, h_n\}, h\rangle$,其产生式规则为:

$R:if\ h_1\ and\ \cdots \ and\ h_n\ then\ h. $

本定义是对IBIS模型进行扩展,即对争议进行结构化处理,支持多个前提对一个结论的论证.

在实际协商对话中,争议具有不确定性.可以用模糊争议来表示这种不确定性.

定义5 (Fuzzy Argument)  模糊争议是一个四元组

$A=\langle H, h, cf, d \rangle, $

其中$H=\{h_1, \cdots, h_n\}$, $h_i\in {\cal L}(i\in \{1, 2, \cdots, n\})$称为争议的前提; $h\in {\cal L}$称为争议的结论; $cf:H\to [0, 1]$,是给每个前提赋予一个可信度值的映射; $d$是争议的论证强度,表示争议前提$H$支持结论$h$的强度.

对于前提$h_i$, $cf(h_i)\in [0, 1]$,即争议前提的可信度均为正值,因为争议提出者不会使用可信度为负的陈述作为争议的前提.$d\in [-1, 1]$,如果$d>0$,则表示争议的前提对结论是支持的,如果$d < 0$,则表示争议的前提对结论是反对的,当$d=0$时,则表示争议在协商对话中不起作用.

本定义是对IBIS模型进行量化,有了量化就可以计算方案的共识值,并依共识值确定方案的可接受性.

定义6 (Dialogue)  设有两个争议$A_1=\langle H_1, h_1\rangle$, $A_2=\langle H_2, h_2\rangle $,如果$h_1\in H_2$,则称$A_1$是对$A_2$的对话,记为$\langle A_1, A_2\rangle$.对话实际上是一个争议对另一个争议的响应.所有对话的集合记为${\cal D}$.

定义7 (Deliberation Dialogue Framework)  协商对话框架是一个4元组: $DDF=({\cal L}, t, {\cal A}, {\cal D})$,其中${\cal L}$是陈述集, $t$是协商对话的问题, ${\cal A}$是争议集, ${\cal D}\subseteq {\cal A}\times {\cal A}$是对话集.

协商对话框架可以用一个图表示(如图 2所示).图中矩形表示陈述,圆圈表示争议.由争议指向陈述的带箭头的连线表示争议与陈述之间的论证关系,这里的陈述是争议的结论.连接陈述与争议的无向边表示陈述对争议的支持关系,这里的陈述是争议的前提.

陈述分问题、方案和一般陈述3类,一般陈述可以作为争议的前提,也可以作为争议的结论.方案只能作为方案争议的前提.问题只能作为方案争议的结论.

IBIS模型对方案的论证只有一层,因而无法实现对论证的论证.对IBIS模型的扩展的关键是增加对方案的多重论证,即辩论结构,这样就形成了一个以方案争议为根的对话树.如果针对问题提出多个方案,则产生多个对话树,从而构成对话森林.

定义8 (Dialogue Tree)  对话树是有$n(n\geq 1)$个争议节点的集合.在任意一棵对话树中,有且仅有一个争议$A_0$称为根.当$n>1$时,除根之外的其余争议可以分为$m(m>0)$个互不相交的争议集合$T_1, \cdots, T_m$,其中$T_i(1\leq i\leq m)$本身又是一棵对话树,称为$A_0$的子树(SubTree),且有$\langle A_i, A_0\rangle \in {\cal D}$,其中$A_i$是$T_i$的根争议.

定义9 (Dialogue Forest)  $n(n\geq 0)$棵互不相交的对话树的集合称为对话森林.

对话森林是对整个协商对话过程的抽象描述, 图 2对应的对话树和对话森林如图 3所示.对话森林由若干个对话树组成,每棵对话树描述了对某个方案的辩论过程,其根为方案争议.对话森林中有几棵对话树,就表明在对话过程中产生了几个方案.如果能够计算每棵对话树的方案争议的前提(即方案)的共识值,并根据共识值对方案进行排序,就可以确定整个协商对话的结果.

协商对话框架只是描述了对话过程,但并不能确定哪个方案是可接受的,因此接下来需要对方案的可接受性进行计算.本文采用模糊Petri网对协商对话框架进行映射,并提出求方案共识值的算法,最后根据方案的共识值确定方案的可接受性.

Petri网是一种图形化系统建模工具^[29],适合描述具有并发或并行行为的系统.模糊Petri网是对普通Petri网的模糊化.与普通Petri网相比,模糊Petri网的变迁是否点火取决于变迁的阈值$\tau(\tau \in \mathbb R, \tau \geq 0)$,而不是库所中的标记数;库所的标记数不再是一个正整数,而可以是任意正实数$t_k$;输入弧和输出弧上标有权值,它根据不同应用代表不同意义,也称为连接强度.

在模糊Petri网运行之前,先进行初始化,即给每个库所赋予一个正实数,称为库所的托肯值.运行时,先计算变迁的各输入弧的输入强度.一个变迁的一个输入弧的输入强度由函数$S(i_k, a_k)$确定, $0\leq S(i_k, a_k)\leq i_k, i_k \leq t_k$,其中$i_k$是输入弧的输入量, $t_k$是与输入弧相连接的库所（称为输入库所）的托肯值, $a_k$是输入弧的连接强度.然后计算变迁的总输入量$IN$,它与变迁的各输入弧的输入强度有关,即$IN=f(S(i_1, a_1), \cdots, S(i_n, a_n))$,将$IN$与$\tau$进行比较以决定是不是点火.点火后,该输入库所的托肯值变为：$t_k=t_k-i_k$.与输出弧相连的库所（称为输出库所）的托肯值变为：$t_k=t_k+R(i_j, \beta_j)$,其中$t_k$是输出库所的托肯值, $R(i_j, \beta_j)$是输出弧的输出量, $0\leq R(i_j, \beta_j) \leq i_j$, $i_j$是输出库所的额定输入量, $\beta_j$是变迁到输出库所的连接强度.如此不断改变库所的状态.

协商对话与基于模糊Petri网的逻辑推理有相似之处,可以将协商对话框架映射为模糊petri网.映射方法是将争议的前提和结论映射为库所,将模糊争议映射为变迁,将陈述可信度映射为库所的托肯值,将争议论证强度映射为变迁到输出库所的连接强度.为了简单起见,输入库所到变迁的连接强度统一定为1.将模糊争议映射为变迁是映射过程的关键.可以先将模糊争议转换为模糊产生式规则,再将模糊产生式规则映射为变迁.设有模糊争议$A=\langle H, h, cf, d \rangle$,其模糊产生式规则为:

$R:\ {\rm if} \ h_1(cf_1)\ {\rm and}\ \dots \ {\rm and}\ h_n(cf_n)\ {\rm then}\ h\ (d) $

其对应的模糊petri网如图 4所示.

定义10 (Deliberation Mapping)   协商对话框架可以转换为模糊Petri网,该Petri网称为协商对话模糊Petri网(Fuzzy Petri Net for Deliberation, FPND). FPND是一个7元组: $FPND=(P, T, D, I, O, \tau, G)$,其中

$P=\{p_1, \cdots, p_n\}$表示有限库所集合,它是对协商对话框架中陈述(争议的前提和结论)的映射.

$T=\{t_1, \cdots, t_m\}$表示有限变迁集合,它是对协商对话框架中的模糊争议的映射,它反映了从前提到结论的论证.

$D=\{d_1, \cdots, d_n\}$表示有限陈述集合,它与$P$有一一对应的关系,即$|P|=|D|$.

$I$是定义在$P\times T$上的带权值的连接关系,其权值对应模糊Petri网的输入弧的连接强度.$I(p_i, t_j)\in \{0, 1\}$,如果$I(p_i, t_j)=1$,表示$p_i$是$t_j$的一个前提,如果$I(p_i, t_j)=0$,表示$p_i$不是$t_j$的前提.

$O$是定义在$T\times P$上的带权值的连接关系,它对应模糊Petri网的输出弧的连接强度,且满足$-1 <O(t_j, p_i)\leq 1$.在协商对话框架中,它对应模糊争议的论证强度$d$.如果$O(t_j, p_i)=0$,表示$p_i$不是$t_j$的结论.

$\tau$是变迁点火的阈值,一般规定$\tau \geq0$.

$G:P\to [0, 1]$,是从库所到托肯值的映射,记为$G(p)$.$G_0(p)$表示库所的初始托肯值.

当变迁的总输入量$IN$大于变迁阈值$\tau$时,变迁点火,变迁的输出库所的托肯值将发生改变.为了与实际协商对话一致, FPND与模糊Petri网有一些不同的规定:

(1)变迁的各输入弧上的输入量与输入库所的托肯值一致,不再另设输入量,即$i_k=t_k$;

(2)变迁点火后,只改变变迁输出库所的托肯值,而输入库所的托肯值不变,即不执行$t_k=t_k-i_k$.

FPND是随着对话的进行而逐步构造起来的,新产生的争议所对应的变迁的输出库所是被响应争议所对应的变迁的一个输入库所,如果新产生的变迁点火,则会引起前一变迁的输入库所的托肯值的更新,这种更新进而传递到根节点.与基于模糊Petri网的逻辑推理不同^[30],非叶子争议节点的前提对应的库所的初始托肯值不为0,因而变迁点火后需要对响应链上的库所托肯值进行合成,这种合成一直要传递到根节点.因而FPND中托肯值的计算包括托肯值合成和托肯值传递两个方面.

设有模糊争议$A=\langle H, h, cf, d \rangle$,争议前提陈述$h_1, \cdots, h_n$对应的库所分别为$p_1, \cdots, p_n$,其初始托肯值分别为$cf_1, \cdots, cf_n$,它对应库所的输入量;输入库所到变迁的连接强度分别为$x_1, \cdots, x_n$.争议对应FPND中的变迁,争议论证强度对应FPND的变迁的输出强度.

每个输入弧的输入强度为$S(i_i, a_i) = (cf_i\times x_i)\in [0, 1]$,变迁的总输入量为$IN=\min\{cf_1\times x_1, \cdots, cf_n\times x_n\}$,其中$cf_i\times x_i>0$.如果$IN>\tau$,则变迁点火,这时变迁的输出量$OUT=IN$,否则变迁不能点火,变迁的输出量$OUT=0$.这里,变迁的总输入量取非零输入强度的最小值.

变迁点火后,变迁的输出库所的托肯值将发生变化.其计算方法为:

首先计算该库所的所有输入弧的输入量,如果该库所的第$j$条输入弧对应变迁存在输出量$i_j$,相应的从变迁到输出库所的连接强度为$\beta_j$,则该变迁施加给输出库所的输入量为:

(1) $R(i_j, \beta_j)=i_j\times \beta_j .$

由于$\beta_j$就是争议论证强度,其值的范围在$[-1, 1]$,因此变迁点火后, $R(i_j, \beta_j)$可能为正,也有可能为负.

然后将库所$p$的所有输入量进行集结.假设库所$P$有两个输入量:$R_1$、$R_2$,则集结后的输入量$R_{12}$为:

(2) $ R_{12}=\left\{ \begin{array}{ll} R_1+R_1(1-R_2), & {\rm if}\ R_1\geq 0\ {\rm and}\ R_2\geq 0, \\ R_1+R_1(1+R_2) , & {\rm if}\ R_1<0\ {\rm and}\ R_2<0, \\ \frac{R_1+R_2}{1-\min\{|R_1|, |R_2|\}} , & {\rm if}\ R_1\times R_2 <0, \end{array} \right. $

当库所$p$的输入量有多个时,即$\{R_1, \cdots, R_n\}$,按公式(2)先将$R_1$、$R_2$集结为$R_{12}$,再将$R_{12}$和$R_3$集结为$R_{123}$,依此直到$R_n$,得到库所$p$的总输入量$R$.集结后,库所$p$的总输入量可能为正值,也可能为负值.

最后进行托肯值合成:将库所$p$的总输入量$R$与它的原托肯值$S$进行合成,其合成公式为:

(3) $ S'=\left\{ \begin{array}{ll} S+R(1-S) , &{\rm if}\ 0<R\leq1 , \\ S , & {\rm if}\ R=0, \\ S(1+R), & {\rm if}\ -1\leq R<0, \end{array} \right.$

该公式的一个重要性质是保证了合成后库所的托肯值的取值范围为$[0, 1]$.

一个新的争议产生后,从该争议到根争议的响应链上的所有库所的托肯值都要更新,我们采用矩阵迭代运算对托肯值的更新进行计算.

(1) $X=(x_{ij})_{n\times m}$为输入矩阵.$x_{ij}$表示从库所$p_i$到变迁$t_j$的连接强度.由于连接强度可以折算到库所的托肯值,所以为了简化起见,若库所$p_i$到变迁$t_j$有输入弧,则$x_{ij}=1$,否则$x_{ij}=0$.其中:$i\in\{1, 2, \cdots, n\}$, $j\in\{1, 2, \cdots, m\}$. $n$是库所的个数, $m$是变迁的个数.

(2) $Y=(y_{ij})_{n\times m}$为输出矩阵.$y_{ij}\in [-1, 1]$,表示变迁$t_j$到库所$p_i$的输出强度,它对应争议论证强度$d$.若变迁$t_j$到库所$p_i$没有输出弧,则$y_{ij}=0$.其中: $i\in\{1, 2, \cdots, n\}$, $j\in\{1, 2, \cdots, m\}$.

(3) $S=[S_1, S_2, \cdots, S_n]^T$表示各库所的托肯值.$S_i\in[-1, 1]$, $i\in\{1, 2, \cdots, n\}$. $S_0=[S_{10}, S_{20}, \cdots, S_{n0}]$表示库所的初始托肯值.

(4) ${\varGamma} = [\tau_1, \tau_2, \cdots, \tau_m]^T$表示各变迁点火的阈值, $1\leq \tau_j \leq 1$, $j\in\{1, 2, \cdots, m\}$.

算子定义如下:

(1)连接算子$\bigtriangleup$: $C=A\bigtriangleup B$,其中$A$是$k\times l$矩阵, $B$是$l$维列向量, $C$是$k\times l$矩阵, $C$的元素$c_{ij}=a_{ij}\times b_j$,其中$i\in\{1, 2, \cdots, k\}$, $j\in\{1, 2, \cdots, l\}$.该算子将矩阵$A$中的每行各元素对应乘以列向量$B$中的元素.该算子可用在两处,一是根据输入矩阵和库所的托肯值向量计算各变迁输入弧的输入强度,这时$A$是输入矩阵的转置矩阵, $B$是各库所的托肯值向量;二是根据输出矩阵和变迁点火值向量计算各库所输入弧的输入量,这时$A$是输出矩阵, $B$是各变迁的点火值向量.

(2)行最小算子$\bigtriangledown$: $B=\bigtriangledown A$,其中$A$是$m\times n$矩阵, $B$是$m$维列向量, $b_j=\min(a_{j1}, a_{j2}, \cdots, a_{jn})$,其中$j\in\{1, 2, \cdots, m\}$,且$a_{jk}\neq 0$, $k\in\{1, 2, \cdots, n\}$.该算子求$A$矩阵各行的非零元素的最小元素,其作用是求各变迁的输入量.这里采用Shortliffe^[31]的可信度方法,即模糊命题合取式的真值取各子式真值的最小值.

(3)比较算子$\partial$: $C=A\ \partial\ B$,其中$A$、$B$、$C$都是$m$维列向量,若$a_j\geq b_j$,则$c_j=a_j$,否则$c_j=0$,其中$j\in\{1, 2, \cdots, m\}$.该算子用于计算变迁的点火值,当变迁的输入量大于点火阈值时,点火值为$a_j$,表明能点火,当变迁的输入量小于阈值,点火值为0,表明不能点火.

(4)集结算子$\Phi$: $B=\Phi A$,其中$A$是$m\times n$矩阵, $B$是$m$维列向量.该算子的作用是根据公式(2)对$A$的每一行各元素进行集结.

(5)合成算子$\oplus$: $C=A\ \oplus\ B$,其中$A$、$B$、$C$都是$n$维列向量, $c_i=a_i\ \oplus\ b_i$,其中$i\in \{1, 2, \cdots, n\}$.该算子的作用是根据公式(3)进行可信度合成,其中$A$对应协商对话框架中的库所原托肯值向量, $B$对应变迁点火后产生的各库所的新增托肯值向量.

假设有$n$个库所, $m$个变迁,托肯值更新算法Token-revision如下:

INPUT:协商对话模糊Petri网(FPND),包括输入矩阵$X$,输出矩阵$Y$,库所的初始托肯值向量$S_0$,变迁点火阈值向量${\varGamma}$.

OUTPUT:各库所的托肯值.

设$k$的初值为0; ($k$是迭代次数)

STEP 1.计算各变迁输入弧的输入强度, $E_k=X^T\bigtriangleup S_k$, $E_k$是一个$m\times n$矩阵;

STEP 2.计算各变迁的总输入量：$F_k=\bigtriangledown\ E_k$, $F_k$是一个$m$维的列向量;

STEP 3.将变迁输入量与变迁阈值比较,得到各变迁的有效总输入量:$G_k=F_k\ \partial\ {\varGamma}$;

STEP 4.计算变迁点火后各输出库所的输入量:$H_k=Y\bigtriangleup G_k$;

STEP 5.计算变迁点火后各库所的托肯值的增加量: $S^k=\Phi H_k$;

STEP 6.计算当次迭代后各库所的托肯值:$S_{k+1}=S_0\oplus S^k$;

STEP 7.用$S_{k+1}$代替STEP 1中的$S_k$,重复进行STEP 1-STEP 6,直到所有库所的托肯值不再发生变化,则算法结束.

托肯值更新函数Token-revision的迭代次数与对话树的高度相同,当迭代到根节点时,所有库所的托肯值将不再发生变化.假设对话树的高度为$h$,则算法Token-revision的执行次数为$h$. Token-revision的主要时间消耗是矩阵运算,假设协商对话树的库所的个数为$n$,变迁的个数为$m$,则矩阵运行的时间复杂度为$O(mn)$,再将托肯值更新函数的调用次数考虑进去,则整个算法的时间复杂度为$O(mnh)$.由于考虑了变迁的点火阈值,有些矩阵运算可能不执行,这样还可以进一步提高效率.

协商对话结果是方案所对应的库所的托肯值,这个结果称为方案共识值.方案共识值的取值范围为$[0, +1]$.共识值越大,说明群体成员对此方案的支持程度越大;共识值越小,说明群体成员对此方案的支持程度越小.

假设群体就某一问题进行协商对话,对话过程中,共提出三个方案$P_1^1$、$P_1^2$、$P_1^3$,再对这三个方案进行论证,形成三个协商对话树,相应的FPND协商对话图如图 5所示,相应的初始值如表 1所示.

假设所有变迁的点火阈值都0,具体计算如下:

(1)针对方案$P^1_1$,共有11个库所和5个变迁,算法输入分别为:

1)输入矩阵为:

$ X=\left[ \begin{array}{ccccccccccc} 0 &~ 1~ & 1 &~ 0~ & 0 & ~0~ & 0 & ~0~ & 0 & ~0~ & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right]^T. $

2)输出矩阵为:

$ Y=\left[ \begin{array}{ccccccccccc} 0.9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & ~-0.9~ & 0 &~ 0~ & 0 &~ 0~ & 0 & ~0~ & 0 &~ 0~ & 0\\ 0 & 0.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & -0.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -0.7 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right]^T. $

3)变迁阈值向量为:

$ {\varGamma}=\left[ \begin{array}{ccccc} 0&~0~&0&~0~&0 \end{array} \right]^T . $

4)库所初始托肯值向量为:

$ S_0=\left[ \begin{array}{cccccccccccc} 0 &~ 0.5~ & 0.9 &~ 0.8~ & 0.9 &~ 0.7~ & 0.6 & ~0.7~ & 0.6 & ~0.6~ & 0.8 \end{array}\right]^T . $

第一次迭代:

STEP 1.计算各变迁输入弧的输入强度, $E_0=X^T\bigtriangleup S_0$,

$ E_0=X^T\bigtriangleup S_0=\left[ \begin{array}{cccccccccccc} 0 &~ 0.5~ & 0.9 & ~0~ & 0 &~ 0~ & 0 & ~0~ & 0 &~ 0~ & 0\\ 0 & 0 & 0 & ~0.8~ & 0.9 &~ 0.7~ & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0.6 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & ~0.7~ & 0.6 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ~0.6~ & 0.8 \end{array} \right]. $

STEP 2.计算各变迁的总输入量:$F_0=\bigtriangledown E_0$,

$ F_0=\bigtriangledown E_0=\left[ \begin{array}{ccccc} 0.5 & ~0.7~ & 0.6 &~ 0.6~ & 0.6 \end{array} \right]^T. $

STEP 3.将变迁输入量与变迁阈值比较,得到各变迁的有效总输入量:$G_0=F_0\ \partial\ {\varGamma}$;

$ G_0=F_0\ \partial\ {\varGamma}=\left[ \begin{array}{ccccc} 0.5 &~ 0.7~ & 0.6 & ~0.6~ & 0.6 \end{array} \right]^T. $

STEP 4.计算变迁点火后各库所的输入强度: $H_0=Y\bigtriangleup G_0$;

$ H_0=Y\bigtriangleup G_0=\left[ \begin{array}{cccccccccccc} 0.45 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & ~-0.63~ & 0 & ~0~ & 0 & ~0~ & 0 &~ 0~ & 0 & ~0~ & 0\\ 0 & 0.48 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & -0.48 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -0.42 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right]^T. $

STEP 5.计算变迁点火后各库所的托肯值的增加量: $S^0=\phi H_0$;

$S^0=\phi H_0=\left[\begin{array}{ccccccccccc}0.45 & ~-0.2885~ & -0.48 &~ 0~ & -0.42 & ~0~ & 0 & ~0~ & 0 & ~0~ & 0 \end{array}\right]^T. $

STEP 6.计算本次迭代后各库所的托肯值: $S_1=S_0\oplus S^0$;

$ S_1=S_0\oplus S^0=\left[ \begin{array}{ccccccccccc} 0.45 & ~0.3558 ~& 0.468 & ~0.8 ~& 0.522 & ~0.7~ & 0.6 & ~0.7~ & 0.6 & ~0.6~ & 0.8 \end{array}\right]^T. $

第二次迭代后:

$ S_2=\left[ \begin{array}{ccccccccccc} 0.3202 & ~0.5096~ & 0.468 & ~0.8~ & 0.522 &~ 0.7~ & 0.6 &~ 0.7~ & 0.6 &~ 0.6 ~& 0.8 \end{array}\right]^T. $

第三次迭代后:

$ S_3=\left[ \begin{array}{ccccccccccc} 0.4212 & 0.5096 & ~0.468~ & 0.8 & ~0.522 ~& 0.7 & ~0.6~ & 0.7 &~ 0.6~ & 0.6 & ~0.8 \end{array}\right]^T. $

以后库所托肯值不再发生变化,最后得到$p_1$的可信度值为0.4212.

(2)针对方案$P^2_1$,共有4个库所和2个变迁,依照以上方法计算,第一次迭代的结果为:

$ S_1=S_0\oplus S^0= \left[ \begin{array}{ccccccc} 0& 0.8 & 0.3& 0.5 \end{array} \right]^T \oplus \left[ \begin{array}{ccccccc} 0.21 & 0 &-0.4 & 0 \end{array} \right]^T =\left[ \begin{array}{ccccccc} 0.21 &0.8 & 0.18 & 0.5 \end{array} \right]^T. $

第二次迭代的结果为:

$ S_2=S_0\oplus S^1=\left[ \begin{array}{ccccccc} 0.126 & 0.8& 0.18 & 0.5 \end{array} \right]^T. $

以后库所托肯值不再发生变化,最后得到$P^2_1$的可信度值为0.108.

(3)针对方案$P^3_1$,共有2个库所和1个变迁,算法经过一次迭代即停止,结果为:

$ S_2=S_0 \oplus S^1=\left[ \begin{array}{ccc} 0 & 0.8 \end{array} \right]^T \oplus \left[ \begin{array}{ccc} 0.4 & 0 \end{array} \right]^T =\left[ \begin{array}{ccc} 0.4 & 0.8 \end{array} \right]^T . $

对应$P^3_1$、$P_{17}$的托肯值为分别为:0.4, 0.8.

在本例中, $P^1_1$、$P^2_1$、$P^3_1$为针对问题的三个备选方案.在方案$P^1_1$的对话树中,第一次迭代, $P^1_1$的托肯值因为变迁$t^1_1$的支持由原来的0上升为0.45;$t^1_2$和$t^1_3$的共同作用于$P^1_2$, $t^1_2$以$-0.63$的值反对$P^1_2$,而$t^1_3$以0.48的值支持$P^1_2$,先把支持值与反对值进行集结,得到$-0.2885$,再与$P^1_2$的原值进行合成使$P^1_2$的托肯值由原来的0.5降为0.3558; $P^1_3$的托肯值因为变迁$t^1_4$的反对由原来的0.9下降为0.468; $P^1_5$的托肯值因为变迁$t^1_5$的反对由原来的0.9下降为0.522.第二次迭代,变迁$t^1_1$的输入库所$P^1_2$, $P^1_3$的托肯值由于第一次迭代作用分别由原来的0.5、0.9变为0.3558、0.468, $t^1_1$的总输入量由0.5降为0.3558,致使$P^1_1$的托肯值由原来的0.45下降为0.3202;变迁$t^1_2$的输入库所$P^1_5$的托肯值由于第一次迭代作用由原来的0.9变为0.522, $P^1_2$重新集结合成后其托肯值0.3558变为0.5096,本次迭代$P^1_3$、$P^1_5$的托肯值不变.第三次迭代,变迁$t^1_1$的输入库所$P^1_2$的托肯值由于第二次迭代作用由原来的0.3558变为0.5096,重新计算$P^1_1$的托肯值为0.4212.以后迭代停止.

在方案$P^2_1$的对话树中,第一次迭代, $P^2_1$的托肯值因为变迁$t^2_1$的支持由原来的0上升为0.21;$P^2_3$的托肯值由于变迁$t^2_2$的反对由原来的0.3降为0.18.第二次迭代,变迁$t^2_1$的输入库所$P^2_3$的托肯值由于第一次迭代作用由原来的0.3降为0.18, $t^2_1$的总输入量降为0.18,致使$P^2_1$的托肯值由原来的0.21下降为0.126.其他的库所的托肯值不变.以后迭代停止.

在方案$P^3_1$的对话树中,只经过一次迭代,使$P^3_1$的托肯由原来的0上升为0.4.

整个对话树的库所的托肯值按时间变化如表 2所示.$P^1_4$、$P^1_6$、$P^1_7$、$P^1_8$、$P^1_9$、$P^1_{10}$、$P^1_{11}$、$P^2_2$、$P^2_4$、$P^3_2$因为没有受到其他争议的响应,其托肯值不变, 表 2没有列出它们的托肯值.从表 2可以看出,库所的托肯值随着算法的进行不断发生变化,方案$P^1_1$、$P^2_1$、$P^3_1$的最终托肯值分别为0.4212、0.126、0.4.对方案进行排序即得最优方案为$P^1_1$.

协商对话框架是对协商对话过程的全面刻画,包括争议的结构化分解、争议之间的关系表示,并有相应的争议评价算法.与劝说和谈判对话不同的是,协商对话需要引入不确定性信息表示及处理.协商对话过程中也存在个体信念不一致现象,需要嵌入劝说对话成份,即需要引入辩论推理.本文提出的模型能满足以上要求.一是将争议分解为若干前提和一个结论组成的可废止规则,反映了争议的内部论证结构.二是对IBIS模型进行约简和扩展,使之不仅能表示协商对话实际,同时有利于争议评价计算.约简是指限制问题的泛化和特化,只对单一问题求解;扩展是指增加对方案的多层论证结构,将整个协商对话过程建模成一个对话森林,其中每棵对话树的根节点对应一个方案.三是增加了争议前提和争议的论证强度的量化表示,提出一种基于模糊Petri网的共识评价方法,通过矩阵迭代运算求出方案的最终共识值,算法合理高效.本文方法已用于计算机辅助研讨支持系统中,取得较好的效果.如果要应用于多Agent交互系统中,则还需要做进一步的工作,包括发言信息符号化、Agent信念表示及信念库构建、争议产生方法及对话协议等.