Incremental propagation

From: Aleksandar Bakic <bakicale_at_cse.msu.edu>
Date: Mon 21 Feb 2000 07:43:00 PM GMT
Message-Id: <200002211943.OAA20264@pacific.cps.msu.edu>
Hi,

I do not know if the following is possible in Prolog or ECLiPSe. I
would like to be able to set some constraints, e.g.,

constraints(Ins, Outs)

where Ins is a list of input variables, and Outs is a list of output
variables (whose values are to be found based on given values of the
Ins variables). Then, instead of instantiating all the Ins variables
at once, I would like to do this incrementaly. Namely, if I
instantiated them all at once, e.g.,

constraints(Ins, Outs),
Ins = [...],
labeling(Outs)

it would take, say, N seconds before labeling(Outs) would start,
because the instantiation of the Ins variables would trigger
constraint propagation. My ECLiPSe program is supposed to run like a
read-eval-print server, in "real time". I am interested in an
incremental approach because I know some values of the Ins variables
at t0, some at t1 (t1 > t0), and so on, the last Ins value at tk (tk >
all the previous t's), and I would like to minimize the time that
passes between tk and the start of labeling(Outs). I almost do not
care about how much time it takes before I instantiate the last
uninstantiated Ins variable (in an arbitrary order).

I have tried a few approaches, both in embedded C++ and normal code,
but am not sure about the correctness of ones that seemed
efficient. It would be great if, with some tricks, I could replace

start
time
     constraints([A,B,C],Outs),
t0   [A,B,C] = [1,2,3],
t0+N labeling(Outs)

with something like

start
time
     constraints([A,B,C],Outs),
     read(A),
t0   read(B),
t1   read(C), % value of C is entered at t2
t2+M labeling(Outs)

where M << N. Without tricks, M = N. In C++, I used a list of
references as Ins, and it seemed that the sum of constraint
propagation times triggered by individual instantiations was equal to
the time it takes to propagate all instantiations at once. However,
references are not the same as logical variables, so I am not sure if
this was correct.

I would greatly appreciate any help.

Aleksandar


From: Aleksandar Bakic <bakicale@cse.msu.edu>
Message-Id: <200002212002.PAA20859@pacific.cps.msu.edu>
Subject: Re: Incremental propagation
Date: Mon, 21 Feb 2000 15:02:45 -0500 (EST)

I would like to add to my previous message, and hopefully make it
clearer. Basically, I want to split the time it takes after

[A,B,C] = [1,2,3]

onto three time intervals that take after read(A), read(B) and
read(C). So, all these constraint propagation times are related, and I
want to minimize the last one. I just do not like the fact that
without tricks, instantiating only one or all Ins variables takes
about the same time, resulting in K-fold slowdown when Ins has K
variables.

> with something like
> 
> start
> time
>      constraints([A,B,C],Outs),
>      read(A),
> t0   read(B),
> t1   read(C), % value of C is entered at t2
> t2+M labeling(Outs)
> 
> where M << N. Without tricks, M = N. In C++, I used a list of
                                     ^
                                 approximately

Aleks
Received on Mon Feb 21 20:15:39 2000

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:05 PM GMT GMT