Proceedings

On Finding a Solution in Temporal Constraint Satisfaction Problems

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Temporal Reasoning. Pages 1460-1464.

© 1997 International Joint Conferences on Artificial Intelligence

Abstract

Computing a consiste nt int erpretatio n of th e variables involved in a set of temporal constraints is an important task for many areas of AI requiring temporal reasoning. We focus on the important classes of the qualit at ive relations in Nebel and Biirckert's ORD-Horn algebra, and of the metric constraints forming a STP , possibly augmented with in equat ions. For these tractable classes we prese nt three new algorithms for solving the problem of finding a solution, and an efficie nt algorithm for determining the consistency of a STP augmented with inequations.

  1. [Allen, 1983] J. Allen. Maintaining knowledge about tem-poral intervals. Communication of the ACM, 26(1):832-843, 1983.
  2. [Cormen et al., 1990] T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.
  3. [Dechter et al., 1991] R. Dechter, I. Meiri, and J . Pearl. Temporal constraint networks. ATtificial Intelligence, 49:61 -95, 1991.
  4. [Gerevini and Cristani, 1995] A. Gerevini and M. Grist- ani. Reasoning with inequations in temporal con- straint networks. In Proc. of IJCAI-95 Workshop on Spatial and Temporal Reasoning, pp. 13-23, 1995.
  5. [Gerevini and Schubert , 1995] A. Gerevini and L. Schu- bert. Efficient Algorithms for Qualitative Reasoning about Time. Artificial Intelligence 1 74:207-248, 1995.
  6. [Henschen and Wos, 1974] L. Henschen and L. Wos. Unit refutations and Horn sets. Journal of ACM, 21 :590-605, 1974.
  7. [Kautz and Ladkin, 1991] H.A. Kautz and P.B. Ladkin. Integrating metric and qualitative temporal reasoning. In Proc. of AAAI-91. The MIT press, 1991.
  8. [Koubarakis, 1992] M. Koubarakis. Dense time and temporal constraints with =f.. In Proc. of KRf3R'92, pp. 24-35, Cambridge, MA, 1992.
  9. [Koubarakis, 1995] M. Koubarakis. From local to global consistency in temporal constraint networks. In Proc. of the 1st Int. Conf. on Principle and Practice of Con- straint Programming, 1995. Springer Verlag.
  10. [Ladkin and Maddux, 1988] P.B. Ladkin and R. Mad- dux. On binary constraint networks. Technical Report KES.U.88.8 Kestrel Institute, Palo Alto, CA, 1988.
  11. Ligozat, 1996J G. Ligozat. A new proof of the tractabil- ity of ORD-Horn Relations. Proc. of AAAI-96, pp. 395-401. 1996. AAAI Press/The MIT Press
  12. [Montanari, 1974] U. Montanari. Networks of constrain- ts: Fundamental properties and applications to pictu- re processing. InfoTmation Science, 7(3):95-132, 1974.
  13. [Nebel and Biirckert, 1995] B. Nebel and H. J. Biirckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Jour- nal of the ACM 42(1):43-66, 1995.
  14. [van Beek, 1990] P. van Beek. Reasoning about qualita- tive temporal information. In Pmc. of AAAI-90, pp. 728-734, Boston, MA 1990.
  15. Vilain and Kautz, 1986J M. Vilain and H.A. Kautz. Constraint propagation algorithms for temporal rea- soning. In Proc. of AAAI-86, pp. 377-382. 1996.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards