Dynamic arc consistency for CSPs

Article type: Research Article

Authors: Mouhoub, Malek

Affiliations: University of Regina, Wascana Parkway, Regina, SK, S4S 0A2, Canada. Tel.: +1 306 585 4700; Fax: +1 306 585 4745; E-mail: mouhoubm@cs.uregina.ca

Abstract: Constraint Satisfaction Problems (CSPs) are fundamental in many real world applications such as interpreting a visual image, laying out a silicon chip, frequency assignment, scheduling, planning and molecular biology. A main challenge when designing a CSP-based system is the ability to deal with constraints in a dynamic and evolutive environment. We talk then about on line CSP-based systems capable of reacting, in an efficient way, to any new external information during the constraint resolution process. During the conceptual phase of design, for example, the designers should be able to add/remove constraints at any time after specifying an initial statement describing the desired properties of a required artifact. We propose in this paper a new algorithm capable of dealing with dynamic constraints at the arc consistency level of the resolution process. More precisely, we present a new dynamic arc consistency algorithm that has a better compromise, in practice, between time and space than those algorithms proposed in the literature, in addition to the simplicity of its implementation. Experimental tests on randomly generated CSPs as well as on CSPs involving temporal constraints (that we call TCSPs), have been conducted. The results of the experimentation demonstrate the efficiency, in time and space costs, of our algorithm to deal with large size CSPs in a dynamic environment.

Keywords: Constraint satisfaction, temporal reasoning, dynamic arc consistency

DOI: 10.3233/JAD-2009-0173

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 13, no. 2, pp. 45-58, 2009