Rule Engines and Knowledge-Intensive Processing wi...
Artificial Intelligence and Machine Learning Blogs
Explore AI and ML blogs. Discover use cases, advancements, and the transformative potential of AI for businesses. Stay informed of trends and applications.
Answer Set Programming (ASP) is a software paradigm that can be used to represent knowledge and to solve combinatorial and information-intensive problems. Combinatorial search problems are those believed to not have an efficient way to reduce the space of solutions (NP-hard), some examples of this sort are presented in this article. The notion of knowledge is very broad and very dependent on the domain. It is inclusive of beliefs to various degrees, facts and rules that can be applied for enabling reasoning, and generally, that commonsense understanding we have about the world.
The puzzles presented here are solved within a programming tool I made, freely inspired by Datalog and Clingo, the ASP developed at University of Potsdam. Differently from Datalog, the scripts reported here are based on a domain specific language, and they leverage the strongly typed compiler of Scala. The objective of this dissertation is not to provide a more efficient way to do ASP but rather to build the tools for moving on with the project I’m conducting, and to explore the potential of this paradigm in other areas such as data management and rule systems. I wish to convey the awareness that this software paradigm brings advantages in terms elasticity and completeness for real world scenarios. ASP has been used for:
Decision support system to help the Space Shuttle controllers to deal with critical situations caused by multiple failures.
Efficient workforce management of Gioia Tauro seaport subjected to enormous amounts of constraints.
Classify profiles and actual needs of Telecom Italia users (1M calls/day) for creating personalized experience of customer care.
Configuration of products and services are subjected to complex rules in railways safety controls, tourism, automotive, computer hardware, software packages.
ASP is a form of logic programming where rules (or arguments) can be thought of as executable specifications. An ASP program does not listen for queries, rather it applies all conditions recursively until the generated knowledge does not evolve anymore. When there are no more satisfiable conditions to run, the system returns the list of results, the so called stable models, or answer sets. Let’s see it with an example about prime numbers.
What are prime numbers? Numbers only divisible by itself and one. In logic, for assessing a statement as a valid one, we have to disqualify any possible counterexample. A number is not prime if it is a product of two numbers different from one and itself. Reformulating the definition in this perspective we have:
X is a prime number if there is no evidence that it is a compound number.
Let’s get a list of compound (or composite) numbers by generating all possible combinations of factors in a given range, and then check whether their module (the remainder of their division) is zero.
("compound" :: X :: e) :- (X := (1 to N), Y := (2 to X - 1), (X %% Y) === 0)
In the first clause of the premise (X := (1 to N)) I simply assign a list to a variable X. In the second, for each X there is a list of Y, and the corresponding combination of them is the cartesian product of all Xs and Ys. Last clause will check whether any single instance of X is divisible by Y. If so, a new atom “compound” is generated. Lastly, the following argument will instantiate the “prime” atoms:
(“prime” :: X :: e) :- (X := (1 to N), not “compound” :: X :: e)
What is new here is the not keyword called negation as a failure. It checks whether that atom instance “compound” :: X exists in the knowledge graph, and returns true when there is not. The full program is:
import com.sap.cxlabs.bewater.logic.asp._
val N = 7
val arguments = Args(
("compound" :: X :: e) :- (X := (1 to N), Y := (2 to X - 1), (X %% Y) === 0)
(“prime” :: X :: e) :- (X := (1 to N), not “compound” :: X :: e)
)
val results = arguments.deduct()
In ASP there are at least two main stages that denote the execution of the program:
Grounding. The space of possible solutions is fully expanded.
Solving. The unmatching solutions are filtered out according to the defined constraints.
Graph Coloring
This is a classical combinatorial problem where the nodes in a graph are colored by keeping in consideration that the color of a node must be different from the color of the adjacent ones. The input graph contains the nodes, the edges and the given colors:
In the grounding phase all possible permutations of assignment color/node:
val p = new FactBuilder()
p.color(X, Y).^(1) :- (p.node(X), p.col(Y)),
In here the atom “color” is generated for each node and each color present in the knowledge base. Given that a node is assigned one and only one color, we create all possible permutations and we specify (with the operation ^(1)) that in each solution the field in the argument (1) is unique. The FactBuilder is an helper tool for writing atoms in a more convenient way than in the previous example.
The solver part will drop out all solutions on which two adjacent nodes have the same color:
If you have already played Chess, you know that the Queen is the most powerful piece on the chessboard, and losing it is usually the preamble of a defeat. In this puzzle, the problem is to find all dispositions of N Queens in a N*N chessboard, on which any Queen can’t attack none of the others. The ASP program will generate all permutations of Queens in the chessboard, and it filter out all configurations on which:
Two or more Queens are in the same row.
Two or more Queens are in the same column.
Two or more Queens are in the same diagonal.
How to check whether two pieces are in diagonal? They lay in the same diagonal when the difference of X axis is the same as the (absolute) difference of the Y axis. Following the data and program:
val N = 6
val facts = new FactBuilder
facts.row(1 to N)
facts.col(1 to N)
val arguments = Args(
(("queen" :: X :: Y :: e) $$ (N)) :- ("row" :: X :: e, "col" :: Y :: e),
:-("queen" :: X :: Y :: e, "queen" :: X :: Z :: e, Y <> Z),
:-("queen" :: X :: Y :: e, "queen" :: Z :: Y :: e, X <> Z),
:-("queen" :: X :: Y :: e, "queen" :: W :: Z :: e, !((X === W) && (Y === Z)), (X - W).abs === (Y - Z).abs),
)
arguments.deduct(facts)
Sudoku
val f = new FactBuilder
f.x(1 to 9)
f.y(1 to 9)
f.n(1 to 9)
val p = new FactBuilder
val arguments = Args(
p.cell(X, Y, Z).^(1, 2) :- (p.x(X), p.y(Y), p.n(Z)),
p.subgrid(X, Y, A, B) :- (p.x(X), p.x(A), p.y(Y), p.y(B), (X - 1) / 3 === (A - 1) / 3, (Y - 1) / 3 === (B - 1) / 3),
:-(p.cell(X, Y, Z), p.cell(W, Y, Z), X <> W),
:-(p.cell(X, Y, Z), p.cell(X, W, Z), Y <> W),
:-(p.cell(X, Y, Z), p.cell(A, B, Z), p.subgrid(X, Y, A, B), X <> A, Y <> B)
)
Unfortunately I can’t show you any results out of this program. In this puzzle the limits of such an explorative ASP engine are obvious. The space of solutions is prohibitive for the simple grounding algorithm I employed. Anyway, the efficiency and effectiveness of the tool are not the point of this article. Instead, I invite you to run an equivalent program on Clingo. It takes something like a second the resolved matrixes, how can it be? Well, thanks to lazy-grounding, Conflict-Driven solvers, some giant leaps have been done even in the field of logic programming. The evolution of such algorithms is attributable to academic research. They are publicly accessible and there are no constraints on their implementation in commercial systems.
Shortest Path
In the shortest path, the problem is to find a way between two connected nodes in a graph and whether there are more than one path, select the ones with minimum cost. The data should contain the “start” and “end” nodes, and the edges, the connections between different nodes. The atoms “edge” define the points and the weight of such a connection. The program is:
val shortestPath = SModels(Args(
p.path(X, Y, W) :-(p.start(X), p.edge(X, Y, W)),
p.path(X, Z, A + B) :- (p.path(X, Y, A), p.edge(Y, Z, B)),
p.shortest(W) :- (p.end(Y), p.path(X, Y, W), not p.path(X, Y, Z), W < Z),
))
shortestPath.deduct(facts)
This is an example of recursivity in ASP. The SModels wrapper is intended to return stable models since the “path” atom is generated for all connected edges, and the number of iterations depends on the distance degree of the nodes (e.g. Munich and Tokyo are certainly connected through roads, but the degree of distance between them is high).
I think it is interesting to note the last argument, which is intended to enlight the minimum cost:
p.shortest(W) :- (p.end(Y), p.path(X, Y, W), not p.path(X, Y, Z), W < Z)
Here it is like to say:
“W is the minimum cost if there is no evidence that there exists a lesser one”
Is it like the prime numbers proof?
Giancarlo Frison is Technology Strategist at SAP Customer Experience Labs
