Introduction to Answer Set Programming (Part 2) – Solving and ASP Systems

In the first part of this article series we have discussed the syntax and semantics of ASP and wrote a simple program to encode the Tweety example. If you have not installed Clingo (or another solver) yet, I strongly suggest doing so now as we are going to talk about answer set solving and different ASP systems in this part. Answer set programming is a powerful tool for reasoning, which can also be used in industrial applications. In order to take advantage of its benefits we need to first understand the solving process, which is different from Prolog. Due to the development of ASP during the past 20 to 30 years, we are also going to take a look at ASP language dialects/agreements.

If you have not read part 1 of this article series, you can have a look:
Introduction to Answer Set Programming (Part 1) – Methodology and Syntax

The solving process

When using an answer set programming system like Clingo or DLV2 for solving answer set programs, the solving is usually done in two steps, namely grounding and solving. During the grounding step the system transforms the program in order to only contain variable free terms. To keep it simple we could say that it replaces all variables in the program with all possible constants that are valid based on the facts and the already derived variable free terms. If we consider the program of the Tweety example from the first part, grounding would look like the following.

===== ORIGINAL PROGRAM =====
bird(tweety).
bird(peregrine).
penguin(peregrine).
canFly(X) :- bird(X), not penguin(X).


===== GROUND PROGRAM =====
bird(tweety).
bird(peregrine).
penguin(peregrine).
canFly(tweety) :- bird(tweety), not penguin(tweety).

Note that the only valid variable replacement resulted in the ground rule canFly(tweety) :- bird(tweety), not penguin(tweety). since it is not possible to use the constant peregrine in that rule. To be precise we derived the rule canFly(tweety) by instantiation. This grounding step is also called instantiation and is usually computationally expensive. Hence grounding has a big impact on the performance of the overall answer set solving process. As a result, efficient grounders have been developed to avoid a naïve grounding approach, which replaces variables with all possible constants and produces the full instantiation.

Solving is the second step performed by an ASP system. The algorithms used in this step originate in satisfiability testing. In its early days variants of the Davis-Putnam-Lodgeman-Loveland (DPLL) algorithm, that use backtrack search, were utilized to perform the search for valid answer sets. Nowadays more mature conflict-driven search procedures exist to enhance overall performance. To explain this step with simple words, one could say that an algorithm is used to determine if the ground program contains valid answer sets considering the constraints. As explaining the DPLL algorithm or Conflict-Driven Clause Learning would be too much at this point, I am going to reference a paper that summarizes both grounding and solving, namely “Grounding and Solving in Answer Set programming” by Kaufmann, Leone, Perri and Schaub. This paper outlines solving as follows:

“ […] Modern ASP solvers rely upon advanced conflict-driven search procedures, pioneered in the area of satisfiability testing (SAT; [Biere et al. 2009]). Conflicts are analyzed and recorded, decisions are taken in view of conflict scores, and back-jumps are directed to the origin of a conflict. […] “

Kaufmann, Benjamin & Leone, Nicola & Perri, Simona & Schaub, Torsten. (2016). Grounding and Solving in Answer Set Programming. AI Magazine. 37. 25-32. 10.1609/aimag.v37i3.2672.

ASP Systems

We have already clarified that the solving process consists of two steps, which are grounding and solving. Therefore, answer set solving systems like Clingo or DLV2 need to perform these two steps in order to compute the answer sets, which is what they do. In fact Clingo combines two tools, namely Gringo (the grounder) and Clasp (the solver), to perform these tasks. Also DLV2 contains a grounder and a solver. As a result they are called answer set solving systems or ASP systems as they support the full solving from the ASP program to the resulting answer sets. For simplicity we can still refer to them as “Solvers” as it is clear that there is no solving without grounding.

Clingo is distributed as Windows and Linux binary and basically a ready-to-use command line tool with a wide range of options (command line arguments). The same is true for DLV2 except that it is only available as Linux binary at the moment. For now, let’s stick to Clingo to support readers from both OS platforms and consider a more interesting answer set program than the tweety example.

3-colorability problem

The objective of the 3-colorability problem is to assign 3 colors (e.g. red, green, blue) to the nodes of an undirected graph such that connected nodes always have a different color. If we consider the graph below, a human can easily conclude that there are 6 possible assignments that fulfill this requirement.

6 possible color assignments (answer sets) for this problem instance.

Taking a look at the corresponding answer set program, things start to get interesting for the first time.

1|  node(1). node(2). node(3).
2|  edge(1, 2). edge(1, 3). edge(2, 3).
3|  
4|  col(X, red) | col(X, blue) | col(X, green) :- node(X).
5|  :- edge(X, Y), col(X,C), col(Y,C).

The first two lines of the program above just describe our problem instance. In this case we have three nodes (1, 2 and 3) to which we would like to assign the colors (line 1). Moreover, we have three edges, each of them connecting a node with the two other nodes (line 2). So far so good, now we would like to express what we are looking for in this problem.

In line 4 we are assigning the color red, blue or green to each node. Remember how ASP rules should be read (discussed in part 1): “If body is true, then head is true”. So if we want to formulate the semantics of line 4 in a sentence, one could say: “For each node X, we are assigning either the color red, blue or green to it“. Since this would also allow invalid solutions (e.g. red for all nodes, or blue for two and green for the other) we also formulate an integrity constraint in line 5. Remember, that an integrity constraint expresses a circumstance that must be false in a valid solution (discussed in part 1). We could read line 5 as: “If there is an edge from X to Y and the color of X is C and the color of Y is also C, then this is no valid solution/answer set“. We could also say: “There is no valid solution/answer set that contains an edge from X to Y where the color of X is C and the color of Y is also C“.

By executing this program with Clingo, we can observe that the output corresponds with the 6 possible assignments. Each answer set contains the facts describing the problem instance (lines 1 and 2 of the program), but also the actual valid color assignment. These assignments are also expressed as facts, that were logically derived by the solver based on the rules we defined.

Executing the 3-colorability problem instance with Clingo.

To be fair, this is still a pretty basic example, but it is enough to have a first glimpse of how answer set programming can be utilized. You can maybe already think of a use case in a project or business process, where logical reasoning/decision making could help to simplify things.

ASP Dialects

Answer set programming originally evolved from Datalog more than 20 years ago. Since then the dialects (syntax) diverged with the increasing number of answer set solvers. Around 2013 a “ASP Standardization Working Group” did major work to standardize the ASP language syntax. The “ASP-Core-2 Input Language Format” is nowadays supported by most answer set solvers and also acknowledged as the required syntax in various ASP competitions. Clingo as well as DLV2 support the basic elements of this input language format and/or even extend the specification with further language features. Anyhow this specification can be considered as the standardized ASP dialect at the moment.

Summary

This post was part two of the ASP article series and was mainly theoretical but also a little bit practical. We revised the ASP solving process, as well as the inner components of an answer set solving system. Furthermore, we also wrote an interesting answer set program, which solves the 3-colorability problem and talked about certain dialects and standards of the ASP syntax. The next (and last) part of this introductory series about ASP will be more practical. We are going to look at a more complex problem and try to solve it with ASP. As last time: Stay tuned and feel free to leave feedback or to post any open questions regarding ASP.

Leave a Reply

Your email address will not be published. Required fields are marked *