A study on the termination of negotiation dialogues

ABSTRACT

Dialogue represents a powerful means to solve problems using agents that have an explicit knowledge representation, and exhibit a goal-oriented behaviour. In recent years, computational logic gave a relevant contribution to the development of Multi-Agent Systems, showing that a logic-based formalism can be effectively used to model and implement the agent knowledge, reasoning, and interactions, and can be used to generate dialogues among agents and to prove properties such as termination and success. In this paper, we discuss the meaning of termination in agent dialogue, and identify a trade-off between ensuring dialogue termination, and therefore robustness in the agent system, and achieving completeness in problem solving. Then, building on an existing negotiation framework, where dialogues are obtained as a product of the combination of the reasoning activity of two agents on a logic program, we define a syntactic transformation of existing agent programs, with the purpose to ensure termination in the negotiation process. We show how such transformations can make existing agent systems more robust against possible situations of non-terminating dialogues, while reducing the class of reachable solutions in a specific application domain, that of resource reallocation.

REFERENCES

• 1: L. Amgoud, S. Parsons, and N. Maudet. Arguments, dialogue and negotiation. In W. Horn, editor, Proc. 14th ECAI, Berlin, Germany. IOS Press, August 2000.
• 2: R. N. Bol, Loop checking in logic programming, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 3: Paul Davidsson, Categories of Artificial Societies, Proceedings of the Second International Workshop on Engineering Societies in the Agents World II, p.1-9, July 07, 2001
• 4: Frank Dignum , Barbara Dunin-Keplicz , Rineke Verbrugge, Dialogue in Team Formation, Issues in Agent Communication, p.264-280, January 2000
• 5: J. Dix, F. Sadri, and K. Satoh, editors. Computational Logic and Multi Agency, Special Issue of the AMAI. Baltzer Science Publishers, to appear.
• 6: T. H. Fung and R. A. Kowalski. The IFF proof procedure for abductive logic programming. Journal of Logic Programming, 1997.
• 7: A. C. Kakas, R. A. Kowalski, and F. Toni. The role of abduction in logic programming. Handbook of Logic in AI and Logic Programming, 5:235--324, 1998.
• 8: A. C. Kakas and P. Mancarella. On the relation between Truth Maintenance and Abduction. In T. Fukumura, editor, Proc. PRICAI-90, Nagoya, Japan, pages 438--443, 1990.
• 9: Robert Kowalski , Fariba Sadri, From logic programming towards multi-agent systems, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.391-419, 1999 [doi>10.1023/A:1018934223383]
• 10: Sarit Kraus , Katia Sycara , Amir Evenchik, Reaching agreements through argumentation: a logical model and implementation, Artificial Intelligence, v.104 n.1-2, p.1-69, Sept. 1998 [doi>10.1016/S0004-3702(98)00078-2]
• 11: P. McBurney and S. Parsons. A geometric semantics for dialogue game protocols for autonomous agent interactions. In UKMAS, Oxford, UK, Dec. 2001.
• 12: S. Parsons, C. Sierra, and N. R. Jennings. Agents that reason and negotiate by arguing. Journal of Logic and Computation, 8(3):261--292, 1998.
• 13: S. Rochefort, F. Sadri, and F. Toni, editors. Proc. Int'l. Work. on Multi-Agent Systems in Logic Programming, ICLP'99, Las Cruces, NM. Nov. 1999.
• 14: Fariba Sadri , Francesca Toni , Paolo Torroni, Dialogues for Negotiation: Agent Varieties and Dialogue Sequences, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.405-421, August 01-03, 2001
• 15: F. Sadri, F. Toni, and P. Torroni. Logic agents, dialogues and negotiation: an abductive approach. In Proc. AISB'01 Convention, York, UK, March 2001.
• 16: Tuomas Wilhelm Sandholm , Victor R. Lesser, Negotiation among self-interested computationally limited agents, 1996
• 17: Ken Satoh , Keiji Yamamoto, Speculative computation with multi-agent belief revision, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544950]
• 18: D. N. Walton and E. C. W. Krabbe. Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning. State University of New York Press, Albany, NY, 1995.
• 19: M. J. Wooldridge and S. Parsons. Languages for negotiation. In W. Horn, editor, Proc. 14th ECAI, Berlin, Germany. IOS Press, August 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Design, Languages

Keywords:
abduction, computational logic, dialogue, multi-agent systems, negotiation, termination