一种基于回答集程序的多方协商方法研究

摘要

人工智能的研究涉及了控制论、信息论、语言学、数理逻辑和哲学等多门学科，人们期待智能体Agent能够像人类本身一样进行思维和推理，智能Agent可以被认为是存在于某一环境的实体，能够感知环境，接收来自环境的消息，并做出反应，进而反作用于环境。其研究的主要内容包括知识表示、自动推理和搜索方法、机器学习和知识获取、知识处理系统、自然语言理解等。因此，知识表示和推理成为智能系统中重要的组成部分，它决定了Agent的推理和学习能力。
　　 协商理论在多Agent系统研究过程中起到了至关重要的作用。20世纪80年代末至90年代，多Agent系统协商模型大部分是静态的，该类模型是利用博弈论在近似完备知识情况下和封闭环境下进行研究的。值得注意的是，博弈论在多Agent系统协商中起着非常重要的作用，这是因为博弈论被公认为是研究人类社会交互的最佳数学工具，它能够评价协商是否有效。而随着人工智能的发展，完备知识和封闭状态下的协商根本满足不了现实的需要。人们希望智能体能够像人类本身一样，完成对不确定因素的推理过程。该过程是一个非单调推理的过程。近年来，研究者采用具有非单调属性的回答集程序(Answer Set Program，简称ASP)表示Agent参与协商的背景知识，通过逻辑推理的手段对双方协商机制、方法等进行了一系列研究。ASP具有强大的知识表达力，本文继续采用ASP表示协商背景知识。ASP是一种声明式的编程方式，根据提供的知识库和想要达成的结果，Agent自动完成计算，并将实现该结果的路径反馈给用户，从某种程度上体现了人工智能的自动推理能力。采用ASP表示Agent协商背景知识，一个回答集是Agent的一个协商需求。由于回答集是文字集合，因此协商需求实际是文字集合。本文中，各个Agent根据自己的偏好，对需要接收和需要放弃的文字统一进行排序。优先级高的文字能够换取优先级低的文字，反之则不可以。
　　 协商是各参与人为达成共识而消除不一致或减少不确定性因素的过程，整个过程实际上是各方博弈的过程，通过协商，各参与人交换某些资源达成协议。目前，协商研究主要集中在两个Agent间，但两个Agent间的协商存在有较大的局限性，常常会因为资源稀缺而导致类似于“哲学家用餐”的死锁问题，从而导致协商失败。如果有第三方Agent的存在，各参与人在协商对象和协商内容上有更多的选择，从而可能避免上述问题。因此，我们在两个Agent间的多轮协商基础上，建立了多Agent多轮协商模型，提出了利益补偿概念以及多方协商下的信念修正方法。在协商中，如果存在有某些因素阻碍协商进一步进行，Agent会考察自己能否在下轮中获得利益补偿，如果可以获得利益补偿，Agent会剔除掉这些因素，同时进行信念修正，促使协商继续进行。同时，我们利用博弈论概念，证明了给出的多Agent的多轮协商结论是有效的。通过计算机仿真，利用ASP，求解出给定的实例中多方协商的解，实践了多方协商在给定协商协议下的可行性，其中得出的实验结果与我们的理论预测是一致的，其结果满足博弈中的子博弈完美Nash均衡。

目录

声明

摘要

第1章 绪论

1．1 选题背景及意义

1．2 本文的主要工作

第2章 回答集程序基础

2．1 非单调逻辑

2．2 回答集程序

2．3 本章小结

第3章 协商中的博弈

3．1 协商

3．1．1 协商协议

3．1．2 知识库

3．2 Nash均衡

3．2．1 博弈的表述

3．2．2 Nash均衡

3．3 扩展型博弈

3．3．1 博弈树

3．3．2 子博弈完美Nash均衡

3．4 本章小结

第4章 多方协商机制

4．1 Agent间的协商

4．1．1 文字优先级

4．1．2 多轮协商

4．1．3 回答集修改

4．2 多方协商

4．2．1 交易对象选择

4．2．2 利益补偿

4．3 Nash均衡存在证明

4．4 本章小节

第5章 实验

5．1 实验背景

5．2 实验流程

5．2．1 实验流程图

5．2．2 伪代码

5．3 实验结果与分析

5．3．1 实验结果

5．3．2 动态博弈树

5．3．3 双矩阵图

5．4 本章小节

第6章 工作总结与展望

6．1 工作总结

6．2 展望

参考文献

致谢

攻读硕士期间发表的论文情况