We provide a tutorial on answer set programming, a modern approach towards true declarative programming. We first introduce the required theoretical background in a compact, yet sufficient way and continue to elaborate problem encodings for some well known problems. We do so by also introducing the tools gringo and clasp, a sophisticated state-of-the-art grounder and solver, respectively. In that way we cover theoretical as well as practical aspects of answer set programming, such that the interested reader will gather sufficient knowledge and experience in order to continue discovering the field of answer set programming.
Answer set programming (ASP) is a modern approach to declarative programming, where a user focusses on declaratively specifying his or her problem. ASP has its roots in deductive databases, logic programming, logic based knowledge representation and reasoning, constraint solving, and satisfiability testing. It can be applied in a uniform way to search problems in the classes P , NP , and
optimization, database integration, decision support, model checking, robotics,
system syntheses, and many more. We assume the reader to be familiar with
propositional and first-order logic as well as with logic programming [5,13,3].
A college in the USA uses the following rules for awarding scholarships to
students: (
These rules can be encoded in the following program:
eligible(X) ← highGPA(X)
eligible(X) ← minority (X) ∧ fairGPA(X)
¬eligible(X) ← ¬fairGPA(X)
interview (X) ← ∼ eligible(X)∧ ∼ ¬eligible(X)
(
respectively, and we assume that all rules are universally closed. One should observe that the last rule specifies that interview (X) holds if neither eligible(X) nor ¬eligible(X) can be determined.
Now suppose the scholarship selection committee learns that John has a GPA of 3.7, but his application does not give any information on whether he does or does not belong to a minority. What happens with John? Will he be invited to an interview? This additional information can be specified by: 3
fairGPA(john) ←
¬highGPA(john) ←
Propositional Programs For the moment we restrict ASP to propositional
programs. Towards the end of this section we will extend it to first-order logic. The
alphabet is the usual alphabet of propositional logic extended by the
connective ∼denoting default negation. The set of literals consists of all propositional
variables and their (classical) negations. A rule is an expression of the form
L1 ∨ . . . ∨ Lk∨ ∼Lk+1 ∨ . . . ∨ ∼Ll ← Ll+1 ∧ . . . ∧ Lm∧ ∼Lm+1 ∧ . . . ∧ ∼Ln, (
For a rule r of the form shown in (
L1 ∨ . . . ∨ Lk ← Ll+1 ∧ . . . ∧ Lm.
One should observe that for all classical rules r we find head (r) = head +(r) and
body (r) = body +(r). A program is said to be classical if all its rules are classical.
Answer Sets for Classical Programs Let P be a classical program and M be
a satisfiable set of literals, i.e., a set which does not contain a complementary
pair A, ¬A of literals. M is said to be closed under P iff for every (classical)
rule r ∈ P we find that
head (r) ∩ M 6= ∅
whenever body (r) ⊆ M.
(
One may read these rules as either the sprinkler is on (s) or it is raining (r) and
if it is raining, then the color of the sky is not blue. The sets {s, r, ¬b}, {s, ¬b},
s , {r, ¬b} are closed under P, but only the latter two are minimal and, thus,
{ }
are answer sets. On the other hand, the sets ∅, {r} and {r, s} are not closed
under P. One should observe that if we add to P the constraint
s ∨ r ←
¬b ← r
← s
(
{head +(r) ← body +(r) | r ∈ P ∧ head −(r) ⊆ M ∧ body −(r) ∩ M = ∅},
(
As an example consider the program P = {¬p ← ∼p}. We obtain: P|∅ P|{p} P|{¬p} = {¬p} = {¬p} = ∅ One should observe that the reduct of a program relative to a satisfiable set of literals is a classical program.
literals. M is said to be an answer set for P iff M is an answer set for P|M.
Returning to the example discussed in the previous paragraph we observe that ∅ is not closed under P|∅ = {¬p} as ¬p 6∈ ∅, {p} is closed under P|{p} = ∅ but not minimal as ∅ ⊂ { }
p , and {¬p} is minimal and closed under P{¬p} = {¬p}.
Hence, the only answer set for P = {¬p ← ∼p} is {¬p}. Hence, the rule ¬p ← ∼p captures negation by failure: if one cannot show that p holds, then ¬p is true.
Interested readers may try to compute answer sets for the following programs: {p ← ∼ q}, {p ← ∼ ¬p}, {q ← p ∧ ∼ q, p ←, q ←}.
in (
large set of propositional variables and, hence, g P is equivalent to a propositional program. 4
Let P be the set of rules shown in (
M = {fairGPA(john), ¬highGPA(john), interview (john)}.
The reduct of g P relative to M contains the following rules:
eligible(john) ← highGPA(john)
eligible(john) ← minority (john) ∧ fairGPA(john)
¬eligible(john) ← ¬fairGPA(john)
interview (john) ←
fairGPA(john) ←
¬highGPA(john) ←
(
for g P. Reasoning with respect to this answer set tells the selection committee that it should invite John for an interview.
Now suppose that the selection committee learns during the interview that John belongs to a minority. Let
P0 = P ∪ {minority (john) ←}.
M0 = {fairGPA(john), ¬highGPA(john), minority (john), eligible(john)} (
We now want to provide an inside on the methodology of how problems are encoded into programs that can be processed by ASP tools like gringo and clasp [6]. The first tool, gringo, takes a program and transforms it to its propositional equivalent - i.e. grounding the first-order program as defined in Section 3. For the resulting program, clasp is able to compute all answer sets – which refers to the solving process and clasp is therefore a solver.
We have chosen some well known problems taken from constraint programming and SAT-solving to demonstrate step by step the modeling process and its underlying paradigm.1 From now on, we will use the syntax for programs accepted by gringo and explain each new construct used.2 Sudoku The famous number riddle Sudoku represents a constraint problem, typically defined on a 9 × 9 board, where numbers 1 . . . 9 are placed on each cell. The goal is to complete a given board such that in each row, column, and square the numbers 1 . . . 9 occur exactly once.
Now lets develop an encoding of Sudokus as programs. We do not bother about how to solve a Sudoku at all, since we take a truly declarative approach and simply describe the problem. Explaining the game to another person, one would start with defining the board layout, i.e. there is a 9 × 9 grid, and the 1 We use the terms modeling, encoding or reducing a problem rather than programming, because in ASP one does actually not program in terms of control structures specifying a solving strategy. 2 We use version 3.0.4 of gringo, and 2.1.1 of clasp. One should be careful with gringo versions ≥ 4, since the syntax is different than the one introduced in this tutorial. notion of nine rows and columns as well as nine non-overlapping squares of size
number (1..9). row (0..8). column(0..8).
square(0, 0..2, 0..2). square(1, 0..2, 3..5). square(2, 0..2, 6..8).
square(3, 3..5, 0..2). square(4, 3..5, 3..5). square(5, 3..5, 6..8).
square(6, 6..8, 0..2). square(7, 6..8, 3..5). square(8, 6..8, 6..8).
(17)
Rules are separated by a dot. Facts are rules with an empty body, in which case
the implication symbol is omitted in gringo and clasp. number (1..9) is a
syntactical shorthand notation representing the nine facts number (
gringo sudoku.lp --text The --text option prints the grounded program in a human readable way. One should see now that all facts are listed line by line and shorthand expressions are fully spelled out. But there is no need for actual grounding, as we have not used first-order variables yet. Therefore, we want to change the way the squares are defined.
square(0, X, Y ) :- row (X), column(Y ), X < 3, Y < 3. square(1, X, Y ) :- row (X), column(Y ), X < 3, Y > 2, Y < 6. square(2, X, Y ) :- row (X), column(Y ), X < 3, Y > 5. square(3, X, Y ) :- row (X), column(Y ), X > 2, X < 6, Y < 3. square(4, X, Y ) :- row (X), column(Y ), X > 2, X < 6, Y > 2, Y < 6. (18) square(5, X, Y ) :- row (X), column(Y ), X > 2, X < 6, Y > 5. square(6, X, Y ) :- row (X), column(Y ), X > 5, Y < 3. square(7, X, Y ) :- row (X), column(Y ), X > 5, Y > 2, Y < 6.
square(8, X, Y ) :- row (X), column(Y ), X > 5, Y > 5.
Now, each square is defined via a rule, specifying the corresponding ranges of the X and Y values, where :- is the syntactic equivalent to the implication symbol (←) used so far. Replacing the square facts by these new rules in the sudoku.lp file and calling gringo again, yields the same result as before. This is interesting as we would expect grounded rules where X and Y are replaced by the constants 1 . . . 9. Instead we only find the grounded square atoms in the output as intended. It is easy to see that with a naive grounding approach, the resulting grounded program for these nine rules and the nine constants would already be quite large. The gringo grounder applies highly sophisticated grounding strategies. In our case, this even includes the full evaluation of the rule bodies. One should note that this is only possible in our case since in (17) we used the naturals numbers 0 . . . 8 as constants for rows and columns and the comparison relations (<, >, =, ! =, >=, <=) are already predefined for natural numbers. We are not going into details of grounding strategies here; the interesting reader might want to look in [8] for details.
So far we have just encoded the basic Sudoku board. Explaining the game further, one would continue with providing the rules of the game, viz. that (a) in each of the 81 cells exactly one number in {1 . . . 9} can be placed, and (b) in each row, column and square a number is allowed to occur only once. Regarding (a), we introduce the rules cell(X, Y, 1) :- row (X), column(Y ), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 2) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 3) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 4) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 5) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 6) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 7), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 7) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 8), not cell(X, Y, 9). cell(X, Y, 8) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 9). cell(X, Y, 9) :- row (X), column(Y ), not cell(X, Y, 1), not cell(X, Y, 2), not cell(X, Y, 3), not cell(X, Y, 4), not cell(X, Y, 5), not cell(X, Y, 6), not cell(X, Y, 7), not cell(X, Y, 8). each expressing that we can assert a number, e.g. 1, to the cell at position (X, Y ) if we can ensure that none of the remaining numbers 2 . . . 9 is already asserted to (X, Y ). We do so by using default negation not, the syntactic symbol for ∼ as used in gringo and clasp.
Now lets have a closer look on the semantics of these rules, as they have a very special character and role in programs. Assume we only have the first rule, then applying the rule yields a new fact stating that on position (X, Y ) number 1 is placed, if X is a row and Y is a column and none of the remaining numbers 2 . . . 9 is already assigned to position (X, Y ). Since we do not have further initial knowledge telling us that there is already another number placed on cell (X, Y ), the rule is applicable for every position (X, Y ) leading to a grid full of 1’s. Considering all nine rules now, we are faced with some non-determinism, as for each cell we need to guess whether we place a 1 by applying the first rule, or lets say a 7 by applying the seventh rule. Note that the order of rules in a program does not play any role. In consequence, these nine rules define our (complete) search space, namely all 981 number placements possible on a 9 × 9 board. Usually, such rules are called generating or guessing rules and represent and essential part of program encodings - we will later discuss this in more detail.
Apparently, we need to encode the Sudoku rules in (b) in order to suppress those guesses not representing a proper number assignment. We define the constraints :- cell(X, Y 1, N ), cell(X, Y 2, N ), Y 1 != Y 2. :- cell(X1, Y, N ), cell(X2, Y, N ), X1 != X2. #hide. #show cell /3. (19) which express that we would derive false, whenever we have the same number twice in one row (first rule) or column (second rules), respectively. With the help of the statements #hide and #show cell /3 clasp is instructed to print only the predicate cell /3 and to hide the other elements of an answer set.
Furthermore, we need a notion for a number to be in a square, and consequently rule out answer sets where a number does not occur in every square. in square(S, N ) :- cell (X, Y, N ), square(S, X, Y ).
:- number (N ), not in square(S, N ), square(S, , ).
Predicate in square holds for square S and number N if we find N in a cell (X, Y ) which belongs to square S. The second rule, i.e., the constraint, ensures that every number occurs in every square. Note that underscores, as occurring in the very last square predicate, represent anonymous variables which can be used if their assignment is not important, i.e. if they are not used in another predicate of the rule.
One might ask why square(S, , ) is actually needed? Are the first two body literals not sufficient? One can try dropping it from the constraint and call the grounder again. The grounder will state that the variable S is unsafe and, therefore, the rule is unsafe. In fact, gringo requires a program to be safe, which is the case if every rule occurring in the program is safe. A rule is safe, if every variable occurring in the rule occurs in some of the rule’s positive body literals. State-of-the-art grounders like gringo require programs to be safe in order to guarantee termination.
Putting things together, we have fully encoded all rules of Sudoku. One should observe that we have not defined anything instructing how an instance of Sudoku needs to be solved – and we will not do so subsequently. This should emphasize the truly declarative approach. Saving the elaborated rules again to file sudoku.lp and calling
gringo sudoku.lp | clasp will ground the program and pipe the output to clasp. We should get an output similar to the following: clasp version 2.1.1 Reading from stdin Solving...
Answer: 1
cell(
Our encoding so far produces fully filled Sudoku boards, which all agree on
the defined constraints and therefore represent solved Sudoku games. However,
we do not yet solve a given partially filled Sudoku board. We need to provide a
so-called problem instance. For example, we add subsequent cell facts.
cell(
cell(
gringo sudoku.lp sudoku instance.lp | clasp --number 0 With --number 0 we also instruct clasp to enumerate all models, which in our case should be exactly one.
Guess & Check Paradigm Let us reconsider the involved modeling steps in the Sudoku example. We started by specifying a fixed board layout by providing appropriate facts. The possible actions – placing exactly one number on each cell of the board – were modeled as guessing rules. We can see that part of an answer set program as the guessing part, where the search space for answer sets is defined. Secondly, we encoded constraints in order to check whether a generated solution is an answer set according to the rules of the Sudoku game.
This approach of modeling is often referred to as the guess & check or generate-and-test paradigm (see e.g. [8]). This is also motivated by NP problems, having a non-deterministical guessing of prospective solutions and subsequent checking. The interested reader might look at [12], from whom the paradigm originates.
At the end we added to our problem specification a concrete problem instance.
game. Therefore, such problem specifications are said to be uniform. We will use this separation into problem specification following the guess and check paradigm, and problem instance for all subsequent examples.
Graph Coloring We want to illustrate the guess & check paradigm again with a very concise and nice example - the graph coloring problem. In detail, the problem asks whether there is some coloring of the nodes of a given undirected graph using n colors, such that no two nodes connected via an edge share the same color. We restrict the example to n = 3. For encoding the problem we need the notion of color , node, edge and the coloring of nodes. We do so and stick to our paradigm by color (green). color (red). color (blue). coloring(X, green) :- node(X), not coloring(X, red), not coloring(X, blue). coloring(X, red) :- node(X), not coloring(X, green), not coloring(X, blue). coloring(X, blue) :- node(X), not coloring(X, green), not coloring(X, red).
:- coloring(X1, C), coloring(X2, C), edge(X1, X2). which fully specifies the problem. We have three colors specified in the first three facts, three guessing rules as well as a single constraint eliminating solutions where two nodes in an edge relation have identical coloring. We encode the color-guess analogously to the number-guess in the previous Sudoku example.
Because guessing is an essential part, the syntax offers so-called choice rules. As defined in gringo’s syntax documentation [7], choice rules are of the form {a1, . . . , am} :- am+1, . . . , an, not an+1, . . . , not ak. where 0 ≤ m ≤ n ≤ k, and each ai is an atom for 0 ≤ i ≤ k. This allows us to derive any subset of {a1, . . . , am} (head atoms), provided that the body is satisfied. We could encode the following for coloring nodes:
{coloring(X, green), coloring(X, red), coloring(X, blue)} :- node(X). But since we can derive any subset for some node, this would yield nodes having more than one color assigned, or even no color at all. Therefore, the syntax allows an extension to put cardinality restrictions on the subset choice: l {a1, . . . , am} u :- am+1, . . . , an, not an+1, . . . , not ak. forcing the subset size to be within the lower bound l and upper bound u. I.e., we assign exactly 1 color to each node by
1 {coloring(X, green), coloring(X, red), coloring(X, blue)} 1 :- node(X). (20) ensuring that whenever we have some node X, we are allowed to add exactly one of the three head atoms to an answer set. We can even generalize rule (20) such that we do not need to partially instantiate the coloring predicate in the head. The syntax therefore offers so-called conditional literals of the form l : l1 : . . . : ln, with 0 ≤ i ≤ n. While grounding, l is instantiated under the conditions l1 to ln. It can be used for our purpose as follows: 1 {coloring(X, C) : color(C)} 1 :- node(X). (21) The grounding of expression {coloring(X, C) : color(C)} expands to the one in (20). I.e. the set is generated by instantiating the coloring atom where C must be some color . We end up with a very compact encoding of the graph coloring problem: color (green). color (red). color (blue). 1 {coloring(X, C) : color(C)} 1 :- node(X).
:- coloring(X1, C), coloring(X2, C), edge(X1, X2).
For the problem instance, we provide a small graph with 4 nodes and 4 edges: node(1..4).
edge(
Saving the problem description to coloring.lp and the problem instance to simple-graph.lp, we can first get again an impression on the grounder’s work: gringo coloring.lp simple-graph.lp --text This yields the following output besides existing facts: 1#count{coloring(4,blue),coloring(4,red),coloring(4,green)}1. 1#count{coloring(3,blue),coloring(3,red),coloring(3,green)}1. 1#count{coloring(2,blue),coloring(2,red),coloring(2,green)}1. 1#count{coloring(1,blue),coloring(1,red),coloring(1,green)}1. :-coloring(3,green),coloring(4,green). :-coloring(3,red),coloring(4,red). :-coloring(3,blue),coloring(4,blue). :-coloring(3,green),coloring(2,green). :-coloring(3,red),coloring(2,red). :-coloring(3,blue),coloring(2,blue). :-coloring(1,green),coloring(3,green). :-coloring(1,red),coloring(3,red). :-coloring(1,blue),coloring(3,blue). :-coloring(1,green),coloring(2,green). :-coloring(1,red),coloring(2,red).
:-coloring(1,blue),coloring(2,blue).
It is interesting to see that the resulting program is already partially evaluated. For example, the edge atom in all constraints is missing, which is fine since it was merely used for instantiation of the other two coloring atoms. Also the choice rule was turned into four constraints, each for one of the nodes. I.e. the constraint
1 #count{coloring(1, blue), coloring(1, red), coloring(1, green)} 1. represents the instantiation of rule (20) for node 1, where the node predicate in the body was instantiated with 1 and, therefore, omitted since, in this case, we only care about the head. With this constraint we fail if the #count function counts more than 1 occurrences of colorings for node 1 or less, respectively. We compute all answer sets for the union of the problem description (coloring.lp) and problem instance (simple-graph.lp) with:
gringo coloring.lp simple-graph.lp | clasp --number 0 For the provided graph, 12 colorings exist. The interested reader should try with an encoding of a more complex graph, e.g. the Petersen graph [15,16], in order to get an impression of clasp’s performance.
Traveling Salesman Problem Another combinatorial problem, but with an optimization aspect, is the so-called traveling salesman problem (TSP). We want to demonstrate that answer set programming can also be applied to find optimal solutions. A salesman is requested to visit some pre-defined cities. In order to be as efficient as possible, he wants to visit every city only once, as well as to travel the shortest roundtrip visiting all cities starting and ending in the same city.
The problem can be separated into, (a) finding roundtrips beginning from and ending in the same city visiting all other cities only once, and (b) computing the length of each roundtrip in order to find the shortest. The first is known as the problem of finding Hamiltonian cycles in graphs, another well-known NP -complete problem. Therefore, we are faced with the optimization aspect to find the minimal Hamiltonian cycle in a given weighted graph, where the nodes in the graph represent our cities and labeled edges between nodes represent connections (e.g. highways or railways) between the cities. We encode the TSP problem description in exactly these steps, starting with appropriate guessing rules: 1 {cycle(X, Y ) : edge(X, Y )} 1 :- node(X).
1 {cycle(X, Y ) : edge(X, Y )} 1 :- node(Y ).
Apparently, for a node to be in a cycle it must have an incoming edge as well as an outgoing edge. In the case of Hamiltonian cycles, a node in the cycle has exactly one incoming and one outgoing edge. This is specified in the rules (22) and (23). Again we use a cardinality restriction (exactly 1) on the head’s choice expression {cycle(X, Y ) : edge(X, Y )}. I.e., for every node X, in the first rule we choose exactly 1 of the instantiated cycle(X, Y ) literals, which the grounder instantiates with some Y whenever the conditional edge(X, Y ) is fulfilled. In (22) we choose an outgoing edge and derive that it belongs to the cycle, whereas in (23) we do so for incoming edges. Since for every node we non-deterministically pick one outgoing and incoming edge, we might have generated a cycle or not. To rule out model candidates not representing cycles, we check whether every node can be reached by every other node and exclude models where there is an unreachable node.
reachable(Y ) :- cycle(s, Y ). reachable(Y ) :- cycle(X, Y ), reachable(X).
:- node(X), not reachable(X).
Rule (24) and (25) define the notion for a node being reachable from all other nodes. It is defined recursively, i.e., a node Y is reachable if it is a direct neighbor of the starting node s (recursion base case). Furthermore, we conclude that node Y is reachable if for another reachable node X we find (X, Y ) is in the cycle. We simply define the constraint (26) to fail whenever we have a node X for which we can not demonstrate its reachability. Saving (22)-(26) to hamiltonian.lp we can compute Hamiltonian cycles for some given graph, e.g.
node(dresden). node(novosibirsk). node(moscow). edge(dresden, moscow). edge(dresden, petersburg). edge(dresden, stavropol). edge(petersburg, novosibirsk).
node(petersburg). node(stavropol). edge(stavropol, novosibirsk). edge(moscow, petersburg). edge(moscow, stavropol). edge(moscow, novosibirsk). edge(Y, X) :- edge(X, Y ). encodes, without edge weights, the graph depicted in Figure 1. The last rule models symmetry of the edge relation in order to only provide one direction via (22) (23) (24) (25) (26) (27) Moscow 14
36 Petersburg
Stavropol Dresden Novosibirsk the facts. We save (27) to map.lp and call:
gringo -c s=dresden hamiltonian.lp map.lp | clasp --number 0 With -c s=dresden the constant s in (24) is rewritten with dresden, in order to define that we want to start from the city of Dresden. We should receive 8 answer sets, each including instantiated cycle literals representing edges of the Hamiltonian cycle, similar as in subsequent output.
clasp version 2.1.1 Reading from stdin Solving...
Answer: 1 cycle(dresden,stavropol) cycle(moscow,dresden) cycle(stavropol,novosibirsk) cycle(petersburg,moscow) cycle(novosibirsk,petersburg) ...
Answer: 8 cycle(dresden,moscow) cycle(moscow,stavropol) cycle(petersburg,dresden) cycle(stavropol,novosibirsk) cycle(novosibirsk,petersburg) SATISFIABLE Models : 8 Time : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 0.000s The interested reader might try simple-graph.lp from the previous example: Are there any Hamiltonian cycles?
We can compute cycles now, however, we have not respected the optimizing aspect of the TSP problem yet – i.e. Hamiltonian cycles with minimal overall distance. We need additional knowledge representing the distances between the cities, by defining the ternary predicate distance and providing the following instances: distance(dresden, moscow, 20). distance(dresden, stavropol, 26). distance(moscow, petersburg, 7). distance(novosibirsk, petersburg, 38). distance(X, Y, C) :- distance(Y, X, C). distance(dresden, petersburg, 18). distance(moscow, stavropol, 14). distance(moscow, novosibirsk, 34). distance(stavropol, novosibirsk, 36).
Intuitively, distance(dresden, moscow, 20) represents the fact, that the distance between Dresden and Moscow is 20. And to keep it less complex, we express symmetry of distances via the last rule. Since we want to minimize a cycle’s overall length, we need to know the length of each cycle. The syntax offers some build-in constructs for such purposes called aggregate functions. They are used within aggregate atoms, which are atoms of the form
l #A[l1 = w1, . . . , ln = wn] u.
Each literal li has an assigned weight wi which is 1 if not given explicitly, and the function A is applied to the weights of all literals li, 1 ≤ i ≤ n. Aggregate atoms can be used as constraints, or on the right hand-side of some variable assignment. For example, we use #sum in order to assign the sum of all distances between cities in some hamiltonian cycle.
circumference(N ) :- N = #sum [cycle(X, Y ) : distance(X, Y, C) = C]. (28) Lets disassemble rule (28). We know conditional literals already from choice rules like the one in (22), i.e. the expression cycle(X, Y ) : distance(X, Y, C) will be evaluated while grounding and yields instantiated cycle(X, Y ) atoms whenever there is a corresponding distance(X, Y, C). The only difference now, is that we take the distance value C and use it as the weight. For cycle(dresden, stavropol) and cycle(mosow, dresden), we obtain the grounded rule circumference(46) :- 46 = #sum[cycle(dresden, stavropol) = 26, cycle(moscow, dresden) = 20].
It should be clear to see now how #sum yields the sum 46, which is assigned to variable N and therefore the new fact circumference(46) is introduced. We can save the distance facts and rule (28) to distances.lp and again request all answer sets via: gringo -c s=dresden hamiltonian.lp map.lp distances.lp | clasp --number 0
One should see that each answer set now also includes circumference denoting the cycle’s overall length. We now only need to instruct clasp to provide only the answer set having minimal circumference value. We do so using an objective optimization function, in our case #minimize.
#minimize [circumference(N ) = N ]. (29) It operates on the same input as aggregate functions, but it does actually not represent a constraint nor a rule. It simply instructs clasp to print answer sets with optimal value, in our case the hamiltonian cycle with overall length 121. We suggest to have a look at clasp’s optimization features documented in [7,8], which is quite involved since there are many command options instructing clasp on how to deal with optimal solutions. It is also worth to have a look at all other aggregate functions, namely #count, #avg, #min and #max.
We provide some more problems, which we suggest the interested reader to model and encode in a similar fashion as we have done in the previous examples. The planning problems Cannibals and Missionaries and Towers of Hanoi might be slightly more involved. Moreover, one can find more problems, as for example in [9,11,8].
The Seating Problem Workshop organizers want to arrange the seating of a social dinner in such a way that participants share a table only together with participants they don’t know (yet), respectively participants for who it is known that they know each other should not sit at the same table. There are n tables with some fixed number m of chairs available. Naturally, participants can only sit at one table and chair, however, tables do not need to be fully seated in case there are less than m × n seats.
Cannibals and Missionaries We can also encode planning problems, like the famous one proposed by [2]. Three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board. Towers of Hanoi Another famous and historic planning problem is the hanoi tower problem. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: – Only one disk can be moved at a time. – Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
– No disk may be placed on top of a smaller disk. 6
In this tutorial, we introduced the theoretical background by means of the interview example, i.e. the notion of a program, rule types, answer sets for programs, as well as the reduct of a program. Equipped with the theory, we had a closer practical look at some encodings of problems using the syntax of gringo in order to solve the problem with the clasp solver. Both tools emerged from the potassco project [6]. The introduced language constructs should cover the basics as far as possible, such that the interested reader should be able to model the three open problems from the previous section. All these problems and especially the provided problem instances are quite small, though clasp is able to deal with extreme large problem instances, as annual competitions demonstrate [1].
Especially for readers familiar with logic programming (e.g. in prolog ), it might have immediately become clear, that we do not have to care about the ordering of rules in any way, which imposes the answer set approach to be truly declarative; and, as [8] point out, is a real separation of logic and control compared to other approaches. Also one might miss data structures as they are known as nested terms e.g. in prolog. In answer set programs n-ary tuples and (flat, since grounded) terms are the choice for data structures. Further reading We have not covered details, for example, on using arithmetics or other language extensions, which are fully covered in [7,8]. In general we used the syntax accepted by gringo in version 3.0, as documented in [7]. Also, entire lectures could be dedicated to grounding and solving strategies, which is due to the fact that modern solvers use state-of-the-art SAT techniques. In [8] these insights are provided in detail.
We should also note, that although we used the potassco tools in this tutorial, there are several more systems available and used in academical as well as industrial applications. Just to mention, there is the dlv system introduced in [11] and professionally maintained by DLVSYSTEM s.r.l., some spin-off company of the university of calabria. Moreover there is the Smodels solver and corresponding grounder Lparse, which was the very first implementation of the stable model semantics for logic programs, developed by [14]. In fact Lparse imposes some unofficial standard syntax, which is also accepted as input by clasp. There is evan an answer set extension to prolog - Answer Set Prolog (AnsProlog). In their comprehensive work, [9] use AnsProlog to introduce the ASP approach.
Among these systems, unfortunately their syntax is not standardized yet. Therefore the syntactic structures introduced in this tutorial may not work, or lead to other results when using other tools. However, there is an ASP standardization working group elaborating a common input language definition [4]. New versions of gringo, up from 4.0, stick to the current version of the standard.