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. CONSTRAINT PROPAGATION

4.1. PROPAGATING CHANGES

A key innovation behind constraint programming is constraint propagation. Propagation is a generalization of data-driven computation. Consider the constraint x = y + 1, where x and y are variables. In a constraint program, any assignment to the variable y (e.g., y = 5) causes an assignment to x (x = 6). Moreover, the very same constraint also works in the other direction: any assignment to x (e.g., x = 3) causes an assignment to y (y = 2).

In a graphical application, constraint propagation can be used to maintain constraints between graphical objects when they are moved. For example, if one object is constrained to appear on top of another object, and the end-user then moves one of the objects sideways, the other object will move with it as a result of constraint propagation.

In general, each object may be involved in many constraints. Consequently, the assignment of a new position to a given object as a result of propagation, may propagate further new assignments to other objects, which may cause further propagation in turn. If each constraint between two objects is represented as an edge in a graph, the propagation spreads through the connected components of the graph.

When a particular object is assigned a new position, and the change is propagated from the object to other objects, there is a causal direction. In this case, we can assign a direction with each edge of the (connected component of) the graph. As long as the graph is free of cycles, the propagation behavior is guaranteed to terminate, and produce the same final state irrespective of the order in which constraints are propagated. Efficient algorithms, such as the DeltaBlue algorithm, have been developed for propagation of graphical constraints. They work by firstly generating the directed graph whenever an object is moved, and then compiling this directed graph into highly efficient event-driven code.

However, if the graph contains cycles, both these issues arise. Consider, as a simple example, the three constraints C1, C2, and C3 specified thus -- C1: x = y + 1, C2: y = z + 1 and C3: z = x + 1 (see Figure 2).

Assigning y = 3 may start a nonterminating sequence of propagations cycling through the constraints C1 (which yields x = 4), then C3 (which yields z = 5), then C2 (which yields y = 6), and then C1 again and so on. Alternatively, the same assignment y = 3 could propagate through C2 yielding z = 2, thence x = 1 and y = 0 via C3 and C1. In this case, the propagation also goes on for ever, but this time the values of the variables decrease on each cycle! Third, the same assignment y = 3 could yield z = 5 via C1 and C3, and z = 2 via C2!

In this example, the original constraints are, logically, inconsistent. However, similar behavior can occur when the constraints are consistent. In the following example there are constraints on three variables. C4: x + y = z, C5: x - y = z. Suppose the initial (consistent) assignments are x = 2, y = 0, z = 2. Now a new assignment is made to z: z = 3. If constraint propagation on C4 yields y = 1, then propagation on C5 yields x = 4. Now propagation on C4 and C5 can continue forever, alternately updating y and x.

Propagation algorithms have been developed that can deal with cycles, but if the class of admissible constraints is too general, it is not possible to guarantee that the propagation is confluent and terminating.


FIGURE 2 An example constraint graph.

4.2. ACTIVE CONSTRAINTS

4.2.1. Propagating New Information

The changes propagated by label propagation, as discussed in the previous section, are variable assignments as held in a traditional program store. However, in this section we explore the application of constraint propagation to constraint stores, which maintain partial information about the program variables expressed as primitive constraints. Using a constraint store, it is possible to develop a quite different model of computation in which the store is never destructively changed by propagation, but only augmented. One great advantage of this combination is that confluence properties are easy to establish, and consequently there is little need for the programmer or applications designer to know in what order the propagation steps take place.

4.2.2. Constraint Agents

We have encountered two very different kinds of constraints. Primitive constraints are held in a constraint store, and tested for consistency by a constraint solver. On the other hand, propagation constraints actively propagate new information, and they operate independently of each other. Propagation constraints are more commonly called constraint agents. The behavior of a constraint agent is to propagate information to the underlying store. In case the underlying store is a constraint store, the information propagated is expressed as primitive constraints.

Constraint agents are processes that involve a fixed set of variables. During their lifetime they alternate between suspended and waking states. They are woken from suspension when an extra primitive constraint on one or more of their variables is recorded. Sometimes, after checking certain conditions, the woken agent simply suspends again. Otherwise, the agent exhibits some active behavior that may result in new agents being spawned, new primitive constraints being added to the store, or an inconsistency being detected (which is equivalent to an inconsistent constraint being added to the store). Subsequently, the agent either suspends again, or exits, according to its specification.


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.