Knowledge Representation And Reasoning With Answer Set Programming

Natalie Kuster Natalie Kuster
August 25, 2020 AI & Machine Learning

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!

Knowledge Representation And Reasoning With Answer Set Programming
Seagull ‘Malvin’ — slightly showing off because he can fly. (Photo by Phil Botha on Unsplash)

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.

Knowledge Representation And Reasoning With Answer Set Programming
Exemplary Sudoku game (adopted from Potassco.org).

Python (imperative)

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

Knowledge Representation And Reasoning With Answer Set Programming

C (imperative)

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

Solving the Sudoku game in C looks very similar to Python

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.

  • Experfy Insights

    Top articles, research, podcasts, webinars and more delivered to you monthly.

  • Natalie Kuster

    Tags
    KnowledgeKnowledge RepresentationProgrammingReasoning
    Leave a Comment
    Next Post
    The Power Of Why

    Why 5G Matters to IoT and High Tech

    Comments 1

    1. Natalie Kuster says:
      3 years ago

      You’re welcome! 🙂 There will be more about this topic soon on https://medium.com/@nataliekuster

      Reply

    Leave a Reply Cancel reply

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

    More in AI & Machine Learning
    AI & Machine Learning,Future of Work
    AI’s Role in the Future of Work

    Artificial intelligence is shaping the future of work around the world in virtually every field. The role AI will play in employment in the years ahead is dynamic and collaborative. Rather than eliminating jobs altogether, AI will augment the capabilities and resources of employees and businesses, allowing them to do more with less. In more

    5 MINUTES READ Continue Reading »
    AI & Machine Learning
    How Can AI Help Improve Legal Services Delivery?

    Everybody is discussing Artificial Intelligence (AI) and machine learning, and some legal professionals are already leveraging these technological capabilities.  AI is not the future expectation; it is the present reality.  Aside from law, AI is widely used in various fields such as transportation and manufacturing, education, employment, defense, health care, business intelligence, robotics, and so

    5 MINUTES READ Continue Reading »
    AI & Machine Learning
    5 AI Applications Changing the Energy Industry

    The energy industry faces some significant challenges, but AI applications could help. Increasing demand, population expansion, and climate change necessitate creative solutions that could fundamentally alter how businesses generate and utilize electricity. Industry researchers looking for ways to solve these problems have turned to data and new data-processing technology. Artificial intelligence, in particular — and

    3 MINUTES READ Continue Reading »

    About Us

    Incubated in Harvard Innovation Lab, Experfy specializes in pipelining and deploying the world's best AI and engineering talent at breakneck speed, with exceptional focus on quality and compliance. Enterprises and governments also leverage our award-winning SaaS platform to build their own customized future of work solutions such as talent clouds.

    Join Us At

    Contact Us

    1700 West Park Drive, Suite 190
    Westborough, MA 01581

    Email: support@experfy.com

    Toll Free: (844) EXPERFY or
    (844) 397-3739

    © 2023, Experfy Inc. All rights reserved.