Formalizing Local Propagation in Constraint Maintenance Systems

. Local propagation is one of the most simple and general ways to maintain the consistency of constraint problems. When some variable's values are changed or when new constraints are added, it allows to incre mentally resatisfy a set of constraints by calling local solving methods. This is particularly useful for interactive applications in computer graph ics including geometric design and user interface construction. However, the great weakness of local propagation comes from cycles in the constraint graph so that local propagation is generally viewed as a weak paradigm that should be assisted by more powerful solvers. We claim that local propagation is powerful enough to tackle complex con straint maintenance problems, provided that the solving methods are expressed in a suOEciently general formalism which allows the user to express any solving method in a natural way. Thus, local propagation should be considered the main constraint maintenance engine that can pilot numeric solvers w..