Proceedings

Qualitative Spatial and Temporal Reasoning: Efficient Algorithms for Everyone

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 526-530.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

In the past years a lot of research effort has been put into finding tractable subsets of spatial and temporal calculi. It has been shown empirically that large tractable subsets of these calculi not only provide efficient algorithms for reasoning problems that can be expressed with relations contained in the tractable subsets, but also surprisingly efficient solutions to the general, NP-hard reasoning problems of the full calculi. An important step in this direction was the refinement algorithm which provides a heuristic for proving tractability of given subsets of relations. In this paper we extend the refinement algorithm and present a procedure which identifies large tractable subsets of spatial and temporal calculi automatically without any manual intervention and without the need for additional NP-hardness proofs. While we can only guarantee tractability of the resulting sets, our experiments show that for RCC8 and the Interval Algebra, our procedure automatically identifies all maximal tractable subsets. Using our procedure, other researchers and practitioners can automatically develop efficient reasoning algorithms for their spatial or temporal calculi without any theoretical knowledge about how to formally analyse these calculi.

  1. Algorithm: FIND-TRACTABILITY-CANDIDATES (F-T-C) Input: A set of tractable relations T and a set of supposedly NP-hard relations H. (Note: cl = closure) Output: Candidates for tractable subsets CS i ⊆ 2 B 1. L ← ∅ (set of incompatible pairs); n ← 0; max ← 1
  2. for all T a , T b ∈ T do 3. if cl({{T a }, {T b }} ∪ B) ∩H = ∅ then L ← L ∪ T a , T b 4. ∀r, s ∈ 2 B : M [r][s] ← true if r = s and false if r = s
  3. cand ← B; newcand ← B 6. while (true) do 7. nextrels ← ∅; newrel ← ∅; n++
  4. for all T j ∈ T with T j ∈ cand do 9. if there is an R ∈ cand such that T j , R ∈ L 10. then nextrels ← nextrels ∪{T j }; continue;
  5. if newcand ∩H = ∅ then
  6. nextrels ← nextrels ∪{T j }; continue;
  7. if C-S-R(T j , cand, M ) = fail then 15. cand ← newcand 16. else nextrels ← nextrels ∪{T j };
  8. CS n ← cand 18. newrel is any relation in (nextrels \ i CS i ) 19. if newrel = ∅ then
  9. cand ← cl(B∪ newrel); newcand ← cand; max++ 21. while max = n do
  10. T k , T j ∈ T is a pair s.t. T k , T j ∈ L 23. and {T k , T j } is not contained in any CS i 24. if there is no such pair then return all CS i
  11. cand ← cl(B ∪ {T j }); newcand ← cl(cand ∪{T k })
  12. if C-S-R(T k , cand, M ) = fail then 27. L ← L ∪ T k , T j ; continue 28. cand ← newcand; max++ References [Allen, 1983]
  13. J. F. Allen. Maintaining knowledge about temporal intervals. Comm. ACM, 26(11):832-843, Nov 1983.
  14. [Ladkin and Maddux, 1988] P. Ladkin and R. Maddux. On binary constraint networks. Technical Report, Kestrel Institute, 1988.
  15. [Ligozat and Renz, 2004] G. Ligozat and J. Renz. What is a qualita- tive calculus? a general framework. In PRICAI'04, 53-64, 2004.
  16. [Nebel and Bürckert, 1995] B. Nebel and H-J. Bürckert. Reason- ing about temporal relations: A maximal tractable subclass of Allen's interval algebra. J.ACM, 42(1):43-66, Jan 1995.
  17. [Nebel, 1997] B. Nebel. Solving hard qualitative temporal reason- ing problems: Evaluating the efficiency of using the ORD-Horn class. CONSTRAINTS, 3(1):175-190, 1997.
  18. [Randell et al., 1992] D. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In KR'92, 165-176, 1992.
  19. [Renz and Ligozat, 2005] J. Renz and G. Ligozat. Weak com- position for qualitative spatial and temporal reasoning. In Proc. CP'05, 534-548, 2005.
  20. [Renz and Nebel, 2001] J. Renz and B. Nebel. Efficient methods for qualitative spatial reasoning. JAIR, 15:289-318, 2001.
  21. [Renz, 1999] J. Renz. Maximal tractable fragments of the Region Connection Calculus: A complete analysis. In Proc. IJCAI'99, 448-454, 1999. IJCAI

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

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