More Web Proxy on the site http://driver.im/

article

Open access

Dealing with incomplete knowledge on CLP(FD) variable domains

Authors:

Marco Gavanelli,

Michela MilanoAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 27, Issue 2

Pages 236 - 263

https://doi.org/10.1145/1057387.1057389

Published: 01 March 2005 Publication History

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]

Alberti, M., Gavanelli, M., Lamma, E., Mello, P., and Milano, M. 2005. A CHR-based implementation of known arc-consistency. Theory Prac. Logic Prog. To appear.]]

[3]

Baader, F. and Schulz, K. 1998. Combination of constraint solvers for free and quasi-free structures. Theoret. Comput. Sci. 192, 1 (Feb.), 107--161.]]

[4]

Baader, F. and Schulz, K. 2001. Combining constraint solving. In Constraints in Computational Logics: Theory and Applications, H. Comon, C. Marché, and R. Treinen, Eds. Lecture Notes in Computer Science, vol. 2002. Springer-Verlag, Berlin, Germany, 104--158.]]

[5]

Barruffi, R., Lamma, E., Mello, P., and Milano, M. 1999. Least commitment on variable binding in presence of incomplete knowledge. In Recent Advances in AI Planning, 5th European Conference on Planning, ECP'99 (Durham, UK). S. Biundo and M. Fox, Eds. Lecture Notes in Computer Science, vol. 1809. Springer-Verlag, New York, pp. 159--171.]]

[6]

Bessiére, C. 1994. Arc-consistency and arc-consistency again. Artif. Intel. 65, 1 (Jan.), 179--190.]]

[7]

Bessiére, C., Freuder, E., and Régin, J. 1999. Using constraint metaknowledge to reduce arc consistency computation. Artif. Intel. 107, 1 (Jan.), 125--148.]]

[8]

Codognet, P. and Diaz, D. 1996. Compiling constraints in clp(FD). J. Logic Prog. 27, 3 (June), 185--226.]]

[9]

Cohen, J., Koiran, P., and Perrin, C. 1993. Meta-level interpretation of CLP(lists). In Constraint Logic Programming---Selected Research (Marseilles, France). F. Benhamou and A. Colmerauer, Eds. MIT Press, Cambridge, Mass., 457--481.]]

[10]

Cucchiara, R., Gavanelli, M., Lamma, E., Mello, P., Milano, M., and Piccardi, M. 1999a. Constraint propagation and value acquisition: why we should do it interactively. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (Stockholm, Sweden). T. Dean, Ed. Morgan-Kaufmann, San Francisco, Calif., 468--477.]]

[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]

Cucchiara, R., Gavanelli, M., Lamma, E., Mello, P., Milano, M., and Piccardi, M. 2001. From eager to lazy constrained data acquisition: A general framework. New Generation Computing 19, 4 (Aug.), 339--367.]]

[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]

Dovier, A., Piazza, C., Pontelli, E., and Rossi, G. 2000. Sets and constraint logic programming. ACM Trans. Prog. Lang. Syst. 22, 5 (Sept.), 861--931.]]

[18]

Dovier, A. and Rossi, G. 1993. Embedding extensional finite sets in CLP. In Proceedings of the 1993 International Symposium on Logic Programming (Vancouver, B.C., Canada), D. Miller, Ed. MIT Press, Cambridge, Mass., 540--556.]]

[19]

Freuder, E. 1996. In pursuit of the holy grail. ACM Comput. Surv. 28, 4es (Dec.), 63.]]

[20]

Freuder, E. C. 1982. A sufficient condition for backtrack-free search. J. ACM 29, 1 (Jan.), 24--32.]]

[21]

Gervet, C. 1997. Propagation to reason about sets: Definition and implementation of a practical language. Constraints 1, 3, 191--244.]]

[22]

Hentenryck, P. V., Deville, Y., and Teng, C. 1992. A generic arc-consistency algorithm and its specializations. Artif. Intel. 57, 2--3, 291--321.]]

[23]

Jaffar, J. and Lassez, J. 1987. Constraint logic programming. In Proceedings of the Conference on Principle of Programming Languages (Munich, Germany).]]

[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]

Knoblock, C., Minton, S., Ambite, J., Muslea, M., Oh, J., and Frank, M. 2001. Mixed-initiative, multi-source information assistants. In Proceedings of the 10th International World Wide Web Conference, WWW 10 (Hong Kong, China). ACM, New York, 697--707.]]

[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]

Mailharro, D. 1998. A classification and constraint-based framework for configuration. Artif. Intel. Engineer. Design Analy. Manuf. 12, 04 (Sept.), 383--397.]]

[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]

Mohr, R. and Henderson, T. C. 1986, Arc and path consistency revisited. Artif. Intel. 28, 2 (Mar.), 225--233.]]

[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]

Shapiro, E., Ed. 1987. Concurrent Prolog - Vol. I. MIT Press, Cambridge, Mass.]]

[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.]]

Cited By

MAHER M(2017)Contractibility for open global constraintsTheory and Practice of Logic Programming10.1017/S147106841700012617:04(365-407)Online publication date: 27-Jun-2017
https://doi.org/10.1017/S1471068417000126
Caballero RStuckey PTenorio-Fornés A(2015)Two type extensions for the constraint modeling language MiniZincScience of Computer Programming10.1016/j.scico.2015.04.007111:P1(156-189)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.scico.2015.04.007
Estévez-Martín SCorreas Fernández JSáenz-Pérez F(2012)Extending the TOY system with the ECLPS solver over sets of integersProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_12(120-135)Online publication date: 23-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29822-6_12
Show More Cited By

Index Terms

Dealing with incomplete knowledge on CLP(FD) variable domains

Recommendations

Compiling Semiring-Based Constraints with clp (FD, S)
CP '98: Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming

In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs, weighted CSPs, partial CSPs and others can be easily cast. This framework, based on a semiring structure, allows, ...
The CLP( ℛ ) language and system

The CLP( ℛ ) programming language is defined, its underlying philosophy and programming methodology are discussed, important implementation issues are explored in detail, and finally, a prototype interpreter is described.

CLP( ℛ ) is designed to be an ...
Exploiting Constraints for Domain Managing in CLP(FD)
FroCoS '02: Proceedings of the 4th International Workshop on Frontiers of Combining Systems

Constraint Logic Programming languages on Finite Domains CLP(FD) provide a declarative framework for dealing with problems in Artificial Intelligence (AI). However, in many applications, domains are not known at the beginning of the computation and must ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 27, Issue 2

March 2005

198 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1057387

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2005

Published in TOPLAS Volume 27, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
541
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)10

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

MAHER M(2017)Contractibility for open global constraintsTheory and Practice of Logic Programming10.1017/S147106841700012617:04(365-407)Online publication date: 27-Jun-2017
https://doi.org/10.1017/S1471068417000126
Caballero RStuckey PTenorio-Fornés A(2015)Two type extensions for the constraint modeling language MiniZincScience of Computer Programming10.1016/j.scico.2015.04.007111:P1(156-189)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.scico.2015.04.007
Estévez-Martín SCorreas Fernández JSáenz-Pérez F(2012)Extending the TOY system with the ECLPS solver over sets of integersProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_12(120-135)Online publication date: 23-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29822-6_12
Lallouet ALaw YLee JSiu C(2011)Constraint programming on infinite data streamsProceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One10.5555/2283396.2283494(597-604)Online publication date: 16-Jul-2011
https://dl.acm.org/doi/10.5555/2283396.2283494
Bergenti FChiarabini LRossi G(2011)Programming with partially specified aggregates in JavaComputer Languages, Systems and Structures10.1016/j.cl.2011.07.00237:4(178-192)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.cl.2011.07.002
Gavanelli MRossi F(2010)Constraint logic programmingA 25-year perspective on logic programming10.5555/1880413.1880418(64-86)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1880413.1880418
Gavanelli MRossi F(2010)Constraint Logic ProgrammingA 25-Year Perspective on Logic Programming10.1007/978-3-642-14309-0_4(64-86)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14309-0_4
Bergenti FDal Pal ` ARossi G(2009)Integrating Finite Domain and Set Constraints into a Set-based Constraint LanguageFundamenta Informaticae10.5555/2365156.236515896:3(227-252)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.5555/2365156.2365158
Bergenti FDal Pal ` ARossi G(2009)Integrating Finite Domain and Set Constraints into a Set-based Constraint LanguageFundamenta Informaticae10.5555/1735370.173537296:3(227-252)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.5555/1735370.1735372

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents