Previous Up Next

14.4  Programming Basic Behaviours

As an example, we will look at creating constraint versions of the following predicate. It defines a relationship between containers of type 1, 2 or 3, and their capacity: 

capacity(1, N) :- N>=0.0, N=<350.0.
capacity(2, N) :- N>=0.0, N=<180.0.
capacity(3, N) :- N>=0.0, N=<50.0.

This definition gives the intended declarative meaning, but does not behave as a constraint: capacity(3, C) will raise an error, and capacity(Type, 30.5) will generate several solutions nondeterministically. Only calls like capacity(3, 27.1) will act correctly as a test.

14.4.1  Consistency Check

To program the passive consistency check behaviour, we need to wait until both arguments of the predicate are instantiated. This can be achieved by adding an ECLiPSe delay clause: 

delay capacity(T,N) if var(T);var(N).
capacity(1, N) :- N>=0.0, N=<350.0.
capacity(2, N) :- N>=0.0, N=<180.0.
capacity(3, N) :- N>=0.0, N=<50.0.

The delay clause specifies that any call to capacity/2 will delay as long as one of the arguments is a variable. When the variables become instantiated later, execution will be resumed automatically, and the instantiations will be checked for satisfying the constraint.

14.4.2  Forward Checking

For Forward Checking, we will assume that we have interval domain variables, as provided by the ic library (without domain variables, there would not be much interesting propagation to be done).

Here is one implementation of a forward checking version: 

:- lib(ic).
delay capacity(T, N) if var(T), var(N).
capacity(T, N) :- nonvar(N), !,
        N >= 0,
        ( N =< 50.0 -> T :: [1,2,3]
        ; N =< 180.0 -> T :: [1,2]
        ; N =< 350.0 -> T = 1
        ; fail
        ).
capacity(1, N) :- N$>=0.0, N$=<350.0.
capacity(2, N) :- N$>=0.0, N$=<180.0.
capacity(3, N) :- N$>=0.0, N$=<50.0.

Note that the delay clause now only lets goals delay when both arguments are variables. As soon as one is instantiated, the goal wakes up and, depending on which is the instantiated argument, either the first, or one of the last three clauses is executed. Some examples of the behaviour: 

?- capacity(T, C).
There is 1 delayed goal.
Yes (0.00s cpu)

?- capacity(3, C).
C = C{0.0 .. 50.0}
Yes (0.00s cpu)

?- capacity(T, C), C = 100.
T = T{[1, 2]}
C = 100
Yes (0.00s cpu)

A disadvantage of the above implementation is that when the predicate wakes up, it can be either because T was instantiated, or because C was instantiated. An extra check (nonvar(N)) is needed to distinguish the two cases. Alternatively, we could have created two agents (delayed goals), each one specialised for one of these cases: 

capacity(T, N) :-
        capacity_forward(T, N),
        capacity_backward(T, N).

delay capacity_forward(T, _N) if var(T).
capacity_forward(1, N) :- N$>=0.0, N$=<350.0.
capacity_forward(2, N) :- N$>=0.0, N$=<180.0.
capacity_forward(3, N) :- N$>=0.0, N$=<50.0.

delay capacity_backward(_T, N) if var(N).
capacity_backward(T, N) :-
        N >= 0,
        ( N =< 50.0 -> T :: [1,2,3]
        ; N =< 180.0 -> T :: [1,2]
        ; N =< 350.0 -> T = 1
        ; fail
        ).

Unfortunately, there is a drawback to this implementation as well: once one of the two delayed goals has done its work, all the constraint’s information has been incorporated into the remaining variable’s domain. However, the other delayed goal is still waiting, and will eventually wake up when the remaining variable gets instantiated as well, at which time it will then do a redundant check.

The choice between having one or several agents for a constraint is a choice we will face every time we implement a constraint.

Previous Up Next