[Oz] Filtering of values of constraint variables

[Raphael Collet]

Benko Tamas wrote:
> I'm from the Prolog world, and I'm interested in solving constraint
> problems.  There is a technique called filtering which I use quite often,
> but I don't see how I could implement it in Mozart.
> 
> Filtering is used in (or before) the labeling phase and it means that
> before committing to a possible value we try to exclude values by
> tentatively instantiating it to a value and watching if it fails.
> 
> In Prolog it looks like this: (...)
> 
> This kind of filtering is useful if the constraint system is unable infer
> that X can't have the value V, but it can detect the inconsistency if X is
> instantiated to V.
> 
> In Mozart the constraint posting and the search phases are nicely
> separated, and I don't know to which phase filtering belongs.

As far as I know, Mozart does not provide a filtering facility which is
equivalent to Prolog's.  IMHO the two main reasons are: there is no
backtracking, and propagators must be considered as "user threads".

The backtracking mechanism is replaced by injecting the speculative
computation in a computation space, waiting for stability and watching
the space status (succeeded or failed).  The basic constraints are
simply added to the constraint store, while nonbasic constraints are
implemented by propagators, which behave like user threads.

It is possible to filter a space S with respect to a value V by creating
a clone of S (say S'), injecting something like "proc {$ X} X=V end" in
S' and then watching the status of S'.  However, it does not speedup the
search, as it mimics a very primitive distribution strategy.  Though it
can be used to "interactively" try to exclude values from a space.  This
is how I implemented a digital assistant for a minesweeper game (it will
be soon in the distribution of Mozart.)

The cost of backtracking in Prolog appears in Mozart as the cost of
cloning spaces.  Christian Schulte showed that it is not prohibitive
w.r.t. trailing-based techniques.

> Another (completely unrelated) question: is it possible to program
> constraint propagators in Mozart without using the C++ interface?  For
> prototyping purposes it would be fast enough for me.

You can use reified constraints for this.  See the Finite Domain
Constraint Programming Tutorial and the doc of module FD.  But be
careful, I just found bugs in it...

--
Raphaël Collet
raph at info.ucl.ac.be
-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.