Constraint Satisfaction Problems Based Spatial Direction Relation Reasoning

Qualitative Spatial Reasoning (QSR) is a method of qualitative reasoning mainlyin the shape of geometry or with the character of movement. It models,describes andrepresents spatial objects by using spatial theory and Artificial Intelligence (AI)technology. Based on this, QSR analyzes and handles qualitatively the spatial relationsof spatial objects. QSR is introduced into Spatial Reasoning (SR) in order to deal withthe uncertain spatial objects. People meet more uncertain than certain spatialinformation, so QSR is a necessary part of SR.The main researching content of QSR is the representation and reasoning of spatialobjects. The research of spatial direction relation and reasoning is one important part ofQSR. This paper combines the representation and reasoning of spatial directionrelations with the Constraint Satisfaction Problems (CSP) in order to find a reasoningsolution to spatial direction relation CSP.The paper has the following contents:(1) Qualitative Spatial ReasoningIn this part, we present the critical property, research contents, research status quoand research methodology of QSR, and expatiate the system structure,basic elementsand task of QSR, and introduce the representation model of direction relation andreasoning method in QSR.(2) Constraint Satisfaction PrombemsWe study CSP thoroughly. CSP is a research field in AI. A large number of proble-ms in AI and other areas of computer science can be viewed as special cases of the CSP.The algorithm solutions for CSP ——searching algorithm,arc consistency algorithmand constraint propagation algorithm are introduced. We expatiate Backjumping in det-ail.(3) The CSP methods to solve direction relation reasoning.We present two algorithms: the first algorithm is to reason direction relationconstraint satisfaction and the second is Backjumping-based direction relationreasoning algorithm. For the direction relations CSP of spatial objects, the former canuse constraint propagation and constraint relaxation. For these weak directions ofspatial objects, we can use the constraint propagation to get strong direction relations;on the other hand, for the direction relations that are not consistent, we use constraintrelaxation to get consistent direction relations. The latter reasons by usingBackjumping algorithm from the point of spatial direction relations combinative table.In the end, we perform experiments to validate the two algorithms. Spatial direction relations are an important kind of spatial relations, which decidesthe direction of spatial objective. Direction relations reasoning are playing animportant role in the intelligent navigation, robot, computer vision, image similarityidentifying, minerals forecasting and so on. With the coming of the development of thenew Geographic Information System (GIS), theoretical field needs the research ofspatial reasoning exceedingly. This paper uses the method of CSP into spatial directionrelations reasoning in order to find an efficient technique of direction relationsreasoning.