Proceedings

Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 854-858.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.Weiming Liu, Li Sanjiang, Renz Jochen

  1. [Allen, 1983] J.F. Allen. Maintaining knowledge about tem- poral intervals. C. ACM, 26:832-843, 1983.
  2. [Balbiani et al., 1999] P. Balbiani, J.-F. Condotta, and L. Fariñas del Cerro. A new tractable subclass of the rect- angle algebra. In IJCAI-99, pages 442-447, 1999. IJCAI
  3. [Cohn and Renz, 2007] A.G. Cohn and J. Renz. Qualitative spatial reasoning. In Frank van Harmelen, Vladimir Lifs- chitz, and Bruce Porter, editors, Handbook of Knowledge Representation. Elsevier, 2007.
  4. [Gerevini and Renz, 2002] A. Gerevini and J. Renz. Com- bining topological and size information for spatial reason- ing. Artificial Intelligence, 137(1-2):1-42, 2002.
  5. [Goyal and Egenhofer, 2001] R. Goyal and M.J. Egenhofer. Similarity of cardinal directions. In SSTD, pages 36-58, 2001.
  6. [Li, 2006] S. Li. On topological consistency and realization. Constraints, 11(1):31-51, 2006.
  7. [Li, 2007] S. Li. Combining topological and directional in- formation for spatial reasoning. In M.M. Veloso, editor, IJCAI, pages 435-440, 2007. IJCAI
  8. [Randell et al., 1992] D.A. Randell, Z. Cui, and A.G. Cohn. A spatial logic based on regions and connection. In KR-92, pages 165-176, 1992.
  9. [Skiadopoulos and Koubarakis, 2005] S. Skiadopoulos and M. Koubarakis. On the consistency of cardinal direction constraints. Artificial Intelligence, 163(1):91-135, 2005.
  10. [Zhang et al., 2008] X. Zhang, W. Liu, S. Li, and M. Ying. Reasoning with cardinal directions: An efficient algo- rithm. In D. Fox and C.P. Gomes, editors, AAAI, pages 387-392. AAAI Press, 2008.

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

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