🚀 go-pugleaf

My posting about the Echidna CLP language (and how it relates to
scheduling) generated quite a lot of interest.  To all that asked me
to send them papers, there will be a delay while the proof is made
into a technical report (with covers and everything).  In the
meantime, I thought I should post this extended abstract about
Echidna's numeric constraint processing capabilities.  Enjoy!

-----------------------------------8<--------------------------------------

    Hierarchical Arc Consistency Applied to Numeric Processing in
  Constraint Logic Programming (Extended Abstract, Email Version)(1)
				   
	       Greg Sidebottom and William S. Havens(2)

			   1.  Introduction

There have been many proposals for adding sound implementations of
numeric processing to Prolog.  Many constraint logic programming (CLP)
languages use symbolic constraint solving techniques for linear
constraints.  CHIP and BNR Prolog use consistency and case analysis
algorithms (Mackworth, 1977) for solving constraints.  This paper
describes an approach to real numeric constraint processing which has
been implemented in Echidna, a new CLP language.  Like CHIP and BNR
Prolog, Echidna uses consistency algorithms which can actively process
a wide variety of numeric constraints.  The key difference is that
Echidna implements domains which are disconnected sets using a
hierarchical data structure and exploits this structure using a
hierarchical arc consistency algorithm (Mackworth, Mulder and Havens,
1985) which is specialized for numeric constraints.  The hierarchial
datastructure makes it possible to represent disjunctive information
directly.

Echidna can handle such general systems of constraints because it uses
partial consistency algorithms.  Normally, consistency algorithms
compute solutions to sets of constraints.  Partial consistency
algorithms approximate the set of solutions with a super-set.  Good
partial consistency algorithms compute a super-set which is only
slightly bigger than the actual set of solutions for a substantially
reduced cost.  Echidna's algorithms are easily parameterized to
compute arbitrarily close to the actual set of solutions.

	   2.  Numeric Constraints in the Echidna Language

This section describes the particular extensions to Edinburgh syntax
Prolog which are relevant to numeric constraint processing and takes
some liberties with syntax.  Echidna provides domain constraints,
equalities, inequalities, and disjunctions of inequalities on real
numeric expressions.  A domain constraint is a unary constraint of the
form 'X in Set' where X is a real valued variable and Set denotes the
domain of X.  The Set in a domain constraint is specified by a finite
union of real intervals.  Equalities and inequalities constrain real
numeric expressions.  Expressions are built up from variables and real
constant symbols using numeric function symbols(3).  Echidna also
supports disjunctive inequalities constraints of the form 'C1 or C2'
where C1 and C2 are inequalities.  For instance, Figure 1 gives an
Echidna program for scheduling tasks using some of the relations on
temporal intervals.  A task is represented by a term task(S, D) where
S is the start time of the task and D is the duration of the task.
The predicate, in(Task, SuperTask), is true if the interval for
SuperTask contains the interval for Task.  NoOverlap(Task, Tasks) is
true if Task overlaps with none of the tasks in the list Tasks.  It
uses a disjunctive inequality constraint to make sure Task is either
before or after each of the tasks in Tasks.  Schedule(Tasks,
SuperTask) is true if all the tasks in the list Tasks are in SuperTask
but no pair in Tasks overlap.

  in(task(S1, D1), task(S2, D2)) :-
      S1 >= S2,
      S1+D1 <= S2+D2.

  noOverlap(_, []).
  noOverlap(task(S1, D1),
             [task(S2,D2)|Tasks]):-
      S1+D1<=S2 or S1>=S2+D2,
      noOverlap(task(S1, D1),Tasks).  
  schedule([], _).
  schedule([Task | Tasks], SuperTask) :-
      in(Task, SuperTask), 
      noOverlap(Task, Tasks),
      schedule(Tasks, SuperTask).

	  Figure 1. An Echidna Program for scheduling tasks

	       3.  Overview of Echidna's Implementation

Echidna programs are executed by an SLD-resolution theorem prover
which incrementally constructs and maintains a constraint satisfaction
problem (CSP).  A CSP consists of a set of variables, each associated
with a domain of possible values; and a set of constraint relations on
subsets of the variables which specify values to which those variables
can simultaneously be assigned.  The notation D(X) is used to denote
the domain of the variable X.  When a constraint is selected by the
theorem prover, it is added to the CSP.  Echidna manipulates the CSP
using two kinds of algorithms (Mackworth, 1977):

1.  arc consistency is used to remove inconsistent values from the
domains of variables participating in numeric constraints, and

2.  case analysis is used to consider, alternatively, different halves
of real variable domains.

If the arc consistency algorithm ever removes all values from a
variable domain, the theorem prover backtracks using dependency
backtracking (Havens, 1991).  Backtracking through a constraint
consists of removing it from the CSP.

The case analysis algorithms implement a divide and conquer search for
solutions to the CSP. The arc consistency algorithms are interleaved
with the case analysis algorithms to help reduce the search space.
The case analysis algorithm is accessed by the built in predicate
split(Vars).  Split(Vars) repeatedly cycles through the list Vars of
variables in a round robin fashion removing approximately half the
values in each variable's domain.  Upon backtracking, split will
restore half of a domain and remove the other half.  Currently, the
number of times each variable in a list can be split is determined by
a call to the built in predicate precision(Vars, Prec).

	       4.  Numeric Hierarchical Arc Consistency

This section describes HACR, the hierarchical arc consistency
algorithm Echidna uses for real numeric constraints.  We use the
notation v(C) to denote the set of variables in the constraint C.  We
assume the CSP is formulated as a directed hypergraph where variables
are associated with nodes and each constraint C is a set of hyperarcs
of the form (T, C) for each T in v(C).  T is called the target and the
rest of the variables in v(C) are called sources.  Let C be constraint
with v(C) = {X(1), X(2), I, X(k)}.  The notation pi(X(i),C) means the
result of projecting the constraint C onto the variable Xi.  More
formally,

  pi(X(i),C) =
    {a(i) in D(X(i)) |
         there exists (a(1),...,a(i-1),a(i+1),...,a(k)) in
               D(X(1))x...xD(X(i-1))xD(X(i+1))x...xD(X(k)
                     such that C(a(1),...,a(k))}.  

Full arc consistency algorithms terminate with D(T) = pi(T,C) for
every hyperarc (T, C) which formulates the CSP.  Partial arc
consistency algorithms set D(T) to some efficiently computable
superset of pi(T,C).  HACR is a partial arc consistency algorithm
based on the full hierarchical arc consistency algorithm HAC
(Mackworth, Mulder and Havens, 1985).  Both are similar to AC-3
(Mackworth, 1977), but they use different arc revision algorithms
which operate on hierachically structured domains.  HACR represents a
domain such as [1, 1.875] U [3.75, 4] using the structure shown in
figure 2 (in the hardcopy version of this abstract).  The root's
interval contains the domain and the intervals for the two children of
an node are roughly the lower and upper halves of the their parent's
domain.  The relationship between a parent and its children's is


				[x, y]
				  /\
				 /  \
		      [x,mid(x,y)]  (mid(x,y),y]
				   
where x < mid(x,y) < y.  The types of boundary (open or closed)
associated with x and y in the children are inherited from parent and
one of the boundaries associated with mid(x,y) is open while the other
is closed.  A node is marked 'c', '?', or 'x' if, respectively, all,
some (but not all), or none of the numbers in its interval are in the
domain.  The trees are conceptually infinite but only a finite part
needs to be examined by HACR.  The intervals can be computed using the
path from the root, so no intervals are stored at each node.

	      (in the hardcopy version of this abstract)
	       Figure 2  The domain for a real variable

For a hyperarc (T, C), HACR deletes values outside pi(T,C) by
manipulating the marks in the tree representing D(T).  A set of
intervals whose union is pi(T,C) is generated one at a time and a new
value for D(T) is accumulated by adding an approximation of each
interval to it.  HACR would be a full arc consistency algorithm if the
marks could each D(T) could be set exactly to pi(T,C).  However, with
any a priori splitting strategy, it is possible that an an unbounded
amount of refinement will be required.  Since real domain trees are
infinite, a full arc consistency algorithm using these trees may
require infinite space and may not terminate.  Instead, HACR
associates a non-negative integer precision P(X) with each variable X.
P(X) is the maximum distance from the root to any node in the tree for
D(X) which will be accessed by HACR.  Thus, at any particular point,
HACR can only access a finite part of each domain tree.  The Echidna
built in predicate precision(Vars, P) sets the precision of each
variable in the list Vars to P.  When HACR determines that a node
should be refined, that is its mark should be set to '?' and its
children analyzed, if the node is at the precision limit then its mark
is left 'c'.  For this reason, ReviseHACR is a partial arc revision
algorithm, but it can be made arbitrarily close to a full arc revision
algorithm by increasing the precision of variables.  If the predicate
precision is used to increase the precision of a variable X, then HACR
is reinvoked because it may be possible to refine D(X) and some other
domains.

A set of intervals whose union is pi(T,C) is generated differently for
each class of constraint.  All complex constraints are broken down
into an equivalent set of constraints using at most one numeric
function each using intermediate variables.

For an equality, pi(T,C) is computed by solving C for T.  Then, the
projection is generated by iterating through all the combinations of
intervals marked 'c' in the source domains.  This is done by
traversing the fringe of domain trees and combining adjacent intervals
marked 'c'.  The numeric function used in the constraint is then
applied to each pair of intervals using formulas such as:

    [x1, x2] + [y1, y2] = [x1+y1, x2+y2], 
    [x1, x2] - [y1, y2] = [x1-y2, x2-y1], 
    [x1, x2]*[y1, y2] =
       [min{x1*y1,x1*y2,x2*y1,x2*y2},max{x1*y1,x1*y2,x2*y1,x2*y2}], and
    [x1, x2] / [y1, y2] = [x1, x2]*[1/y2, 1/y1].

Limit values are used where functions are discontinuous (eg. division
by 0).  It is easy to verify that the projection of an inequality of
the form 'T 2 S' is:

    pi(T,C) = [min D(T), max D(S)]  

and other inequality cases are similar.  

For a disjunctive inequality of the form C1 or C2,

pi(T,C1 or C2) =
       -
      | pi(T,C1) U pi(T,C2)  if T in v(C1) and T in v(C2)
     <  D(T)     if T in v(C1) and T notin v(C2) and C2 is satisfiable
      | pi(T,C1) if T in v(C1) and T notin v(C2) and C2 is unsatisfiable
       -

			     5.  Examples

This section contains example runs of Echidna version 1.0 on a Sun
Sparcstation.  Echidna can numerically solve polynomials with varying
precision using the built in predicate precision.  Consider the
following query, where, as described in section 3, precision([X], 8)
sets the precision P(X) of the variable X to 8 bits and the call
split([X]) invokes a case analysis algorithm to search for solutions
for X.

  ?- X in [-1000, 1000), precision([X], 8),
     (X - 1)*(X - 2) = 0, split([X]).

Since Echidna's numeric constraint solving system is incomplete,
Echidna outputs approximate answers but guarantees that all solutions
to the query are present in some answer.  For this query, Echidna
computes the following three answers:

  X in [0, 7.8125)        ; % both solutions here
  X in [7.8125, 15.625)   ;
  X in [15.625, 23.4375)  ;
  no.

More precise approximations of the solution can be obtained by
computing CSPs with smaller domains.  Echidna can be used to do this
by setting P(X) higher.  For instance, if P(X) is set to 32, then the
following CSPs are computed.

  X in [0.9999997, 1.0000002) ;
  X in [1.9999998, 2.0000003) ;
  no.

For an example with disjunctive inequalities, consider the program
given in figure 1 with the query:

  ?- precision([S1, S2], 3), S1 N [0, 4], S2 N [0, 4],
     schedule([task(S1, 2), task(S2, 1.5)], task(0, 4)).

Echidna answers:

  S1 in [0, 0.5] U [1.5, 2], S2 in [0, 0.5] U [2, 2.5]

All other real numeric CLP systems can only implement disjunctive
constraints using explicit disjunction in the logic program.

			      References

Havens, W. S. 1991. Dataflow Dependency Backtracking in a New CLP
Language. In Proc. AAAI Spring Symposium on Constraint-Based
Reasoning. Stanford.  110-127.

Mackworth, A. K. 1977. Consistency in Networks of Relations.
Artificial Intelligence. 8. 99-118.

Mackworth, A. K., Mulder, J. A. and Havens, W. S. 1985. Hierarchical
arc consistency: exploiting structured domains in constraint
satisfaction problems.  Computational Intelligence. 1. 118-126.

			      Footnotes

(1)The full version of this paper appears under the same title as
Centre for Systems Science technical report CSS-IS TR 91-06 and will
appear in Computational Intelligence 8(4), Blackwell Publishers, 1992.

(2)Expert Systems Lab, Centre for Systems Science and School of
Computing Science, Simon Fraser University, Burnaby, British Columbia,
V5A 1S6, Canada.  Email: {gregory,havens}@cs.sfu.ca

(3)Echidna currently supports the arithmetic functions, some
trigonometric functions, exponentiation, logarithm, and root
extraction.
-- 
Greg Sidebottom,                                      | There's not a word that
Expert Systems Laboratory, Centre for Systems Science | goes here that rhymes
Simon Fraser University, Burnaby BC V5A 1S6, Canada   | with anything. -CVB