Here I will go over the main reasons for using ASP, syntax, and best practices. Feel free to check my github repo for working examples (if this is useful to you, consider dropping a star). All the specific syntax I use is from clingo.
What problem does an ASP solve?
ASP is, as the wiki page states, a good approach to solving NP-hard problems where we want to establish a search space and let a solver find a solution without having to design an algorithm (but keeping some explainability). In a more practical way, we write programs that are lists of rules; then we let a solver find solution/s that satisfy all rules.
What does it mean to satisfy all rules?
All rules are in the shape head :- body which roughly translates to the logic statement head <- body, which is a logical equivalence to head or not(body). To satisfy all rules is then equivalent to find a set of variables such that for each rule either the head is true, or the body is false .
If you come from Prolog this is extremely familiar; the advantage being that ASP can deal with circular dependency loops.
Syntax
Let’s go over practical, concise explanations on semantics:
head <- rule.- head is part of a solution if rule is part of a solution
head <-.- head is part of a solution (always)
<- rule.- rule cannot be part of the solution
{head }<- rule.- head is (or not) a part of a solution if rule is a part of a solution
head <- {rule1;rule2}.- head is a part of a solution if rule1 OR rule2 is a part of a solution
{head1;head2} <- rule.- head1 or head2 are a part of a solution if rule is a part of a solution. We can read the
;as an OR. L{head1;head2;head3}U <- rule.- [L,U] heads are a part of a solution if rule is a part of a solution
Syntax extension with variables
L{var_head_1(A,B):var(B);var_head_2(A,C):var(C)}U <- var_body(A).- for every var_body(A) we guessi a total of [L,U] (summing var_head_1 and var_head_2) are a part of a solution. Each
var_head_1(A,B)needs there to be a correspondingvar(B)(and the same applies to(var_head_2(A,C)andvar(C)). We can read the:as “such that”.
Debugging ASP problems
General methodology
It is just good practice to use the methodology officially recomended. The approach suggested is called generate (rules with {} on the head) and test (rules of the shape :-body). Generate refers to the fact that, in the simplest of cases {a}., the solver will clone every pre-existing solution that didn’t have a and add a to it (if a had not been referenced, duplicating the solutions).
I will add to this methodology that implications head :- body by themselves only extend the current solution by sometimes deducing some variables. If we had 3 solutions prior to an implication, we will keep the same solutions with some more variables on them.
Common pitfalls
I want to create the pairs of different numbers between 1 and 2. I have num(1).num(2).
- Wrong solution
pair(A,B):- num(A),num(B). - Correct solution
pair(A,B):- num(A),num(B),A!=B. - Reason: The body
num(A),num(B)will be generated for EVERY possible combination of A and B. If the body wasnum(A),num(A)we have forced the variable substitution to be the same, but when using difference variables we have to manually enforce it.
I am getting too many incorrect solutions
- That is the easiest thing to solve; when you run
clingoyou can check which invalid solutions appear, and looking at your program you should be able to infer which constraints (:-body.) have to be more restrictive or new ones to add.
Now I am getting an UNSAT
- UNSAT have to be caused by constraints. What you can do is add a head
error("error text")as a head of a:-bodyconstraint. Next you can add (probably at the end of the program) a constraint of the shape:-error(_).. To identify which constraint is too restrictive, you can test commenting the headerror("error text")of the particular error you are testing. If a constraint is filtering all your solutions; it is too restrictive or you were not generating enough solutions.
Let me create this relation that uses 6+ terms and expresses perfectly all the constraints of the problem
- Wrong solution: using long rules in general.
- Correct solution: split into smaller implications and relations
- Reason: #1 it becomes very difficult to identify what exact part of the rule is the one that is breaking. #2 there are rarely relations with so many prerequisites. #3 heads are generated according to the combinations of bodies they have. You are greatly increasing the complexity of the problem.
My program never finishes
- You probably have an incremental loop with no ceiling in a rule like this:
var(I+1):-var(I)(or the increment involves several rules). A quick test of who is at fault is to add a reasonable cap (100 iterations should be instantaneous) and see if it terminates.
Efficiency tricks
Generally speaking, the easiest way to increase efficiency is to generate less possible variables. Lets use an example from the github on robots.
A specific (but very common) example:
Robots doing some tasks in a map represented by edges edge(Node1,Node2). There is also a time T.
- Robots on a map can move to somewhere adjacent.
- Inefficient solution:
{at(R,N2,T+1)}=1:-at(R,N1,T)} ,time(T+1).% a robot will be exactly at one place at a time
:- at(R,N2,T+1),at(R,N1,T),edge(N1,N2) . % no teleporting
- Efficient solution
{at(R,N2,T): edge(N1,N2);at(R,N1,T)}=1 :- at(R,N1,T-1),time(T).% a robot will exactly be at one adjactent place at a time
- Reason: The inefficient solution HAS to generate every possible combination (Robot,Node,Time) which grows cubicly with the problem. The efficient version allows only to generate the adjacent variables.
- These robots have to do a series of tasks in a certain order.
- Inefficient version
can_be_done(J,O,T2):- %operation O of job J can be done at T2
operation(J,O-1,_),%the previous operation exists
done(J,O-1,T1),time(T2),T1<T2.% previos was finished before
- Efficient version
done(J,O,T) :- done(J,O,T-1),time(T).
can_be_done(J,O,T2):- %operation O of job J can be done at T2
operation(J,O-1,_),%the previous operation exists
done(J,O-1,T2-1).% previos was finished before
- Reason: The inefficient version has to check every combination T1,T2; this is very inefficient as bit T values happen. In the efficient version, we generate a lot more “superfluous”
done(_,_,_)statements; however that reduces the dimensionality ofcan_be_done.
Donation
Monero 49va5kaQ8qzQjfNpTjURwiFR9Zh1uQQsT5cbnnur2NUsfzCbU1QQ2tG3PhdeapEGFTLuGMcx46ss6grJTKKFfP8EC1ePk9M
