Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


4.2.3. Some Built-In Constraint Agents

The simplest constraint agent is one which adds a primitive constraint to the constraint store and then exits. The most fundamental example is assigning a value to a variable, e.g., X = 3. This agent adds X = 3 to the constraint store and exits.

The next two examples are disequality constraints, which will be illustrated in the next section. The first disequality constraint is invoked by the syntax X~ = Y. This agent does not do anything until both X and Y have a fixed value. Only when the primitive constraints in the store entail X = valx and Y = valy for some unique values valx and valy, does the agent wake up. Then its behavior is to check that valx is different from valy. In case they are the same, an inconsistency has been detected.


FIGURE 3 A simple map to color.

If the constraint store holds finite domain constraints, then the more powerful constraint agent invoked by the syntax X ## Y can be used. This agent wakes up as soon as either X or Y has a fixed value. It then removes this value from the finite domain of the other variable and exits.

4.3. MAP COLORING

4.3.1. The Map Coloring Program

As a toy example, let us write a program to color a map so that no two neighboring countries have the same color (Figure 3). In constraint logic programs, variables start with a capital letter (e.g., A), and constants with a small letter (e.g., red).

A generic logic program, in Prolog syntax, that tries to find possible ways of coloring this map with only three colors (red, green, and blue) is given in Figure 4.

In this program, the (as yet undefined) predicate ne constrains its arguments to take different values. We will show how different definitions of ne cause the program to behave in different ways.

The predicate chosen can be satisfied in three ways. At runtime the system tries each alternative in turn. If a failure occurs later in the computation, then the alternatives are tried in a last-in, first-out basis.

The first definition of ne uses the original disequality of Prolog:

ne(X,Y) :- X\=Y

If invoked when either of its arguments are uninstantiated variables, X\=Y simply fails. To avoid this incorrect behavior, it is possible to place the constraints after all the choices. In this case, the program correctly detects that there is no possible coloring after checking all 81 alternatives.

A more efficient Prolog program can be written by interleaving choices and constraints, but this requires the programmer to think in terms of the operational behaviour of the program on this particular map. The same effect can be achieved much more cleanly by using the program of Figure4 with a new definition:

colored(A,B,C,D) :-
  ne(A,B), ne(A,C), ne(A,D), ne(B,C), ne(B,D), ne(C,D),
  chosen(A), chosen(B), chosen(C), chosen(D).

chosen(red).
chosen(green).
chosen (blue).

FIGURE 4 A generic logic program for map coloring.

colored(A,B,C,D) :-
  [A,B,C,D]::[red,green,blue],
  ne(A,B), ne(A,C), ne(A,D), ne(B,C), ne(B,D), ne(C,D),
  chosen(A), chosen(B), chosen(C), chosen(D).

ne(X,Y) :- X##Y.

chosen(red). chosen(green). chosen(blue).

FIGURE 5 A finite domain CLP program for map coloring.

ne(X,Y) :- X~=Y

This disequality predicate delays until both arguments have a fixed value. It then immediately wakes up and fails if both values are the same. If the values are different, it succeeds. This program detects that our map cannot be colored with three colors after trying only 33 alternatives.

Another disequality constraint is available in CLP, which assumes its arguments have a finite set of possible values. We can use it by defining

ne(X,Y) :- X##Y

This disequality delays until one of its arguments has a fixed value. This value is then removed from the set of possible values for the other. To obtain the advantage of X##Y, it is necessary to declare the set of possible values for each variable, by writing [A,B,C,D]::[red,green,blue] (Figure 5).

This program detects that the map cannot be colored after trying only 6 alternatives.

Although this example is so trivial that it is quite simple to solve it in Prolog, the CLP program scales up to complex maps and graphs in a way that is impossible using a programming language without constraints.

4.4. BUILDING CONSTRAINT AGENTS

4.4.1. Guards

Constraint agents can be built by directly defining their waking behavior using the notion of a "guard." As an example, we take a resource constraint on two tasks, t1 with duration d1 and t2 with duration d2 forcing them not to overlap. The variable ST1 denotes the start time of t1, and ST2 denotes the start time of t2. Suppose we wish to define the agent constraint agent(ST1,ST2) thus: if the domain constraints on the start time of t1 and t2 prevent t1 from starting after t2 has finished, constrain it to finish before t2 has started.

This behavior can be expressed as follows:

agent(ST_1,ST_2)<==>             % agent name and parameters
        ST_1 #< ST_2+d2 |        % guard
            ST_1+d1 #<= ST_2     % body

The guard will keep the agent suspended until the domains of ST1 and ST2 are reduced to the point that the inequation ST1 [less than or equal to] ST2 + d2 holds for every possible value of ST1 and ST2. When this is true, it wakes up and executes the body, invoking a new agent ST_1+d1 #<= ST_2. Of course, this guard may never become true, in case task t2 runs before task t1. To cope with this alternative, we add another guard and body, yielding the final definition:

agent(ST_1,ST_2) <==>               % agent name and parameters
        ST_1 #< ST_2+d2 |           % guard1
             ST_1+d1 #<= ST_2 ;     % body1
        ST_2 #< ST_1+d2 |           % guard 2
             ST_2+d2 #<= ST_1       % body2

This agent wakes up as soon as either of the guards are satisfied, and executes the relevant body. As soon as one guard is satisfied, the other guard and body are discarded.

4.4.2. Agents Defined by Specific Codes

Constraint programming systems implement their built-in agents using specific codes that wake up, for example, whenever the upper or lower bound of the domain constraint on a given variable is altered.

Using specific codes, it is also possible to build complex constraints and constraint behaviors to obtain good performance on large complex problems. Indeed, this is the approach that has been very successfully applied on job-shop scheduling benchmarks and incorporated into commercial constraint programming tools such as CHIP and ILOG SCHEDULE.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.