Abstract
In previous work, a new approach called Open CSP (OCSP) was defined as a way of integrate information gathering and problem solving. Instead of collecting all variable values before CSP resolution starts, OCSP asks for values dynamically as required by the solving process, starting from possibly empty domains. This strategy permits to handle unbounded domains keeping completeness. However, current OCSP algorithms show a poor performance. For instance, the FO-Search algorithm uses a Backtracking and needs to solve the new problem from scratch every time a new value is acquired. In this paper we improve the original algorithm for the OCSP model. Our contribution is two-fold: we incorporate local consistency and we avoid solving subproblems already explored in previous steps. Moreover, these two contributions guarantee the completeness of the algorithm and they do not increase the number of values needed for finding a solution. We provide experimental results than confirm a significant speed-up on the original approach.
Research partially supported by TIN2004-07933-C03-03, TIN2005-09312-C03-01 and TIC2003-00950 funded by the Ministerio de Educación y Ciencia.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Nodine, M., Fowler, J., Ksiezyk, T., Perry, B., Taylor, M., Unruh, A.: Active Information Gathering in InfoSleuth. International Journal of Cooperative Information Systems 9, 3–28 (2000)
Genesereth, M., Keller, R., Duschka, A.M.: Infomaster: An Information Integration System. In: Proceedings of 1997 ACM SIGMOD Conference (May 1997)
Levy, A.Y., Rajaraman, A., Ordille, J.J.: Querying Heterogeneous Information Sources Using Source Descriptions. In: Alon, Y. (ed.) Proceedings of the Twenty-second International Conference on Very Large Databases, VLDB Endowment, Saratoga, Calif., Bombay, India, pp. 251–262 (1996)
Freuder, E.C., Hubbe, P.D.: Extracting Constraint Satisfaction Subproblems. In: IJCAI 1995, pp. 548–557 (1995)
Macho-Gonzalez, S., Meseguer, P.: Open, Interactive and Dynamic CSP. In: Changes 2005 International Workshop on Constraint Solving under Change and Uncertainty (CP 2005) (2005)
Faltings, B., Macho-Gonzalez, S.: Open Constraint Programming. Artificial Intelligence 161, 181–208 (2005)
Wiederhold, G., Genesereth, M.R.: The Conceptual Basis for Mediation Services. IEEE Expert 12(5), 38–47 (1997)
Jiang, Y., Richards, T., Richards, B.: No-good backmarking with min-conflicts repair in constraint satisfaction and optimization. In: Proceedings of Principles and Practice of Constraint Programming, vol. 94, pp. 21–39 (1994)
Schiex, T., Verfaillie, G.: Nogood Recording for Static and Dynamic Constraint Satisfaction Problems. International Journal on Artificial Intelligence Tools 3(2), 187–207 (1994)
Kondrak, G., van Beek, P.: A theoretical evaluation of selected backtracking algorithms. Artificial Intelligence 89, 365–387 (1997)
Haralick, Elliot: Increasing tree search efficiency for constraint-satisfaction problems. Artificial Intelligence 14(3), 263–313 (1980)
Rossi, F., Petrie, C., Dhar, V.: In the equivalence of constraint satisfaction problems. In: Proc. ECAI 1990, pp. 550–556 (1990)
Stergiou, K., Walsh, T.: Encodings of Non-binary Constraint Satisfaction Problems. In: Proceedings of AAAI/IAAI, pp. 163–168 (1999)
Lamma, E., Mello, P., Milano, M., Cucchiara, R., Gavanelli, M., Piccardi, M.: Constraint Propagation and Value Acquisition: Why we should do it Interactively. In: Proceeding of IJCAI 1999, pp. 468–477 (1999)
Schiex, T., Verfaillie, G.: Nogood Recording for Static and Dynamic Constraint Satisfaction Problem. International Journal of Artificial Intelligence Tools 2(3), 187–207 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
González, S.M., Ansótegui, C., Meseguer, P. (2006). Boosting Open CSPs. In: Benhamou, F. (eds) Principles and Practice of Constraint Programming - CP 2006. CP 2006. Lecture Notes in Computer Science, vol 4204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11889205_24
Download citation
DOI: https://doi.org/10.1007/11889205_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46267-5
Online ISBN: 978-3-540-46268-2
eBook Packages: Computer ScienceComputer Science (R0)