Argumentation as distributed constraint satisfaction: applications and results

ABSTRACT

Conflict resolution is a critical problem in distributed and collaborative multi-agent systems. Negotiation via argumentation (NVA), where agents provide explicit arguments or justifications for their proposals for resolving conflicts, is an effective approach to resolve conflicts. Indeed, we are applying argumentation in some real-world multi-agent applications. However, a key problem in such applications is that a well-understood computational model of argumentation is currently missing, making it difficult to investigate convergence and scalability of argumentation techniques, and to understand and characterize different collaborative NVA strategies in a principled manner. To alleviate these difficulties, we present distributed constraint satisfaction problem (DCSP) as a computational model for investigating NVA. We model argumentation as constraint propagation in DCSP. This model enables us to study convergence properties of argumentation, and formulate and experimentally compare 16 different NVA strategies with different levels of agent cooperativeness towards others. One surprising result from our experiments is that maximizing cooperativeness is not necessarily the best strategy even in a completely cooperative environment. The paper illustrates the usefulness of these results in applying NVA to multi-agent systems, as well as to DCSP systems in general.

REFERENCES

• 1: A. Armstrong and E. H. Durfee, Dynamic prioritization of complex agents in distributed constraint satisfaction problems, Proc. of IJCAI, 1997.
• 2: Mike H. Chia , Daniel E. Neiman , Victor R. Lesser, Poaching and Distraction in Asynchronous Agent Activities, Proceedings of the 3rd International Conference on Multi Agent Systems, p.88, July 03-07, 1998
• 3: Daniel Frost and Rina Dechter, Look-ahead value ordering for constraint satisfaction problems, Proc. of IJCAI, 1995.
• 4: B. Grosz, Collaborating systems, AI magazine, 17(2), 1996.
• 5: N. R. Jennings et al., On argumentation-based negotiation, Proc. of the Intl. Workshop on Multi-Agent Systems, 1998.
• 6: 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]
• 7: Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
• 8: Jyi-Shane Liu and Katia P. Sycara, Multiagent coordination in tightly coupled task scheduling, Proc. of ICMAS, 1996.
• 9: N. Matos , C. Sierra , N. Jennings, Determining Successful Negotiation Strategies: An Evolutionary Approach, Proceedings of the 3rd International Conference on Multi Agent Systems, p.182, July 03-07, 1998
• 10: S. Minton, M. D. Johnston, A. Philips, and P. Laird, Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method, Proc. of AAAI, 1990.
• 11: H. Sawamura, Y. Umeda, and R. K. Meyer, Computational dialectics for argument-based agent systems, Proc. of the Intl. Conf. on Multi-Agent Systems, 2000.
• 12: M. Tambe, Towards flexible teamwork, Journal of Artificial Intelligence Research (JAIR), 7:83-124, 1997.
• 13: M. Tambe and H. Jung, The benefits of arguing in a team, AI Magazine, 20(4), 1999.
• 14: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707]
• 15: M. Yokoo , K. Hirayama, Distributed Constraint Satisfaction Algorithm for Complex Local Problems, Proceedings of the 3rd International Conference on Multi Agent Systems, p.372, July 03-07, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory