Managing Dynamic Temporal Constraint Networks

This paper concerns the specialization of arc-consistency algorithms for constraint satisfaction in the management of quantitative temporal constraint networks. Attention is devoted to the design of algorithms that support an incremental style of building solutions allowing both constraint posting and constraint retraction. In particular, the AC-3 algorithm for constraint propagation, customized to temporal networks without disjunctions, is presented, and the concept of dependency between constraints described. The dependency information is useful to dynamically maintain a trace of the more relevant constraints in a network. The concept of dependency is used to integrate the basic AC-3 algorithm with a sufficient condition for inconsistency detection that speeds up its performance, and to design an effective incremental operator for constraint retraction.