Dealing with incomplete knowledge on CLP(FD) variable domains

ABSTRACT

Constraint Logic Programming languages on Finite Domains, CLP(FD), provide a declarative framework for Artificial Intelligence problems. However, in many real life cases, domains are not known and must be acquired or computed. In systems that interact with the outer world, domain elements synthesize information on the environment, they are not all known at the beginning of the computation, and must be retrieved through an expensive acquisition process.In this article, we extend the CLP(FD) language by combining it with a new sort (called Incrementally specified Sets, I-Set). In the resulting language, CLP(FD + I-Set), FD variables can be defined on partially or fully unknown domains (I-Set). Domains can be linked each other through relations, and constraints can be imposed on them. We describe a propagation algorithm (called Known Arc Consistency (KAC)) based on known domain elements, and theoretically compare it with arc-consistency.The language can be implemented on top of different CLP systems, thus letting the user exploit different possible semantics for domains (e.g., lists, sets or streams). We state the specifications that the employed system should provide, and we show that two different CLP systems (Conjunto and {log}) can be effectively used.We provide motivating examples and describe promising applications.

REFERENCES

• 1: Aggoun, A., Chan, D., Dufresne, P., Falvey, E., Grant, H., Harvey, W., Herold, A., Macartney, G., Meier, M., Miller, D., Mudambi, S., Novello, S., Perez, B., van Rossum, E., Schimpf, J., Shen, K., Tsahageas, P. A., and de Villeneuve, D. H. 2001. ECLiPSe User Manual, Release 5.2. IC-Parc, Imperial College, London, UK.
• 2: Marco Alberti , Marco Gavanelli , Evelina Lamma , Paola Mello , Michela Milano, A CHR-based implementation of known arc-consistency, Theory and Practice of Logic Programming, v.5 n.4-5, p.419-440, July 2005 [doi>10.1017/S147106840500236X]
• 3: Franz Baader , Klaus U. Schulz, Combination of constraint solvers for free and quasi-free structures, Theoretical Computer Science, v.192 n.1, p.107-161, Feb. 10, 1998 [doi>10.1016/S0304-3975(97)00147-3]
• 4: Franz Baader , Klaus U. Schulz, Combining constraint solving, Constraints in computational logics: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2001
• 5: Rosy Barruffi , Evelina Lamma , Paola Mello , Michela Milano, Least Commitment on Variable Binding in Presence of Incomplete Knowledge, Proceedings of the 5th European Conference on Planning: Recent Advances in AI Planning, p.159-171, September 08-10, 1999
• 6: Christian Bessière, Arc-consistency and arc-consistency again, Artificial Intelligence, v.65 n.1, p.179-190, Jan. 1994 [doi>10.1016/0004-3702(94)90041-8]
• 7: Christian Bessière , Eugene C. Freuder , Jean-Charles Régin, Using constraint metaknowledge to reduce arc consistency computation, Artificial Intelligence, v.107 n.1, p.125-148, Jan. 1999 [doi>10.1016/S0004-3702(98)00105-2]
• 8: Codognet, P. and Diaz, D. 1996. Compiling constraints in clp(FD). J. Logic Prog. 27, 3 (June), 185--226.
• 9: Jacques Cohen , Pascal Koiran , Catherine Perrin, Meta-level interpretation of CLP(Lists), Constraint logic programming: selected research, MIT Press, Cambridge, MA, 1993
• 10: Evelina Lamma , Paola Mello , Michela Milano , Rita Cucchiara , Marco Gavanelli , Massimo Piccardi, Constraint Propagation and Value Acquisition: Why we should do it Interactively, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.468-477, July 31-August 06, 1999
• 11: Cucchiara, R., Gavanelli, M., Lamma, E., Mello, P., Milano, M., and Piccardi, M. 1999b. Extending CLP(FD) with interactive data acquisition for 3D visual object recognition. In Proceedings of the 1st International Conference on the Practical Application of Constraint Technologies and Logic Programming. Practical Application Company, London, U.K., 137--155.
• 12: Paola Mello , Michela Milano , Marco Gavanelli , Evelina Lamma , Massimo Piccardi , Rita Cucchiara, From eager to lazy constrained data acquisition: a general framework, New Generation Computing, v.19 n.4, p.339-367, January 2001 [doi>10.1007/BF03037573]
• 13: Dechter, R. and Dechter, A. 1988. Belief maintenance in dynamic constraint networks. In Proceedings of the 7th National Conference on Artificial Intelligence (St. Paul, Minn.), T. M. Smith and Reid G. Mitchell, Eds., Morgan-Kaufmann, San Francisco, Calif., 37--42.
• 14: Dent, M. and Mercer, R. 1994. Minimal forward checking. In Proceedings of the 6th International Conference on Tools with Artificial Intelligence (ICTAI '94) (New Orleans, La). IEEE Computer Society Press, Los Alamitos, Calif., 432--438.
• 15: Dincbas, M., Hentenryck, P. V., Simonis, H., Aggoun, A., Graf, T., and Berthier, F. 1988. The constraint logic programming language CHIP. In Proceedings of the International Conference on 5th Generation Computer System, I. for New Generation Computer Technology (ICOT), Ed. OHMSHA Ltd. Tokyo and Springer-Verlag, Tokyo, Japan, 693--702.
• 16: Dovier, A., Omodeo, E., Pontelli, E., and Rossi, G. 1996. {log}: A language for programming in logic with finite sets. J. Logic Prog. 28, 1 (July), 1--44.
• 17: Agostino Dovier , Carla Piazza , Enrico Pontelli , Gianfranco Rossi, Sets and constraint logic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.861-931, Sept. 2000 [doi>10.1145/365151.365169]
• 18: Agostino Dovier , Gianfranco Rossi, Embedding extensional finite sets in CLP, Proceedings of the 1993 international symposium on Logic programming, p.540-556, December 1993, Vancouver, British Columbia, Canada
• 19: E. Freuder, In pursuit of the holy grail, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242304]
• 20: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• 21: Gervet, C. 1997. Propagation to reason about sets: Definition and implementation of a practical language. Constraints 1, 3, 191--244.
• 22: Pascal Van Hentenryck , Yves Deville , Choh-Man Teng, A generic arc-consistency algorithm and its specializations, Artificial Intelligence, v.57 n.2-3, p.291-321, Oct. 1992 [doi>10.1016/0004-3702(92)90020-X]
• 23: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 24: Jaffar, J. and Maher, M. 1994. Constraint logic programming: A survey. J. Logic Prog. 19--20, 503--582.
• 25: Jaffar, J., Maher, M., Marriott, K., and Stuckey, P. 1998. The semantics of constraint logic programs. J. Logic Prog. 37, 1--3 (Oct.), 1--46.
• 26: Craig A. Knoblock , Steven Minton , José Luis Ambite , Maria Muslea , Jean Oh , Martin Frank, Mixed-initiative, multi-source information assistants, Proceedings of the 10th international conference on World Wide Web, p.697-707, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372185]
• 27: Legeard, B. and Legros, E. 1991. Short overview of the CLPS system. In Proceedings of the 3rd International Symposium on Programming Language Implementation and Logic Programming (PLILP91) (Passau, Germany), J. Maluszyński and M. Wirsing, Eds. Lecture Notes in Computer Science, vol. 528. Springer-Verlag, New York, 431--433.
• 28: Mackworth, A. 1977. Consistency in networks of relations. Artif. Intel. 8, 1 (Feb.), 99--118.
• 29: Daniel Mailharro, A classification and constraint-based framework for configuration, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.12 n.4, p.383-397, September 1998 [doi>10.1017/S0890060498124101]
• 30: Mittal, S. and Falkenhainer, B. 1990. Dynamic constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence. AAAI Press/The MIT Press, Boston, Mass., 25--32.
• 31: Roger Mohr , Thomas C. Henderson, Arc and path consistence revisited, Artificial Intelligence, v.28 n.2, p.225-233, March 1986 [doi>10.1016/0004-3702(86)90083-4]
• 32: Montanari, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7, 2 (Apr.), 95--132.
• 33: Schiex, T., Régin, J., Gaspin, C., and Verfaillie, G. 1996. Lazy arc consistency. In Proceedings of the 13th National Conference on Artificial Intelligence and the 8th Innovative Applications of Artificial Intelligence Conference (AAAI 96) (Menlo Park, N.J.). Vol. 1. AAAI Press/The MIT Press, Cambridge, Mass., 216--221.
• 34: Schiex, T. and Verfaillie, G. 1993. Nogood recording for static and dynamic constraint satisfaction problems. In Proceedings of the 5th International Conference on Tools with Artificial Intelligence. IEEE Computer Society Press, Los Alamitos, Calif., 48--55.
• 35: Sergot, M. J. 1983. A query-the-user facility for logic programming. In Integrated Interactive Computing Systems, P. Degano and E. Sandewall, Eds. North-Holland, Amsterdam, The Netherlands, 27--41.
• 36: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• 37: Waltz, D. 1975. Generating Semantic Descriptions from Drawings of Scenes with Shadows. In The Psychology of Computer Vision, P. Winston, Ed. McGraw-Hill, New York, Chap. 3.
• 38: Zweben, M. and Eskey, M. 1989. Constraint satisfaction with delayed evaluation. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (Detroit, Mich.), N. S. Sridharan, Ed. Morgan-Kaufmann, San Francisco, Calif., 875--880.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics; Syntax

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
Constraints, domain acquisition, interaction, lazy evaluation, sets, streams