Constraint Propagation and Value Acquisition: Why We Should Do It Interactively

Abstract

In Constraint Satisfaction Problems #CSPs# values belonging to variable domains should be completely known before the constraint propagation process starts. In many applications, however, the acquisition of domain values is a computational expensive process or some domain values could not be available at the beginning of the computation. For this purpose, we introduce an Interactive Constraint Satisfaction Problem #ICSP# model as extension of the widely used CSP model. The variable domain values can be acquired when needed during the resolution process by means of Interactive Constraints, which retrieve #possibly consistent # information. Experimental results on randomly generated CSPs and for 3D object recognition show the e#ectiveness of the proposed approach. 1 Introduction The Constraint Satisfaction Problem #CSP# formalization has been widely used within Arti#cial Intelligence and related areas. A CSP is de#ned on a #nite set of variables each ranging on a #nite...