Research On Reasoning About Cardinal Direction Relations And About Combining Different Spatial Relations

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.