Programming Constraint Propagators

AR is a powerful implementation language for programming constraint propagators [16]. We will show in this chapter how to program constraint propagators for various constraints.

The following set of event patterns are provided for programming constraint propagators:

• generated: when an agent is generated.
• ins(X): When any variable in X is instantiated.
• bound(X): The lower or upper bound of any variable in X is updated. There is no distinction between lower and upper bounds changes.
• dom(X): Some inner element has been excluded from the domain of X.
• dom(X,E): An inner element E has been excluded from the domain of X.
• dom_any(X): Some arbitrary element has been excluded from the domain of X.
• dom_any(X,E): An arbitrary element E has been excluded from the domain of X.

Note that when a variable is instantiated, no bound or dom event is posted. Consider the following example:

p(X),{dom(X,E)} => write(dom(E)).

q(X),{dom_any(X,E)} => write(dom_any(E)).

r(X),{bound(X)} => write(bound).

go:-X :: 1..4, p(X), q(X), r(X), X #\= 2, X #\= 4, X #\= 1.

The query go gives the following outputs: dom(2), dom_any(2), dom_any(4) and bound.^14.1 The outputs dom(2) and dom_any(2) are caused by X #\= 2, and the outputs dom_any(4) and bound are caused by X #\= 4. After the constraint X #\= 1 is posted, X is instantiated to 3, which posts an ins(X) event but not a bound or dom event.

Note also that the dom_any(X,E) event pattern should be used only on small-sized domains. If used on large domains, constraint propagators could be over-flooded with a huge number of dom_any events. For instance, for the propagator q(X) defined in the previous example, the query

      X :: 1..1002, q(X), X #>1000

posts 1000 dom_any events. For this reason, in B-Prolog propagators for handling dom_any($X$,$E$) events are generated only after constraints are preprocessed and the domains of variables in them become small.

Except for dom(X,E) and dom_any(X,E) that have two arguments, all the events do not have extra information to be transmitted to their handlers. An action rule can handle multiple single-parameter events. For example, for the following rule,

      p(X),{generated,ins(X),bound(X)} => q(X).

p(X) is activated when p(X) is generated, when X is instantiated, or when either bound of X's domain is updated.

We also introduce the following two types of conditions that can be used in the guards of rules:

• dvar(X): X is an integer domain variable.
• n_vars_gt(M,N): The number of variables in the last M arguments of the agent is greater than N, where both M and N must be integer constants. Notice that the condition does not take the arguments whose variables are to be counted. The system can always fetch that information from its parent call. This built-in should be used only in guards of action rules or matching clauses. The behavior is unpredictable if this built-in is used elsewhere.