Introduction to Answer Set Programming (Part 1) – Methodology and Syntax

Answer set programming (ASP) is a form of logic programming and a formalism for knowledge representation and reasoning. Since my thesis is related to ASP, I have familiarized with this methodology over the past year and want to provide an introduction for those who have not heard of it yet. Keep in mind that I will be explaining things from my point of view with the background of having two master’s degrees in computer science. I am familiar with conventional programming languages and methodologies but have only slightly touched any form of logic programming. Nonetheless, I have realized that this is a very powerful and easy to use technology for reasoning.

What is ASP?

Let’s start with a basic explanation of what it can be used for. As already mentioned, it is a formalism for knowledge representation and reasoning. This means, that with ASP we can encode given knowledge in form of an answer set program. For simplicity, assume that our knowledge is the following: “birds can fly”. Now, we can use an answer set program to write down this knowledge. This is how the knowledge representation aspect of answer set programming can be imagined, but we can also do reasoning. Consequently, we are able to evaluate the set of valid states/outputs based on the given knowledge. To keep it simple, let’s consider the following. If we know that “birds can fly” (already encoded in an answer set program) and we add knowledge like “Tweety is a bird”, with ASP we can automatically conclude that Tweety can fly. This might not seem like a big game changer, but this is the basic functioning of most logic programming languages as Prolog. It can be utilized in various industrial applications (as mentioned here) and also be used for modern reasoning tasks, model building, classification and last but not least AI. In fact, it is very easy to incorporate simple reasoning tasks in modern applications due to the convenient tools provided for answer set programming and the simple programming model. In order to understand how to do this, we have to first jump into the programming model of ASP before we continue with further interesting topics.

So this part will discuss the syntax and semantics, while in the following parts we will discover answer set solvers, the evaluation method, interesting programs and maybe even some advanced concepts. Please note that you can (and should!) execute the examples given below with an answer set solver like Clingo (download here). It is provided as a command line tool or you can use the online version Clingo in the Browser.

Syntax and Semantics

An answer set program consists of rules. It is a declarative form of programming and the order of the rules is not influencing the output. Rules are expressions of the form:

<head> :- <body>.

The head is a conjunction of atoms, while the body is a disjunction of atoms. Atoms in the body can also be negated, which are then called negative atoms. Atoms can be imagined as functions that evaluate to true or false according to given input parameters. Answer set rules can be read as “If body is true, then head is true”. To make this even clearer, let’s try to encode our knowledge “birds can fly” with an answer set rule. This would look like:

canFly(X) :- bird(X).

Note that X is a variable (as it starts with a capital letter) while constants (and usually also atoms) start with a small letter. Now we can read this rule like: “If X is a bird, then X can fly”. Now let’s continue and add more knowledge to it. Therefore, we need to talk about two special kinds of rules, namely facts and integrity constraints.

Facts are rules without a body. They model an unconditional truth and can be used to encode circumstances or knowledge which we know is true for sure. For example, we can use facts to encode “Tweety is a bird”, which could extend our original program like:

canFly(X) :- bird(X).
bird(tweety).

=== OUTPUT FROM CLINGO ===
Answer: 1
bird(tweety) canFly(tweety)
SATISFIABLE

Note that the ordering of the rules does not matter in ASP. Nevertheless, it is good practice to keep related rules together. Also notice that Tweety is written with small starting letter as it represents a constant, respectively a real entity instead of a variable.

I have also included the output of Clingo above. As you can see, Clingo generates all atoms (facts) that can be constructed with the given input. In this case we already knew that Tweety is a bird, but the answer set solver concluded that it can also fly based on our rule in the first line.

With integrity constraints we are able to express circumstances (atoms) that must not be contained in a valid solution. Let’s say we know that birds can fly, but we also know that penguins are birds that are unable to fly. Or to say it differently: “There is no bird that is a penguin, which is able to fly”. Now if we want to be sure, that our answer set program only prints valid solutions, we could add an integrity constraint to our existing program:

:- canFly(X), penguin(X).

Unfortunately, this does not bring the expected results, so let’s check out why. Adding this integrity constraint does not guarantee, that a new constant (or entity), let’s call him “Peregrine”, who is a penguin, is not able to fly. Instead it only models that if there is some constant that can fly and it is a penguin, than it is not a valid solution. I admit, that this is hard to understand, but this is a very important aspect. Consider the following answer set program including Peregrine and the newly introduced integrity constraint:

canFly(X) :- bird(X).
bird(tweety).
bird(peregrine).
penguin(peregrine).
:- canFly(X), penguin(X).

=== OUTPUT FROM CLINGO ===
UNSATISFIABLE

According to this program, although Peregrine is a penguin, he will be able to fly since he is also a bird (rule in the first line). Then the integrity constraint will check for all constants (variable X) that can fly and are penguins and will eliminate peregrine and therefore the solution. The whole program will therefore be unsatisfiable as you can see in the output.

In order to avoid this behavior, we have to modify the rule in the first line, to express that only birds that are not penguins, are able to fly. This will result in the following program, that will produce the desired output:

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

=== OUTPUT FROM CLINGO ===
Answer: 1
bird(tweety) bird(peregrine) penguin(peregrine) canFly(tweety)
SATISFIABLE

The output now tells us that Tweety is a bird and he is able to fly, while Peregrine is a bird and a penguin. Therefore the atom canFly(peregrine) is not present in the solution as it cannot be logically concluded/entailed from the answer set solver (based on the given rules).

To be precise, after modifying the first rule, we could also omit the integrity constraint as it is not possible to produce a solution in which a penguin can fly anymore. But the one thing you should keep in mind anyways, is that integrity constraints only check if a solution does (not) contain the specified atoms.

Summary

In this article we have discovered answer set programming, which is a form of logic programming. We can use it for representing knowledge and doing reasoning, respectively decision making. Furthermore, we have worked with rules, facts and integrity constraint by encoding our simple Tweety example in form of an answer set program. Maybe you have also installed the answer set solver Clingo or used the online version. If not, I would suggest doing it in order to fully understand the usage of ASP and the solver. In the next part we are going to talk about different answer set solvers and how they work in detail. Stay tuned for the next part and feel free to leave feedback or to post any open questions regarding ASP.

Further parts of this article series:
Introduction to Answer Set Programming (Part 2) – Solving and ASP Systems

Leave a Reply

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