From eager to lazy constrained data acquisition: A general framework

Constraint Satisfaction Problems (CSPs) are an effective framework for modeling a variety of real life applications and many techniques have been proposed for solving them efficiently. CSPs are based on the assumption that all constrained data (values in variable domains) are available at the beginning of the computation. However, many non-toy problems derive their parameters from an external environment. Data retrieval can be a hard task, because data can come from a third-party system that has to convert information encoded with signals (derived from sensors) into symbolic information (exploitable by a CSP solver). Also, data can be provided by the user or have to be queried to a database. For this purpose, we introduce an extension of the widely used CSP model, called Interactive Constraint Satisfaction Problem (ICSP) model. The variable domain values can be acquired when needed during the resolution process by means of Interactive Constraints, which retrieve (possibly consistent) information. A general framework for constraint propagation algorithms is proposed which is parametric in the number of acquisitions performed at each step. Experimental results show the effectiveness of the proposed approach. Some applications which can benefit from the proposed solution are also discussed.