Author(s)

A. Bellicha

Abstract

Maintenance of solution in a dynamic constraint satisfaction problem A. Bellicha LIRMM, 161 rue ADA, 34392 Montpellier Cedex 5, France ABSTRACT Constraint Satisfaction Problems (CSP) have been shown to be a useful way of formulating problems such as design, scene labelling and temporal rea- soning. As many problems using constraints need a dynamic environment, the static framework of CSPs extend into DCSP (Dynamic Constraint Sat- isfaction Problems). Up to now, most papers about DCSPs have dealt with the problem of the existence of a solution and the filtering techniques. The problem of the maintenance of a solution, after the DCSP has evolved, has mainly been approached through re-execution or delay to the computation of the solution. This paper first presents the CSP framework and its dy- namic evolution DCSP, and then assigns bounds to the study of the problem of the maintenance of solution: given an instance of a binary DCSP, a so- lution to it and a new constraint w

Keywords