自主Agent交互对话博弈协议的几何语义

《理论计算机科学电子札记》52卷第2期（2002）网址：http://www.elsevier.nl/locate/entcs/volume52.html18页自主Agent交互对话博弈协议的几何语义彼得·麦克伯尼和西蒙·帕森斯利物浦大学计算机科学系。K.电子邮件：fp. j. mcburney，s.d.parsonsg@csc。丽芙AC. 英国摘要自亚里士多德时代以来，哲学家们研究的正式对话游戏最近在人工智能中得到了应用，作为自治软件代理之间交互协议的基础例如，游戏协议已被提出的代理人的对话，涉及团队的形成，说服，谈判和审议。然而，还没有正式的，数学理论的对话游戏协议，比较两个协议或研究其形式的属性。在本文1中，我们提出了这样一个理论的初步工作，我们开发了这些协议的几何语义，并与它，定义了两个协议之间的等价性然后，我们证明了一个代数属性的协议等价性，并使用这两个类似的通用协议的非等价性。我们还探讨了夜间和夜间对话之间的关系，其动机是Escherichfeucht-Fra模型论的游戏我们的研究结果的设计和评估代理对话游戏协议的影响关键词：Agent通信语言，论证，计算辩证法，对话游戏。1介绍和动机自主和智能软件实体的概念|剂|相互作用以共同实现某些目标已成为人工智能（AI）近期研究的重要指导原则[32]。典型的应用涉及代表不同利益的代理，例如，电信或电力网络中的不同网络元素，1 部分由欧盟IST计划通过信息生态系统可持续生命周期（SLIE）项目（IST-1999-10948）和英国工程和物理科学研究委员会（EPSRC）通过博士生奖学金资助。我们也感谢匿名裁判、奥尔堡GETCO-2001研讨会的观众、马克·约翰逊和格兰特·马尔科姆的评论。c 2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。麦克伯尼和帕森斯2协商稀缺资源的使用在这些情况下，经济拍卖机制为代理之间的谈判交互的操作化提供了强大的计算工具[15]。然而，拍卖机制只允许参与者|通常，只有在特定价格水平上接受或拒绝订单，埃尔。了解特定行动的理由，以及接受或反对行动的理由，可以使参与者能够撤回他们的行动或提出适当的反行动。因此，该附加信息可以潜在地增加各方达成解决方案的可能性，并且如果实现，则可能减少所需的平均时间或计算资源。出于这个原因，使用论证，辩论和对话的哲学理论，最近被提议用于自治代理之间的交互[26，29]。我们如何在设计代理人互动协议时将论证操作化？一种方法是使用正式的对话游戏。这些是两个或多个参与者之间的交互，其中每个参与者通过说出符合一些预先定义和公知的规则集的表达方式（即口头话语）来“移动”。 例如，一个表达方式可以是说话者对某个主张的断言，或者是关于另一个说话者所做的断言的问题，或者是响应于这样的问题的主张的论点。游戏规则规定了在什么情况下每一种表达方式是允许的，或强制性的，或禁止的，以及在什么情况下对话游戏至少可以追溯到亚里士多德时代[3]，并在中世纪被哲学家广泛研究[11]。在现代，它们被用于错误推理的上下文分析[11，18]，为直觉主义和经典逻辑提供语义它们与经济博弈论的博弈不同，因为不考虑输赢的报酬，也不使用不确定性度量，如概率，来模拟对手的可能行动。它们也不同于最近作为理论计算机科学中编程语言的语义而开发的抽象游戏[1]，因为这些后者游戏通常不共享对话游戏的丰富规则结构，并且不打算作为交互协议来实现在多智能体系统领域，对话游戏已经被提出作为几种类型的智能体交互协议的基础，包括：团队的形成和集体意图[4，5];信息寻求对话[14];说服对话[22];谈判[2，24，28];对可能行动的联合审议[12];和不确定信念的联合确定[22]。 2作为一个例子，我们在下面列出了一个协议中的九种表达方式，以供审议。2 请注意，这些对话类型中的一些是根据人类对话的标准论证理论分类定义的[30]。然而，本文中讨论的工作与使用对话游戏来解释或生成计算语言学中的自然语言对话无关，如[16]。麦克伯尼和帕森斯3我们最近提出了可能的行动[12];该协议实现了人类审议的哲学模型，称为追溯性论证，由于Harald Wohlrapp [31]。审议议定书公开对话（P i; q？）对话（Pj;q？）提议（Pi;type; t）断言（Pi;type; t）偏好（Pi; a;b）移动（Pi;动作; a）收回（Pi;location）用一段对话（Pj;q？）其中：Pi;Pj是代理标识符;q？是关于在某种情况下要做什么的问题;类型是以下类别的命题之一：问题，目标，约束，事实，观点，行动或评价;t; a; b是命题[12]。然而，这些不同的代理协议基本上是ad-hoc的，没有为它们开发的正式的统一理论。也许正因为如此，迄今为止还没有对这类协议的性质进行研究，无论是特别的还是一般的，例如，它们是促进还是阻碍对话解决;或者它们是否容易受到参与者破坏性行为的影响（例如，反复问同一个问题）。因此，对话游戏协议的设计者目前没有针对以下问题的指导：应该有多少个发音？应包括哪些类型的用语？（例如：断言、问题等）什么是适当的规则组合的说法？什么时候应该禁止行为，例如，重复一个位置的话语？在什么情况下应该终止对话？根据特定协议进行的对话何时保证终止？对于保证终止的对话，需要输出多少语句才能实现这一点，即在给定协议下对话的计算复杂度是多少？同样，随着协议的激增，打算使用它们的代理人（或其人类负责人）将需要针对以下问题的指导：什么时候两个协议是相同的？不同的协议可能不同麦克伯尼和帕森斯4只是在表面细节上，而不是在它们所表现出的形式属性上;相反，类似的协议可能具有非常不同的属性。如何比较不同的协议以及如何测量这些差异？在何种情况下应首选何种协议？(i.e.、它们各自的优点和缺点是什么？对话游戏协议和已经提出的各种通用代理通信语言之间的正式关系是什么，例如，知识查询和操作语言（KQML）[19]或智能物理代理基金会的代理通信语言（FIPA）[9]。什么时候对话游戏协议比其他形式的代理交互（如拍卖机制或通用代理通信语言）更可取？在特定的协议下，参与对话的智能体采用什么策略是合适的？这些问题对于Agent对话游戏协议的设计者和使用者来说都是非常重要的。严格地描述它们将需要一种形式化的语言来推理协议的属性，以及将一个协议与另一个协议进行比较的技术。我们相信代数拓扑方法在发展这样一种协议的数学理论中可能有很大的价值，本文介绍了我们在这方面的初步研究。我们的方法是定义一个通用的对话游戏协议的元素，这样我们就可以将任何协议转换为几何表示，特别是一个真实的多维空间的子集。然后我们定义了两个协议的等价概念，并构造了等价概念的代数不变量。因为在我们的语义下，对话对应于欧几里德空间中的时间定向路径，所以我们没有逆的概念，因此这个代数不变量不是群结构。因此，我们的工作迄今为止是在代数拓扑的精神，没有使用任何复杂的数学。本文的结构如下：第2节再现了我们以前的工作的对话游戏的形式化模型，第3节定义了我们的几何语义的对话游戏协议和根据这样的游戏进行的对话第四节定义了两个协议等价的拓扑概念，并推导出该概念的代数不变量。证明了两个仅由一种语言区分的通用协议实际上是不等价的 。在 第 5 节 中 ， 我 们 探 讨 了夜 晚 和在 夜 间 对 话 中 ， 使 用Escherichfeucht-Fra模型论的SS E游戏第六节是论文的总结。麦克伯尼和帕森斯52一个通用的对话游戏根据我们的经验，阐明了一些代理对话游戏协议的用语和规则[2，22，24]，我们提出了通用对话游戏的第一个形式模型[20，23];我们在这里重复这项工作。在这个模型中，假设参与者之间的讨论主题用某种逻辑语言表示，其格式良好的公式由小写希腊字母、、等表示。对话游戏协议包括几种类型的规则：评论规则：定义对话开始的环境的规则。语言：指示允许哪些话语的规则。这些规则通常规定了一个参与者在说出一个言语之前必须具备的先决条件、该言语的法律句法以及其他参与者随后被允许说出的回应。例如，法律用语可以使参与者能够断言命题，允许其他人质疑或质疑先前的断言，并允许那些断言命题的人随后质疑或质疑他们的断言。正当化可能涉及对命题的证明或对命题的论证的陈述，并且这样的陈述也可能是合法的话语。在一些对话游戏的多智能体系统应用例如[2]），真诚条件被施加在话语上，例如al-只有当他们自己有一个先前的论点或证明从他们自己的知识库，降低代理断言语句。组合规则：定义对话语境的规则，在这些规则下，特定的语言被允许或不被允许，或强制或不强制。例如，在同一对话中，不允许参与者断言一个命题类似地，如果一个参与者质疑另一个参与者所做的先前陈述，则可以要求该后3承诺：规定参与者对一个命题表示承诺的一般来说，在辩论中，如果其他参与者提出质疑或争议，则向其他参与者表明在对话中为自己辩护的某种程度的意愿。自[11]以来，通常在一组公共可读的黑板中跟踪承诺，称为承诺存储。终止规则：规定在何种情况下，3 作为在前一部分中呈现的商议对话协议中的组合规则的示例，除非先前的发言者已经说出了对动作进行评估的两个或更多个语句，否则不能说出语句prefer（Pi ; a; b）-选项a和b，即， 其中a和b分别在命题e和f中引用断言（Pj;evaluation;e）和断言（Pk;evaluation n;f）。麦克伯尼和帕森斯6对话结束。这些规则可以用一个或多个参与者的承诺库的内容来表达;例如，当所有参与者说出一个接受有争议的命题的表达方式时，说服对话可以终止，该表达方式将该命题插入代理的承诺库。在哲学的对话游戏传统中，承诺是一个对话概念[11]：承诺表达了一个代理人在对话中捍卫该代理人先前断言的主张的意愿，并且不一定与对话外部的任何现实有任何联系。 因此，例如，一个参与者在对话中断言某个命题并不一定意味着这个参与者在对话之外相信所断言的命题。4.只有当对话的参与者一致同意赋予对话的语言以这种意义时，对话的语言才与外部现实有联系。然而，对于智能体设计者感兴趣的对话，特别是谈判和审议，语言和外部现实之间的联系例如，谈判双方可能同意，谈判的成功结束将导致在对话终止后执行购买交易。因此，我们假设对话的参与者可能会说出所有参与者都理解为暗示愿意在对话之外和之后执行一个或多个行动的话语。[5]我们进一步假设，这些行动可以用与讨论的主题相同的逻辑语言来表达。3几何语义在这一节中，我们将为刚刚提出的框架开发一个几何语义我们使用R+和Z+分别表示由所有非负实数和整数组成的空间我们使用符号Rn+表示R+的n重积，即Rn的子空间，其中所有点在每个维度上都有非负坐标。3.1辩证体系我们假设对话参与者或代理的集合A=fPi ji= 1;：; pg。我们用可能下标的大写罗马字母D; E等来表示对话游戏。每个对话游戏包括一组法律语言类型，表示为L =fLj jj= 1;：; lg，以及一些规则，4 在[30，p.72]中，这样的承诺被称为命题的。5 在[23]中，我们形式化了承诺的这两个概念，对话的和语义的。由于一个非常聪明的智能体总是可以不真诚地模拟任何所需的心理状态，智能体通信语言的语义验证问题{我们如何验证所有参与者对话语有相同的真诚理解这是一个棘手的问题，我们不在这里讨论。更多详情请参见：[33]。作为一个例子，Durrenmatt的小说“Die Panne”[6]关注的是一场人类对话，参与者赋予了非常不同的含义，并产生了悲剧性的后果。麦克伯尼和帕森斯7我们将立即考虑。根据对话游戏的规则进行的对话被假定为涉及一个固定，夜间集合=fi ji = 1;：; q g在一些命题语言中的合式公式，我们称之为话语的uni- verse。6这些命题中的一些或全部可能代表外部行动，这些行动可能是对话中说话者发出特定语句所招致的承诺的主题，因此我们区分出一个特定子集。一，我们称之为动作集。我们进一步假设，所有的语言类型可以分为三种类型中的一种或多种：（a）承诺语言：表达某种外部或对话承诺的语言，例如，在完成对话后执行购买行为的承诺;这些语言是用a中的一个或多个元素以及可能的na中的一个或多个元素来实例化的;(b) 信息语篇：传递某些信息的语篇，演讲者对听众，例如一个说话者对某组对象的偏好排序的陈述;这些语句用一个或多个na元素来实例化;（c）程序性语句：既不传递信息，也不承诺行动的语句;例如，这样的语句可能编码一种论证理论，例如，向其他说话者提出问题或挑战等;这些语句不直接用的元素来实例化，尽管它们可能用出现的元素的其他语句来实例化。 我们假设对话的话语发生在离散的时间-点，称为舍入，由非负整数表示一种语言由说话者P i执行，该说话者P i实例化适当的语句类型L j，该语句类型L j具有：表示说话时间的正整数（时间戳）;语句的说话者的标识符P i;以及可能来自集合的命题k。[7]因此，我们将这样例示的一个语句Lj表示为：Lj（t;Pi;k）。由Commit-ment语句的实例化语句所涉及的动作和由Information语句的实例化语句所传递的信息被假定为可在集合中包含的公式中表达。因为有些表达方式可能需要用不止一个命题来实例化，例如。在谈判中表达对两个采购选项的偏好排序的语句，我们假设在语句类型的句法所要求的命题组合下是封闭的。 我们用L表示由来自A的可能说话者和来自的讨论主题实例化的语言类型L的集合。换句话说，L同构于3元组的集合f（L; Ai）g的子集。在上一节中，我们确定了对话游戏模型中不同类型的规则。因为特定类型6 当然，这样的命题语言可能有一组完整的格式良好的公式。我们把对这件案子的讨论留到另一个场合。7 一些对话游戏协议，例如，[24]，允许说话者将话语瞄准特定的听众，在这种情况下，也可以使用A. 在本文中，为了简单起见，我们假设所有的话语都是针对所有参与者的，并且被所有参与者听到麦克伯尼和帕森斯8对于发生在它之外的特定话题，我们不假设开始规则是对话游戏协议的定义的一部分。然而，对于所有其他规则，可以将每个规则定义为从适当的对话历史（在下一轮之前实际说出的实例化语句）到集合L（在组合和终止规则的情况下）或到集合（在提交规则的情况下）的映射。这些定义的细节可以在[23]中找到为了目前的目的，需要注意的是，对话游戏协议包括这样的映射的规范，并且它们在每一轮为每个代理引入可能的实例化语句的划分：强制性动作：实例化语句，其中一个必须由代理在下一轮发出;合法动作：可以由代理在下一轮发出的实例化语句接下来我们定义一个辩证体系。定义3.1假设A是一个个体集合，一系列的话题的讨论（包括一个可能的子集的行动承诺），和D的对话游戏协议与一组语句L。我们说四元组D~=（A;L;D）是一个拨号系统。如果A的大小为p，则的大小为q且L的大小为l，则D~具有维数n=pql. 一个表盘-根据这样一个辩证系统采取的是由A中的代理人说出的一系列按时间排序的语句，其中的每个元素由集合L中的一个实例化语句组成，根据对话游戏D的规则说出。我们所说的对话是按照辩证的体系进行的与辩证体系相联系或在辩证体系之下。 我们也把这样的对话称为法律对话，尽管我们不允许在辩证体系下出现不符合相应对话游戏规则的语句序列。在下一节中，我们提出了一个几何语义的对话系统及其相关的对话。3.2对话途径让D~=（A; L; D）是一个辩证系统，并设置n=pql，其中这些常数的定义见3.1节 我们解释相关的对话作为实n维空间Rn+中的路径。我们通过用三元组（Pi;k;Lj）标记Rn+的每个轴来做到这一点，对于所有Pi2A，对于所有k2和对于所有Lj2L。对应于对话的路径，我们称之为对话路径，从原点开始，并且如下进行关于主题k的句子Lj，路径从其当前位置向前移动一个单位，方向平行于标记为麦克伯尼和帕森斯9n（P i;k; L j）。 我们首先这样的路径正式如下：定义3.2对话路径是函数d（：）：R+！Rn+，使得条件（a）、（b）和（c）各自满足：(a)int maximum（0）=;(b) 以下任一项：（i）对于所有整数k2 R+， d（ k）=（ y1; y2;：;yn），其中每个yj2 Z+，j=1yj =k;或(ii) 有一个整数m0使得对于所有正整数km，d（ k）=（ y ;y ;：; y），其中每个 y2Z+和Pny= k，并且对于所有1 2njj=1j整数k > m， d（ k）= d（ m）;(c) 如果x 2R+不是整数，则d（x）= d（[x] + 1），其中[x]是x的整数部分。定义3.3设D~=（A;;L;D）是一个辩证系统，设 dL是一个关联的对话，也就是说，一个可能的nite时间顺序序列的语句从L实例化的主题，说出的代理人在A根据游戏规则D。假设dL的第t个元素是实例化的语句Lj（t;Pi;k），其中t= 1; 2;：。与 d L相关联的对话路径d是函数d：R+！通过设置d（0）= 0，设置每个d（t）等于：d（t 1）+（0;：; 0; 1; 0;：：; 0），其中非零坐标对应于标记为（Pi; k; L j）的轴;并且其中d（x）= d（[x]+1），当x 2 [t 1; t）时。我们说d是对应或匹配d L的对话路径。很容易看出这样的d是一个对话路径。因此，对于每一个法律对话，我们都有一个从原点开始的通过Rn+的相关的连续有向路径，该路径由平行于空间轴的直线段组成，每个直线段的长度为一个单位这样的路径可以表示在nite（定义2的条件bi在后一种情况下，我们说路径d是具有终止时间点m的终止路径，或者路径在m处终止，其中m是条件中提到的整数(b)（二）定义2。在这种情况下，我们也说对话路径是长度的M.如果是前一种情况，我们说路径d是无穷的或无穷的。区分一般的对话路径（如上所述）和那些遵守对话游戏规则的对话路径是有用的。定义3.4设d：R+！假设A是一组大小为p的代理人，一组大小为q的讨论主题，D是一个对话游戏协议，具有一组大小为l的语句L，n=pql，使得A中的代理人之间存在合法对话，该对话涉及D中的主题，并根据D的规则进行，使用其对话路径匹配d的语句L的集合。那么我们说d在辩证体系（A; ; L; D）下是一条对话道路或者是合法的。P麦克伯尼和帕森斯10一般而言，并非所有对话途径都与法律对话相对应。这是因为各种组合，终止和承诺规则cre-ate子集的Rn+的一个合法的对话路径不能进入或必须遍历。因为组合规则通常根据对话中的先前发声和说话主体的身份来指定哪些实例化的发声可以、可以不或必须发声，所以这些禁止和强制区域将在对话中的每一轮中消失。因此，因为在任何一个时间的两个对话的历史可能是不同的，一个对话路径可以穿过对另一个对话路径禁止的区域;一个对话路径甚至可以穿过在同一对话中稍后或较早对其本身禁止的区域。在下面的章节中，我们将提到禁忌区和终结区，这是在特定时间点特定辩证体系下的一条对话路径，具有明显的意义。3.3路径和系统等价因为我们的重点是特定类型的代理互动，如谈判或说服，我们关心的是看到什么外部行动承诺在对话过程中，以及什么信息是参与者之间传递，以实现这些承诺。因此，我们需要对这些特征进行某种测量，这是我们首先通过考察每一种语言类型的句法而获得的。定义3.5主格D=（A;;L;D）是一个辩证系统，L2L是一个语类.我们定义了说话人发出L语言时可能传递的信息，记为PossInfo（L），它是由L语言中所有可能的子集构成的集合。类似地，由说出语言L的参与者可能做出的动作，表示为Poss Acts（L），是所有可能的子集的集合。a可以被实例化为L中的动作。 一个程序性语句L有PossInfo（L）= PossActs（L）= f;g，即只包含空集的集合。例如，具有语法seek price（k; P i;）的语句，其中k是正整数（时间戳），P i2 A是代理，并且2是命题，将具有Poss Info（seekprice）=ffg j 2 g，即的所有单例子集。相比之下，具有句法prefer（k; Pi;;）的语句，其中k和Pi如前所述，并且具有;2个命题，将具有PossInfo（prefer）=ff;gj; 2; 6= g，即的两个不同元素的所有子集。因此，Poss Info（seek price）6= Poss Info（prefer）。因此，每一个语句都定义为P（）P（a）的子集。给定对话中的信息传递位置L的每个话语用P（）的子集PossInfo（L）的一个元素的内容来实例化。考虑到实例化导致我们去-ne实际传输的信息和实际承诺的行动参与者在一个特定的对话。麦克伯尼和帕森斯11定义3.6设d为辩证体系下的对话路径D~=（A; ; L; D），设dL为相应的对话。我们定义d传递的信息，记为Info（d），作为dL中说出的语句传递的信息集，即。Info（d）=f2j9Lj（t; Pi;）2 dLg.同样地，我们定义d所承诺的行动，记为Acts（d），作为dL中说出的话语的说话者所承诺的行动命题的集合，即。Acts（d）=f2 a j 9 L j（t; P i;）2 d Lg.利用这些定义，我们接下来定义了两个对话路径的“接近度”的概念。定义3.7设d; e：R+！Rn+，是同一辩证体系（A; ; L; D）下的两条法律对话路径。我们说d接近于e，恰恰是在两条路径都终止且Info（d）=Info（e）和Acts（d）的情况下。= Acts（e）.注意，两个接近的路径可以在不同的时间点终止，即，不同的长度。我们有下面的结果，省略了它的直接证明。命题3.8两条法律对话路径之间的接近关系是一种等价关系。2因此，我们可以说在同一对话系统下的两个对话路径d和e是等价的，我们用d e表示。我们也提到相应的对话是等价的。我们用[d]表示对话路径d的等价类，我们称之为路径等价。我们还有以下几点。命题3.9对于任何辩证体系D~，path-e等价的集合D~（1/2）下的线性对偶图类是夜。证据这一结果来自于这样的假设：是夜。 2使用路径等价的概念，我们现在定义一个辩证系统之间的相似关系定义3.10子命题D~=（AD;D;LD;D）和E~=（AE;E;LE;E）分别是m维和n维的两个辩证系统。 我们证明了D~与E ~相似，如果存在一对一且到函数h：Rm+！ Rn +麦克伯尼和帕森斯12使得对于D~下每个终止对话路径d，存在E ~下的终止h（ d）= e，Info（d）= Info（e），Acts（d）= Acts（e），并且使得对于所有对话路径E0e在E ~下，存在对话路径d 0d，使得h（d 0）= e 0。换句话说，两个对话系统是相似的，如果第一个可以被映射到第二个，使得终止对话被映射到终止对话，同时保留信息传输和动作承诺，并且使得等价的对话路径被映射到等价的对话路径。显然，要使这样一个地图h存在，话语D和E的两个宇宙必须相交，它们各自的行动子集也必须相交。h的定义中的第二个条件，即对于每个e0存在d0，且h（d0）=e0，可以被认为类似于对h的连续性要求，因为在第二辩证系统中彼此接近的对话路径被要求是在第二辩证系统中彼此接近的对话路径的图像。第一。与路径等价一样，我们关于辩证系统相似性的概念也是一种等价关系，我们省略了它的直接证明。命题3.11辩证体系之间的关系是等价关系。2因此，我们可以把两个辩证系统D~和E~的峰值等价，表示为D~E~。 这种辩证系统的等价性概念是一种全局性质，它是根据局部性质的存在而定义的，即：相似性对话之路。 注意等价映射h将合法的对话路径映射到合法的对话路径;由于这些路径在各自的空间中避免了禁区，因此h在将R m+映射到Rn+时保持了这种结构。4比较辩证体系在这一节中，我们从对话系统的等价和对话系统下对话路径的等价类集合之间的联系开始。建议4.1补位D~E~是两个等价的拨号系统。 则每个系统下合法终止对话路径所生成的路径等价类的集合是同构的。麦克伯尼和帕森斯13L2 JjL2 JjD对应于P（）的子集的E~下的路等价类[e在路径等价类[e]中的对话路径e。因为D~E~，那么那里证据我们需要证明在两组路径等价类之间存在一对一和一对映射。设=D[E]是两个论述域的联合，a=Da[E]是两个行动命题子集的联合。通过路等价的定义，特定辩证系统的路等价类集中的每个类对应于P（）P（a）的唯一子集，其中P（X）是X的幂集.F或E~下的路等式，赋予它E~下的路等式对应于P（）P（a）的相同子集E ~下存在这样一个路径等价类是因为从D~到E~的等价映射h包含了每个对话所传递的信息和所承诺的动作。这个映射是一对一的，因为每个路径等价类都与P（）P（a）的唯一子集相关联。为了证明它是对的，假设，为了矛盾的目的，有一些P（a）在D~（？）对应。 考虑一个必须是D~下的对话路径d使得h（d）=e。 因此，Info（d）=信息（e）和行为（d）=行为（e）。 但这仅仅意味着[d]与P（）P（a）的相同子集是[e]相关联，这与假设不符。2命题4.1表明，根据实空间之间的映射定义的对话等价保持了相关路径等价类集合的结构考虑到对话对等的定义，这并不奇怪。然而，它允许我们推导出以下有趣的推论：命题4.2补充命题D~=（A;;LD;D）和E~=（A;;LE;E）是两个分别为m维和n维的辩证系统，使得L E = L D[fL0 g. 此外，假设f;g=PossInfo（L0）6=SPossInfo（L），J我是JLD。 则D~和E~不等价。P roof. 如果我们有D~E~，那么，根据命题4.1，我们将有一个等-两组路径等价类的态射。 然而，由于f;g 6=位置信息（L0）6=S所有J的位置信息（L）L，至少有一个JL0的实例化，其传递P（）的非空子集，通过任何对话转移，而不是这种表达方式。 由于D~系统中的对话只包含L D中的语句，我们就存在一个矛盾。 因此，D~和E~不相等。2一个类似的结果也适用于对话系统，这种对话系统的死亡仅仅是因为一种语言承诺了其他语言所不承诺的行为此外，委员会认为，两个结果都适用，如果有一个以上的losureL0 2 Ln LD 这传递信息或承诺采取不可能使用语言的行动E麦克伯尼和帕森斯14在LD.类似地，我们有下面的推论，我们省略了它的类似证明命题4.3补充命题D~=（A;;LD;D）和E~=（A;;LE;E）是两个分别为m维和n维的辩证系统，使得协议D和E仅通过E中的规则而死亡，该规则在某些条件下终止对话。则D~E~仅当对于E下的每个终接拨号路径e其中规则被调用并导致终止，在D下存在终止对话路径d，其中Info（d）= Info（e）并且Acts（d）= Acts（e）。2这些推论很重要，因为它们为我们设计对话系统提供了一些指导。有了它们，我们知道，增加一个表达方式或终止规则，传递在当前表达方式集合中没有传递的信息，将创建一个非等价系统，即一个对话系统，其中将有对话传递不同的信息或承诺不同的动作。 对话系统的等价性，正如我们所做的那样，在这里，并不是设计和评估的唯一标准对话游戏协议;人们可能希望添加或不添加这样的语句或其他原因的规则，例如整体简单性或编码特定的论证理论[21]。然而，我们相信对话等价性是一个重要的标准，这些结果给我们一个购买了解其含义的对话游戏协议设计。5有限对话与无限对话在对话协议下进行的对话可以在若干次对话之后终止，或者如果协议规则允许，它们可以独立地继续。由于大多数软件代理都是为现实世界的应用程序，它是不可能的代理将被允许他们的人的校长独立地参与对话。每一个代理人最终都将不得不退出无终止的对话，无论代理人或其委托人认为对话目标的实现多么可取。但何时应该退出？为了探讨这个问题，我们考虑了在一个协议下nite（终止）和innite对话之间的我们是从Escherichfeucht-Fra的角度来做的。 数学逻辑的SS E游戏[13]。这些考虑的问题，同构的两个在尼特结构评估是否同构之间存在的部分，结构的子集8我们从定义对话的子集开始根据在给定数量的话语内终止的协议8.两个无限结构之间的部分无限同构的概念 ss e [10]. Andrzej Eughfeucht [7]通过在两个玩家之间构建2n步的抽象游戏来扩展这个想法，复制者和破坏者，他们交替选择nite结构中的两个元素进行nite数量的移动。Duplicator的目的是表明这两种结构是同构的，而Spoiler的目的是表明它们不是。如果n麦克伯尼和帕森斯15P roof. 集合[D~]的每一个元素都是某个元素的等价类定义5.1设D~是一个辩证系统，n是一个正整数.那我们就走吧 D~n是在D~ n下进行的所有法律对话的集合其终止于时间t，对于0tn。此外，在记法的滥用中，设[D~n]表示包含在D~n中的对话的路等类的集合，设[D~]表示包含在D~ n中的对话的路等类的集合。 我们称[D~n]为有限路等类集，[D~]为D ~的路等类集.然后，我们有以下命题连接nite对话到协议下的所有可能对话。建议5.2补充建议D~是一个辩证的体系。则存在m，a非负整数，使得对任意整数n>m，[D~n]同构于[D~].下的对话D~;这样的对话必须最终终止，包含在[D~n]中，对n. 但由命题2可知，集合[D~]是nite的. 结果如下。2作为这个命题的推论，我们可以证明等价的辩证系统最终有同构的nite路等价类集。建议5.3补位D~E~是两个等价的拨号系统。 则re存在非负整数m，使得对任意整数n>m，[D~n]同构于[E~n].证据我们用矛盾来证明这一点。假设结果不为真意味着对于整数m中的每一个位置，存在一个更大的整数n，使得[D~n]与[E~n]不同构. 但这两个辩证系统是等价的，因此它们各自的（不）路径等价类集是同构的（提案4）。但这两个集合都是nite（prop.2）。因此，最终必须存在某个整数值m，在该整数值m之后，nite路径等价集合的相应序列都不增加大小。因此，这两个序列必须收敛在一个nite时间后的nite集上，这与不是所有这样的对都同构的假设相矛盾。2回想一下，路径等价类是根据在对话过程中传输的信息或产生的动作承诺来定义的因此，如果代理人的目标是这样定义的，|信息的接收或传递，或行动承诺的发生|第7号提案他说，每一个可能的对话目标都是可以在某些对话中实现的，参与者从两个父结构中选择的元素是同构的。否则剧透就赢了。如果两个nite结构实际上是同构的，那么对于每个niten，对于大小为2n的博弈，复制者存在一个获胜策略。然而，反过来也不一定是真的，因为人们可以很容易地想象每对大小相等的在父结构之间没有（不）同构的nite子集麦克伯尼和帕森斯16其他在一个晚上的时间。当然，尽管这令人欣慰，但这可能无法为正在进行特定对话的智能体提供关于是继续还是离开的指导;我们希望将来能回到这个问题，也许将其与人工智能中最近关于重新考虑智能体意图的研究联系起来。6结论在本文中，我们已经定义了一个新的几何语义的对话游戏协议之间的互动自治代理，并开始探索其形式化的属性。我们已经用这些性质证明了，如果附加的语言所传递的信息或使说话者承担的行动是其他语言的任何组合所不能我们也开始探索夜间和夜间对话之间的关系。虽然我们的方法在数学上并不复杂，但我们相信我们的结果是重要的，因为它们为对话游戏协议的设计和评估提供了正式的指导。我们相信这个应用领域包含进一步调查的潜力。除了上述问题外，我们还关注另外两个问题。首先，在这里介绍的工作中，我们没有使用对话路径是时间导向的这一事实。最近的有向同伦理论，或dihomotopies [8，27]，这已经出现在应用代数拓扑学的并发问题，在理论计算机科学，可能是相关的，因为我们考虑的时间方向的对话。其次，我们相信本文的结果可以很容易地表示在范畴理论方面，的确，范畴理论可以提供一个更优雅的手段来抽象远离非必要的功能的协议，并对类协议的我们正在进行这两方面的调查。引用[1] S.艾布拉姆斯基互动语义学：游戏语义学导论。在A. M. Pitts和P.Dybjer，编辑，Semantics and Logics of Computation，第1页{31.剑桥大学出版社，剑桥，英国，1997年。[2] L. Amgoud ， N. Maudet 和 S. 帕 森 斯 使 用 论 证 来 模 拟 对 话 。 在 大 肠Durfee，编辑，Proceedings of the Fourth International Conference on Multi-Agent Systems（ICMAS 2000），第31页，Boston，MA，USA，2000年。Press.[3] 亚里士多德。 话题 克拉伦登出版社，牛津，英国，1928年。[4] F.迪格努姆湾Dunin-Keplicz和R.维尔布鲁日基于Agent理论的对话式团队组建。In C. Castelfranchi和Y. Lesp erance，编辑，第七届Agent理论、架构和语言国际研讨会（ATAL-2000），第141{156}页，波士顿，美国，2000年。麦克伯尼和帕森斯17[5] F.迪格努姆湾Dunin-Keplicz和R.维尔布鲁日通过对话创造集体意愿。 LogicJournal of the IGPL，9（2）：305{319，2001.[6] F. Durrenmatt。 危险的游戏。乔纳森·卡普，伦敦，英国，1960年。（翻译R。和C. Winston ofDie Panne，1956年以德文出版。[7] A. Eschericht feucht. 对 策 在 形 式 化 理 论 完 备 性 问 题 中 的 应 用 。Fundamenta Mathematicae，49：129{141，1961.[8] L.法伊斯特鲁普循环、双拓扑和死锁。计算机科学，10：459{480，2000。[9] FIPA。沟通行为图书馆规范。技术报告XC 00037H，智能物理代理基础，2001年8月10日[10] R. Fra SS E.论关系系统的分类。Publications Scienti ques de l'Universited'Alger，1（1），juin 1954.[11] C. L. 汉布林 谬误。 梅图恩，英国伦敦，1970年。[12] D. Hitchcock，P. McBurney，and S.帕森斯审议对话的框架。In H. V.Hansen，C. W. Tindale，J. A. Blair和R. H. Johnson，editors，Proceedingsof the Fourth Biennial Conference of the Ontario Society for the Study ofArgumentation（OSSA 2001），Windsor，Ontario，Canada，2001.[13] W. 霍奇斯较短的模型理论剑桥大学出版社，剑桥，英国，1997年。[14] J. Hulstijn。询问和交易的对话模式。荷兰恩斯赫德特文特大学博士论文，2000年。[15] N. R. Jennings，P. Faratin，A. R. Lomuscio，S. Parsons，M. Wooldridge和C.西拉自动化谈判：前景、方法和挑战。国际群体决策与谈判杂志，10（2）：199{215，2001。[16] J. A. Levin和J.A. 摩尔对话游戏：自然语言交互的元认知认知科学，1（4）：395{420，1978。[17] Lorenzen 和 K. 洛 伦 兹 。 对 话 逻 辑 Wissenschaftliche Buchgesellschaft ，Darmstadt，德国，1978年。[18] J. D.麦肯齐在非累积系统中的无条件乞讨。哲学逻辑，8：117{133，1979。[19] J. May eld，Y. Labrou和T. Finin.评估KQML作为代理通信语言。 InM. J. 奥尔德里奇，J。 P. 微米的ller和M. Tambe，编辑，Intelligent Agents II，Lecture Notes in Arti cial Intelligence的第1039卷