We have shown how the nine tiles in the projection-based model for cardinal directions can be partitioned into sets based on horizontal and vertical constraints (called Horizontal and Vertical Constraints Model) in our previous papers (Kor and Bennett, 2003 and 2010). In order to come up with an expressive hybrid model for direction relations between two-dimensional single-piece regions (without holes), we integrate the well-known RCC-8 model with the above-mentioned model. From this expressive hybrid model, we derive 8 basic binary relations and 13 feasible as well as jointly exhaustive relations for the x- and y-directions, respectively. Based on these basic binary relations, we derive two separate composition tables for both the expressive and weak direction relations. We introduce a formula that can be used for the computation of the composition of expressive and weak direction relations between “whole or part” regions. Lastly, we also show how the expressive hybrid model can be used to make several existential inferences that are not possible for existing models. 1. Introduction Relative positions of regions in large-scale spaces, and particularly in the geographic domain, are often described by relations referring to cardinal directions. These relations specify the direction from one region to another in terms of the familiar compass bearings: north, south, east, and west. The intermediate directions northwest, northeast, southwest, and southeast are also often used. Some models for reasoning with cardinal directions are the cone-shaped [1, 2], projection-based models (ibid), and direction matrix [3–5]. Papadias and Theodoridis [6] describe topological and direction relations between regions using their minimum bounding rectangles (MBRs). However, the language used is not expressive enough to describe direction relations. Additionally, the MBR technique yields erroneous outcome when involving regions that are not rectangular in shape [4] Some work has been done on hybrid direction models. Escrig and Toledo [7] and Clementini et al. [8] integrated qualitative orientation and distance to obtain positional information. Isli [9] combined Frank’s [1, 2] cardinal direction relations model and Freksa’s [10] orientation model to facilitate a more expressive reasoning mechanism. Sharma and Flewelling [11] infer spatial relations from integrated topological and cardinal direction relations. Liu and colleagues [12] have developed reasoning algorithms which combine RCC-8 [13] for topological relations (discussed in Section 4) and the cardinal direction
References
[1]
A. U. Frank, “Qualitative spatial reasoning with cardinal directions,” Journal of Visual Languages and Computing, vol. 3, pp. 343–371, 1992.
[2]
A. U. Frank, “Qualitative spatial reasoning: cardinal directions as an example,” International Journal of Geographic Information Systems, vol. 10, no. 3, pp. 269–290, 1996.
[3]
R. K. Goyal, Similarity assessment for cardinal directions between extended spatial objects [Ph.D. thesis], University of Maine, 2000.
[4]
R. Goyal and M. Egenhofer, “Consistent queries over cardinal directions across different levels of detail,” in Proceedings of the 11th International Workshop on Database and Expert Systems Applications, Greenwich, UK, 2000, A. M. Tjoa, R. Wagner, and A. Al-Zobaidie, Eds., pp. 876–880, IEEE Computer Society, September 2000.
[5]
R. Goyal and M. Egenhofer, “Similarity of cardinal directions,” in Proceedings of the 7th International Symposium on Spatial and Temporal Databases, C. Jensen, M. Schneider, B. Seeger, and V. Tsotras, Eds., vol. 2121 of Lecture Notes in Computer Science, pp. 36–55, Springer, Berlin, Germany, 2001.
[6]
D. Papadias and Y. Theodoridis, “Spatial relations, minimum bounding rectangles, and spatial data structures,” Tech. Rep. KDBSLAB-TR-94-04, University of California, Berkeley, Calif, USA, 1994.
[7]
M. T. Escrig and F. Toledo, “A framework based on CLP extended with CHRS for reasoning with qualitative orientation and positional information,” Journal of Visual Languages & Computing, vol. 9, no. 1, pp. 81–101, 1998.
[8]
E. Clementini, P. Di Felice, and D. Hernández, “Qualitative representation and positional information,” Artificial Intelligence, vol. 95, pp. 315–356, 1997.
[9]
A. Isli, “Combining cardinal direction relations and relative relations in QSR,” in Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics (AI&M), Fort Lauderdale, Fla, USA, January 2004.
[10]
C. C. Freksa, “Using orientation information for qualitative spatial reasoning,” in Proceedings of GIS—From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning, A. U. Frank, I. Campari, and U. Formentini, Eds., Springer, Berlin, Germany, 1992.
[11]
J. Sharma and D. Flewelling, “Inferences from combined knowledge about topology and directions,” in Proceedings of the 4th International Symposium on Advances in Spatial Databses, pp. 271–291, Portland, Me, USA, 1995.
[12]
W. M. Liu, S. J. Li, and J. Renz, “Combining RCC-8 with qualitative direction calculi: algorithms and complexity,” in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), pp. 854–859, Pasadena, Calif, USA, July 2009.
[13]
D. Randell, Z. Cui, and A. G. Cohn, “A spatial logic based on regions and connection,” in Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning, 1992.
[14]
S. J. Li, “Combining topological and directional information for spatial reasoning,” in Proceedings of the 20th International Joint Conference on Artifical Intelligence (IJCAI'07), pp. 435–440, 2007.
[15]
S. J. Li and A. G. Cohn, “Reasoning with topological and directional spatial information,” Computational Intelligence, vol. 28, no. 4, pp. 579–616, 2012.
[16]
P. Balbiani, J. Condotta, and L. F. A. del Cerro, “A Model for reasoning about bidimensional temporal relations,” in Proceedings of the 6th International Conference on Knowledge Representation and Reasoning, 1998.
[17]
P. Balbiani, J. Condotta, and L. F. del Cerro, “A new tractable subclass of the rectangle algebra,” in Proceedings of the 16th International Joint Conference on Artifical Intelligence (IJCAI'99), vol. 1, pp. 442–447, 1999.
[18]
A. G. Cohn, B. Bennett, J. Gooday, and N. M. Gotts, “Qualitative spatial representation and reasoning with the region connection calculus,” GeoInformatica, vol. 1, no. 3, pp. 275–316, 1997.
[19]
J. Sharma, Integrated spatial reasoning in geographic information systems: combining topology and direction [Ph.D. thesis], University of Maine, 1993, http://www.library.umaine.edu/theses/pdf/Sharma.pdf.
[20]
D. Papadias, M. J. Egenhofer, and J. Sharma, “Hierarchical reasoning about direction relations,” in Proceedings of the 4th ACM workshop on Advances on Advances in Geographic Information Systems (GIS'96), ACM-GIS, Rockville, Md, USA, November 1996.
[21]
G. Ligozat, “Reasoning about cardinal directions,” Journal of Visual Languages and Computing, vol. 9, pp. 23–44, 1998.
[22]
M. T. Escrig and F. Toledo, Qualitative Spatial Reasoning: Theory and Practice: Application to Robot Navigation, IOS Press, Amsterdam, The Netherlands, 1998.
[23]
S. Skiadopoulos and M. Koubarakis, “Composing cardinal direction relations,” in Proceedings of the SSTD-01, Redondo Beach, Calif, USA, July 2001.
[24]
S. Skiadopoulos and M. Koubarakis, “Composing cardinal direction relations,” Artificial Intelligence, vol. 152, no. 2, pp. 143–171, 2004.
[25]
B. Bennett, A. Isli, and A. G. Cohn, “When does a composition table provide a complete and tractable proof procedure for a relational constraint language?” in Proceedings of the IJCAI-97 Workshop on Spatial and Temporal Reasoning, Nagoya, Japan, 1997.
[26]
A. Isli, “Integrating existing cone-shaped and projection-based cardinal direction relations and a TCSP-like decidable generalisation,” CoRR cs.AI/0311051, 2003.
[27]
W. M. Liu, X. T. Zhang, S. J. Li, and M. S. Ying, “Reasoning about cardinal directions between extended objects,” Artificial Intelligence, vol. 174, pp. 951–983, 2011.
[28]
W. M. Liu and S. J. Li, “Reasoning about cardinal directions between extended objects: the NP-hardness result,” Artificial Intelligence, vol. 175, no. 18, pp. 2155–2169, 2011.
[29]
A.L. Kor and B. Bennett, “Composition for cardinal directions by decomposing horizontal and vertical constraints,” in Proceedings of the AAAI 2003 Spring Symposium, D. Dicheva and D. Dochev, Eds., Stanford University, Stanford, Calif, USA, March 2003.
[30]
A. L. Kor and B. Bennett, “Reasoning mechanism for cardinal direction relations,” in AIMSA 2010, D. Dicheva and D. Dochev, Eds., vol. 6304 of Lecture Notes in Artificial Intelligence (LNAI), pp. 32–41, Springer, 2010.
[31]
A. G. Cohn, B. Bennett, J. Gooday, and N. Gotts, “Representing and reasoning with qualitative spatial relations about regions,” in Temporal and Spatial Reasoning, O. Stock, Ed., Kluwer, New York, NY, USA, 1997.
[32]
B. L. Clarke, “Calculus of individuals based on connection,” Notre Dame Journal of Formal Logic, vol. 23, no. 3, pp. 204–218, 1981.
[33]
B. L. Clarke, “Individuals and points,” Notre Dame Journal of Formal Logic, vol. 26, no. 1, pp. 61–75, 1985.
[34]
B. Bennett, A. Isli, and A. G. Cohn, “A system handling RCC-8 queries on 2D regions representable in the closure algebra of half-planes ?” in Proceedings of the 11th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE'98), pp. 281–290, Springer, 1998.
[35]
F. Wolter and M. Zakharyaschev, “Spatio-temporal representation and reasoning based on RCC-8,” in Proceedings of the 7th Conference on Principles of Knowledge Representation and Reasoning (KR'00), 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.4558.
[36]
A. C. Varchi, “Parts, wholes, and part-whole relations: the prospects of mereotopology,” Data And Knowledge Engineering, vol. 20, pp. 259–286, 1996.
[37]
J. F. Allen, “Maintaining knowledge about temporal intervals,” Communications of the ACM, vol. 26, no. 11, pp. 832–843, 1983.
[38]
M. Egenhofer, “Reasoning about binary topological relations,” in Proceedings of the 2nd Symposium on Large Spatial Databases (SSD'91), O. Gunther and H. J. Schek, Eds., vol. 525, pp. 143–160, Lecture Notes in Computer Science, Zurich, Switzerland, 1991.
[39]
M. Egenhofer, “Deriving the composition of binary topological relations,” Journal of Visual Languages and Computing, vol. 5, no. 2, pp. 133–149, 1994.
[40]
Z. Cui, A. G. Cohn, and D. A. Randell, “Qualitative simulation absed on logical formalism of space and time,” in Proceedings of the AAAI'92, pp. 679–684, AAAI Press, Menlo Park, Calif, USA, 1992.
[41]
B. Bennett, “Some observations and puzzles about composing spatial and temporal relations,” in Proceedings of the 11th European Conference on Artificial Intelligence, Workshop on Spatial and Temporal Reasoning (ECAI), Amsterdam, The Netherlands, August 1994.
[42]
G. Ligozat, “Simple models for simple calculi,” in COSIT'99, C. Freksa and D. M. Mark, Eds., vol. 1661 of Lecture Notes in Computer Science, pp. 173–188, Springer, Berlin, Germany, 1999.
