摘要
本文围绕方向关系推理以及多种空间关系结合推理展开一系列的研究工作，研究内容包括以下几个方面：
1.从定性空间信息的表示和推理两个方面阐述了定性空间推理的研究现状及热点问题。重点介绍了基于区域的定性空间推理模型，包括区域连接演算、区间代数、矩形代数以及主方向演算。
2.研究了空间主方向关系的逆关系推理。给出了推理矩形主方向关系及一般主方向关系的逆关系的算法，证明它们是正确完备的，并给出了主方向演算中全部218个基本关系的逆关系表。
3.给出一种新的主方向关系复合推理算法，证明该算法是正确完备的，并指出对算法做两处改动就可以使之用于REG*区域集合上的主方向关系推理。
4.给出主方向演算的一个新的易处理子集——饱和凸矩形主方向关系集合。证明出其上的相容性问题可以利用路径相容算法在多项式时间内得到判定，并证明出该子集是主方向演算的一个子代数。
5.研究了RCC-8关系、矩形主方向关系以及定性尺寸关系三者结合的定性空间推理。提出一种面向三种关系结合的相容性判定算法——TRIPATH-CONSISTENCY，证明出该算法的时间复杂性为O(n3)，空间复杂性为O(n2)。进一步证明出当限定所考虑的区域集合为矩形区域，所输入的关系集合为基本RCC-8关系集合、基本矩形主方向关系集合以及定性尺寸关系集合时，算法TRIPATH-CONSISTENCY对于判定结合后的约束网络的相容性是充分的。
Space is a fundamental part of our life. Our whole existence is embedded in space.Perceiving space, representing space, reasoning about space, and communicating about spaceare the major abilities and requirements of any intelligent system. Therefore, it is an importanttask of Artificial Intelligence research to provide methods for handling spatial information.
There are mainly two different approaches for representing spatial knowledge, thequantitative approach and the qualitative approach. The quantitative is the classical approachwhich depends on numerical values. However, when describing a spatial configuration orwhen reasoning about such a configuration, often it is not possible or desirable to obtainprecise quantitative data. In these cases, quantitative approach doesn’t work, and qualitativeapproach may be used. Qualitative reasoning is an approach for dealing with commonsensespatial knowledge without using numerical computation.
Qualitative spatial representation and reasoning (QSR) has become an important subfieldof Artificial Intelligence. QSR has gained increasing popularity in recent years withapplications in spatial information systems, navigation, natural language understanding,spatial databases, spatial data mining, computer vision, CAD/CAM and so on. However, thereare still several problems in existing researches in QSR and need to take some further anddeep investigations.
In this paper, we do some researches on reasoning about cardinal direction relations andabout combining different spatial relations. We start with an overview of qualitative spatialrepresentation and reasoning, and especially focus on those models based on regions,including Region Connection Calculus (RCC), Interval Algebra (IA), Rectangle Algebra (RA)as well as Cardinal Direction Calculus (CDC). Then, we carry out and complete the following research contents:
1. The inverse and composition operations are used as mechanisms for inferring new spatialrelations from existing ones. Such mechanisms are typically an essential part of theoryresearch and practical application, e.g. consistency checking, preprocessing spatial queries,identifying tractable subclass of a set of relations, and so on. Inverse and composition arealso an essential part of Relation Algebra, so their formal study is a prerequisite to anyalgebraic approach to spatial reasoning. In this thesis, we investigate the two problems ofthe CDC which is a cardinal direction relation model proposed by Goyal and Egenhoferfor extended objects.
（1） Research on computing the inverse of cardinal direction relations (CRs). We firstdevelopment an algorithm for computing the inverse of rectangle-CRs, which is a setof a special type of CRs defined in CDC, by exploiting the evident connectionbetween basic rectangle-CRs and interval relations. Then, we consider progressivelythe general cardinal direction relations in CDC, the inverse of which is computed byreducing to the computation of the inverse of rectangle-CRs. Analyzing in theoryand the final results both demonstrate that our algorithms are correct and complete.
（2） Research on composing cardinal direction relations (CRs). We first propose a novelmethod for computing the composition of cardinal direction relations over connectedregions. We demonstrate our algorithms are correct and complete. Then, ouralgorithm is adapted to compute the composition of cardinal direction relationsbetween possibly disconnected regions.
2. Research on tractable subclass. We present a new tractable subclass of CDC: the set ofsaturated-convex rectangle cardinal direction relations which we redefined and contain400relations. We also prove that the path-consistency method is sufficient for decidingconsistency in the new subclass.
3. Research on combining different spatial relations. We addressed the problem of combiningthree types of spatial relations, namely topology relations, expressed as RCC-8contraints,qualitative size relations(QS), and direction relations, expressed as rectangle-CRscontraints. We present a cubic time path-consistency algorithm, namedTRIPATH-CONSISTENCY, for processing a set of constraints that combine RCC-8, QSand rectangle-CRs. We show that when only basic RCC-8relations, basic rectangle-CRs,and any QS relations are used, the algorithm TRIPATH-CONSISTENCY is correct and complete for deciding the consistency of the combined sets of constraints.
引文
[1]. Bittner T, Donnelly M, Smith B. A spatio-temporal ontology for geographicinformation integration [J]. International Journal on Geographic Information Science,2009,23(6):765-798.
[2]. Egenhofer M J, Golledge R G(Eds.), Spatial and Temporal Reasoning in GeographicInformation Systems [M], Oxford University Press, Oxford,1998.
[3]. Giorgio De Felice, Paolo Fogliaroni, Jan Oliver Wallgrün. A HybridGeometric-Qualitative Spatial Reasoning System and its Application in GIS [C].Spatial Information Theory-10th International Conference, COSIT2011, Belfast, ME,USA, September12-16,2011. Proceedings. Lecture Notes in Computer Science. vol.6899, pp.188-209. ed. Max J. Egenhofer, Nicholas A. Giudice, Reinhard Moratz,Michael F. Worboys. Springer.
[4]. Paolo Fogliaroni, Giorgio de Felice, Falko Schimd, Jan Oliver Wallgrün. ManagingQualitative Spatial Information to Support Query-by-Sketch [C]. An InterdisciplinaryApproach to Understanding and Processing Sketch Maps, COSIT,2011.
[5]. Escrig M T. Qualitative Spatial Reasoning: Theory and Practice: Application toRobot Navigation [M]. IOS Press, Amsterdam,1998.
[6]. Jan Oliver Wallgrün. Exploiting qualitative spatial constraints for multihypothesistopological map learning [C]. In9th international conference of COSIT,2009.
[7]. Jan Oliver Wallgrün. Hierarchical Voronoi graphs-Spatial representation andreasoning for mobile robots [M]. Springer,2010.
[8]. Maa W, Wazinski P, Herzog G. VITRA GUIDE: Multimodal route descriptions forcomputer assisted vehicle navigation [C], in: Proc. Sixth Internat. Conference onIndustrial and Engineering Applications of Artificial Intelligence and Expert SystemsIEA/AIE-93, Edinburgh, Scotland,1993:144–147.
[9]. Egenhofer Max J, Rashid A, Shariff B M. Metric Details for Natural-LanguageSpatial Relations [J]. ACM Transactions on Information Systems,1998,16(4):295-321.
[10]. Huang P W, Lee C H. Image database design based on9D-SPA representation forspatial relations [J]. IEEE Transactions on Knowledge and Data Engineering,2004,16(12):1486-1496.
[11]. Papadias D, Theodoridis Y, Sellis T, Egenhofer M J. Topological relations in theworld of minimum bounding rectangles: A study with R-trees [C], in: Proceedings ofACM SIGMOD-95,1995:92–103.
[12]. Ceci M, Appice A. Spatial associative classification: propositional vs structuralapproach [J]. Journal of Intelligent Information System,2006,27(3):191-213.
[13].刘大有,王生生,虞强源,胡鹤.基于定性空间推理的多层空间关联规则挖掘算法[J].计算机研究与发展,2004,14(4):565-570.
[14]. Santos M Y, Amaral L A. Mining geo-referenced data with qualitative spatialreasoning strategies [J]. Computers&Graphics,2004,28(3):371-379.
[15]. Yang H, Parthasarathy S, Mehta S. Mining spatial object associations for scientificdata [C]. In Proceedings of the19th International Joint Conference on ArtificialIntelligence (IJCAI),2005:902-907.
[16]. Egenhofer M J. Query processing in spatial-query-by-sketch [J]. Journal of VisualLanguages and Computing,1997,8(4):403–424.
[17]. Gooday J M, Cohn A G. Using spatial logic to describe visual programminglanguages [J]. Artificial Intelligence,1996,10(3-4):171–186.
[18]. Bhatt M, Dylla F, Hois J. Spatio-terminological inference for the design of ambientenvironments [C]. In K. S. Hornsby, C. Claramunt, M. Denis,&G. Ligozat (Eds.),Spatial information theory,9th international conference, COSIT,2009.
[19]. Bojduj B, Weber B, Richter K F, Bertel S. Computer aided architectural design:Wayfinding complexity analysis [C]. In Proceedings of the12th internationalconference on computer supported collaborative work in design (CSCWD),2008:919-924.
[20]. Cohn A G. Qualitative spatial representation and reasoning techniques [C]. In the21th Annual German Conference on Artificial Intelligence (KI-97), Freiburg,1997:1-30.
[21].刘亚彬,刘大有,王飞.定性空间表示与定性空间的研究与发展[J].计算机科学,2003,30(3):65-67.
[22].谢琦,刘大有,虞强源,陈娟.定性方向关系模型研究进展[J].计算机科学,2006,33:5-9.
[23].欧阳继红.时空推理中一些问题的研究[D].吉林大学,2005.
[24].胡鹤.本体方法及其时空推理应用研究[D].吉林大学,2004.
[25].谢琦.空间方位关系模型与时空结合推理的研究[D].吉林大学,2006.
[26].陈娟.空间方位关系模型与多方面空间关系结合推理的研究[D].吉林大学,2007.
[27].富倩.空间凹形区域中拓扑关系模型和形状关系模型的研究[D].吉林大学,2010.
[28].董轶群.定性空间方向关系建模中若干问题研究[D].吉林大学,2011.
[29]. Sanjing Li, Mingsheng Ying. Region Connection Calculus: Its models andcomposition table [J]. Artificial Intelligence,2003,145(1-2):121-146.
[30]. Sanjiang Li. Combining Topological and Directional Information for SpatialReasoning [C]. In proceedings of the20th International Joint Conference onArtificial Intelligence (IJCAI-07),2007:435-440.
[31]. Weiming Liu, Sanjiang Li, Jochen Renz. Combining RCC-8with QualitativeDirection Calculi: Algorithms and Complexity [C]. In proceedings of the21thInternational Joint Conference on Artificial Intelligence (IJCAI-09),2009:854-859.
[32].杜世宏.空间关系模糊描述及组合推理的理论和方法研究[D].中国科学院研究生院（遥感应用研究所）,2004.
[33].曹菡.空间关系推理的知识表示与推理机制研究[D].武汉大学,2002.
[34].郭平.定性空间推理技术及应用研究[D].重庆大学,2004.
[35]. Cohn A G, Renz J. Qualitative Spatial Representation and Reasoning [M]. Handbookof Knowledge Representation, Harmelen F van, Lifschitz V, Porter B (eds), Elsevier,2008:551-596.
[36]. Brandon Bennett, Modal logic for qualitative spatial reasoning [J]. Logic Journal ofthe IGPL,1996,4(1):23-45.
[37]. Renz Jochen. Qualitative Spatial Reasoning with Topological Information [M],volume2293of Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin,Heidelberg, New York,2002.
[38]. Biacino L, Gerla G. Connection structures [J]. Notre Dame Journal of Formal Logic,1991,32(2):242-247.
[39]. Cohn A G. Mereotopological Connection [J]. Journal of Philosophical Logic,2003,32(4):357-390.
[40]. Bowman L Clarke. A calculus of individuals based on connection [J]. Notre DameJournal of Formal Logic,1981,22(3):204–218.
[41]. Bowman L Clarke. Individuals and points [J]. Notre Dame Journal of Formal Logic,1985,26(1):61–75.
[42]. Stefano Borgo, Nicola Guarino, and Claudio Masolo. A pointless theory of spacebased on strong connection and congruence [C]. In Proceedings of Principles ofKnowledge Representation and Reasoning (KR96),1996:220–229.
[43]. David A Randell, Zhan Cui, Anthony G Cohn. A spatial logic based on regions andconnection [C]. In B. Nebel, W. Swartout, and C. Rich, editors, Principles ofKnowledge Representation and Reasoning: Proceedings of the3rd InternationalConference, pages165–176, Cambridge, MA, October1992. Morgan Kaufmann,1992:165-176.
[44]. David A Randell, Anthony G Cohn. Modelling topological and metrical properties inphysical processes [C]. In R. Brachman, H. J. Levesque, and R. Reiter, editors,Principles of Knowledge Representation and Reasoning: Proceedings of the1stInternational Conference, pages55–66, Toronto, ON, May1989. Morgan Kaufmann.,1989:55-66.
[45]. Nicholas Asher, Laure Vieu. Towards a geometry of common sense: A semantics anda complete axiomatization of mereotopology [C]. In IJCAI-95,1995:846–852.
[46]. Anthony G Cohn, Brandon Bennett, John Gooday, Nicholas M Gotts. Representingand reasoning with qualitative spatial relations about regions [M]. In O. Stock, editor,Spatial and Temporal Reasoning, springer,1997:97-134.
[47]. Anthony G Cohn, Achille C Varzi. Connection relations in mereotopology [C]. InECAI-98,1998:150-154.
[48]. Anthony G Cohn, Achille C Varzi. Modes of connection [C]. In Proceedings of theInternational Conference on Spatial Information Theory: Cognitive andComputational Foundations of Geographic Information Science (COSIT-99),1999:299–314.
[49]. Andrzej Grzegorczyk. Undecidability of some topological theories [J]. FundamentaMathematicae,1951,38:137-152.
[50]. Ian Pratt, DominikSc hoop. A complete axiom system for polygonal mereotopologyof the real plane [J]. Journal of Philosophical Logic,1998,27:621-658.
[51]. DominikSc hoop. A model-theoretic approach to mereotopology [D]. PhD thesis,Faculty of Science and Engineering, University of Manchester,1999.
[52]. Bennett B. Spatial reasoning with propositional logic [C]. In Proceedings of the4thInternational Conference on Knowledge Representation and Reasoning,1994:51-62.
[53]. Egenhofer Max J. Reasoning about binary topological relations [C]. In proceedingsof the Second Symposium on Large Spatial Databases, SSD-91,1991.
[54]. SanJiang Li, Mingsheng Ying. Generalized Region Connection Calculus [J].Artificial Intelligence,2004,160(1-2):1-34.
[55]. Max J Egenhofer, Eliseo Clementini, Paolino Di Felice. Topological relationsbetween regions with holes [J]. International Journal of Geographical InformationSystems,1994,8(2):129–144.
[56]. Max J Egenhofer, Robert D Franzosa. On the equivalence of topological relations [J].International Journal of Geographical Information Systems,1994,8(6):133–152.
[57]. G Retz-Schmidt. Various views on spatial prepositions [J]. AI Magazine,1988,9(2):95-105.
[58]. Andrew U Frank. Qualitative spatial reasoning about cardinal directions [C]. InProceedings of the7th Austrian Conference on Artificial Intelligence,1991:157–167.
[59]. Gerard Ligozat. Reasoning about cardinal directions [J]. Journal of Visual Languagesand Computing,1998,9:23-44.
[60]. Ligozat G. A New Proof of Tractability for ORD-HornRelations [C]. In proceedingsof AAAI-96,1996:395-401.
[61]. Renz Jochen, Mitra Debasis. Qualitative direction calculi with arbitrary granularity[C]. In PRICAI2004: Trends in Artificial Intelligence,8th Pacific Rim InternationalConference on Artificial Intelligence,2004:65–74.
[62]. Christian Freksa. Using orientation information for qualitative spatial reasoning [C].Proceedings of the International Conference GIS-From Space to Territory: Theoriesand Methods of Spatio-Temporal Reasoning on Theories and Methods ofSpatio-Temporal Reasoning in Geographic Space,1992.
[63]. Hans Guesgen. Spatial reasoning based on Allen’s temporal logic. Technical Report[R]. TR-89-049, ICSI, Berkeley, CA,1989.
[64]. Dimitris Papadias, Yannis Theodoridis. Spatial relations, minimum boundingrectangles, and spatial data structures [J]. International Journal of GeographicInformation Systems,1997,11(2):111–138.
[65]. Balbiani P, Condotta J F, Luis Fari as del Cerro. A model for reasoning aboutbidimensional temporal relations [C]. In Proceedings of the Sixth InternationalConference on Principles of Knowledge Representation and Reasoning, KR’98.1998:124–130.
[66].刘永山,郝忠孝.基于MBR的主方向关系一致性检验.软件学报,2006,17(5):976-982.
[67]. Balbiani P, Condotta J F, Luis Fari as del Cerro. A new tractable subclass of therectangle algebra [C]. In Proc. of the16th International Joint Conference on ArtificialIntelligence (IJCAI),1999:442–447.
[68]. Philippe Balbiani, Jean-Fran ois Condotta, Luis Fari as del Cerro. A tractablesubclass of the block algebra: constraint propagation and preconvex relations. InProccedings of the9th Portuguese Conference on Artificial Intelligence,1999.
[69]. Goyal R K. Similarity assessment for cardinal directions between extended spatialobjects [D], PhD thesis, The University of Maine,2000.
[70]. Goyal R K, Egenhofer M J. The direction-relation matrix: A representation ofdirection relations for extended spatial objects [C]. In: UCGIS Annual Assembly andSummer Retreat, Bar Harbor, ME,1997.
[71]. Skiadopoulos S, Koubarakis M. Composing cardinal direction relations [J]. ArtificialIntelligence,2004:152(2):143–171.
[72]. Skiadopoulos S, Koubarakis M. On the consistency of cardinal direction constraints[J]. Artificial Intelligence,2005,163(1):91–135.
[73]. Weiming Liu, Xiaotong Zhang, Sanjiang Li, Mingsheng Ying. Reasoning aboutcardinal directions between extended objects [J]. Artificial intelligence,2010,174(12-13):951-983.
[74]. Skiadopoulos S, Sarkas N, Sellis T, Koubarakis M. A family of directional relationmodels for extended objects [J]. IEEE Transactions on Knowledge and DataEngineering,2007,19(8):1116-1130.
[75]. Daniel Hernández, Eliseo Clementini, and Paolino di Felice. Qualitative distances [J].In Spatial Information Theory: A Theoretical basis for GIS, of LNCS,1995,988:45-58.
[76]. Eliseo Clementini, Paolino di Felice, and Daniel Hernandez. Qualitativerepresentation of positional information [J]. Artificial Intelligence,1997,95(2):317–356.
[77]. Amar Isli, Reinhard Moratz. Qualitative spatial representation and reasoning:Algebraic models for relative position [R]. Technical Report284, Universit tHamburg, Fachbereich Informatik,1999.
[78]. Arun K Pujari, G Vijaya Kumari, Sattar Abdul. INDU: An interval and durationnetwork [C]. In Australian Joint Conference on Artificial Intelligence,1999,291-303.
[79]. Renz Jochen. Aspatial odyssey of the interval algebra:1.directed intervals [C]. InProceedings of the17th International Joint Conference on Artificial Intelligence,Seattle,WA,2001,51-56,
[80]. Golumbic Martin C, Shamir Ron. Complexity and algorithms for reasoning abouttime: A graph-theoretic approach [J]. Journal of the Association for ComputingMachinery,1993,40(5):1128–1133.
[81]. Vilain Marc B, Kautz Henry A, and van Beek Peter. Constraint propagationalgorithms for temporal reasoning: A revised report [M]. In Weld D S and de Kleer J,editors, Readings in Qualitative Reasoning about Physical Systems,1989:373–381.
[82]. Alfred Tarski. On the calculus of relations [J]. Journal of Symbolic Logic,1941,6:73-89.
[83]. Peter B Ladkin, Roger Maddux. On binary constraint problems [J]. Journal of theAssociation for Computing Machinery,1994,41(3):435–469.
[84]. Robin Hirsch. A finite relation algebra with undecidable network satisfactionproblem [J]. Logic Journal of the IGPL,1999,7(4):547-554.
[85]. Renz J, Nebel B. Qualitative spatial reasoning using constraint calculi [M].Handbook of spatial logics, Aiello M, et al.(eds). Springer Verlag,2007:161-215.
[86]. Mackworth A K. Consistency in networks of relations [J]. Artificial Intelligence,1977,8(1):99-118.
[87]. Ligozat G, Renz J. What is a Qualitative Calculus? A General Framework [C]. InTrends in Artificial Intelligence (Pricai2004), Berlin: Springer-Verlag,2004:53-64.
[88]. Randell D A, Cohn A G, Cui Z. computing transitivity tables: a challenge forautomated theorem provers [C]. In proceedings CADE11, Springer Verlag,1992.
[89]. Bennett Brandon. Logical Representations for Automated Reasoning about SpatialRelationships [D]. PH.D. thesis. School of Computer Studies. University of Leeds,October1997.
[90]. Bennett B. Modal logics for qualitative spatial reasoning [J]. Journal of the IGPL,1996,4(1):23–45.
[91]. Nebel B. Computational properties of qualitative spatial reasoning: First results [C].In Wachsmuth I, Rollinger R, Brauer W, editors. In proceedings of the19th GermanAI Conference (KI-95), Springer-Verlag,1995. Lecture Notes in Computer Science,1995,981:233–244.
[92]. Renz J, Nebel B. On the complexity of qualitative spatial reasoning: A maximaltractable fragment of the region connection calculus [J]. Artificial Intelligence,1999,108(1-2):69-123.
[93]. Goranko V, Montanari A, Sciavicco G. Propositional interval neighborhood temporallogics [J]. Journal of Universal Computer Science,2003,9(9):1137-1167.
[94]. Antonio Morales, Isabel Navarrete, Guido Sciavicco. a new modal logic forreasoning about space: spatial propositional neighborhood logic [J]. Annals ofMathematics and Artificial Intelligence,2007,51(1):1-25.
[95]. Balbiani P, Tinchev T, Vakarelov D. Dynamic logics of region-based theory ofdiscrete space [J]. Journal of Applied Non-classical logics,2007,17(1):39-61.
[96]. Balbiani P, Tinchev T, Vakarelov D. modal logics for region-based theories of space[J]. Fundamental Information,2007,81(1-3):29-82.
[97]. Philippe Balbiani, Hans van Ditmarsch, Andreas Herzig, Tiago de Lima. A tableaumethod for public announcement logics [C]. In Aix en Provence, France: SpringerVerlag, Heideberg, D-69121, Germany,2007:43-59.
[98]. Balbiani P, Vakarelov D. Arrow logic with arbitrary intersections: applications toPawlak’s information system [J]. Fundamental Information,2007,75(1-4):1-25.
[99]. Mikhail Sheremet, Frank Wolter, Michael Zakharyaschev. A modal logic frameworkfor reasoning about comparative distance and topology [J]. Annals of Pure andApplied Logic,2010,161(4):534-559.
[100]. Ralf M ller, Michael Wessel. Terminological Default Reasoning about SpatialInformation: A First Step [C]. Proceedings of the1999International Conference onSpatial Information Theory (COSIT1999), Springer-Verlag,1999.
[101]. Michael Wessel. Obstacles on the Way to Spatial Reasoning with DescriptionLogics-Some Undecidability Results [C]. Proceedings of the International Workshopon Description Logics2001(DL2001), CEUR Workshop Proceedings (Vol.49),2001.
[102]. Pham D N, Thornton J R, Sattar A. Modelling and solving temporal reasoning aspropositional satisfiability [C]. In Proceeding of the4th International Workshop onModelling and Reformulating, Sitges, Spain,2005.
[103]. Cohn A G. A hierarchical representation of qualitative shape based on connection andconvexity [C]. In Proceedings of COSIT-95, Semmering,1995.
[104]. Cohn A G, Bennett B, Gooday J, Gotts N M. Qualitative spatial representation andreasoning with the region connection calculus [J]. GeoInformatica,1997,1(1):1-44.
[105].欧阳继红,富倩,刘大有.简单凹形区域间空间关系的一种表示及推理模型[J].电子学报,2009,37(8):1830-1836.
[106]. Nicholas M Gotts. How far can we ‘C’? Defining a ‘doughnut’ using connectionalone [C]. In E. Sandewall J. Doyle and P. Torasso, editors, Principles of KnowledgeRepresentation and Reasoning: Proceedings of the4th International Conference(KR94),1994:246–257.
[107]. Nicholas M Gotts. Topology from a single primitive relation: Defining topologicalproperties and relations in terms of connection [R]. Technical Report96-23,University of Leeds, School of Computer Studies,1996:96-23.
[108]. Dornheim C. Undecidability of plane polygonal mereotopology [C]. In Anthony G.Cohn, Leonard Schubert, and S. Shapiro, editors, Principles of KnowledgeRepresentation and Reasoning: Proceedings of the6th International Conference(KR’98), Morgan Kaufman,1998:342-353.
[109]. Gotts N M. Using the RCC formalism to describe the topology of spherical regions[R]. Technical Report96.24, School of Computer Studies, University of Leeds,1996.
[110]. Wolter F, Zakharyaschev M. Qualitative spatio-temporal representation andreasoning: a computational perspective [M]. In: Exploring Artificial Intelligence inthe New Millenium. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA,2003.
[111]. Knauff M, Rauh R, Renz J. A cognitive assessment of topological spatial relations:Results from an empirical investigation [C]. In Proceeding of3rd InternationalConference on Spatial Information Theory (COSIT-97), Lecture Notes in ComputerScience, Springer, Berlin,1997,1329:193-206.
[112]. Renz J, Rauh R, Knauff M. Towards cognitive adequacy of topological spatialrelations [C]. In: C. Freksa, W. Brauer, C. Habel, K.F. Wender (Eds.), SpatialCognition II—Integrating Abstract Theories, Empirical Studies, Formal Models, andPractical Applications, Lecture Notes in Computer Science, Springer, Berlin,2000,1849:184–197.
[113]. Papadimitriou C H, Suciu D, Vianu V. Topological queries in spatial databases [J].Journal of Computer and System Sciences.1999,58(1):29-53.
[114]. Aiello M, Areces C, de Rijke M. Spatial reasoning for image retrieval [C]. InProceedings of1999International Workshop on Description Logics (DL-99),Link ping, Sweden,1999.
[115]. Renz J. Maximal tractable fragments of the region connection calculus: A completeanalysis [C]. In: Proc. IJCAI-99, Stocholm, Sweden,1999.
[116]. Gerevini A, Renz J. Combining topological and size information for spatial reasoning[J]. Artificial Intelligence,2002,137(1-2):1-42.
[117]. Allen J F. Maintaining knowledge about temporal intervals [J]. Communications ofthe ACM,1983,26(11):832–843.
[118]. Allen J F, Hayes P. A common sense theory of time [C]. A. Joshi (editor), IJCAI-85,Proceedings of the9th International Joint Conference on Artificial Intelligence,Volume1,528-531, Morgan Kaufmann,1985.
[119]. Nebel B, Bürckert H J. Reasoning about temporal relations: A maximal tractablesubclass of Allen’s interval algebra [J]. Journal of the ACM,1995,42(1):43-66.
[120]. Krokhin A, Jeavons P, Jonsson P. Reasoning about temporal relations: The tractablesubalgebras of Allen’s interval algebra [J]. Journal of the ACM,2003,50(5):591-640.
[121]. Marc B Vilain, Henry A Kautz. Constraint propagation algorithms for temporalreasoning [C]. In Proceedings of the5th National Conference of the AmericanAssociation for Artificial Intelligence, Philadelphia, PA, August1986:377-382.
[122]. Valdés-Pérez R E, The satisfiability of temporal constraint networks [C]. InProceedings of the6th National Conference on Artificial Intelligence (AAAI-87),1987:256–260.
[123]. Drakengren T, Jonsson P. Eight maximal tractable subclasses of Allen’s algebra withmetric time [J]. Journal of Artificial Intelligence Research,1997,7:25-45.
[124]. Drakengren T, Jonsson P. Twenty-one large tractable subclasses of Allen’s algebra [J].Artificial Intelligence,1997,93(1-2),297–319.
[125]. Ligozat G.“Corner” relations in Allen’s algebra [J]. Constraints,1998,3(2-3):165-177.
[126]. Andrei A Krokhin, Peter Jeavons, Peter Jonsson. Reasoning about temporal relations:The tractable subalgebras of Allen's interval algebra [J]. Journal of the ACM,2003,50(5):591-640.
[127]. Ligozat G. On generalized interval calculi [C]. In proceedings of AAAI-91,1991:234-240.
[128]. Nicholas M Gotts, John M Gooday, Anthony G Cohn. A connection based approachto commonsense topological description and reasoning [J]. The Monist,1996,79(1):51-75.
[129]. Cui Z, Cohn A G, Randell D A. Qualitative and topological relationships in spatialdatabases [J], in D. Abel and B. C. Ooi (Eds.), Advances in Spatial Databases,Lecture Notes in Computer Science, Springer Verlag, Berlin,1993,692:293-315.
[130]. Renz J, Nebel B. Efficient Methods for Qualitative Spatial Reasoning [J]. Journal ofArtificial Intelligence Research,2001,15:289-318.
[131]. Renz J, Li J J. Automated Complexity Proofs for Qualitative Spatial and TemporalCalculi [C], Proceedings of the Eleventh International Conference on Principles ofKnowledge Representation and Reasoning (KR'08), Sydney, Australia, September2008:715-723.
[132]. Renz J. Qualitative Spatial and Temporal Reasoning: Efficient Algorithms forEveryone [C]. In Proceedings of the20th International Joint Conference on ArtificialIntelligence (IJCAI-07), Hyderabad, India, January2007:526-531.
[133]. Papadias D, Arkoumanis N, Karacapilidis N. On The Retrieval of SimilarConfigurations [C]. In Proceedings of SDH’98,1998:510-521.
[134]. Shengsheng Wang, Dayou Liu, Jie Liu. Preprocessing of Spatial Query in DistributedGIS [J]. Journal of Communication and Computer,2005,2(5):1-5.
[135]. Navarrete I, Sciavicco G. Spatial Reasoning with Rectangular Cardinal DirectionRelations [C]. In Proceedings of the11th European Conference on ArtificialIntelligence, ECAI2006, Workshop on Spatial and Temporal Reasoning, Riva delGarda, Italy,2006:1-9.
[136]. Bennett B. Some observations and puzzles about composing spatial and temporalrelations [C]. In R. Rodr′guez (Ed.), Proceedings ECAI-94Workshop on Spatial andTemporal Reasoning,1994.
[137]. Bennett B, Isli A, Cohn A G. When does a composition table provide a complete andtractable proof procedure for a relational constraint language?[C]. In Proceedings ofIJCAI-97, Nagoya, Japan,1997.
[138]. Ligozat G. When tables tell it all: Qualitative spatial and temporal reasoning based onlinear ordering [C]. In Proceedings of COSIT-01, in: Lecture Notes in Comput. Sci.,Vol.2205, Springer, Berlin,2001,2205:60–75.
[139]. Papadias D. Relation-based representation of spatial knowledge [D]. PhD Thesis,Department of Electrical and Computer Engineering, National Technical Universityof Athens,1994.
[140]. Goyal R, Egenhofer M. Cardinal directions between extended spatial objects [J],IEEE Transactions on Knowledge and Data Engineering. Available athttp://www.spatial.maine. edu/~max/RJ36.html,2000.
[141]. Navarrete I, Morales A, Sciavicco G. Consistency checking of basic cardinalconstraints over connected regions [C]. In Proceedings of the20th International JointConference on Artificial Intelligence (IJCAI-07),2007:495–500.
[142].王生生,刘大有,谢琦.集成多方面信息的定性空间推理及应用[J].软件学报,2003,14(11):1857~1862.
[143]. Renz Jochen. A spatial odyssey of the interval algebra: directed intervals [C]. InProceedings of the17th International Joint Conference on Artificial Intelligence,Seattle, WA,2001:51-56.
[144]. Li J J, Kowalski T, Renz J, and Li S J. Combining Binary Constraint Networks inQualitative Reasoning [C]. In Proceedings of the18th European Conference onArtificial Intelligence (ECAI'08), Patras, Greece, July2008:515-519.
[145].陈娟,刘大有,贾海洋,张长海.基于MBR的拓扑、方位、尺寸结合的定性空间推理[J].计算机研究与发展,2010,47(3):426-433.
[146]. Ladkin P B, Maddux R. On binary constraint networks [R]. Technical ReportKES.U.88.8, Kestrel Institute, Palo Alto, CA,1988.
[147]. Clementini E, Di Felice P, Hernandez D. Qualitative representation of positionalinformation [J]. Artificial Intelligence,1997,95(2):317-356.
[148]. Galton A, Meathrel R C. Qualitative outline theory [C]. In: Proc. IJCAI-99,Stockholm, Sweden,1999:1061–1066.
[149]. Raiman O. Order of magnitude reasoning [J]. Artificial Intelligence,1991,51(1-3):11-38.
[150]. Zimmermann K. Measuring without measures: The delta-calculus [C]. In: Proc.2ndInternational Conference on Spatial Information Theory (COSIT-95), Lecture Notesin Computer Science, Springer, Berlin,1995,988:59–67.
