基于回答集程序设计的引入中间人的协商方法

摘要

本发明公开基于回答集程序设计的引入中间人的协商方法，通过)引入一个中立的agent，使得协商agent可以同时提出自己的建议，通过中间agent的引导来完成协商过程；同时，通过在协商的准备阶段，由协商agent向中间agent提交关于协商物品的已知事实以及可获取的相关文字，来减少协商agent的不诚信行为。本发明分析中间Agent的作用，给出了协商流程，建立了具有中间Agent的协商模型，利用ASP语言来实现中间Agent的基本功能并给出协商Agent的协商建议生成算法，可以有效的解决顺序协商中的一些问题。

权利要求

1.基于回答集程序设计的引入中间人的协商方法，其特征是，包括如下步骤：步骤1、双方协商代理向中间代理提出开始协商的相关信息；

步骤2、中间代理初始化协商协议，负责验证协商是否可以开始，若可以开启协商，则收集与即将开始的协商相关的各项信息；

步骤3、协商代理判断协商建议是否全被协商，如果全被协商则转到步骤6，否则转到步骤4；

步骤4、双方协商代理分别生成协商建议，并提交给中间代理；

步骤4.1、输入协商物品的ASP规则的规则集Π和协商中需要了解文字的文字集H；

步骤4.2、把目标g作为约束加入规则集Π中，形成新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.9；如果新的规则集Π'中没有回答集，则转到步骤4.3；

步骤4.3、任选并删除文字集H中的一个文字，将其加入到新的文字集H'中；

步骤4.4、将新的文字集H'加入到新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.5；如果新的规则集Π'中没有回答集，则转到步骤4.3；

步骤4.5、若新的文字集H'为空，则转到步骤4.9；若新的文字集H'不为空，则转到步骤

4.6；

步骤4.6、从新的文字集H'中任选并删除一个文字；

步骤4.7、将步骤4.6得到的新的文字集H'加入新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.5；如果新的规则集Π'中没有回答集，则转到步骤4.8；

步骤4.8、将步骤4.6所删除的文字加入新的规则集Π'，转到步骤4.5；

步骤4.9、新的规则集Π'的回答集与文字集H的交集即为生成的协商建议；

步骤5、中间代理收到双方协商代理提交的协商建议，根据协商规则判断协商是否成功；如果协商成功，通知双方协商代理协商成功，并结束协商进程；否则，中间代理向双方协商代理发送本轮协商双方提议协商失败的原因，并通知协商代理进入下一轮，即转到步骤

3；

步骤6、当双方协商代理的协商建议全部被协商过且均未被采纳或当双方协商代理违反规则的次数达到了规定次数时，则中间代理就认为该协商的结果是失败的并结束协商进程。

说明书

基于回答集程序设计的引入中间人的协商方法

技术领域

[0001] 本发明涉及人工智能技术领域，具体涉及基于回答集程序设计的引入中间人的协商方法。

背景技术

[0002] 协商是社会活动的主要形式，人们主要通过协商来解决生活中的矛盾冲突。然而由于人类处理信息的能力有限，而且在受到其它因素影响时不能做出完全理性的决策，所以导致在面临复杂的协商问题时，协商进程不能有效的进行。

[0003] 在顺序协商(即协商参与人交替提出协商建议的协商)方面，Tran Cao Son提出使用带有一致性恢复规则的逻辑程序(CR-Prolong)使协商过程形式化，Wu Chen给出了一种使用回答集程序设计(Answer Set Programming，简称ASP)的连续交替出价协商模型。然而，这些方法存在以下不足：从计算机资源使用的角度，存在协商agent(代理)在生成协商意见时，对手处于空闲等待的情况，从而造成资源浪费；从协商进程推进的角度而言，顺序协商开始时，由于agent害怕暴露协商底线，所以没有agent愿意首先给出协商建议，从而造成协商无法顺利开始。

[0004] 在现实世界中，为了使协商更快完成并使自身利益最大化，常常会出现参与协商的一方提供虚假信息的情况。对协商中的不诚信问题的研究有：Tran Cao Son和Enrico Pontelli给出了一个具有不诚信行为的形式化的协商过程。但是没有给出有效减少协商agent不诚信行为的方法。由于说谎这个行为是一个激活—决策—构建的过程，所以谎言是不能被预测的。即在协商未开始时，协商agent不存在对协商已知事实说谎的行为(不诚信行为)。

发明内容

[0005] 本发明所要解决的是顺序协商中的资源浪费和协商不诚信的的问题，提供基于回答集程序设计的引入中间人的协商方法。

[0006] 为解决上述问题，本发明是通过以下技术方案实现的：

[0007] 基于回答集程序设计的引入中间人的协商方法，包括如下步骤：

[0008] 步骤1、双方协商代理向中间代理提出开始协商的相关信息；

[0009] 步骤2、中间代理初始化协商协议，负责验证协商是否可以开始，若可以开启协商，则收集与即将开始的协商相关的各项信息；

[0010] 步骤3、协商代理判断协商建议是否全被协商，如果全被协商则转到步骤6，否则转到步骤4；

[0011] 步骤4、双方协商代理分别生成协商建议，并提交给中间代理；

[0012] 步骤4.1、输入协商物品的ASP规则的规则集Π和协商中需要了解文字的文字集H；

[0013] 步骤4.2、把目标g作为约束加入规则集Π中，形成新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.9；如果新的规则集Π'中没有回答集，则转到步骤4.3；

[0014] 步骤4.3、任选并删除文字集H中的一个文字，将其加入到新的文字集H'中；

[0015] 步骤4.4、将新的文字集H'加入到新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.5；如果新的规则集Π'中没有回答集，则转到步骤4.3；

[0016] 步骤4.5、若新的文字集H'为空，则转到步骤4.9；若新的文字集H'不为空，则转到步骤4.6；

[0017] 步骤4.6、从新的文字集H'中任选并删除一个文字；

[0018] 步骤4.7、将步骤4.6得到的新的文字集H'加入新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤4.5；如果新的规则集Π'中没有回答集，则转到步骤4.8；

[0019] 步骤4.8、将步骤4.6所删除的文字加入新的规则集Π'，转到步骤4.5；

[0020] 步骤4.9、新的规则集Π'的回答集与文字集H的交集即为生成的协商建议；

[0021] 步骤5、中间代理收到双方协商代理提交的协商建议，根据协商规则判断协商是否成功；如果协商成功，通知双方协商代理协商成功，并结束协商进程；否则，中间代理向双方协商代理发送本轮协商双方提议协商失败的原因，并通知协商代理进入下一轮，即转到步骤3；

[0022] 步骤6、当双方协商代理的协商建议全部被协商过且均未被采纳或当双方协商代理违反规则的次数达到了规定次数时，则中间代理就认为该协商的结果是失败的并结束协商进程。

[0023] 与现有技术相比，本发明具有如下特点：

[0024] (1)引入一个中立的agent，使得协商agent可以同时提出自己的建议，通过中间agent的引导来完成协商过程；

[0025] (2)通过在协商的准备阶段，由协商agent向中间agent提交关于协商物品的已知事实以及可获取的相关文字，来减少协商agent的不诚信行为。

附图说明

[0026] 图1为协商流程图。

具体实施方式

[0027] 为使本发明的目的、技术方案和优点更加清楚明白,下面结合一个具体实施例和附图对本发明进一步详细说明。

[0028] 定义1.协商知识库的定义：

[0029] 协商agent的协商知识库是一个三元组<Π,H,G>，其中：

[0030] Π为协商物品的知识的集合，即规则的集合；

[0031] H为在协商中需要了解的文字的集合，即需求文字集；

[0032] G为协商目标的集合以及其优先级，即目标集。

[0033] 根据上述定义，每个协商agent对协商物品最少拥有一个协商目标，并且每个目标之间是分离的，具有各自的优先级顺序的。所以在协商过程中，首先实现优先级最高的目标，若实现不了，则考虑次一级的目标，直至所有的协商目标都没有实现，才判断协商失败。

[0034] 在协商中，每个协商agent都是通过协商建议与其他agent进行协商的。在使用以数值为目标的协商模型中，agent通过计算预定义的公式来生成建议。然而，在基于ASP的模型中，建议可以通过计算协商知识库的回答集来生成。

[0035] 定义2.协商建议的定义：

[0036] 已知agent的协商知识库为<Π,H,G>，并且目标g∈G。协商建议R的定义如下：

[0037] (1)如果程序(Π∪{:-not g.})有回答集，那么

[0038] (2)如果程序(Π∪{:-not g.})没有回答集，那么R就是H的一个子集，且R＝M∩H，其中M为程序(Π∪{:-not g.}∪R)的回答集。

[0039] 定义3.协商建议不成功的原因的定义：

[0040] 已知R为agentA在本轮中的协商建议，agentB的协商知识库为<ΠB,HB,GB>。假设中间agent的协商规则集ΠB中的事实的集合为FB，那么协商失败的原因是集合F＝R\FB。

[0041] 协商agent还需要进行协商建议是否全部被协商过的判断并以此来决定下一轮协商过程中向中间agent发送的协商建议。给出如何判断协商agent的协商建议是否全部协商过以及向中间agent发送的协商建议。

[0042] 算法1.协商建议的生成算法GenProp(Π，H，g)：

[0043]

[0044]

[0045] 步骤1.1、输入协商物品的ASP规则的规则合Π和协商中需要了解文字的文字集H；

[0046] 步骤1.2、把目标g作为约束加入规则集Π中，形成新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤1.9；如果新的规则集Π'中没有回答集，则转到步骤1.3；

[0047] 步骤1.3、任选并删除文字集H中的一个文字，将其加入到新的文字集H'中；

[0048] 步骤1.4、将新的文字集H'加入到新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤1.5；如果新的规则集Π'中没有回答集，则转到步骤1.3；

[0049] 步骤1.5、若新的文字集H'为空，则转到步骤1.9；若新的文字集H'不为空，则转到步骤1.6；

[0050] 步骤1.6、从新的文字集H'中，任选并删除一个文字；

[0051] 步骤1.7、将步骤1.6得到的新的文字集H'加入新的规则集Π'；如果新的规则集Π'中有回答集，则转到步骤1.5；如果新的规则集Π'中没有回答集，则转到步骤1.8；

[0052] 步骤1.8、将步骤1.6所删除的文字加入新的规则集Π'，转到步骤1.5；

[0053] 步骤1.9、当前新的规则集Π'的回答集与文字集H的交集即为生成的协商建议。

[0054] 在算法中GenProp(Π,H,g)中，第2-8行描述了寻找H的子集H’的过程，其中H’可以使程序(Π∪{:-not g.}∪H')产生回答集。第9-16行确保如果程序Π’不包含文字h还能得到回答集M，其中h∈H’，则确保M中不包含文字h。函数select(h,H)表示随机挑选集合H中的一个文字h。

[0055] 算法2.新的协商建议生成算法：

[0056]

[0057]

[0058] 步骤2.1、输入协商物品的ASP规则的集合和协商中需要了解的文字的集合和协商失败的原因；

[0059] 步骤2.2、第i+1轮将协商需求集Hi的失败原因文字Fi剔除，形成新的协商需求集Hi+1；

[0060] 步骤2.3、调用算法1求解第i+1轮的协商建议集Ri+1；

[0061] 步骤2.4、如果协商建议集Ri+1为空，则转到步骤2.5；若协商建议集Ri+1不为空，则转到步骤2.9；

[0062] 步骤2.5、若当前目标集G'不为空，转到步骤2.6；若当前目标集G'为空，则转到步骤2.8；

[0063] 步骤2.6、将当前目标集G'中比当前协商目标低一级的目标g'返回，并删除目标g生成更新后的目标集G'；

[0064] 步骤2.7、使用低一级的协商目标g’替换现在的协商目标g，转到步骤2.3；

[0065] 步骤2.8、令Ri+1为“fail”；

[0066] 步骤2.9、返回Ri+1，结束。

[0067] 在算法GenNProp(Π,Hi,G',Fi)中，第一行是将agent在第i轮的需求集Hi中属于协商失败的原因的集合中的文字删去，从而生成agent在第(i+1)轮的需求集Hi+1。函数low(g,G)的功能是将目标集G中比当前目标g低一优先级的目标g'返回。第5-7行的目的是在目标g'下生成一个新的建议。第10行表示如果所有的建议都被协商过，那么新的建议为fail。当中间agent在收到建议R＝{fail}时，它会结束当前协商。如果还存在建议没有被协商过，那么协商agent会将该建议发送给中间agent使协商继续进行。

[0068] 基于回答集程序设计的引入中间人的协商方法，参见图1，包括如下步骤：

[0069] 步骤1：买卖酸奶协商双方中任何一方都可以请求初始化协议,交易双方提交各自的初始信息给中间Agent；

[0070] 步骤2：中间Agent负责验证交易双方身份的合法性,并收集与即将开始的协商相关的各项信息。其中交易双方提交协商物品的相关信息及其作用如下：①协商物品的名称，以此来判断协商参与者是否可以参与协商；②针对这个协商物品的一些已知的事实，以此来判断协商是否成功。其相关的规则如下：

[0071] ％双方协商的是同一个项目，则协商开始

[0072] start:-itemA(X),itemB(X).

[0073] 步骤3：交易双方必须遵守协商规则,并提交符合协商规则的提议；否则中间Agent将对违反规则的参与人发出警告信息。为提高协商效率，在发明中协商规则为已经协商过得建议不允许再次提出进行协商。

[0074] 步骤4：协商Agent的协商建议成功后，不允许协商Agent修改建议，即不允许协商Agent继续协商。其相关规则如下：

[0075] ％已经协商过的不可以再次协商

[0076] ～Ayes(X,W):-agentA(X,Z),agentA(Y,W),X＝Y,Z

[0077] ％已经确定的不可以修改

[0078] allowA(X,Z):-#subList(X,Y),agentA(X,Z),factB(Y).

[0079] Byes(X,Y):-not allowB(X,Y),not～Byes(X,Y),agentB(X,Y).

[0080] ％协商成功后不允许继续协商

[0081] :-allowA(X,Y),agentA(_,Z),X

[0082] 步骤5：在协商的每一轮,中间Agent收到交易双方提交的提议,根据协商规则判断交易是否成功。如果协商成功,通知交易双方协商的成交结果；否则,中间Agent向交易双方发送本协议轮双方提议匹配部分的信息,并通知协商进入下一轮。

[0083] ％Agent A与Agent B的协商建议均被允许，则协商成功。

[0084] success:-allowA(X,Y),allowB(Z,W).

[0085] ％在本轮中协商建议是符合规则的，则允许进入下一轮

[0086] continueA:-Ayes(X,Y),Y＝term.

[0087] ％本轮中的协商建议不是第二次不符合协商规则的情况，则允许进入下一轮[0088] continueA:-～Ayes(X,Y),not～Ayes(Z,W),agentA(Z,W),Y

[0089] 步骤6：当协议达成一致或交易双方中有一方因所有提议全部协商过或有一方协商Agent多次不遵守协商规则而退出协商过程时,中间Agent负责来结束整个协商过程。

[0090] end:-～Ayes(X,Y),～Ayes(Z,W),Y！＝W.

[0091] end:-#member(fail,X),agentA(X,Y).

[0092] 本发明分析中间Agent的作用，给出了协商流程，建立了具有中间Agent的协商模型，利用ASP语言来实现中间Agent的基本功能并给出协商Agent的协商建议生成算法，可以有效的解决顺序协商中的一些问题。