This post is intended to provide a very cursory introduction, and, hopefully, a greater appreciation for Knowledge Representation and Reasoning (KRR) as a burgeoning field within Artificial Intelligence (AI). One of my favorite topics in KRR, ontologies, is not even discussed in this post, but it holds a prominent place in the field of KRR, as does Resource Description Framework (RDF), RDFS, the Semantic Web, and more. This post focuses on the benefits of Answer Set Programming (ASP) and its many applications across multiple industries.

The goal of AI is to have a computer behave intelligently through computational means. When we think of AI most of us think about things like image recognition, recommendation systems, chatbots, and self-driving cars for example. However, most of these capabilities come from models that were taught through the application of algorithms against data. KRR, however, is the area of AI that deals with how to reason with knowledge so the computer will do the correct thing. We want the self-driving car to stop instead of striking the pedestrian, but do we want the car to stop when a speeding vehicle is following too closely and a tumbleweed blows across the street? This reasoning capability has many industrial applications outside of the obvious and we are just beginning to scratch the surface. Before providing some concrete examples, let’s briefly discuss what we mean by reasoning with knowledge and why it is just now beginning to be fully realized.

KRR is a field of study within Artificial Intelligence (AI) that has existed along side algorithms like back-propagation for years, and the value of both are just now being realized due to the increased compute capacity of modern day computers. While most fields like machine learning, deep learning neural networks, and Natural Language Processing (NLP) all depend on data to learn facts, KRR is about reasoning with knowledge, and the computations require comparable resources.

As an example, we use an Artificial Neural Network (ANN) to identify objects such as a dog, cat, vacuum cleaner, and a food blender by analyzing photographs, or videos. One method of accomplishing this is to have a program analyze a Red, Blue, and Green three dimensional image. Each RBG layer is a matrix of numbers with values dependent on the intensity of each color, and these numbers are processed through the back-propagation algorithm which is eventually trained to distinguish between the various objects. The algorithm is learning through the use of data. The computer now knows how to identify each of the objects previously mentioned. However, if a robot is programmed to house sit, which object will the robot remove from the house in the event of a fire.

Before the robot will behave the way we would expect, or want it to behave, we must be able to represent knowledge in a way that a computer can use that knowledge. Once the knowledge is represented, new information can be derived from that knowledge. One way of representing this knowledge is through the use of symbols. For example: ??? man ;??? woman. Using these representations, we can use reasoning which is a form of calculation with symbols that stand for propositions.

If you’ve ever taken a logic course, you recognize where I’m going with this. KRR relies on formal logic that provides the framework for discussing various kinds of deductive, abductive, default, and epistemic forms of reasoning, among others. While the premise might sound simplistic, it is not. Through the formalization of the syntax and semantics of various types of logic like propositional, and first-order logic, arose Answer Set Programming (ASP) which is a declarative programming paradigm suitable for knowledge intensive and combinatorial search problems. There are several ASP solvers out there, but the one I will use to demonstrate the capabilities of ASP is called Clingo.

Before we get into the weeds of a real world problem, let’s demonstrate some fun problems that are easily solved via the use of Clingo, and without nearly the brain power required to solve the same problem in C++, or Python even. Most everyone is familiar with the puzzle Towers of Hanoi where there are three pegs and a fixed number of disks. The rules can be found here if you are not familiar with the puzzle.

If there are n disks, the puzzle can be solved in 2?-1 moves, so a three disk puzzle can be solved in 7 moves, and four disk with 15 moves etc. Here Clingo solves the problem of 5 disks with 31 moves in 0.054s:

Granted this is a game, and it can be used to solve chess problems as well as Sudoku, and other games, but it can just as easily be used to solve problems like assigning adjusters to claims while minimizing costs associated with travel and use of external adjusters, while at the same time maximizing assignment of adjuster’s to claims according to personal preferences. This problem is described in detail below for those interested, but as you look through the problem domains for the ASP Challenge 2019 discussed below, you will see that the problems have in common optimizing solutions that reduce costs, and risks applied to a number of industries ranging from insurance, to Amazon robotic warehouses, to optimizing restaurant distribution routes. KRR is how computers will learn to reason.

ASP Challenge 2019

The problem for this exercise was taken directly from the ASP Challenge 2019 web site which has the purpose as quoted from their web site:

Invite the ASP community to face novel and challenging real-world/industrial benchmarks.
Make it possible for all solvers and solver extensions to participate.
Push the limits of ASP languages and solvers.”

ASP Challenge 2019

Problem Statement:

The problem statement is to “define an efficient method for reliably, and consistently assigning adjusters to each insurance claim based on the adjuster’s availability, qualifications, proximity to a claim, the adjuster’s preferences, level of effort, while minimizing the cost associated with external adjusters/referees.” Because the term adjuster is more common in the United States, I replaced occurrences of referee with adjuster, with the exception of the model below where I had already captured the image.

Requirements:

As with any project, you must have well defined requirements and understand the data, and its relationships:

Hard Constraints:

1. The maximum number of working minutes of a adjuster must not be exceeded by the actual workload, where the actual workload is the sum of the efforts of all cases assigned to this adjuster.
2. A case must not be assigned to a adjuster who is not in charge of the region at all (i.e., who has preference 0; see below).
3. A case must not be assigned to a adjuster who is not in charge of the type of the case at all (i.e., who has preference 0; see below).
4. Cases with an amount of damage that exceeds a certain threshold can only be assigned to internal adjusters.

Weak Constraints:

1. Internal adjusters are preferred in order to minimize the costs of external ones.
2. The assignment of cases to external adjusters should be fair in the sense that their overall payment should be balanced (i.e., they should all have the chance to handle cases such that their overall payments are similar).
3. The assignment of cases to (internal and external) adjusters should be fair in the sense that their overall workload should be balanced.
4. Adjusters should handle types of cases with higher preference.

The description of the complete problem, along with signatures and predicates can be found on the ASP Challenge 2019 under problem domain. Instance data is provided as well to validate the coded solution. For example, given the following signatures, the result should be to assign claim to adjuster: assign(cid, aid).

Example 1:

given:
case(4, c, 90, 3000, 2000, 90).
referee(4, i, 480, 220, 0).
referee(5, i, 360, 140, 0).
referee(6, e, 480, 40, 700).
prefType(4, c, 0).
prefType(5, c, 2).
prefType(6, c, 3).
prefRegion(4,2000,3).
prefRegion(5,2000,2).
prefRegion(6,2000,2).
externalMaxDamage(1500).
assignment:
assign(4, 5)

As you can see highlighted in the figure above, the problem was correctly solved by assigning Claim ID 4, to Adjuster ID 5.

References

Vladimir Lifschitz, Programming with CLINGO, Department of Computer Science, University of Texas https://www.cs.utexas.edu/~vl/teaching/378/pwc.pdf.

ASP Challenge 2019 https://sites.google.com/view/aspcomp2019/home?authuser=0