Constraint propagation versus local search for incremental temporal constraint problems

Summary form only given. Our aim is to maintain the global consistency of a constraint satisfaction problem involving temporal constraints any time a new constraint is added. This problem is of practical relevance since it is often required to check whether a solution to a CSP continues to be a solution when a new constraint is added and if not, whether a new solution satisfying the old and new constraints can be found. The two methods that we present are respectively a complete search technique based on constraint propagation and an approximation method based on stochastic local search. The goal of both methods is to check whether the existence of a solution is maintained any time a new constraint is added. The approximation method does not guarantee the completeness of the solution provided, but is of interest for those problems where it is impossible or impractical to find a complete solution. This is the case for real time applications where a solution should be returned within a given deadline and over constrained problems where a complete solution does not exist.