Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Cerutti, Federico ORCID: https://orcid.org/0000-0003-0755-0358, Giacomin, Massimiliano and Vallati, Mauro 2019. How we designed winning algorithms for abstract argumentation and which insight we attained. Artificial Intelligence 276 , pp. 1-40.

[thumbnail of argsemsat_journal.pdf]
Preview
PDF - Submitted Pre-Print Version
Download (1MB) | Preview

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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher: Elsevier
ISSN: 0004-3702
Date of Acceptance: 1 August 2019
Last Modified: 04 May 2023 18:33
URI: https://orca.cardiff.ac.uk/id/eprint/124671

Citation Data

Cited 17 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics