西南大学学报 (自然科学版)  2018, Vol. 40 Issue (10): 162-172.  DOI: 10.13718/j.cnki.xdzk.2018.10.025
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    高龙云
    曾庆华
    陈武
    欢迎关注西南大学期刊社
     

  • 基于良基语义的协商机制研究    [PDF全文]
    高龙云1, 曾庆华2, 陈武1     
    1. 西南大学 计算机与信息科学学院, 重庆 400715;
    2. 中国人民公安大学 侦查与反恐怖学院, 北京 100038
    摘要:在当今社会生活中,协商已渗透到人类活动的各个方面,自动协商一直是多Agent领域研究的热点之一.近年来,一些学者采用具有非单调特征的回答集程序表示Agent知识,通过回答集程序的相互更新实现协商.虽然目前已经提出一些基于回答集程序的方法来解决协商问题,但这些研究并没有充分考虑协商最优解和协商过程复杂性之间的平衡问题.寻找基于回答集程序的协商解实际上至少是一个NP-难的搜索问题,而回答集程序的良基语义模型在多项式时间内可以计算得到.因此,本文利用良基语义,结合信念修正的思想对协商过程进行优化,从而提出了一个基于良基语义的双边协商模型.该模型可有效缩短协商过程,实现协商最优解和协商过程复杂性之间的平衡.最后,本文通过实验验证了协商模型的有效性和适用性.
    关键词回答集程序    良基语义    信念修正    双边协商    

    在多Agent系统研究中,学者对Agent之间的协商机制、规则以及策略等不同角度进行了深入探索[1-2],一些学者还致力于解决复杂协商问题[3-5].有学者从信念修正的角度提出了新的关于协商的形式化方法,其中,协商机制的设计、协商规则的制定、协商策略的采用以及协商成功与否,都是根据每个参与协商的智能Agent自己的信念确定.此外,也有很多学者针对Agent的信念修正进行了深入研究[6-7].文献[8]采用基于信念修正的方法研究了2个Agent之间的一轮协商情况,每个Agent利用强(弱)忘记方法舍弃自身的部分信念.舍弃信念的前提是尽可能地保证在Agent信念修正后自身的利益损失降到最小.但在该文所述方法中,协商双方的需求只是在不断地收缩,这样就导致采用该协商方法建模时存在一定的局限性,即未充分考虑协商最优解和协商过程复杂性之间的平衡问题.

    针对上述基于信念修正的协商方法存在的不足,本文提出了一种改进的双边协商机制.首先,利用回答集程序对Agent的知识进行转换;其次,通过良基语义将协商参与者的需求进行划分;再次,采用交替提议协议进行协商,在协商过程中,采用基于信念修正的协商决策模型,有效地缩短协商过程,在保证协商结果效益的同时兼顾协商速度,实现协商最优解和协商过程复杂性之间的平衡.

    1 基础知识 1.1 回答集程序

    为了弥补传统逻辑程序在常识推理方面的不足,Gelfond和Lifschitz在1991年将经典的否定、否定即失败和封闭世界假设的概念引入到传统逻辑程序中,提出了逻辑程序的稳定模型语义的概念[9],为回答集语义奠定了基础.

    定义1.1(文字集的协调性) 如果一个文字集S包含了一对互补的文字pp′,则该文字集S被称作是不协调的;反之,如果文字集S中不包含任何一对互补的文字,则该文字集S被称作是协调的[7].

    定义1.2(规则) 假设Li(ni≥0)是逻辑语言L中的一个文字,则规则r可以表示为如下形式[7]

    $ {L_0} \leftarrow {L_1}, {L_2}, {L_3}, \cdots, {L_{n-1}}, {L_n}\left( {n \ge 0} \right) $ (1)

    其中,Head(r)是规则r的头文字,Body(r)是规则r的体文字,对应的形式化表示为

    $ Head\left( r \right) = {L_0}, \;Body\left( r \right) = {L_1}, {L_2}, {L_3}, \cdots, {L_{n-1}}, {L_n} $ (2)

    定义1.3(回答集语义) 如果程序∏为基础逻辑程序,则程序∏的回答集就是该程序的最小Herbrand模型;对任意一个逻辑程序P,都满足以下三条之一[10]

    1) 程序P没有回答集;

    2) 程序P有唯一回答集Lit

    3) 程序P有回答集,并且其所有的回答集是协调的.

    令∏表示一个基础程序,Lit表示∏的语言中所有文字的集合,则∏的回答集是Lit使得下列条件成立的最小子集S

    1) 对于∏中的任意规则L0L1L2,…,Ln(n>0),如果L1L2,…,LnS,那么L0S

    2) 如果S包含一对互补的文字,则S=Lit.

    本文用符号Cn(∏)表示关于∏封闭且逻辑封闭的最小文字集(即程序∏的回答集).

    1.2 良基语义

    在20世纪90年代,Van Gelder A.等人提出了良基语义的概念,每个正规逻辑程序都存在良基模型,而且这个模型在多项式时间内可以计算得到[11].

    定义1.4(良基模型) 利用最小不动点理论,程序∏的良基模型可以看作是良基集合W的最小不动点[12].良基模型是一个三值模型,可以解释为:负文字对应的原子的值在该解释下为假,正文字对应的原子的值在该解释下为真,而没有在良基语义中出现的原子的真值是不确定的[13].文献[11]表明,根据良基模型的定义得到的模型与利用交替不动点的方法得到的正规逻辑程序的良基模型是保持一致的.

    对正规程序∏,定义由GAtomGAtom的函数γ,对任意文字集X满足

    $ X \subseteq GAto{m_\Pi }, {\gamma _\Pi }\left( X \right) = {C_n}\left( {{\Pi ^X}} \right) $ (3)

    ∏的回答集可以表示为γ的不动点.若Xγ2的唯一不动点,则X也是γ的唯一不动点.其中,GAtom表示所有规则中的基原子组成的集合,GAtom表示所有规则中基原子组成的集合经过函数转换后的集合.

    属于γ2的最小不动点的原子,称作是关于∏良基的(即为良基结论),不属于γ2的最大不动点的原子则被称作是关于∏无基的(即为无基结论).所以,一个正规程序∏可以将集合GAtom划分为3部分:良基集(用W表示)、无基集(用U表示)和其他文字集(用OT表示).

    针对正规逻辑程序P,最大无基集是程序关于解释I的所有无基集的并集,这个并集也是一个关于解释I的无基集,用算子UP(I)表示.定义程序P的算子TP(I)如下所示:

    $ {T_P}\left( I \right) = \{ p\left| {\exists r \in P, \;Head\left( r \right) = \{ p\} \& Body\left( r \right) \subseteq I} \right.\} $ (4)

    则程序P的良基集用算子WP(I)表示如下:

    $ {W_P}\left( I \right) = {T_P}\left( I \right) \cup \neg {U_P}\left( I \right) $ (5)

    从上面的定义可知,TP(I)、UP(I)、WP(I)都是单调的算子.

    根据良基模型和回答集的定义,则有如下定理:

    定理1.1 正规逻辑程序∏的回答集包含所有关于∏良基的原子,但不含关于∏无基的原子[7].

    定理1.2 正规逻辑程序∏中出现的任一原子或者是关于∏良基的或者是无基的,则所有良基原子的集合是∏的唯一回答集[7].

    1.3 信念修正

    1985年,Alchourron C. E.等人提出了信念修正理论(简称AGM理论),AGM理论是在信念修正领域中提出较早和影响最为深远的理论[14].

    假设L表示命题语言,用A表示语言L中的任意一个语句,K表示由语言L中的某些语句组成的集合,用K表示一个人的认知状态,则称K为信念集合.

    依据AGM理论,信念的变化存在3种基本形式:信念扩充、信念收缩和信念修正.

    定义1.5(信念修正) 将一个与K不一致的语句A加入K中,为保证所得到的集合一致,需要将K中原有的某些语句删除,由语句A修正K所得到的信念集合用KA*表示[14].

    在协商领域,协商参与者之间的知识可以看作是一种信念集合.针对某一议题存在分歧时,两个或者多个协商参与者为了能够达成共识,就需要对自身的信念进行一定程度的修正.

    1.4 忘记理论

    在2005年,Foo N.等人以ASP为知识表示的工具,提出了基于强(弱)忘记理论的一次协商方法[8].在该理论中,每个Agent的知识都是利用ASP表示,ASP对应的每一个回答集就是该Agent的一个协商需求候选集.利用强忘记理论和弱忘记理论来放弃ASP中的某些文字,从而对原始的回答集程序进行修改,可以得到2种不同的效果:

    1) 如果这些文字出现在某个回答集中,则除了放弃的这些文字以外,原有回答集的其余文字继续保留在修改后获得的新程序的某一新回答集中;

    2) 如果这些文字不出现在某一个回答集中,则这个回答集将是新程序的一个回答集.

    同样地,上述理论还可以应用于放弃一个文字集.假设∏表示一个ASP,X表示需要放弃的文字集,则SReduce(∏,X)表示应用强忘记理论来放弃文字集X后得到的新的逻辑程序.

    2 基于良基语义的双边协商机制

    本文围绕4个核心问题“文字和文字集的优先级如何排序”、“初始化协商需求如何选择”、“协商需求如何更新”和“协商结果如何评价”进行研究,提出了一个基于良基语义的双边协商机制.

    2.1 优先级排序规则

    在真实的协商环境中,协商的每一个参与者对自身的协商需求都有一定的偏好.一个理性Agent在选择协商的交易集时,都会根据自身的偏好优先选择更适合自己的交易集,尽可能地使自身利益最大化.协商双方在选择好交易集的情况下,可能存在多个协商结果,即存在多个交易.因此,选择尽可能好的交易对最终的协商结果具有至关重要的作用.

    2.1.1 文字的优先级排序规则

    在协商环境中,一个理性Agent会选择具有更高优先级的文字作为自身协商需求.针对文字的优先级排序,学者们从定性和定量2个方面进行了研究.本文文字优先级排序的规则属于一种定性规则.

    在对协商需求中的文字进行优先级排序时,通过计算程序∏的良基集W、无基集U和其他文字集OT,将所有的需求文字对应分为第一梯度、第二梯度、第三梯度这3个大范围的优先级.从第一梯度优先级到第三梯度优先级,文字的优先级逐级递减.针对每个梯度内的文字,进一步确定优先级的划分方法.本文提出的文字优先级排序规则标准如下:

    1) 首先,从总体上,将程序∏的文字的优先级分为3个优先级梯度.

    第一优先级梯度PR1(∏):良基集中的文字拥有最高优先级;

    第二优先级梯度PR2(∏):其他文字集中的文字拥有仅次于良基集中文字的优先级;

    第三优先级梯度PR3(∏):无基集中的文字优先级最低.

    2) 针对同一个优先级梯度里面的多个文字,则根据这些文字在回答集程序中出现的次数进行优先级排序.一个文字在回答集程序中出现次数越多,则该文字在对应梯度中的优先级越高;反之,出现次数越少,则优先级越低;出现次数相同的文字,对应的优先级相同.

    2.1.2 文字集的优先级

    文字集的优先级排序是建立在文字的优先级排序的基础上的.文字集的具体排序规则如下所示:

    1) 如果多个文字集都存在第一优先级梯度的文字,包含第一优先级文字个数越多,则文字集的优先级越高;

    2) 如果在第一优先级梯度中进行比较时,两个或多个文字集包含的第一优先级梯度的文字个数相同,则对这些文字集中第一优先级梯度中文字的优先级进行比较.文字集中文字对应的优先级越高,则文字集的优先级越高;反之,文字的优先级越低,文字集的优先级就越低.

    3) 如果判断了第一优先级的文字,仍然无法判断文字集之间的优先级关系,则在第二优先级文字的前提下,依次运用步骤1和步骤2的方法进行排序.如果第二优先级文字还是无法比较文字集的优先级,则利用第三优先级文字.如果遍历结束,仍无法判断,则被看作同一优先级.

    2.2 基于信念修正的决策模型

    在多Agent协商领域中,根据参与协商的Agent个数,协商可以分为双边协商和多方协商.本文主要研究双边协商问题的快速协商框架.

    定义2.1(双边多议题协商框架) 本文的协商框架(Negotiation Framework,简称NF)用如下五元组进行定义:

    $ NF = \left\langle {I, S, P, D, T} \right\rangle $ (6)

    其中:

    I:表示协商主体,即指整个协商参与者的集合;

    S:表示协商所涉及的议题集合,需要对协商的议题个数、议题取值范围等进行定义;

    P:表示协商参与者之间所采用的协商协议,本文采用的协议是交替提议协议(Alternating Offers Protocol,简称AOP)[15]

    D:表示协商参与者使用的决策模型,本文设计了一种基于信念修正的决策模型;

    T:表示完成从协商开始到协商结束的时间消耗.在本文中,T表示协商的轮数.

    本文基于双边协商进行探讨,所以只存在2个协商主体.假设用Agent A表示其中一个协商参与者,用Agent B表示另一个协商参与者.例如在劳资谈判问题中,工会即是Agent A,资方即是Agent B,而协商的议题就包括{罢工(strike),涨工资(raise_sal),涨福利(raise_wel),辞退劳工(lay_off),引进新技术(new_tech),…}等议题.而罢工这个议题的取值范围就包括2个:进行罢工和不进行罢工.

    定义2.2(协商策略) 协商策略是Agent在协商过程中,依据自身对对手和协商环境等信息的估计,结合自身协商参数而采用的决策方式[16].通常来讲,可将协商策略分为以下3种:协作型、竞争型和单方让步型.

    协作型协商策略,指的是协商中的参与者需要同时考虑协商对手和自身可获得的效用,从而在协商过程中采取相互合作的方式,最终达成一个对协商双方都有利,且协商双方都能够接受的协商结果;竞争型协商策略,指的是协商中的参与者为了让自身获得较好的效用,从而坚持自身立场,在协商过程中不采取让步或者采取很小幅度的让步,表现出竞争性;单方让步型协商策略,指的是无论协商中的一方提出什么需求,协商中的另一方都会全部接受.

    因为协作型协商策略通常能够得到较好的结果,协商成功几率相对较高,所以本文采用协作型协商策略.

    定义2.3(协商交易) Agent A和Agent B分别表示双边协商的两个参与者,文字集RA表示Agent A需要保留的协商需求,文字集RB表示Agent B需要保留的协商需求.在既定的接受准则下,如果Agent A和Agent B能够相互接受对方的需求,则这一对文字集的组合就是一个可行的协商交易,用TradeSet表示,简写为TS.

    定义2.4(协商结果) 如果协商终止时,存在一个可行的协商交易TS=(RARB),则协商的结果为文字集RA和文字集RB的并集,协商成功.如果协商终止时,不存在任何一个可行的协商交易,则协商结果为空,即协商失败.

    定义2.5(文字集和文字的生成规则) 假设∏代表一个回答集程序,程序∏中所有文字的集合用Lit表示;S表示一个文字集,且SLitl表示一个文字,且lSr表示程序∏中的任意一条规则,则文字集S的生成规则GR(S)为

    $ GR\left( S \right) = \{ r \in \Pi \left| {Head\left( r \right) \subseteq S, Body\left( r \right) \subseteq S, Neg\left( r \right) \cap S = \emptyset } \right.\} $ (7)

    GR(S)定义的基础上,文字l在文字集S下的生成规则GR(lS)可定义为

    $ GR\left( {l, S} \right) = \{ r \in GR\left( S \right)\left| {Head\left( r \right) = l} \right.\} $ (8)

    S=Lit时,则GR(lS)可以记作GR(l).

    下面用例2.1来进一步说明文字和文字集的生成规则.

    例2.1 给定一个回答集程序∏,由如下三条规则构成:

    $ \begin{array}{l} \;\;\;\;{r_1}:{l_1} \leftarrow \\ {r_2}:{l_2} \leftarrow {\rm{not}}\;{l_{\rm{3}}}\\ {r_3}:{l_3} \leftarrow {\rm{not}}\;{l_{\rm{2}}} \end{array} $ (9)

    令文字集Lit={l1l2l3},文字集S={l1l3}.根据定义2.5可得,文字集S的生成规则GR(S)={r1r3},文字集Lit的生成规则GR(Lit)={r1r2r3};文字l3在文字集S下的生成规则GR(l3S)=GR(l3)={r3},文字l2在文字集S下的生成规则GR(l2S)=GR(l2)={r2}.

    忘记理论建立在回答集程序基础上.在该理论中,一个回答集程序放弃了自身的部分文字后,如果这些文字出现在某个回答集中,则除了放弃的这些文字以外,原来回答集的其余文字继续保留在修改后获得的新程序的某一新回答集中;如果这些文字不出现在某一个回答集中,则这个回答集将是新程序的一个回答集.由不动点理论可知,基于ASP的忘记理论同样适用于良基语义.因此,在使用忘记理论时,同样有以下结论成立.

    定理2.1 假设∏是一个ASP,X是∏所需要放弃的文字集,W是程序∏的良基集.程序∏利用ASP的强忘记理论放弃文字集X后,得到的新程序为∏′;程序∏利用ASP的弱忘记理论放弃文字集X后,得到的新程序为∏″.则有如下结论成立:

    1) 如果XW,那么W-XW∏′

    2) 如果XW=Ø,那么WW∏″.

    Foo N.、Chen W.等人选择回答集作为协商参与者的初始需求,并提出了相应的协商模型.但是求解回答集是一个NP完全问题,此类问题一般被认为是不存在多项式时间的算法.因此,选择回答集作为协商参与者的初始协商需求的做法也存在一定缺陷.对于协商初始化的问题,本文选择良基语义进行改进.因为回答集程序的良基语义模型在多项式时间内可以求解得到,这样能够有效缩短协商时间.所以,选择良基语义对协商需求进行划分是一个较为合理的解决方案.

    为了更恰当地描述协商参与者的需求偏好,本文选择良基语义进行描述,回答集程序中的每一个文字就代表Agent的一个信念.通过良基模型的三值语义,将程序中的所有文字划分为3类:良基集、无基集和其他文字集.对于协商的一方Agent A,则有

    $ Li{t_A} = {W_A} \cup {U_A} \cup O{T_A} $ (10)

    对于协商的另一方Agent B,则有

    $ Li{t_B} = {W_B} \cup {U_B} \cup O{T_B} $ (11)

    本文中,将Agent对应的回答集程序∏的良基集W和其他文字集OT作为Agent可协商的需求,将回答集程序∏的无基集U作为Agent不关心的需求,即这部分文字对协商结果无关紧要.在可协商的需求中,W作为Agent优先保留的文字集合,而OT作为Agent次要保留的需求.换言之,程序∏的协商空间NS可以表示为

    $ N{S_\Pi } = {W_\Pi } \cup O{T_\Pi } $ (12)

    理性Agent会根据自身的偏好进行协商.这个协商过程可以抽象为协商双方回答集程序的文字通信过程.但由于大多数的协商都是信息不完全的,即协商参与者不清楚协商对手的全部协商需求.所以,为保证自身利益的最大化,理性Agent应尽可能放弃较少文字,并尽可能使这些放弃的文字对自身利益的影响最小.在此基础上,如果协商双方能够达成共识(即互相接受),则这就是协商的一个可行解.

    然而,在实际协商过程中,协商双方的Agent通过一味放弃自身需求所达成的协商结果大多都不太理想.因此,本文在放弃自身部分需求的同时,也选择接纳一部分对方的文字.在接受文字时,通过计算该文字在原有程序中的生成规则GR,然后将这些生成规则加入到对方的程序中,从而保留原有文字与其他文字存在的关联或约束.这个接受文字的过程,本文结合了信念修正的思想:如果协商参与者的回答集程序中的规则与新加入的规则存在冲突,则放弃自身原本的规则,接受新加入的规则.

    每个ASP接受对方的文字时,必须满足以下2个特性:

    1) 自身选择保留的协商需求不被减少,即在ASP加入了对方文字的生成规则后,得到新的ASP的良基集必须包含原本ASP的良基集(不包含放弃的冲突文字);

    2) 在加入了对方文字的生成规则后得到的新良基集中的文字不能存在任何一对不协调的文字.

    基于上述2个特性,本文给出了判断协商交易可行性的算法伪代码,如图 1所示.

    图 1 判断协商交易可行性的算法

    本文通过借鉴信念修正的思想,提出了一种基于信念修正的协商决策模型,在双方能够达成共识的前提下,对协商的各方有如下结论:

    1) 在最理想的情况下,Agent最优的协商结果为良基集和其它文字集的并集;

    2) 在最不理想的情况下,Agent最差的协商结果为保留自身需求中的一个文字.

    协商双方在放弃自身需求的时候,必须满足这个约束条件:协商中的任何一方都不能完全放弃自身的需求,即在协商成功的情况下,协商双方至少要保留一个自身的需求.

    根据上述的情况1,在协商双方能够达成共识的前提下,最大的协商结果为Agent的良基集和其他文字集的并集.从Agent的最大协商结果开始,逐步减少Agent的需求,即按照文字的优先级,逐步将Agent的可协商文字从Agent的需求中进行删减,从而不断缩小Agent的信念集合,直到达成协商共识或者协商结束.对应的决策模型的算法伪代码如图 2所示.

    图 2 基于信念修正的协商决策模型
    2.3 基于良基语义的双边协商模型

    结合信念修正的协商决策模型,提出一种基于良基语义的双边协商模型.协商模型中,采用Agent A和Agent B表示双边协商问题中的协商参与者.协商模型依次分为以下4个主要步骤:

    2.3.1 协商双方知识的形式化

    人类的自然语言是协商问题的最原始表示方式,然而,自然语言在机器进行自动协商过程中存在一定不足.为更好地表示协商参与者的已有知识,从而实现自动协商,本文选择使用回答集程序对协商参与者的知识进行形式化表示,将自然语言描述的协商问题转换为2个ASP之间的更新问题.其中,Agent A的回答集程序用∏A表示,Agent B的回答集程序用∏B表示.

    2.3.2 协商双方回答集程序的良基模型的求解

    由于回答集的求解是一个NP完全问题,无法通过计算多项式的时间得到,而回答集程序的良基模型的求解,在多项式时间内可以得到.因此,在对协商双方知识进行形式化之后,分别计算Agent A和Agent B的ASP的良基模型,从而将2个ASP中的文字分别划分为良基集、无基集和其他文字集3个部分.其中,Agent A的良基集用WA表示,无基集用UA表示,其他文字集用OTA表示;Agent B的良基集用WB表示,无基集用UB表示,其他文字集用OTB表示.

    2.3.3 协商双方的初始化协商需求的选择

    通过计算步骤2中的良基模型,将Agent A和Agent B对应的ASP的良基集和其他文字集分别作为各自的初始协商需求.当Agent A和Agent B初始化协商文字集存在不协调的文字时,如果存在协商占优的一方,则占优的一方保留冲突文字,协商的另一方放弃冲突文字;如果协商双方是平等的,则协商的任一方放弃自身的冲突文字即可.其中,ASP在放弃冲突文字时,还需要接受对方需求中与该文字冲突的文字的生成规则.其中,Agent A的初始化协商需求用NSA表示,Agent B的初始化协商需求用NSB表示,文字l的生成规则用GR(1)表示,协商双方的冲突文字集用Conf表示.

    2.3.4 协商双方进行协商决策

    初始化Agent A和Agent B的协商需求后,协商双方采用基于ASP的交替提议协议进行协商.首先,将Agent A、Agent B的协商空间(在步骤3中已经放弃不协调的文字)按照文字的优先级进行降序排列;其次,Agent A与Agent B交替提议放弃自身的一部分需求,直至遍历结束各自的协商空间.在多轮协商的过程中,利用本文提出的协商结果评价准则对比新的交易集和临时交易集的收益.如果新的交易集的收益更大,则用新的交易集替换临时交易集;反之,则保留原本的交易集.

    在交替提议结束后,如果临时交易集不为空,则协商成功,这个交易集就是协商的可行解;如果临时交易集为空,则协商失败,不存在协商的可行解.在协商成功的情况下,协商的结果就是协商交易集的并集.例如,Agent A和Agent B在交替提议结束后,协商的交易集为TS=({abc},{cd}),则协商的结果则为{abcd}.

    其中,基于ASP的交替提议协议流程图如图 3所示.

    图 3 基于ASP的交替提议协议流程图
    2.4 协商结果评价准则

    从上述协商模型的算法中,可得出协商的终止存在3种情况:

    1) 协商双方中至少有一方的协商空间为空,则协商失败;

    2) 协商双方经多轮提议后无法达成一致,不存在交易集,则协商失败;

    3) 协商双方经多轮提议后达成一致,存在一个或者多个交易集,则协商成功.

    在本文模型中,假定协商双方都是平等的,即不存在占优的一方.由于在协商过程中,协商双方采用交替提议协议,提议的过程(即协商的总的轮数)就是协商双方的协商空间中的文字个数(除去协商双方的冲突文字)的乘积.假设Agent A的初始化协商空间中的文字个数为m,Agent B的初始化协商空间中的文字个数为n,协商双方的冲突文字个数为k,则协商的最大可能轮数则为(m-k-1)*(n-k-1).因为协商的空间是有穷的,并且每一轮放弃的文字也都是单调增加的,所以协商在有限时间内是可终止的.

    但是在该模型下,对于同一个协商问题可能存在一个或多个协商交易集.因此,建立一套协商结果评价准则就显得尤为重要.

    本文通过协商议题(即文字)的个数和协商议题的优先级来选择最优的协商交易集.具体准则如下:

    1) 分别对(CountATSCountBTS)和(CountATSCountBTS)这2组数据求解平均数VagTSVagTS、方差DTSDTS.如果VagTSVagTS并且DTSDTS,则保留原本的交易集TS

    2) 如果VagTSVagTS并且DTSDTS,更新交易集为TS′;

    3) 如果通过上述方法,仍无法判断2个交易集的优先级,则利用文字集的优先级的排序规则来判断交易后协商结果的优先级:如果协商双方的新协商结果都优于之前的协商结果,则更新协商结果;否则,保留原本的协商结果,进行下一轮协商.

    其中,CountATS表示原始协商交易集TS中包含的Agent A的议题数量之和;

    CountATS表示更新后的协商交易集TS′中包含的Agent A的议题数量之和;

    CountBTS表示协商交易集TS中包含的Agent B的议题数量之和;

    CountBTS表示更新后的协商交易集TS′中包含的Agent B的议题数量之和;

    VagTS表示协商交易集TS中包含的Agent A和Agent B议题数量之和的平均值,即VagTS=(CountATS+CountBTS)/2;

    VagTS表示更新后的协商交易集TS′中包含的Agent A和Agent B议题数量之和的平均值,即VagTS=(CountATS+CountBTS)/2;

    DTS表示CountATSCountBTS的方差;

    DTS表示CountATSCountBTS的方差.

    2.5 实验

    例2.2  给定回答集程序∏A和∏B的组成规则如表 1所示.

    表 1 回答集程序∏A和∏B

    采用本文提出的协商模型计算可得协商的结果为{abf,¬ g},协商的交易为({ab,¬ g},{f}),协商的轮数为6轮.通过上述实例分析可以看出,协商模型能够有效求解双边协商问题.

    根据回答集程序中包含的不同数量的规则,将本文模型与文献[8]的方法进行对比.首先,在每一轮协商选择初始化需求的过程中,文献[8]的方法通过求解回答集得到,这一过程是一个NP完全问题;而本文模型通过计算回答集程序的良基模型确定初始化需求,时间复杂度是O(n2);其次,针对协商的整个过程需求的轮数也进行了比较,具体对比结果如表 2所示. Agent A和Agent B分别表示双边协商中的2个协商参与者.

    表 2 处理不同数量的回答集程序之间的协商时间比较

    通过上表可以得出,在应用于相同的协商问题时,与文献[8]的方法相比,本文的双边协商模型求解过程经历的协商轮数更少.而且随着协商规则数量的增加,本文协商模型的优势更加明显.

    协商模型还可以根据是否包含环、是否存在交叉等将回答集程序划分为不同类型.为了进一步证明本文提出的双边协商模型的适用性,还针对不同类型的回答集程序之间的协商进行了对比实验,实验结果如表 3所示.其中,Agent A和Agent B的回答集程序包含的规则数量默认为10条.

    表 3 处理不同类型的回答集程序之间的协商时间比较

    通过利用不同类型的回答集程序和不同规则数量的回答集程序进行一系列实验,表明本模型能够快速求解出一个较好的协商结果.

    3 结论与展望 3.1 结论

    Foo N.等人在2005年提出了从信念修正的角度研究多Agent之间的协商[8],本文的协商决策模型正是基于这个思想.本文与Foo N.等人的研究,主要区别体现在以下几点:

    1) 文献[8]中,协商的初始化需求是用回答集来表示的,而本文的初始化协商需求是由回答集程序的良基集和其他文字集组成的,通过计算逻辑程序的良基模型得到.其中,回答集的求解是一个NP完全问题,在多项式时间内无法获得;而本文将良基语义应用到多Agent协商问题上,回答集程序的良基模型可以在多项式时间内求解得到.同时,文献[8]中的初始化需求选择是选择任意一个回答集,这种做法随机性很大,而本文通过良基模型来对协商需求进行划分是固定的,所以更为快速、合理.

    2) 文献[8]中,协商算法只考虑了协商者放弃自身文字的情况,而本文在放弃自身文字的同时,还接受一部分对方的文字.单一地放弃文字只能够解决经典否定的矛盾,却无法处理否定即失败的隐含矛盾.本文提出的将放弃文字和接受文字相结合的协商模型,可同时解决上述2种矛盾;同时,也区别于文献[13]中的协商方法,本文在接受文字时,接受的是该文字在原程序中的生成规则,而不是使用加入事实的方法.这样处理更能够体现该文字与其他文字之间的关联和制约特性.

    3) 文献[8]中,协商方法并没有对文字和文字集之间的优先级关系进行探讨,在初始化协商需求的选择中也是随机的;而本文提出了文字和文字集的优先级排序方法,并结合此方法提出了一个基于信念修正的协商决策模型.

    为保证本模型的适用性,本文不仅将方法用于无交叉的双环回答集程序之间的协商,还用于单环、双环交叉等不同类型的回答集程序中.实验结果表明:本模型能够快速求解出一个较好的协商结果.

    3.2 展望

    下一步,将对加入协商的时间限制等外部因素进行研究.本文提出的文字和文字集的优先级排序规则是一种定性规则,而不是优先级的量化规则,如果能够选择合适方法,对协商双方需求的优先级进行合理、高效的量化,则将会对最终的协商结果起到至关重要的作用.因此,后期将对文字和文字集优先级的量化方法进行深入研究,并对协商结果的评价准则进行一定程度的优化.

    参考文献
    [1] LANG F, FINK A, BRANDT T. Design of Automated Negotiation Mechanisms for Decentralized Heterogeneous Machine Scheduling[J]. European Journal of Operational Research, 2016, 248(1): 192-203. DOI:10.1016/j.ejor.2015.06.058
    [2] TSAI K M, CHOU F C. Developing a Fuzzy Multi-Attribute Matching and Negotiation Mechanism for Sealed-Bid Online Reverse Auctions[J]. Journal of Theoretical and Applied Electronic Commerce Research, 2011, 6(3): 85-96.
    [3] CHEN S, AMMAR H B, TUYLS K, et al. Conditional Restricted Boltzmann Machines for Negotiations in Highly Competitive and Complex Domains[C]//Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Beijing, China: AAAI Press, 2013: 69-75.
    [4] PELECKIS K. International Business Negotiations:Innovation, Negotiation Team, Preparation[J]. Procedia-Social and Behavioral Sciences, 2014, 110: 64-73. DOI:10.1016/j.sbspro.2013.12.848
    [5] DE C S, SCHOCKAERT S, NOWE A, et al. Multilateral Negotiation in Boolean Games with Incomplete Information Using Generalized Possibilistic Logic[C]//Proceedings of the 24th International Conference on Artificial Intelligence. Buenos Argentina: AAAI Press, 2015: 2890-2896.
    [6] ENQVIST S. Interrogative Belief Revision in Modal Logic[J]. Journal of Philosophical Logic, 2009, 38(5): 527-548. DOI:10.1007/s10992-009-9101-2
    [7] LIFSCHITZV. Foundations of Logic Programming[M]//Principles of Knowledge Representation. California: CSLI Publications, 1996: 69-128.
    [8] FOO N, MEYER T, ZHANG Y, et al. Negotiating Logic Programs[C]//Proceedings of the 6th Workshop on Nonmonotonic Reasoning, Action and Change. California: AAAI Press, 2005: 403-407.
    [9] GELFOND M, LIFSCHITZ V. The Stable Model Semantics for Logic Programming[C]//5th International Conf. of Symp. on Logic Programming. Seattle, Washington: The MIT Press, 1988: 1070-1080.
    [10] LIFSCHITZ V. Answer Set Programming and Plan Generation[J]. Artificial Intelligence, 2002, 138(1/2): 39-54.
    [11] VAN GELDER A, ROSS K A, SCHLIPF J S. The Well-Founded Semantics for General Logic Programs[J]. Journal of the ACM (JACM), 1991, 38(3): 619-649. DOI:10.1145/116825.116838
    [12] SHEN Y D, YOU J H, YUAN L Y. Characterizations of Stable Model Semantics for Logic Programs with Arbitrary Constraint Atoms[J]. Theory and Practice of Logic Programming, 2009, 9(4): 529-564.
    [13] CHEN W, ZHANG M Y, WU M N. A Logic-Program-Based Negotiation Mechanism[J]. Journal of Computer Science and Technology, 2009, 24(4): 753-760. DOI:10.1007/s11390-009-9256-x
    [14] ALCHOURRON C E, GARDENFORS P, MAKINSON D. On the Logic of Theory Change:Partial Meet Contraction and Revision Functions[J]. The Journal of Symbolic Logic, 1985, 50(2): 510-530. DOI:10.2307/2274239
    [15] KRISHNA V, SERRANO R. Multilateral Bargaining[J]. Review of Economic Studies, 1996, 63(1): 61-80. DOI:10.2307/2298115
    [16] 艾解清.双边多议题自动协商研究[D].杭州: 浙江大学, 2011: 3-11.
    A Study on Negotiation Mechanism Based on Well-Founded Semantics
    GAO Long-yun1, ZENG Qing-hua2, CHEN Wu1     
    1. College of Computer & Information Science, Southwest University, Chongqing 400715, China;
    2. School of Investigation and Counterterrorism, People's Public Security University of China, Beijing 100038, China
    Abstract: In today's society, negotiation has permeated all aspects of human activities. The automatic negotiation is a hot topic in the field of the Multi-Agent system. In recent years, some researchers use answer set programs to express the knowledge of agents, and complete the negotiation by updating the answer set programs (ASP). Though some ASP-based methods have recently been proposed in the negotiation field, yet they fail to take into account the balance between the optimal solution and the complexity of the negotiation process. Finding the negotiation result based on answer set programs is, in essence, an NP-hard searching problem. The model of answer set programs based on the well-founded semantics can be computed in polynomial time. Therefore, this paper combines well-founded semantics with belief revision to optimize the negotiation process, and then proposes a negotiation model based on well-founded semantics for bilateral negotiation. Experiment results have verified that this model can effectively speed up the negotiation process, and achieve the balance between the optimal solution and the complexity of the negotiation process.
    Key words: answer set program    well-founded semantics    belief revision    bilateral negotiation    
    X