From eager to lazy constrained data acquisition: A general framework

^*1 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. This paper is an extended and revised version of the paper presented at IJCAI’99 (Stockholm, August 1999)⁴⁾. Paola Mello, Ph.D.: She received her degree in Electronic Engineering from University of Bologna, Italy, in 1982 and her Ph.D. degree in Computer Science in 1989. Since 1994 she is full Professor. She is enrolled, at present, at the Faculty of Engineering of the University of Bologna where she teaches Artificial Intelligence. Her research activity focuses around: programming languages, with particular reference to logic languages and their extensions towards modular and object-oriented programming; artificial intelligence; knowledge representation; expert systems. Her research has covered implementation, application and theoretical aspects and is presented in several national and international publications. She took part to several national (Progetti Finalizzati e MURST) and international (UE) research projects in the context of computational logic. Michela Milano, Ph.D.: She is a Researcher in the Department of Electronics, Computer Science and Systems at the University of Bologna. From the same University she obtained her master degree in 1994 and her Ph.D. in 1998. In 1999 she had a post-doc position at the University of Ferrara. Her research focuses on Artificial Intelligence, Constraint Satisfaction and Constraint Programming. In particular, she worked on using and extending the constraint-based paradigm for solving real-life problems such as scheduling, routing, object recognition and planning. She has served on the program committees of several international conferences in the area of Constraint Satisfaction and Programming, and she has served as referee in several related international journals. Marco Gavanelli: He is currently a Ph.D. Student in the Department of Engineering at the University of Ferrara, Italy. He graduated in Computer Science Engineering in 1998 at the University of Bologna, Italy. His research interest include Artificial Intelligence, Constraint Logic Programming, Constraint Satisfaction and visual recognition. He is a member of ALP (the Association for Logic Programming) and AI^*IA (the Italian Association for Artificial Intelligence). Evelina Lamma, Ph.D.: She got her degree in Electrical Engineering at the University of Bologna in 1985, and her Ph.D. in Computer Science in 1990. Her research activity centers on logic programming languages, Artificial Intelligence and software engineering. She was co-organizers of the 3rd International Workshop on Extensions of Logic Programming ELP92, held in Bologna in February 1992, and of the 6th Italian Congress on Artificial Intelligence, held in Bologna in September 1999. She is a member of the Executive Committee of the Italian Association for Artificial Intelligence (AI^*IA). Currently, she is Full Professor at the University of Ferrara, where she teaches Artificial Intelligence and Fondations of Computer Science. Massimo Piccardi, Ph.D.: He graduated in electronic engineering at the University of Bologna, Italy, in 1991, where he received a Ph.D. in computer science and computer engineering in 1995. He currently an assistant professor of computer science with the Faculty of Engineering at the University of Ferrara, Italy, where he teaches courses on computer architecture and microprocessor systems. Massimo Piccardi participated in several research projects in the area of computer vision and pattern recognition. His research interests include architectures, algorithms and benchmarks for computer vision and pattern recognition. He is author of more than forty papers on international scientific journals and conference proceedings. Dr. Piccardi is a member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter. Rita Cucchiara, Ph.D.: She is an associate professor of computer science at the Faculty of Engineering at the University of Modena and Reggio Emilia, Italy, where she teaches courses on computer architecture and computer vision. She graduated in electronic engineering at the University of Bologna, Italy, in 1989 and she received a Ph.D. in electronic engineering and computer science from the same university in 1993. From 1993 to 1998 she been an assistant professor of computer science with the University of Ferrara, Italy. She participated in many research projects, including a SIMD parallel system for vision in the context of an Italian advanced research program in robotics, funded by CNR (the Italian National Research Council). Her research interests include architecture and algorithms for computer vision and multimedia systems. She is author of several papers on scientific journals and conference proceedings. She is member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter.