Answer Set Programming(ASP)

ASP is a declarative programming method emphasizing on what to be computed rather than how to compute.

alternate text

< Formulas as rules and satisfying assignments as answer sets. Source: Aalto AI [1] >

Theory

Answer sets

  1. The set is closed under the rules of the program.
  2. If some particular atom belongs to the set, then there is at least one supporting rule instance having the atom in question as its head and the body of the rule is satisfied by the set. In other words, atoms cannot be true without a reason.
  3. The set is minimal in this sense. In other words, atoms are false by default.

Positive programs

A positive rule is is an expression of the form

\[a \leftarrow b_1, \cdots ,b_n\]

where the head atom \(a\) can be inferred if the body atoms \(b_1, \cdots ,b_n\) have been inferred by other rules in the program. A rule with an empty body (\(n=0\)) is called a fact.

Definition The (unique) answer set of a positive program is the least set \(S\) of ground atoms which is closed under the ground instances of its rules:

  1. If there is a ground instance \(h(t)\leftarrow b_1(t_1) \cdots b_n(t_n)\) of some rule in the program such that \(b_1(t_1)\in S, \ldots, b_n(t_n)\in S\), then also \(h(t) \in S\)
  2. If some other set \(S'\subseteq S\) is closed in this way, then \(S' = S\)

ASP tutorial

Graph coloring [1]

n-Queen problem [2]

Basic

Advanced

The above code is much faster than the basic one but it will still take much time on solving due to :- { queen(I,J) : D = I+J-1 } >= 2, D=1,..2*n-1.. It is an exhaustive calculation. Let’s be more efficient.


References

[1](1, 2) https://www.youtube.com/watch?v=kdcd7Je2glc
[2]https://www.youtube.com/watch?v=d3arlJlGRTk&feature=youtu.be