Tape Coloring
Date: 26 June Oct 2011
From: Vladimir Lifschitz
To: TAG
Consider the following planning problem. A tape consists of a large
number (say 100) of white squares. In one step, we can paint any
contiguous segment of the tape any given color. The goal is to have
the second square from the left painted red, and the rest of the tape
painted blue. How to do this in 2 steps?
There is obviously one solution: paint the whole tape blue, and then
repaint the second square from the left. The problem can be easily
encoded in ASP, as shown below.
Here is my question: Can we encode this problem in a declarative
language implemented in such a way that grounding will not be required,
so that the solution time will not grow with the length of the tape?
===
% tape coloring in the language of gringo
#const n=2. % length of plan
square(1..100).
#domain square(S).
#domain square(S1).
#domain square(S2).
col(white;red;blue).
#domain col(C).
#domain col(C1).
% effect of painting
color(S,C,I+1) :- paint(S1,S2,C,I), S1<=S, S<=S2, I=0..n-1.
% uniqueness of color
-color(S,C,I) :- color(S,C1,I), C1!=C, I=0..n.
% commonsense law of inertia
color(S,C,I+1) :- color(S,C,I), not -color(S,C,I+1), I=0..n.
% choose actions arbitrarily
{paint(S1,S2,C,I)} 1 :-I=0..n-1.
% no concurrent actions
:- 2 {paint(_,_,_,I)}, I=0..n-1.
% initial conditions
color(S,white,0).
% goal
:- not color(2,red,n).
:- not color(S,blue,n), S!=2.
#hide. #show paint/4.
===
Output of clingo:
Answer: 1
paint(1,100,blue,0) paint(2,2,red,1)
==============
Date: 27 June Oct 2011
From: Roland Kaminski
To: Vladimir Lifschitz
Such problems can be encoded more efficiently by changing the representation.
I switched to intervals in the encoding.
% instance
steps(2).
% interval [x,y)
goal(blue,0,1).
goal(red,1,2).
goal(blue,2,100).
% encoding
color(C) :- goal(C,_,_).
state(white,X,Y,0) :- goal(_,X,Y).
step(1).
step(N+1) :- step(N), not steps(N).
marked(X) :- goal(_,X,_).
marked(X) :- goal(_,_,X).
1 { paint(C,X,Y,N) : color(C) : marked(X;Y) : X <= Y } 1 :- step(N).
painted(C,X,Y,N) :- paint(C,XX,YY,N), goal(_,X,Y), XX <= X, Y <= YY.
painted(X,Y,N) :- painted(_,X,Y,N).
state(C,X,Y,N) :- painted(C,X,Y,N).
state(C,X,Y,N) :- not painted(X,Y,N), state(C,X,Y,N-1), step(N).
:- goal(C,X,Y), not state(C,X,Y,N), steps(N).
#hide.
#show paint/4.
==============
Date: 27 June Oct 2011
From: Vladimir Lifschitz
To: Roland Kaminski
Thank you for sending me the improved representation of the tape coloring
example. I must say though that it does not address my main concern:
solving the problem without grounding, perhaps using ideas of constraint
logic programming. A lot of interesting work on merging ASP with
constraint solving has been done in recent years, and I'm wondering
whether any of that work can be applied to my example.
==============
Date: 12 July 2011
From: Marcello Balduccini
To: Vladimir Lifschitz
Below is an ezcsp encoding of the problem you described. The grounding of
the ezcsp program grows "only" linearly w.r.t. the length of the tape, so,
although better than earlier encodings, strictly speaking it does not
satisfy your requirement that the solution be "implemented in such a way
that grounding will not be required, so that the solution time will not
grow with the length of the tape". (More on this in my next email.) However
this encoding shows how ASP+CP can be effectively used to reduce the size
of the grounding. It is to be noted that the program does not contain any
choice rules: the generation of paint actions (or the determination of
start and end of the segments to be painted, to be more precise) is
performed on the CP side. From this point of view, ASP serves only as a
(very) convenient host language for the encoding of the CP problem. It is
possible to modify the encoding so that the generate part of the program
makes the choices "on the ASP side", e.g. using choice rules, but the
architecture of the ezcsp solver makes such an approach inefficient.
Incidentally, in the rules below, "/\", "\/", and "->" denote,
respectively, conjunction, disjunction and implication between reified
CP constraints.
===
#const mv=100.
#const n=2.
step(0..n).
square(1..mv).
cspvar(paint_color(I),0,2) :- step(I), I paint_end(I)=0) :- step(I), I paint_color(I)=0) :- step(I), I0; red->1; blue->2
cspvar(color_at(S,I),0,2) :- square(S), step(I).
% the color is initially white
required(color_at(S,0)==0) :- square(S).
% NOTE: writing I+1 instead of I2 in the argument
% of required/1 does not work.
%
required((paint_beg(I)<=S /\ paint_end(I)>=S) ->
(color_at(S,I2)=paint_color(I))) :-
square(S), I2=I+1,
step(I), IS \/ paint_end(I)~~
color_at(S,I2)=color_at(S,I)) :-
square(S), I2=I+1,
step(I), I= 1,
N <= mv.
% A square may be of interest for other reasons
% besides being specified in the goal. For
% example squares of interest could be those
% of which we want to know the specific color
% at the end of the execution of the plan.
square_of_interest(sq(N)) :-
query(color(sq(N))),
N >= 1,
N <= mv.
%
% ********* PLANNING MODULE *********
%
% The agent can perform at most one paint
% action at each time step.
0{ hpd(paint(A,C),I) : area(A) : color(C) }1 :- step(I), IS \/ paint_end(I)~~~~
color_at(S,I2)=color_at(S,I)) :-
square(S), I2=I+1,
step(I), I >Thank you for your interesting observations about tape coloring. Your
> >experiments show that ezcsp and cligcon solve the problem faster than
> >"traditional" answer set solvers, but the solution time still grows with
> >the length of the tape.
> >
> >It seems to me that this fact points to an imperfection in the design of
> >the existing CASP solvers, because reasoning about plans of a fixed length
> >in the tape coloring domain is essentially reasoning about a fixed set of
> >linear inequalities. Consider, for instance, a sequence of 2 actions:
I do not think that this is due to the imperfection in the design of the
csp solvers. It is just that the encoding is linear in size.
Consider the rule:
color(S,C,I+1) :- paint_at_step(I), s1(I)$<=S, S$<=s2(I), C$==c(I),
I=0..n-1.
Here the linear size is hidden in the variable S, which is a domain
predicate
square(1..tape).
#domain square(S).
So this rule is grounded "tape" times, resulting in:
color(1,C,1) :- paint_at_step(0), s1(0)$<=1, 1$<=s1(0), C$==c(0).
color(1,C,2) :- paint_at_step(1), s1(1)$<=1, 1$<=s1(1), C$==c(1).
color(2,C,1) :- paint_at_step(0), s1(0)$<=2, 2$<=s1(0), C$==c(0).
color(2,C,2) :- paint_at_step(1), s1(1)$<=2, 2$<=s1(1), C$==c(1).
color(3,C,1) :- paint_at_step(0), s1(0)$<=3, 3$<=s1(0), C$==c(0).
color(3,C,2) :- paint_at_step(1), s1(1)$<=3, 3$<=s1(1), C$==c(1).
color(4,C,1) :- paint_at_step(0), s1(0)$<=4, 4$<=s1(0), C$==c(0).
color(4,C,2) :- paint_at_step(1), s1(1)$<=4, 4$<=s1(1), C$==c(1).
...
color(10000,C,1) :- paint_at_step(0), s1(0)$<=10000, 10000$<=s1(0), C$==c(0).
color(10000,C,2) :- paint_at_step(1), s1(1)$<=10000, 10000$<=s1(1), C$==c(1).
where C={1,2,3}
So this is a linear number of rules. Or better: tape*|colors|*steps
So for all these rules nothing can be unit propagated.
The solver simply has to "choose" one of the constraint literals to be true:
For example
s1(0)$<=5432.
Now the csp solver can propagate a lot of facts, but the solver still has to chose:
5432$<=s1(0).
Then, (choosing again the correct color), the coloring of the tape can begin.
This is very ineffecient!
Please have again a look at the normal ASP encoding by Roland of the problem.
It encodes the problem as described, using only the length of the plan, not the tape size.
Resulting in a runtime independent on the tape length.
$clingo clingo.lp -c tape=10000000 0
Answer: 1
paint(red,1,2,2) paint(blue,0,100,1)
SATISFIABLE
Models : 1
Time : 0.000
Prepare : 0.000
Prepro. : 0.000
Solving : 0.000
Currently i have problems to use clingcon for this problem, as linear
constraints over integer variables do not really help. One would rather
need variables over RANGES of integers, because no "real" integer variables
occur in the problem, as they all need to have values that are "marked" (see
clingo.lp).
===============
Date: 18 July 2011
From: Vladimir Lifschitz
To: Max Ostrowski
> Please have again a look at the normal ASP encoding by Roland of the problem.
> It encodes the problem as described, using only the length of the plan,
> not the tape size.
> Resulting in a runtime independent on the tape length.
>
> $clingo clingo.lp -c tape=10000000 0
What do you mean by "the normal ASP encoding by Roland"? In the version
that Roland sent us on June 27 there is no constant "tape", you are
probably looking at a different solution.
==============
Date: 18 July 2011
From: Marcello Balduccini
To: Vladimir Lifschitz
> I am looking now at your encodings of the tape coloring example that
> make the grounding time independent of the length of the tape. It
> seems
> to me that both solutions are based on the same idea: don't allow
> painting
> segments whose endpoints are "unrelated to the goal."
Actually in my encoding there is no direct relationship between the notion
of square of interest and the goal. The goal is just one of the ways that
squares of interest can be identified. Another source -- as shown in my
encoding -- is that of queries. But the definition of square of interest can
be incrementally extended by adding new rules.
It is also possible to extend the focus to areas of interest (which I should
have probably had in the first place) by defining a relation
area_of_interest and using it a way similar to square_of_interest.
> This is an interesting idea, but it buys efficiency at the cost of
> elaboration tolerance. Let's assume that we are only capable of
> painting
> "short" segments (not longer than a given constant). Then painting
> segments with seemingly irrelevant endpoints will become unavoidable!
This can be easily done in an incremental fashion. There are a few possible
ways of doing it. Here is a straightforward one.
Introduce a new action paint_segment(start,end,color), where start and end
are squares. This action triggers the painting of the corresponding squares:
o(paint(A,C),I) :-
color(C),
step(I),
area(sq(S)), area(sq(E)),
hpd(paint_segment(sq(S),sq(E),C),I),
N=S..E,
A=sq(N).
The segment's length must be within the given maximum:
:- hpd(paint_segment(sq(S),sq(E),C),I),
area(sq(S)), area(sq(E)),
max_segment_len(K),
E-S > K.
Start should be <= end:
:- hpd(paint_segment(sq(S),sq(E),C),I),
area(sq(S)), area(sq(E)),
S > E.
All the squares in the segment must be known areas:
:- hpd(paint_segment(sq(S),sq(E),C),I),
area(sq(S)), area(sq(E)),
N=S..E,
not area(sq(N)).
If strictly necessary -- and only in that case -- allow considering every
square in the tape and allow using the paint_segment action. The notion of
"strictly necessary" is encoded using a consistency-restoring rule of
cr-prolog:
r1: paint_segment_allowed +-.
square_of_interest(sq(N)) :- paint_segment_allowed, N=1..mv.
action(paint_segment(S,E,C)) :-
paint_segment_allowed,
area(S), area(E),
color(C).
To do things properly, re-write the choice rule in the original planning
module as follows:
0{ hpd(Act,I) : action(Act) }1 :- step(I), I What do you mean by "the normal ASP encoding by Roland"? In the version
> that Roland sent us on June 27 there is no constant "tape", you are
> probably looking at a different solution.
Sorry, i recognized that there is no such variable after i send the mail.
There can't be a constant "tape" as the encoding is independent of the
tape length. So the tape can be of any length, that's the only thing i
wanted to say.
~~