Research on Orientation Relations and Integrative Reasoning with Topological Relations and Orientation Relations in Dynamic Settings
|Course||Applied Computer Technology|
|Keywords||Orientation Relations Interval Relations Composition Table Conceptual Neighborhood Graphs|
The modeling of spatio-temporal knowledge is one of the most important issues in thefield of artificial intelligence. In the real world, spatio-temporal knowledge changes with time,and it has been widely used in the field of Robot Navigation, Auto Planning and so on.Inaddition, when dealing with practical problems, we will not only think about single spatialrelation, but also consider multi-aspect spatial relations. For example, there usually existintegrative queries in the application of Geographical Information System (GIS). Therefore, toprecisely describe dynamic settings, we need to research integrative representing andreasoning of multi-aspect spatial relations in dynamic settings.Previous studies were mostly focused on topological relations in dynamic settings, butfew were on orientation relations and the combination of topological and orientation relations.The representative model of orientation relations in dynamic settings includes Rupam’smotion event modeling, while the representative model of the combination of topologicalrelations with orientation relations includes Marco’s reasoning about topological andorientation information in dynamic settings. Marco used the conceptual neighborhood graphsto reason the combinational relation of topological relations and orientation relations.However, some problems were found in Rupam and Marco’s papers. The composition tableand conceptual neighborhood graphs which Rupam gave had some problems. Thecomposition table and conceptual neighborhood graphs which Marco gave was incomplete.As for the problems above, in this paper, we improved Rupam’s base relations’composition table and conceptual neighborhood graphs; based on Marco’s model, weconstrusted a model RCC8-ROR which combined topological relations with orientationrelations; we gave the dynamic reasoning algorithms for model ROR and model RCC8-ROR.The main work and results included in this paper are as follows:Firstly, we analyzed the research status of orientation relations and its combination withtopological relations. There was a short introduction of background and significance of thisarticle.Secondly, we introduced Allen’s temporal interval algebra, Marco’s model RCC8-CD,Rupam’s model ROR, Freksa’s conceptual neighborhood structure and some other basis work.Thirdly, we proposed a static reasoning algorithm to create ROR relations’ compositiontable. Then we proposed an auto-generated algorithm to produce conceptual neighborhoodgraphs of orientation relations. And then a comparison of the composition table and conceptual neighborhood graphs with those of Rupam was conducted. At last, we gave adynamic reasoning algorithm based on Rupam’s model ROR.Fourthly, based on Marco’s model, we construsted a model RCC8-ROR which combinedtopological relations with orientation relations. We gave the definition of model RCC8-RORand turned out the relations of RCC8-ROR were JEPD (jointly exhaustive and pairwisedisjoint, JEPD for short). Then we proposed a static reasoning algorithm to create RCC8-RORrelations’ composition table, and we proposed an auto-generated algorithm to produceconceptual neighborhood graphs of RCC8-ROR relations. And then we gave a dynamicreasoning algorithm based on our model RCC8-ROR. At last, a comparison of dynamicreasoning results with those of Rupam was conducted.Finally, we designed and implement a system for demonstrating reasoning results of RORand RCC8-ROR.Orientation relations and topological relations play an important role in spatial reasoning.With the development of spatial reasoning in practical applications, we need multi-aspectspatial information to reason. Dynamic spatio-temporal knowledge representation andreasoning has gained more attention. But there are lack of research on orientation relationsand its combination with topological relations. This article uses rectangle algebra and Freksa’sconceptual neighborhood structure to improve ROR relations’ composition table andconceptual neighborhood graphs. Based on RCC8-CD, this article constructs a modelRCC8-ROR which combines topological relations with orientation relations. And this articlealso gives a research on dynamic reasoning problems of RCC8-ROR.