Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems

被引:5
作者
Baroni, P [1 ]
Giacomin, M [1 ]
Guida, G [1 ]
机构
[1] Univ Brescia, Dipartimento Elettron & Automaz, I-25123 Brescia, Italy
关键词
argumentation; self-stabilization; multi-agent systems;
D O I
10.1016/j.artint.2005.02.003
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The role of argumentation in supporting various forms of interaction among possibly conflicting autonomous agents has been explicitly recognized in the literature. In argumentation, conflict management is carried out by the formal process of defeat status computation. In this paper we consider the generalization of this process to a distributed setting. We show that significant stabilization problems may arise even in relatively simple cases. A fundamental negative result is then proved: no general self-stabilizing algorithm exists for distributed defeat status computation, indicating that self-stabilizing algorithms for this problem can be defined only under specific conditions. Accordingly, we focus on two cases: an algorithm tailored to a specific family of inference graphs, that include only rebutting defeaters, and an algorithm that applies to any inference graph, also including undercutting defeaters, but may provide (cautiously) incorrect results for some nodes. For both algorithms the worst-case round complexity is analyzed and it is proved that no algorithms with lower complexity exist for the same tasks. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:187 / 259
页数:73
相关论文
共 74 条
[1]   Modelling dialogues using argumentation [J].
Amgoud, L ;
Maudet, N ;
Parsons, S .
FOURTH INTERNATIONAL CONFERENCE ON MULTIAGENT SYSTEMS, PROCEEDINGS, 2000, :31-38
[2]  
Amgoud L, 2000, FRONT ARTIF INTEL AP, V54, P338
[3]   Extending abstract argumentation systems theory [J].
Baroni, P ;
Giacomin, M ;
Guida, G .
ARTIFICIAL INTELLIGENCE, 2000, 120 (02) :251-270
[4]  
Baroni P, 2003, LECT NOTES ARTIF INT, V2711, P440
[5]   Argumentation through a distributed self-stabilizing approach [J].
Baroni, P ;
Giacomin, M .
JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 2002, 14 (04) :273-301
[6]  
BARONI P, 2004, P 10 INT C INF PROC, P1887
[7]  
BARONI P, 2001, P INT PAR DISTR PROC
[8]  
BARONI P, 2004, P 16 EUR C ART INT E, P783
[9]  
BARONI P, 2005, SELF STABILIZING DEF
[10]   A method for the computational modelling of dialectical argument with dialogue games [J].
T. J. M. Bench-Capon ;
T. Geldard ;
P.H. Leng .
Artificial Intelligence and Law, 2000, 8 (2-3) :233-254