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

argumentation
Semantics
semantics
Labeling
international competition
Argumentation
methodology
Chemical analysis
evaluation
knowledge
Encoding
Satisfiability

Cite this

@article{55349540b7a54c4a839877ce7fe7b2f0,
title = "How we designed winning algorithms for abstract argumentation and which insight we attained",
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.",
keywords = "Abstract Argumentation, SAT-based Algorithms, Stable and Preferred Semantics",
author = "Federico Cerutti and Massimiliano Giacomin and Mauro Vallati",
year = "2019",
month = "11",
day = "1",
doi = "10.1016/j.artint.2019.08.001",
language = "English",
volume = "276",
pages = "1--40",
journal = "Artificial Intelligence",
issn = "0004-3702",
publisher = "Elsevier",

}

How we designed winning algorithms for abstract argumentation and which insight we attained. / Cerutti, Federico; Giacomin, Massimiliano; Vallati, Mauro.

In: Artificial Intelligence, Vol. 276, 01.11.2019, p. 1-40.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Cerutti, Federico

AU - Giacomin, Massimiliano

AU - Vallati, Mauro

PY - 2019/11/1

Y1 - 2019/11/1

N2 - 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.

AB - 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.

KW - Abstract Argumentation

KW - SAT-based Algorithms

KW - Stable and Preferred Semantics

UR - http://www.scopus.com/inward/record.url?scp=85070531884&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2019.08.001

DO - 10.1016/j.artint.2019.08.001

M3 - Article

VL - 276

SP - 1

EP - 40

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

ER -