CODEWITHSUNDEEP
answer-set-programmingclingo
weak_at_math
weak_at_math

Reputation: 105

How do I encode this in answer set programming?

I am a total newbie to answer set programming, and I am struggling with a rather simple question. The program needs to be written in clingo.

So here is the question:

An abstract argumentation framework consists of a set A of arguments and an attack relation R ⊆ A X A between them. For any two arguments a1 and a2, if (a1, a2) ∈ R then we say that a1 attacks a2: if one admits argument a1 then it casts doubts on argument a2. Formally, a subset of arguments E ⊆ A is stable if the following two conditions hold:

  1. no arguments in E attack any other argument of E.
  2. any argument outside of E is attacked by an argument from E.

Write an ASP program that identifies stable subsets of arguments in a given instance through answer sets. The instance will be provided via two predicates argument/1 and attack/2 corresponding to A and R respectively.

Here is an example:

argument (a).    
argument (b).    
argument (c).    
argument (d).    
attack (a,b).    
attack (b,c).    
attack (d,c).

Valid output:

choose (a) choose (d)

This what I tried, which is obviously wrong:

choose(X)  :- argument(X), attack(X,Y).

I don't know how to approach this at all.

Please help.

Upvotes: 1

Views: 1431

Answers (1)

Duda
Duda

Reputation: 3746

A simple 3 Step solving approach is the following:

  1. describe the facts (check)
  2. generate what you want as a result, but leave the program a choice
  3. give rules which solutions do not apply

So start with 2:

generate possible outcomes. Think of it in simple words: For every argument I choose it or not.
The may or may not part can be solved with a subsum {}.

{choose(X)} :- argument(X).

or even simpler: I choose a subsum from the arguments

{choose(X):argument(X)}.

Lets check the solutions with Potassco and #show choose/1., resoning mode enumerate all:

Answer: 1

Answer: 2
choose(b)
Answer: 3
choose(c).
..
Answer: 15
choose(a) choose(b) choose(c)
Answer: 16
choose(a) choose(b) choose(c) choose(d)
SATISFIABLE

All combinations are found. Time to remove the wrong stuff. Again: think of it in simple words: It is not possible that I choose two arguments where one attacks the other. (If the head is left open, this is read a False.)

:- choose(X), attack(X,Y), choose(Y).

Now check it again:

Answer: 1

Answer: 2
choose(a)
Answer: 3
choose(d)
Answer: 4
choose(a) choose(d)
Answer: 5
choose(c)
Answer: 6
choose(a) choose(c)
Answer: 7
choose(b)
Answer: 8
choose(b) choose(d)
SATISFIABLE

Now we need to make sure every not choosen argument is attacked by a at least one choosen element:

1 {choose(Y):attack(Y,X)} :- argument(X), not choose(X).

Reads: For every argument X, which is not choosen, the number of choosen arguments which attack it, is at least one.

Lets check it:

Answer: 1
choose(a) choose(d)
SATISFIABLE

Nice.

Since the contraints are normally formulated with an empty head, lets reformulate the last rule:

:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

Reads: There is no argument X, which is not choosen and has maximum 0 choosen arguments, which attack X. It gives the same output.

Complete code:

argument (a;b;c;d).   
attack (a,b).    
attack (b,c).    
attack (d,c).

{choose(X):argument(X)}.
:- choose(X), attack(X,Y), choose(Y).
:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

#show choose/1.

Upvotes: 1

Related Questions