Knowledge Representation And Reasoning With Answer Set Programming

Read about the difference between declarative and imperative programming and learn from code examples (Answer Set Programming, Python and C).

Introduction

The amount of computational problems seems to be unlimited in both industry and science. There is a huge demand for new insights from the vast amount of available data. To obtain this knowledge, dedicated people use all kinds of programming languages for designing and implementing algorithms.

However, many of the current real-world problems are complex (combinatorial) search problems with which we try to automate and optimize processes as well as support people in their decisions. This does not involve encoding of algorithms but encoding given knowledge. In other words, given knowledge about all the rules and constraints to be considered to what is counted as a solution. Instead of writing statements describing the control flow of a computation, declarative programming expresses its logic. What do we want to achieve, not statements about how we can achieve it.

This is called declarative programming.

Why declarative programming?

Using a promising declarative programming paradigm, namely Answer Set Programming (ASP, sometimes also Answer Set Prolog), offers unexpected advantages over the popular imperative programming approach, for example:

• Short solutions (as measured by lines of code)
• Transparency (including readability)
• Reliability

and many more. Once you have broken the problem down into its smallest pieces and written down all the necessary knowledge, you will not only solve the computational challenge. A big advantage is that you have digitized the knowledge and can use it for further problems or make it available in other ways.

Experience and knowledge can be sustainably secured and protected against loss (e.g. through retirement or termination of employees).

Furthermore, it strengthens the cooperation between ‘business people’ and programmers. The integration of artificial intelligence is supported and acceptance at all levels will increase. This is a fundamental process that can only be achieved in cooperation with all departments of a company.

What is ASP and how does it work?

An answer set program consists of given knowledge formulated as facts, rules (head(X) :- body(X).) or constraints. The program is loaded by a solver and returns a “stable model”. This so called answer set consists of all facts that can be derived using the given rules and constraints. A finite amount of stable models are generated as solutions, of which one is finally selected.
Note: grounding and solving the problems are not within the scope of this article.

Let us consider a famous example from logic about birds and penguins. It is a well known fact that birds can fly. This can be encoded as an answert set rule:

canFly(X) :- bird(X).

The rule is read as “If X is a bird, then X can fly”. Now let’s add more knowledge! For example, facts that tell the unconditional truth, just as seagull ‘Malvin’ is a bird, but also penguin ‘Roger’ is one.

canFly(X) :- bird(X).
bird(malvin).
bird(roger).== MODEL OUTPUT ==
Anwer: 1
bird(malvin) bird(roger) canFly(malvin) canFly(roger)
SATISFIABLE

As a result, the answer set tells us the known facts that Malvin and Roger are birds but also concluded that they are able to fly. The biology enthusiasts among us know, that penguins are unable to fly thus the model is wrong!

In order to get acceptable results we need to add more knowledge in form of facts and integrity constraints to the program. Here, the model needs to know that Roger is not only a bird but also a penguin and that there is no bird that is a penguin which is able to fly.

canFly(X) :- bird(X).
bird(malvin).
bird(roger).
seagull(malvin).
penguin(roger).
:- canFly(X), penguin(X).== MODEL OUTPUT ==
UNSATISFIABLE

This does not bring the expected result and shows how important it is to think thoroughly and very carefully about the problem as well as the solution. The model tells, like stated by the programmer, that a bird can fly but there is no advise for birds that belong to the penguin family. To avoid this, we could add that only birds that are not penguins are able to fly.

canFly(X) :- bird(X), not penguin(X).
bird(malvin).
bird(roger).
seagull(malvin).
penguin(roger).
:- canFly(X), penguin(X).== MODEL OUTPUT ==
Answer: 1
bird(malvin) bird(roger) seagull(malvin) penguin(roger) canFly(malvin)
SATISFIABLE

Adding this knwoledge in Line [1], the stable model consists of the expected outcome.

Imperative versus declarative programming

.. for solving Sudoku

Let’s look at another example to highlight the advantages of ASP mentioned above. Sudoku is a well known puzzle game and popular for explaining search problems. Given an initial 9×9 grid of cells containig numbers between 1 and 9 or blanks, all blanks must be filled with numbers. You win Sudoko if you find all values such that every row, column, and 3×3 subsquare contains the numbers 1–9, each with a single occurrence.

Python (imperative)

The following Code snippet will show how to solve the Sudoku in Python.

C (imperative)

Solving the Sudoku game in C looks very similar to Python. There is no significant difference in the approach.

Both, Python and C, show written statements describing the control flow of a computation, thus, the ‘how to solve it’ and how the state has to be changed for the upcoming step.

ASP (declarative)

Last but no least, let’s have a look at the ASP code snippet — after initalization, we are able to solve the Sudoku with less than 10 lines of code!

% Initialize the game (given numbers)
sudoku(1, 1, 5).
sudoku(1, 2, 3).
sudoku(1, 5, 7).
sudoku(2, 1, 6).
sudoku(2, 4, 1).
sudoku(2, 5, 9).
sudoku(2, 6, 5).
sudoku(3, 2, 9).
sudoku(3, 3, 8).
sudoku(3, 8, 6).
sudoku(4, 1, 8).
sudoku(4, 5, 6).
sudoku(4, 9, 3).
sudoku(5, 1, 4).
sudoku(5, 4, 8).
sudoku(5, 6, 3).
sudoku(5, 9, 1).
sudoku(6, 1, 7).
sudoku(6, 5, 2).
sudoku(6, 9, 6).
sudoku(7, 2, 6).
sudoku(7, 7, 2).
sudoku(7, 8, 8).
sudoku(8, 4, 4).
sudoku(8, 5, 1).
sudoku(8, 6, 9).
sudoku(8, 9, 5).
sudoku(9, 5, 8).
sudoku(9, 8, 7).
sudoku(9, 9, 9).
% define the grid
n(1..9).
x(1..9).
y(1..9).% each field contains exactly one number from 1 to 9
{sudoku(X,Y,N): n(N)} = 1 :- x(X) ,y(Y).% helper
subgrid(X,Y,A,B) :- x(X), x(A), y(Y), y(B),(X-1)/3 == (A-1)/3, (Y-1)/3 == (B-1)/3.% constraints
:- sudoku(X,Y,N), sudoku(A,Y,N), X!=A.
:- sudoku(X,Y,N), sudoku(X,B,N), Y!=B.
:- sudoku(X,Y,V), sudoku(A,B,V), subgrid(X,Y,A,B), X != A, Y != B.#show sudoku/3.== MODEL OUTPUT ==
Answer: 1
('sudoku', (2, 1, 6)), ('sudoku', (1, 2, 3)), ('sudoku', (9, 4, 2)), ('sudoku', (7, 2, 6)), ('sudoku', (7, 3, 1)), ('sudoku', (1, 9, 2)), ('sudoku', (5, 1, 4)), ('sudoku', (7, 4, 5)), ('sudoku', (4, 3, 9)), ('sudoku', (9, 1, 3)), ('sudoku', (4, 5, 6)), ('sudoku', (5, 6, 3)), ('sudoku', (2, 4, 1)), ('sudoku', (8, 1, 2)), ('sudoku', (8, 8, 3)), ('sudoku', (7, 9, 4)), ('sudoku', (8, 7, 6)), ('sudoku', (5, 4, 8)), ('sudoku', (7, 6, 7)), ('sudoku', (8, 6, 9)), ('sudoku', (6, 5, 2)), ('sudoku', (9, 7, 1)), ('sudoku', (3, 4, 3)), ('sudoku', (4, 7, 4)), ('sudoku', (3, 3, 8)), ('sudoku', (4, 8, 2)), ('sudoku', (1, 7, 9)), ('sudoku', (9, 9, 9)), ('sudoku', (9, 8, 7)), ('sudoku', (5, 9, 1)), ('sudoku', (4, 4, 7)), ('sudoku', (6, 9, 6)), ('sudoku', (7, 7, 2)), ('sudoku', (2, 7, 3)), ('sudoku', (5, 5, 5)), ('sudoku', (1, 5, 7)), ('sudoku', (1, 1, 5)), ('sudoku', (6, 3, 3)), ('sudoku', (2, 6, 5)), ('sudoku', (2, 9, 8)), ('sudoku', (8, 3, 7)), ('sudoku', (3, 6, 2)), ('sudoku', (3, 8, 6)), ('sudoku', (2, 8, 4)), ('sudoku', (1, 3, 4)), ('sudoku', (8, 2, 8)), ('sudoku', (3, 7, 5)), ('sudoku', (9, 5, 8)), ('sudoku', (4, 9, 3)), ('sudoku', (6, 4, 9)), ('sudoku', (7, 5, 3)), ('sudoku', (2, 5, 9)), ('sudoku', (8, 5, 1)), ('sudoku', (5, 3, 6)), ('sudoku', (4, 6, 1)), ('sudoku', (3, 9, 7)), ('sudoku', (1, 4, 6)), ('sudoku', (9, 2, 4)), ('sudoku', (5, 8, 9)), ('sudoku', (1, 8, 1)), ('sudoku', (6, 6, 4)), ('sudoku', (5, 7, 7)), ('sudoku', (7, 1, 9)), ('sudoku', (3, 5, 4)), ('sudoku', (6, 8, 5)), ('sudoku', (5, 2, 2)), ('sudoku', (2, 3, 2)), ('sudoku', (8, 9, 5)), ('sudoku', (9, 6, 6)), ('sudoku', (9, 3, 5)), ('sudoku', (6, 2, 1)), ('sudoku', (3, 1, 1)), ('sudoku', (4, 2, 5)), ('sudoku', (6, 1, 7)), ('sudoku', (4, 1, 8)), ('sudoku', (8, 4, 4)), ('sudoku', (2, 2, 7)), ('sudoku', (3, 2, 9)), ('sudoku', (1, 6, 8)), ('sudoku', (6, 7, 8)), ('sudoku', (7, 8, 8))}
SATISFIABLE

Note: using for example a Python wrapper for ASP, the result can look as handy as in the code examples above.

Compared to Python and C, this is all about the ‘what’ and not about the ‘how’ — a fundamental difference between the two approaches.

At the very beginning, we define that the Sudoku board is 9×9 cells (or fields) and we use the numbers from 1 to 9 as the values to fill in. Following the basic rule that only one number between 1 and 9 may be filled in each field, we define a little helper. It states which fields refer to the same sub-grid. Finally, we only need the constraints to tell the solver what is possible and what is not. The first line checks, whether the choosen number is unique in the row whereas the second constraint checks the rule for columns. The third constraint completes the rules of the game, according to which a number must also be unique in the subgrid.

That was it. I admit the syntax takes getting used to. But once you’re familiar with it, you can create incredibly readable programs that solve highly complex problems for us.

Summary

ASP is a very promising tool for knowledge preservation and declarative problem solving in the area of Knowledge Representation and Reasoning.

Short solutions — Apart from the initial effort to map the Sudoku game, ASP provides by far the shortest way (measured in lines of code) to the solution.
Transparency — There is no need to create rules which are unclear to the user and which concern the status of the programme. Only the basic conditions and the three rules of the game must be coded in order to end up at the correct result.
Reliability — All rules of the game are fixed and the solver cannot create a black box with solution steps that are not traceable afterwards. This may not be important in the example given, but it is a major issue in many industrial applications.

To mention only a few real-world examples, decision support for space shuttles at NASA, train scheduling in Switzerland — one of the world’s densest train network— , or team building at the largest transshipment terminal on the Mediterranean coast are evidence of its potential.

---

Bottom Line

The acceptance of artificial intelligence in industry is still very low. In addition, many companies are simply overwhelmed by the existing flood of data.

Bring the knowledge of operational subject matter experts together with the strengths of Artificial Intelligence.

ASP offers an unique opportunity to digitalize and protect existing knowledge. Due to the good readability and the required understanding of the process as well as the problem to be solved, IT and business move closer together and thus achieve better and more sustainable success.