A Distributed and Clustering-Based Algorithm for the Enumeration Problem in Abstract Argumentation

Sylvie Doutre (1, 2) , Mickaël Lafages (3) , Marie-Christine Lagasquie-Schiex (3)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
2 UT Capitole - Université Toulouse Capitole
3 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage

Computing acceptability semantics of abstract argumentation frameworks is receiving increasing attention. Large-scale instances, with a clustered structure, have shown particularly difficult to compute. This paper presents a distributed algorithm, AFDivider, that enumerates the acceptable sets under several labelling-based semantics. This algorithm starts with cutting the argumentation framework into clusters thanks to a spectral clustering method, before computing simultaneously in each cluster parts of the labellings. This algorithm is proven to be sound and complete for the stable, complete and preferred semantics, and empirical results are presented.

Le calcul de l’acceptabilité dans les systèmes d’argumentation reçoit une attention croissante. Dans les systèmes de grande envergure, avec une structure en clusters, ce calculs e montre particulièrement difficile. Cet article présente un algorithme distribué, AFDivider, qui énumère les ensembles acceptables sous plusieurs sémantiques, en commençant par découper le système d’argumentation en clusters grâce à une méthode de partitionnement spectral, avant de calculer simultanément dans chaque partition des parties des en-sembles acceptables. Cet algorithme est prouvé correct et complet pour les sémantiques stable, complète et préférée,et des résultats empiriques sont présentés.

Mots clés: Algorithms; Enumeration; Abstract argumentation; Clustering

Domaines: Algorithme et structure de données [cs.DS]; Intelligence artificielle [cs.AI]

Sylvie Doutre, Mickaël Lafages, Marie-Christine Lagasquie-Schiex. A Distributed and Clustering-Based Algorithm for the Enumeration Problem in Abstract Argumentation. 22nd International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2019), Oct 2019, Torino, Italy. pp.87-105, ⟨10.1007/978-3-030-33792-6_6⟩. ⟨hal-02419426⟩