next up previous
Next: Constraint Satisfaction Problems Up: Propagation Previous: Propagation

Early Applications

Constraint propagation was used in 1972 for scene labelling applications, and has produced a long line of local consistency algorithms, recently surveyed in

(Tsang, 1993).

Constraint propagation offers a natural way for a system to spontaneously produce the consequences of a decision. (Propagation is defined in the dictionary as ``dissemination, or diffusion of statements, beliefs, practices''). Propagation is the most important form of immediate feedback for a decision-maker.

Propagation works very effectively in interactive decision support tools. In many applications constraint programming is used in conjunction with other software tools, taking their results as input, performing propagation, and outputting the consequences. Typically feedback from the propagation tool is given in the form of a spreadsheet interface.

Many early applications of constraint programming were related to graphics: geometric layout, user interface toolkits, graphical simulations, and graphical editors. Constraint propagation has played a key role in all these applications, with the result that control over the propagation has been thoroughly investigated: leading to a current generation of very high-performance constraint-based graphics application.

Mark Wallace
Wed Sep 3 18:36:40 BST 1997