|
|
- 2018
基于良基语义的协商机制研究
|
Abstract:
在当今社会生活中，协商已渗透到人类活动的各个方面，自动协商一直是多Agent领域研究的热点之一.近年来，一些学者采用具有非单调特征的回答集程序表示Agent知识，通过回答集程序的相互更新实现协商.虽然目前已经提出一些基于回答集程序的方法来解决协商问题，但这些研究并没有充分考虑协商最优解和协商过程复杂性之间的平衡问题.寻找基于回答集程序的协商解实际上至少是一个NP-难的搜索问题，而回答集程序的良基语义模型在多项式时间内可以计算得到.因此，本文利用良基语义，结合信念修正的思想对协商过程进行优化，从而提出了一个基于良基语义的双边协商模型.该模型可有效缩短协商过程，实现协商最优解和协商过程复杂性之间的平衡.最后，本文通过实验验证了协商模型的有效性和适用性.
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
| [1] | 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 |
| [2] | LIFSCHITZV. Foundations of Logic Programming[M]//Principles of Knowledge Representation. California: CSLI Publications, 1996: 69-128. |
| [3] | 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. |
| [4] | 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 |
| [5] | 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 |
| [6] | 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 |
| [7] | KRISHNA V, SERRANO R. Multilateral Bargaining[J]. Review of Economic Studies, 1996, 63(1): 61-80. DOI:10.2307/2298115 |
| [8] | 艾解清.双边多议题自动协商研究[D].杭州: 浙江大学, 2011: 3-11. |
| [9] | 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. |
| [10] | 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. |
| [11] | 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 |
| [12] | 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. |
| [13] | 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. |
| [14] | LIFSCHITZ V. Answer Set Programming and Plan Generation[J]. Artificial Intelligence, 2002, 138(1/2): 39-54. |
| [15] | 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 |
| [16] | 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. |
