answer-set-programmingclingo

Struggles with the choice rule in Clingo (Answer-Set-Programming)

I'm currently struggling with the following problem: Let's assume this Pseudo-Code:

% Animal:  ID, Type, Cost 
animal    (id1, dog, 300).
animal    (id2, dog, 400).
animal    (id3, dog, 600).
animal    (id1, cat, 200).
animal    (id2, cat, 400).
animal    (id3, cat, 400).
animal    (id1, fish, 20).
animal    (id2, fish, 20).
animal    (id3, fish, 20).

% Search the most expensive animals of each animal-type
most_expensive_animals(ID, Type, Cost) :- animal(ID, Type, Cost),
#max {X:animal(_, Type, X)} =  Cost.

#show most_expensive_animals/3.

The Answer set would be:

most_expensive_animals(id3,dog,600) 
most_expensive_animals(id2,cat,400) 
most_expensive_animals(id3,cat,400) 
most_expensive_animals(id1,fish,20) 
most_expensive_animals(id2,fish,20) 
most_expensive_animals(id3,fish,20)

What I want to achieve is a rule, which chooses just one of each animal type independent of the id (it can also happen randomly). The goal would be, that that the Answer set is the following:

most_expensive_animals(id3,dog,600)  
most_expensive_animals(id2,cat,400) 
most_expensive_animals(id1,fish,20)

In addition, the solutions which are kicked should be saved in an alternative Answer-Set like this:

alternative_most_expensive_animals(id3,cat,400) 
alternative_most_expensive_animals(id2,fish,20)  
alternative_most_expensive_animals(id3,fish,20)

I have followed some approaches with the choice rule, but without success. Can anyone help me further?

Thanks in advance!

Solution

  • Your program as is is deterministic no choices can be made:

    most_expensive_animals(ID, Type, Cost) :- ...

    You could change that by stating

    { most_expensive_animals(ID, Type, Cost) } :- ...

    So every most expensive animal could be listed as most expensive or not. You want to cover the not case as well. I personally would write it as follows:

    1 { most_expensive_animals(ID, Type, Cost) ; alt_most_expensive_animals(ID, Type, Cost) } 1 :- ...

    Meaning every most expensive animal can be listed as such or as an alternative - exactly one of these predicates has to be true if the body fires. But here still lies a problem: multiple or no animal at all could be listed. I personally would write 2 constraints to prevent those two cases.

    :- most_expensive_animals(ID, Type, Cost), most_expensive_animals(ID2, Type, Cost), ID != ID2.
% it is not possible that 2 or more IDs for the same Type and Cost appear

:- animal(_, Type, _), not most_expensive_animals(_, Type, _).
% it is not possible for every type of animal to not have a most expensive listed animal.

    It is possible to use only one constraint:

    :- animal(ID, Type, Cost), #max {X:animal(_, Type, X)} =  Cost, {most_expensive_animals(IDtmp, Type, Cost)} != 1.
% for every Type/Cost pair where Cost is maxuimum for this Type, it can not be the the number of most expensive animals is different to 1.

    Here is the output (tested with the web version of clingo):

    clingo version 5.5.0
Reading from stdin
Solving...
Answer: 1
most_expensive_animals(id3,dog,600) most_expensive_animals(id3,cat,400) most_expensive_animals(id1,fish,20)
Answer: 2
most_expensive_animals(id3,dog,600) most_expensive_animals(id3,cat,400) most_expensive_animals(id3,fish,20)
Answer: 3
most_expensive_animals(id3,dog,600) most_expensive_animals(id3,cat,400) most_expensive_animals(id2,fish,20)
Answer: 4
most_expensive_animals(id3,dog,600) most_expensive_animals(id2,cat,400) most_expensive_animals(id1,fish,20)
Answer: 5
most_expensive_animals(id3,dog,600) most_expensive_animals(id2,cat,400) most_expensive_animals(id3,fish,20)
Answer: 6
most_expensive_animals(id3,dog,600) most_expensive_animals(id2,cat,400) most_expensive_animals(id2,fish,20)
SATISFIABLE