Pakota (and Maadoita)

Systems for extension and status enforcement in abstract argumentation via constraint optimization

The Pakota and Maadoita systems are developed by the Constraint Optimization and Reasoning Group at the Department of Computer Science, University of Helsinki. The systems are implemented by Andreas Niskanen.

NEW: See here for the current version of Pakota featuring so-called strong refinements.

About

Argumentation frameworks (AFs) provide a fundamental formalism for defeasible reasoning in abstract argumentation. AFs are directed graphs with the vertices interpreted as abstract arguments and directed edges as directed conflicts or attacks between arguments. Extension enforcement is a form of AF dynamics that is concerned with enforcing a set of arguments to be an extension under a specified semantics of AFs via modifying the attack structure. Such an enforcement is strict if the set of arguments must be exactly an extension of the given semantics and non-strict if the set of arguments is a subset of an extension. Each modification of an attack incurs a cost. The software system Pakota implements extension (non-)strict enforcement under several semantics of AFs via constraint optimization solvers. In addition to extension enforcement, Pakota allows also to optimally solve the so-called status enforcement problem recently proposed in [2] as an natural generalization of extension enforcement. Extension enforcement under grounded semantics [4] is implemented in the Maadoita system.

Features

Pakota currently supports

  • optimally enforcing an extension both strictly and non-strictly under the standard semantics of admissible, complete, stable, preferred, semi-stable, and stage,
  • optimal credulous and skeptical status enforcement under admissible and stable, and
  • outputting direct encodings of NP-variants of the problems in standard input formats of maximum satisfiability (MaxSAT) and integer programming (IP) solvers.

Maadoita supports both strict and non-strict variants of extension enforcement under grounded semantics, and is also capable of outputting direct encodings for MaxSAT and IP solvers.

The underlying MaxSAT solver is Open-WBO, available here.

Usage

Pakota

USAGE: ./pakota file mode sem [options]

COMMAND LINE ARGUMENTS:

file    : Input filename for enforcement instance in apx format.
mode    : Enforcement variant. mode={strict|non-strict|cred|skept}
    strict     : strict extension enforcement
    non-strict : non-strict extension enforcement
    cred       : credulous status enforcement
    skept      : skeptical status enforcement
sem     : Argumentation semantics. sem={adm|com|stb|prf|sem|stg}
    adm        : admissible
    com        : complete
    stb        : stable
    prf        : preferred
    sem        : semi-stable
    stg        : stage

COMMAND LINE OPTIONS:

-h        : Display this help message.
-v        : Display the version of the program.
-o out  : Output clauses to file out and exit.
-t type : Output clauses in format type={wcnf|lp} (default: wcnf).

Maadoita

USAGE: ./maadoita file mode [options]

COMMAND LINE ARGUMENTS:

file : Input filename for enforcement instance in apx format.
mode : Enforcement variant. mode={strict|non-strict}
    strict     : strict extension enforcement
    non-strict : non-strict extension enforcement

COMMAND LINE OPTIONS:

-h      : Display this help message.
-v      : Display the version of the program.
-c      : Use CEGAR instead of direct MaxSAT encoding.
-s      : Output clauses to stdout and exit.
-o out  : Output clauses to file out and exit.
-t type : Output clauses in format type={wcnf|lp} (default: wcnf).

Input format

Extension Enforcement

In the input an AF is specified as well as an enforcement request.

arg(X).   ... X is an argument
att(X,Y). ... there is an attack from X to Y
enf(X).   ... enforce argument X

example:

arg(a).
arg(b).
arg(c).
arg(d).
att(b,a).
att(b,c).
att(c,a).
att(c,d).
att(d,b).
enf(a).

For this example AF and non-strict enforcement under stable semantics, pakota would return

arg(a).
arg(b).
arg(c).
arg(d).
att(a,c).
att(b,a).
att(b,c).
att(c,a).
att(c,d).
att(d,b).

which corresponds to adding attack (a,c).

Status Enforcement

As in extension enforcement, the AF is represented using the arg and att predicates. The arguments to be positively and negatively enforced are represented via the pos and neg predicates, respectively. For example, pos(a). enforces argument a positively. The reasoning mode between credulous and skeptical is chosen from the command line.

Downloads

Pakota

Version 2017-05-31 available here. See README for instructions.

Maadoita

Version 2018-11-01 available here. See README for instructions.

Benchmarks

Extension Enforcement

Benchmarks used in [1] and [3] are available here.

Status Enforcement

Benchmarks used in [2] and [3] are available here.

Grounded Enforcement

Benchmarks used in [4] are available here.

References

[1] Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation. Johannes P. Wallner, Andreas Niskanen, and Matti Järvisalo. In Dale Schuurmans and Michael Wellman, editors, Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI 2016), pages 1088-1094. AAAI Press, 2016.
[pdf] [abstract/bibtex]

[2] Optimal Status Enforcement in Abstract Argumentation. Andreas Niskanen, Johannes P. Wallner, and Matti Järvisalo. In Subbarao Kambhampati, editor, Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 1216-1222. AAAI Press, 2016. [pdf (extended version with proofs)] [abstract/bibtex]

[3] Pakota: A System for Enforcement in Abstract Argumentation. Andreas Niskanen, Johannes P. Wallner, and Matti Järvisalo. In Loizos Michael and Antonis C. Kakas, editors, Proceedings of the 15th European Conference on Logics in Artificial Intelligence (JELIA 2016), volume 10021 of Lecture Notes in Computer Science, pages 385-400. Springer, 2016. [pdf] [abstract/bibtex]

[4] Extension Enforcement under Grounded Semantics in Abstract Argumentation. Andreas Niskanen, Johannes P. Wallner, and Matti Järvisalo. In Michael Thielscher and Francesca Toni and Frank Wolter, editors, Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), pages 178-183. AAAI Press, 2018. [pdf] [abstract/bibtex]