How we designed winning algorithms for abstract argumentation and which insight we attained

Federico Cerutti, Massimiliano Giacomin, Mauro Vallati

Research output: Contribution to journalArticle

Abstract

In this paper we illustrate the design choices that led to the development of ArgSemSAT, the winner of the preferred semantics track at the 2017 International Competition on Computational Models of Arguments (ICCMA 2017), a biennial contest on problems associated to the Dung’s model of abstract argumentation frameworks, widely recognised as a fundamental reference in computational argumentation. The algorithms of ArgSemSAT are based on multiple calls to a SAT solver to compute complete labellings, and on encoding constraints to drive the search towards the solution of decision and enumeration problems. In this paper we focus on preferred semantics (and incidentally stable as well), one of the most popular and complex semantics for identifying acceptable arguments. We discuss our design methodology that includes a systematic exploration and empirical evaluation of labelling encodings, algorithmic variations and SAT solver choices. In designing the successful ArgSemSAT, we discover that: (1) there is a labelling encoding that appears to be universally better than other, logically equivalent ones; (2) composition of different techniques such as AllSAT and enumerating stable extensions when searching for preferred semantics brings advantages; (3) injecting domain specific knowledge in the algorithm design can lead to significant improvements.
Original languageEnglish
Pages (from-to)1-40
Number of pages40
JournalArtificial Intelligence
Volume276
Early online date6 Aug 2019
DOIs
Publication statusPublished - 1 Nov 2019

    Fingerprint

Cite this