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<n.
cspvar(paint_beg(I),0,mv) :- step(I), I<n.
cspvar(paint_end(I),0,mv) :- step(I), I<n.

required(paint_beg(I)<=paint_end(I)) :- step(I), I<n.

% paint_beg/paint_end=0 means no paint action occurs
required(paint_beg(I)=0 -> paint_end(I)=0) :- step(I), I<n.

% if no paint action occurs, there is no point in choosing a color
required(paint_beg(I)=0 -> paint_color(I)=0) :- step(I), I<n.

% colors: white->0; 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), I<n.

required((paint_beg(I)>S \/ paint_end(I)<S) ->
		color_at(S,I2)=color_at(S,I)) :-
	square(S), I2=I+1,
	step(I), I<n.

% red at position 2
required(color_at(2,N)==1) :- N=n.
% blue everywhere else
required(color_at(S,N)==2) :- square(S), S != 2, N=n.

==============

Date: 12 July 2011
From: Marcello Balduccini
To: Vladimir Lifschitz

Below is another -- very different -- encoding for the problem you
described. This encoding is written in "pure" ASP (I sometimes use the term
pure ASP to distinguish it from hybrid languages such as ASP+CP), in the
dialect of gringo/clasp.
This is a more rigorous attempt at ensuring that the size of the grounding
does not depend on the length of the tape. As a result, the grounding of
this encoding is completely independent of the length of the tape.

In this encoding, I tried to capture the commonsensical reasoning that I use
when solving such a problem in my head. In particular it appears to me that,
at least at first, humans will typically not think about every single square
on the tape, but that they will rather think of the tape as a whole, and of
the squares that are relevant to the problem. (Of course they will also be
ready to switch to a different representation if they need to, which is
something this encoding does not do!)

The resulting encoding (1) allows for the specification of goals regarding
which squares (or the whole tape) should be painted in which colors; (2)
makes it possible to query for the color of a square (or of the whole tape);
(3) allows one to define and reason about compound, hierarchically-organized
areas of the tape (e.g. the block consisting of the first 10 squares, or the
area consisting of the first 3 and last 5 squares).

===

#const mv=100.
#const n=2.

step(0..n).
% No need for a domain predicate for squares.
%square(1..mv).

% OBJECTS: areas (tape + squares of interest)
%
%  We use a hierarchical representation of the tape
%  in which object "tape" represents the whole tape,
%  and the "square" objects represent the squares.
%  During painting, colors are assigned according to
%  a specificity principle, which says that painting
%  an area A causes all the areas that are part of A
%  to be painted in the same color as well.
%
%  Only squares relevant to the problem instance are
%  considered, so that for example if the goal is 
%  to paint the tape in one color and square 2 in
%  another, then only objects "tape" and "sq(2)" are
%  used in the encoding.
% 

% The whole tape is an area.
area(tape).
% Every "square of interest" (or relevant square) is an area.
% The notion of square of interest is defined below.
area(S) :- square_of_interest(S).

% Every square area is part of the tape.
part_of(sq(S),tape) :-
	area(sq(S)).

color(red).
color(white).
color(blue).

% ACTIONS:
%   paint(A,C): paint area A in color C
%
% NOTE:
%  Although the agent is not allowed to
%  perform concurrent actions, in our model
%  the action of painting an area A triggers
%  the painting of the areas that are part of A.
%  These triggered actions occur concurrently.
%  To prevent the agent from performing concurrent
%  actions but to allow the occurrence of
%  concurrent triggered actions, we use relation
%  hpd(A,I) to denote the fact that action A happened
%  because it was performed by the agent, and
%  relation o(A,I) to denote the fact that action A
%  simply occurred -- possibly as a triggered action.
%

% *Impossibility condition*
% One cannot decide to paint an area in the
% color that it already has.
% NOTE: the agent is not allowed to do that,
% but it is ok for a triggered action to
% paint an area in the color it already has.
% For this reason, here we use hpd(_,_)
% instead of o(_,_).
% It may be better to move this constraint to
% planning module below.
:- hpd(paint(A,C),I),
   h(color(A,C),I),
   area(A), color(C), step(I).

% *Triggered actions*
%
% When the agent decides to perform an action,
% that action gets triggered.
%
o(paint(A,C),I) :-
	area(A), color(C),
	step(I),
	hpd(paint(A,C),I).

% If an area A is painted in a color, then
% every area that is part of A is painted
% in the same color.
o(paint(A2,C),I) :-
	step(I), color(C),
	area(A1), area(A2),
	part_of(A2,A1),
	o(paint(A1,C),I).

% *Dynamic Law*
% Painting area A in color C causes
% A to assume that color.
h(color(A,C),I+1) :-
	step(I), I<n,
	color(C),
	area(A),
	o(paint(A,C),I).

% *State Constraint*
% Each area can only have one color
% at a time.
-h(color(A,C2),I) :-
	step(I), area(A),
	color(C1), color(C2),
	h(color(A,C1),I),
	C1 != C2.

% *Inertia*
% (Instantiated to fluent color
% for simplicity.)
h(color(A,C),I+1) :-
	step(I), I<n,
	area(A),
	color(C),
	h(color(A,C),I),
	not -h(color(A,C),I+1).

%
% DEFINITION OF SQUARE OF INTEREST
%
% If a goal specifies the color of a (valid) square,
% then that square is a square of interest.
square_of_interest(sq(N)) :-
	color(C),
	goal(color(sq(N),C)),
	N >= 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), I<n.

% *Goal check*
%
% First we propagate the goals specified in
% the problem instance to the various areas
% of the tape. This is done according to
% a specificity principle, which says that,
% if a goal is to have area A in color C,
% then all the areas that are part of A
% should be in the same color, unless
% a more specific goal is specified.
%
% The propagation of goals is done by
% means of a separate relation area_goal(A,C),
% which intuitively says that the goal color
% for area A is C.
%
%
% If a goal is explicitly specified, for an area,
% then that is the goal for that area.
area_goal(A,C) :-
	area(A), color(C),
	goal(color(A,C)).

% Recursion: if the goal color for area A1 is C,
% then by default every area A2 that is part of A1
% has goal color C.
area_goal(A2,C) :-
	area(A1), area(A2),
	color(C),
	area_goal(A1,C),
	part_of(A2,A1),
	not -area_goal(A2,C).

% Each area can only have one goal color.
-area_goal(A,C2) :-
	area(A),
	color(C1), color(C2),
	area_goal(A,C1),
	C1 != C2.

% The goal for area A has not been achieved at step I
% if the color of A at step I is not the goal color.
-goal_achieved(A,I) :-
	step(I),
	area(A),
	area_goal(A,C),
	-h(color(A,C),I).

% The overall goal has not been achieved at step I
% if the goal of at least one area has not been achieved.
-goal_achieved(I) :-
	step(I), area(A),
	-goal_achieved(A,I).

% The overall goal has been achieved at step I
% if there is no reason to believe that it has not
% been achieved.
goal_achieved(I) :-
	step(I),
	not -goal_achieved(I).

% The overall goal must be achieved by the time horizon.
:- -goal_achieved(n).


% ******** QUERY-ANSWERING MODULE ********

% The answer to a query about the color of
% area A at the end of the execution of the
% plan is the color of A, regardless of
% the color of the areas that are part of A.
% NOTE:
% Disregarding the color of the areas that
% are part of A may be a bit too simplistic
% in case most of A is divided in parts
% with different colors. In that case it
% may be better to answer "unknown" unless
% all the parts of A are in the same color.
% The corresponding changes to the rules do
% not seem major.
answer(color(A),C) :-
	color(C),
	query(color(A)),
	h(color(A,C),n).

% It was possible to determine the
% answer to the query.
answered(color(A)) :-
	color(C),
	query(color(A)),
	answer(color(A),C).

% Otherwise, the answer to the query is "unknown".
answer(color(A),unknown) :-
	query(color(A)),
	not answered(color(A)).

% ******** PROBLEM INSTANCE ********

% Initial situation: all areas are white
h(color(A,white),0) :-
	area(A).

% Goal: square 2 must be red
goal(color(sq(2),red)).
% Goal: blue everywhere else
goal(color(tape,blue)).

% Example queries: what is the color of square 5? Of square 101? Of square
0?
query(color(sq(5))).
query(color(sq(101))).
query(color(sq(0))).


#hide.
#show h(_,_).
#show hpd(_,_).
#show goal_achieved(_).
#show answer(_,_).

==============

Date: 13 July 2011
From: Joohyung Lee
To: TAG

Here is another encoding in the language of clingcon by Yunsong Meng
and me, which looks close to the original encoding by Vladimir, except
for some changes that we use constraint variables as arguments of paint
actions. This significantly reduces the number of ground atoms, though
the grounding time grows linearly to the size of input. Here are some
outputs of clingcon vs. clingo on the new encoding vs. the original
encoding by Vladimir.


$ clingcon -c tape=100 tape-coloring-clingcon 2
Answer: 1
paint(s1(0),s2(0),c(0)) paint(s1(1),s2(1),c(1)) c(0)=3 s1(0)=1 s2(0)=100
c(1)=2 s1(1)=2 s2(1)=2

Models      : 1
Time        : 0.020
$ clingcon -c tape=1000 tape-coloring-clingcon 2
Answer: 1
paint(s1(0),s2(0),c(0)) paint(s1(1),s2(1),c(1)) c(0)=3 s1(0)=1 s2(0)=1000
c(1)=2 s1(1)=2 s2(1)=2

Models      : 1
Time        : 0.420
$ clingcon -c tape=10000 tape-coloring-clingcon 2
Answer: 1
paint(s1(0),s2(0),c(0)) paint(s1(1),s2(1),c(1)) c(0)=3 s1(0)=1 s2(0)=10000
c(1)=2 s1(1)=2 s2(1)=2

Models      : 1
Time        : 6.450

------

$ clingo -c tape=100 tape-coloring 2
Answer: 1
paint(1,100,blue,0) paint(2,2,red,1)
SATISFIABLE

Models      : 1
Time        : 12.160
  Prepare   : 2.710
  Prepro.   : 0.400
  Solving   : 9.050
clingcon$ clingo -c tape=1000 tape-coloring 2

ERROR: std::bad_alloc

=================

Here is the program in clingcon.

===================

%% tape-coloring-clingcon


#const n=2.                       % length of plan

square(1..tape).
#domain square(S).

% constraint domain
$domain(1..tape).

%col(white;red;blue).
col(1;2;3).

#domain col(C).
#domain col(C1).

% effect of painting
color(S,C,I+1) :- paint(s1(I),s2(I),c(I)), s1(I)$<=S, S$<=s2(I), C$==c(I),
                  I=0..n-1.

% uniqueness of color
-color(S,C,I) :- color(S,C1,I), C1!=C.

% 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(I),s2(I),c(I))} 1 :-I=0..n-1.

% initial conditions
color(S,1,0).

% goal

:- not color(2,2,n).
:- not color(S,3,n), S!=2.

#hide.
#show paint/3.

========

Some observation:

We would have liked to encode color as a function like Marcello did,
something like

----
color(S,I+1)$==c(I) :- paint(s1(I),s2(I),c(I)), s1(I)$<=S, S$<=s2(I),
                  I=0..n-1.

% commonsense law of inertia
color(S,I+1)$==C :- color(S,I)$==C, not -(color(S,I+1)$==C), I=0..n.
----

However, this does not work according to the semantics of clingcon
language. The same issue would be present in ezcsp. Instead,
Marcello's program uses some trick to encode the inertia by explicit
effects.

----
required((paint_beg(I)>S \/ paint_end(I)<S) ->
               color_at(S,I2)=color_at(S,I)) :-
       square(S), I2=I+1,
       step(I), I<n.
----

The price to pay for would be non-elaboration tolerance. If we introduce
another action that affects the coloring, then the inertia rule above
should be changed accordingly.

================

Date: 14 July 2011
From: Vladimir Lifschitz
To: Marcello Balduccini, Joohyung Lee, and Yunsong Meng

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:

1. Change the color of the squares in segment [A1,B1] to C1.
2. Change the color of the squares in segment [A2,B2] to C2.

Questions about the relationship between the color of a square X before
and after the execution of these actions can be expressed by Boolean
combinations of inequalities that involve the variables A1,B1,A2,B2,X.
This is what constraint solvers do quickly no matter how large the coefficients
are, isn't that right?  Why do we need grounding at all?

The record of this discussion is posted at http://www.cs.utexas.edu/tag/tape_coloring.

================

Date: 15 July 2011
From: Vladimir Lifschitz
To: Roland Kaminski and Marcello Balduccini

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."

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!

===============

Date: 18 July 2011
From: Max Ostrowski
To: TAG

The encoding using

paint_at_step(I)


seems to me much clearer than the encoding using

paint(s1(I),s2(I),c(I))


but it does not make a difference.

> >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<n.
action(paint(A,C)) :- area(A), color(C). (*)

If re-writing the original choice rule is not desirable or possible, one can
still "fix" the encoding by avoiding (*) and by blocking the original choice
rule with a constraint:
    :- hpd(paint(A,C),I), area(A), color(C), step(I).

Of course with this extension the grounding is no longer independent of the
length of the tape, BUT the use of a cr-rule allows the solver to use the
length-independent encoding first, and the length-dependent rules only if no
solution can be found otherwise.


===============

Date: 19 July 2011
From: Max Ostrowski
To: Vladimir Lifschitz

> 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.