Qualitative Motion Reasoning Via Voronoi Diagram

Qualitative spatial reasoning is an artificial intelligence approach to dealing withcommonsense spatial knowledge, and qualitative motion reasoning is an important is-sue in qualitative spatial reasoning research. Existing works usually concern the static,absolute spatial relationships representation and reasoning, e.g., topology, distance,and orientation relations, and pay little attention to the dynamic, relative spatial rela-tionships representation and reasoning, for instance, the vicinity relations between thespatial objects and their dynamic change.In this thesis, we explore the qualitative motion representation and reasoningmethod via the vicinity relations in Voronoi diagram. Following are the main results.1. A qualitative motion representation method via the vicinity relations in Voronoidiagram is proposed. The concepts of static and dynamic spatial vicinity relations inVoronoi diagram are defined, and the continuous transition between the two spatialvicinity relations in Voronoi diagram is proved. On this basis, the concepts, e.g.,conceptual neighbourhood, qualitative position, and qualitative path, are defined,and then the motion is represented, qualitatively.2. A plane sweep algorithm for computing the qualitative positions and constructingthe conceptual neighbourhood of qualitative positions is designed and implemented,and its time complexity is analyzed.3. An algorithm for reasoning about qualitative position of moving object is designedand implemented. Specifically, the qualitative position index is constructed withthe bucket sort technique, and then the qualitative position reasoning algorithm canwork out the qualitative position of moving object with the incomplete vicinity rela-tion and its changes of moving object in Voronoi diagram, and its time complexityis analyzed.4. A heuristic search algorithm for the shortest path between the qualitative positionsis designed and implemented, and its search space is analyzed. 5. A qualitative path reasoning algorithm with an observer perspective is designed andimplemented. Specifically, with the dynamic Voronoi edge sequence caused by themoving object and the use of qualitative distance as the measure, the algorithm canwork out the qualitative path of moving object.