[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Relaxation of Qualitative Constraint Networks

  • Conference paper
Abstraction, Reformulation, and Approximation (SARA 2007)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4612))

  • 667 Accesses

Abstract

In this paper, we propose to study the interest of relaxing qualitative constraints networks by using the formalism of discrete Constraint Satisfaction Problem (CSP). This allows us to avoid the introduction of new definitions and properties in the domain of qualitative reasoning. We first propose a general (but incomplete) approach to show the unsatisfiability of qualitative networks, by using a relaxation on any set of relations. Interestingly enough, for some qualitative calculi, the proposed scheme can be extended to determine the satisfiability of any qualitative network, leading to an original, simple and complete method. However, as the efficiency of our approach depends on the chosen relaxation, total relations should be preferred due to their connections with the hardness of constraint networks. We then present some preliminary experimental results, with respect to unsatisfiability, which show some promising improvements on some classes of random qualitative networks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, J.F.: An interval-based representation of temporal knowledge. In: Proceedings of IJCAI 1981, pp. 221–226 (1981)

    Google Scholar 

  2. Allen, J.F.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM 26(11), 832–843 (1983)

    Article  MATH  Google Scholar 

  3. Balbiani, P., Condotta, J.F., Fariñas del Cerro, L.: A model for reasoning about bidimensional temporal relations. In: Proceedings of KR 1998, pp. 124–130 (1998)

    Google Scholar 

  4. Balbiani, P., Osmani, A.: A model for reasoning about topologic relations between cyclic intervals. In: Proceedings of KR 2000, pp. 378–385 (2000)

    Google Scholar 

  5. Bistarelli, S., Codognet, P., Rossi, F.: An abstraction framework for soft constraints and its relationship with constraint propagation. In: Choueiry, B.Y., Walsh, T. (eds.) SARA 2000. LNCS (LNAI), vol. 1864, pp. 71–86. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  6. Bistarelli, S., Codognet, P., Rossi, F.: Abstracting soft constraints: framework, properties, examples. Artificial Intelligence 139, 175–211 (2002)

    Article  MathSciNet  Google Scholar 

  7. Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of ECAI 2004, pp. 146–150 (2004)

    Google Scholar 

  8. Cadoli, M.: Tractable Reasoning in Aritificial Intelligence. LNCS, vol. 941. Springer, Heidelberg (1995)

    Google Scholar 

  9. Caseau, Y.: Abstract interpretation of constraints on order-sorted domains. In: Proceedings of ISLP 1991, pp. 435–452 (1991)

    Google Scholar 

  10. Choueiry, B., Faltings, B., Weigel, R.: Abstraction by interchangeability in resource allocation. In: Proceedings of IJCAI 1995, pp. 1694–1710 (1995)

    Google Scholar 

  11. Choueiry, B., Noubir, G.: On the computation of local interchangeability in discrete constraint satisfaction problems. In: Proceedings of AAAI 1998, pp. 326–333 (1998)

    Google Scholar 

  12. Condotta, J.F., Dalmeida, D., Lecoutre, C., Sais, L.: From qualitative to discrete constraint networks. In: Freksa, C., Kohlhase, M., Schill, K. (eds.) KI 2006. LNCS (LNAI), vol. 4314, pp. 54–64. Springer, Heidelberg (2007)

    Google Scholar 

  13. Condotta, J.F., Ligozat, G., Saade, M.: The QAT: A Qualitative Algebra Toolkit. In: Proceedings of TIME 2006, pp. 69–77 (2006)

    Google Scholar 

  14. Cousot, P., Cousot, R.: Abstract interpretation frameworks. Logic and Computation 2(4), 447–511 (1992)

    MathSciNet  Google Scholar 

  15. Freuder, E., Sabin, D.: Interchangeability supports abstraction and reformulation for constraint satisfaction. In: Proceedings of SARA 1995 (1995)

    Google Scholar 

  16. Giunchiglia, F., Walsh, T.: A theory of abstraction. Artificial Intelligence 56(2-3), 323–390 (1992)

    Article  MathSciNet  Google Scholar 

  17. Gomes, C.P., Selman, B., Crato, N., Kautz, H.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning 24, 67–100 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  18. Hornsby, K., Egenhofer, M.J., Hayes, P.J.: Modeling cyclic change. In: Proceedings of REIS 1999, pp. 98–109 (2006)

    Google Scholar 

  19. Isli, A., Cohn, A.G.: A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence 122(1–2), 137–187 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. Jussien, N.: Relaxation de Contraintes pour les problémes dynamiques. PhD thesis, Universitè de Rennes I (1997)

    Google Scholar 

  21. Jussien, N., Boizumault, P.: Implementing constraint relaxation over finite domains using ATMS. In: Jampel, M., Maher, M.J., Freuder, E.C. (eds.) Over-Constrained Systems. LNCS, vol. 1106, Springer, Heidelberg (1996)

    Google Scholar 

  22. Ligozat, G.: Reasoning about cardinal directions. Journal of Visual Languages and Computing 1(9), 23–44 (1998)

    Article  Google Scholar 

  23. Marriott, K.: Frameworks for abstract interpretation. Acta Informatica 30, 103–129 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  24. Merchez, S., Lecoutre, C., Boussemart, F.: Abstraction de réseaux de contraintes. Revue d’Intelligence Artificielle 20(1), 31–62 (2006)

    Article  Google Scholar 

  25. Nebel, B., Bürckert, H.J.: Reasoning About Temporal Relations: A Maximal Tractable Subclass of Allen’s Interval Algebra. Journal of the ACM 42(1), 43–66 (1995)

    Article  MATH  Google Scholar 

  26. Pham, D.N., Thornton, J., Sattar, A.: Modelling and solving temporal reasoning as propositional satisfiablitly. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 117–131. Springer, Heidelberg (2005)

    Google Scholar 

  27. Pujari, A.K., Kumari, G.V., Sattar, A.: Indu: An interval and duration network. In: Proceedings of the Australian Joint Conference on Artificial Intelligence, pp. 291–303 (1999)

    Google Scholar 

  28. Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Proceedings of KR 1992, pp. 165–176 (1992)

    Google Scholar 

  29. Selman, B., Kautz, H.: Knowledge compilation and theory approximation. Journal of the ACM 43(2), 193–224 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  30. Shrag, R., Miranker, D.: Abstraction and the csp phase transition boundary. In: Proceedings of the 4th International Symposium on Artificial Intelligence and Mathematics, pp. 138–141 (1996)

    Google Scholar 

  31. Yokoo, M.: Constraint relaxation in distributed constraint satisfaction problems. In: Proceedings of ICTAI 2003, pp. 56–63 (1993)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CRIL-CNRS, Université d’Artois, rue de l’Université, 62307 Lens, France

    Dominique D’Almeida, Jean-François Condotta, Christophe Lecoutre & Lakhdar Saïs

Authors
  1. Dominique D’Almeida
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-François Condotta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christophe Lecoutre
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lakhdar Saïs
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Ian Miguel Wheeler Ruml

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

D’Almeida, D., Condotta, JF., Lecoutre, C., Saïs, L. (2007). Relaxation of Qualitative Constraint Networks. In: Miguel, I., Ruml, W. (eds) Abstraction, Reformulation, and Approximation. SARA 2007. Lecture Notes in Computer Science(), vol 4612. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73580-9_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73580-9_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73579-3

  • Online ISBN: 978-3-540-73580-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation