From eager to lazy constrained data acquisition: A general framework

(*1) Constraint Satisfaction Problems (CSPs)(17)) are an effective framewor k for modeling a variety of real life applications and many techniques have been proposed for solving them efficiently. CSPs are based on the assumpti on that all constrained data (values in variable domains) are available at the beginning of the computation. However, many non-toy problems derive the ir parameters from an external environment. Data retrieval can be a hard ta sk, because data can come from a third-party system that has to convert inf ormation encoded with signals (derived from sensors) into symbolic informat ion (exploitable by a CSP solver). Also, data can be provided by the user o r have to be queried to a database. For this purpose, we introduce an extension of the widely used CSP model, c alled Interactive Constraint Satisfaction Problem (ICSP) model. The variabl e domain values can be acquired when needed during the resolution process b y means of Interactive Constraints, which retrieve (possibly consistent) in formation. A general framework for constraint propagation algorithms is pro posed which is parametric in the number of acquisitions performed at each s tep. Experimental results show the effectiveness of the proposed approach. Some applications which can benefit from the proposed solution are also dis cussed.