第 1 章 绪论
知识表示和推理是人工智能的一个重要研究领域。在知识表示和推理的相关研究中，大多数研究工作都是以逻辑程序作为工具开展的。从 1972 年诞生的逻辑语言 Prolog，到后来的稳定模型语义，逻辑程序语言取得了里程碑式的进展[1],3]。在将非单调性推理机制与逻辑程序相结合之后，逻辑程序也成为了在实际领域完成非单调推理的有力途径。基于非单调推理的逻辑程序也在协商领域中得到了广泛的应用。本章主要介绍本文的研究背景及意义、国内外基于良基语义的协商方法的研究现状、论文的研究内容以及论文的组织结构。
1.1 研究背景及意义
在云计算、移动终端和物联网等新一代信息技术的高速发展的时代，相关的应用逐渐渗透到社会的各行各业，电子商务就是极具代表性的例子。作为一种新型的商业模式，电子商务对人们的日常生活、消费等方面都产生了较为深刻的影响。与此同时，电子商务已成为信息化、市场化和国际化条件下配置资源的重要途径，是带动经济社会发展的一个强有力的助推器[6]。随着国家“互联网+”行动计划的实施，移动端购物呈现爆炸性增长，电子商务也成为了各级政府高度重视的一个战略性新兴产业[8]。1997 年，世界电子商务会议在法国巴黎召开，大会对电子商务的概念做出了最权威的解释。电子商务，即是 Electronic Commerce，简称 EC。电子商务指的是对整个贸易活动实现电子化。电子商务的概念模型[5]如图 1.1 所示：现实生活中的电子商务活动，买方和卖方存在各种各样的争议和冲突，利用协商来达成共识是一种常用且有效的解决方案。协商存在多种类型：根据协商参与者的个数，协商可以分为双边协商和多边协商；根据协商的议题个数，协商可以分为单议题协商和多议题协商；根据协商的交易轮数，协商还可以分为一轮协商和多轮协商；根据协商的发展历程，协商还可以分为初级协商和自动协商等。本文讨论的协商是双边、多议题、多轮的自动协商。电子商务发展初期，使用最为广泛的协商是初级协商，这是由人们长期的协商历史结果所决定的。最为常见的初级协商包括了招标和拍卖等形式[5]。拍卖是协商的一种常见形式，具体可以分为荷兰式拍卖、英式拍卖等。在英式拍卖中，拍卖方首先给定起拍价，然后不断地提高拍卖的价格，最终仅剩下一个投标者。然而，荷兰式拍卖则恰恰相反，拍卖方首先给定拍卖品的最高价格，然后逐渐降低拍卖的价格，直到有一个投标者愿意接受这个价格结束。常见的拍卖流程如图 1.2 所示。如今，拍卖这种形式的协商已经在电子商务网站中获得了广泛的应用，Ebay 就是一个很好的例子。在 Ebay 网站中采用的是一种单向单拍卖的方式，即一种单向的单议题协商。其中，“单向”是指只能有协商的一方不断出价，而协商的另一方只能够选择接受或者拒绝；而“单议题”指的就是议价，协商双方只能针对商品的价格进行协商。除了 Ebay，国内外许多大型电子商务网站，如京东、天猫、Amazon、Yahoo 等也推出了自己的拍卖系统。这些系统的诞生表明：当今社会活动中，尤其是在电子商务领域，协商扮演着重要的角色。
..........
1.2 基于良基语义的协商问题研究现状
20 世纪 70 年代，历史上首个逻辑程序设计语言 PROLOG 在法国诞生[31]。PROLOG 问世不久，研究者们发现经典逻辑语言在描述人们的推理能力时存在一定的缺陷：它并不能够处理非单调性问题。众所周知，人具有常识的推理能力，而常识推理几乎都存在非单调性[40]。这一问题的发现，开启了学者们针对非单调逻辑的研究的大门。非单调性的主要表现是，当加入一个新的外部信息时，由原本的不完全信息推理得到的结论就不再成立。1980 年，Reiter提出了缺省逻辑（Default Logic）[49]。与此同时，McCarthy 也提出了限制逻辑（Circumscription Logic）[39]。1985 年，Moore 又提出了自认知逻辑（Auto-epistemicLogic）[41]。将经典的逻辑程序设计语言和这些逻辑结合起来，一个新的研究热点就诞生了。为了弥补传统逻辑程序在常识推理方面的不足，Gelfond 和 Lifschitz 在 1991 年将经典的否定（用符号 表示）、否定即失败（Negation as Failure，用符号not表示）和封闭世界假设（ClosedWorldAssumption）的概念引入到传统逻辑程序[50],28]，提出了一种新的逻辑程序——回答集程序（Answer Set Program，简称 ASP）。随着研究的深入，ASP 不断地得到改进，性能也进一步得到提升。回答集程序是一种具有强大的知识表达能力的工具[22]。21 世纪初期，各种设计优良的回答集求解器如雨后春笋般问世，如 Clasp、Smodels 和 Gringo 等。随着回答集求解器的出现，逻辑程序在组合搜索问题领域（如规划、模型检测）也得到了大量应用。毋庸置疑，知识表示长久以来都是人工智能领域的一个研究难点，也是人工智能领域的一个研究重点。而逻辑推理则是研究者们在知识表示领域的常用方法[42],51]。针对多 Agent 系统中的每一个 Agent，都必须选择一个合理、有效的知识表示方法来对它们已有的知识进行表示、推理等。经过大量的研究表明，在知识表示方面逻辑程序毫无疑问是一个首选的工具。近些年，回答集程序被广泛地应用于知识表示与推理[37],42]、规划[34]等领域，并取得了良好的表现。由于 ASP 具有强大的知识表示能力，因此，本文选择回答集程序对协商中的协商参与者的知识进行表示。
........
第 2 章 相关理论
本章首先介绍了逻辑程序与回答集程序的相关知识，揭示了回答集程序在知识表示领域的强大能力。然后，介绍了强、弱忘记理论的相关知识，对良基语义的相关概念进行了一定的说明。最后，还对信念修正的思想进行了介绍。
2.1 逻辑程序
逻辑程序作为陈述知识表示的一种最普遍、最重要的方法，在知识工程中扮演不可或缺的角色[36]。逻辑程序设计是一种表示陈述知识的方法，它为使用计算机求解问题提供了基于逻辑的陈述形式的程序设计语言。接下来，本文将对逻辑程序相关的一些基本概念进行阐述。传统逻辑程序存在一个最大的不足就是不允许直接处理不完全信息。传统逻辑程序中的询问缺少与不可判定的子句相对应的结果，而这些子句表达了经典逻辑理论的信息的不完全性。人类知识绝大部分是常识知识，其主要特征是推理的非单调性，这恰好是经典逻辑程序难以逾越的障碍。为了克服这些不足，文献[28]中提出了回答集程序（Answer Set Program，简称 ASP）。在 ASP 中，提出了“否定即失败（not）”与“经典否定（neg）”这两个概念。这样一来，ASP 不仅能通过“封闭世界假设”来获取隐含的否定信息，也可以包含明确的否定信息，从而使得 ASP 可以对逻辑程序中的不完全信息进行处理。下面主要介绍下 ASP 的简单语法。传统逻辑程序的规则中只包含了正文字和负文字，而回答集程序中则新引入了一个文字，否定即失败（not）。
..........
2.2 忘记理论
在人工智能领域，尤其是知识表示方面，逻辑程序一直都是一种重要工具。从 Prolog 语言到 ASP，逻辑程序在知识表示、推理等场合得到了广泛的应用。随着研究的深入，ASP 也在多 Agent 的协商领域中得到了应用。在 2005 年，Yan Zhang 和 Norman Foo 以 ASP 为知识表示的工具，从而提出了基于强（弱）忘记理论的一次协商方法[61]。这也是强（弱）忘记理论的首次提出。在该理论中，每一个 Agent的知识都是利用 ASP 进行表示，并且 ASP 对应的每一个的回答集就是该 Agent 的一个协商需求候选集。定义 2.17（良基模型）利用最小不动点理论，回答集程序Π的良基模型可以看作是良基集合 Π的最小不动点[54]。良基模型则是一个三值模型，它的解释为：负文字对应的原子的值在该解释下为假，正文字对应的原子的值在该解释下为真，而没有在良基语义中出现的原子的真值是不确定的[10]。文献[24]表明，根据良基模型的定义得到的模型与利用交替不动点的方法得到的回答集程序的良基模型是保持一致的。
............
第 3 章基于良基语义的双边协商模型 ............21
3.1 优先级排序规则 ..............21
3.1.1 文字的优先级 ..........21
3.1.2 文字集的优先级 ......22
3.2 基本定义 ......23
3.3 基于良基语义的双边协商模型 ..........25
3.4 本章小结....... 36
第 4 章实验和分析..............39
4.1 实验设计...... 39
4.1.1 技术可行性分析...... 39
4.1.2 模型界面设计.......... 39
4.1.3 实验数据的选取...... 43
4.2 结果分析...... 44
第 5 章总结与展望..............47
5.1 本文工作的总结.............. 47
5.2 未来工作的展望.............. 47
第 4 章 实验和分析
本文通过前面 1-3 章详细地从理论视角描述了本文设计的基于良基语义的双边协商模型。接下来，本章将通过两个具体的实验进一步来对本文所提出的协商模型的可行性和正确性进行验证。
4.1 实验设计
本文的实验设计以 Java 语言为基础，本实验选择的具体版本号是 Java 1.8.40。本文的实验设计采用的是 B/S 架构（Browser/Server，即浏览器/服务器架构）。本实验所选取的应用服务器是 Tomcat7.0Java 作为一门面向对象编程语言，不仅吸收了 C++语言的各种优点，还摒弃了 C++里难以理解的多继承、指针等概念，因此，Java 语言具有功能强大和简单易用两个特征。Java 语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论。Java 具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。此外，本文实验采用（Java Server Pages，简称 JSP）作为视图层工具，对实验相关的数据和结果进行表示。JSP 是由 Sun Microsystems 公司倡导和许多公司参与共同创建的一种使软件开发者可以响应客户端请求，而动态生成 HTML、XML 或其他格式文档的 Web 网页的技术标准。而 Java的 Servlet 是 JSP 的技术基础，因此，JSP 也同样具备了 Java 技术的简单易用、完全的面向对象、平台无关性且安全可靠等特点。Tomcat 是由 Apache 软件基金会下属的 Jakarta 项目开发的一个 Servlet 容器，按照 SunMicrosystems 提供的技术规范，实现了对 Servlet 和 JavaServer Page（JSP）的支持。概括地说，Tomcat 是一个开放源代码、运行 servlet 和 JSP Web 应用软件的基于 Java 的 Web 应用软件容器。随着互联网应用的快速发展，Java、JSP 等技术以及 Tomcat 服务器都得到了广泛的应用。这一系列庞大的应用也都证明了这些技术和平台的有效性和稳定性，所以，本文选择 Java 和JSP 作为开发技术、以 Tomcat 作为应用服务器来进行实验是完全可行的。
..........
总结
在协商领域，回答集程序是一个强有力的知识表示工具。但从根本来上讲，回答集的求解过程是一个 NP 完全问题，在多项式时间内是无法求解的。而一个回答集程序的良基模型在多项式时间内是可以计算得到的。并且，在现有的基于回答集程序的协商研究中，还没有学者利用良基语义开展过相关工作。因此，本文选择良基语义进行双边协商的研究是合理的，也具有一定的研究价值的。本文以回答集程序作为 Agent 的知识表示工具，采用回答集程序的良基模型对 Agent 的信念进行划分，结合基于信念修正的协商决策模型，从而提出了一个用于快速解决双边协商问题的协商模型。在本文中，首先，利用回答集程序来表示协商参与者所有的知识；然后，通过良基模型的定义分别计算出协商双方的良基模型：将良基集作为协商参与者优先保留的需求，将其它文字集作为协商参与者次要保留的需求，将无基集作为协商参与者不关心的需求，即协商参与者的初始化协商空间是回答集程序的良基集和其它文字集的并集；接着，本文通过预先定义的优先级排序规则对可协商文字集中的文字进行降序排列；最后，利用基于交替提议协议的协商决策模型来实现协商的过程。在协商的过程中，可能存在多个可行的协商交易（即存在多个协商结果），利用本文提出的协商结果评价准则对协商结果进行比较，保留优先级更高的协商结果。本文通过良基模型对 Agent 信念的划分，给定了协商参与者的初始化协商需求，即限定了协商的空间。在协商的过程中，由于协商双方采用交替提议协议，则协商的总的轮数就是有限的。因为协商的空间是有穷的，并且每一轮放弃的文字都是单调增加的，所以协商在有限的时间内是可终止的。本文通过良基语义和基于信念修正的协商决策模型，保证了本文提出的协商的可终止性和收敛性。同时，本文提出的基于良基语义的双边协商模型也定义了双边协商的效益评价准则。在协商决策的过程中，通过合理的效益准则，可以选择更为合理的协商结果。当然，通过计算文字和文字集合的优先级，优先保留较高优先级的文字，放弃较低优先级的文字，在表现出 Agent 的理性特征的同时，尽可能使得自身效益较好。
..........
参考文献（略）