Qualitative reasoning about cardinal directions between spatial objects using answer set programming

İzmirlioğlu, Yusuf (2020) Qualitative reasoning about cardinal directions between spatial objects using answer set programming. [Thesis]

[thumbnail of 10358037_İzmirlioglu_Yusuf.pdf] PDF

Download (1MB)


Qualitative spatial reasoning studies representation and reasoning with different aspects of space, such as direction, distance, size using parts of natural language rather than quantitative data. Qualitative models are useful in contexts where quantitative data is not available due to incomplete knowledge or uncertainty. Qualitative reasoning is also relevant for contexts with complete information and quantitative data because human agents tend to express spatial relation or configuration by means of qualitative terms for the sake of sociable and convenient communication. We introduce a novel formal framework (called NCDC-ASP ) for qualitative reasoning about cardinal directions between spatial objects on a plane, based on Cardinal Directional Calculus (CDC) and using Answer Set Programming (ASP), and extend it further (called 3D-NCDC-ASP ) to 3-dimensional space. Each framework provides solutions to all consistency checking problems in CDC (i.e., for a complete/incomplete set of basic/disjunctive CDC constraints over connected/disconnected spatial objects); many of these consistency checking problems are NP-complete and cannot be solved with the existing systems. Furthermore, each framework extends CDC with novel types of constraints (i.e., default CDC constraints and inferred CDC constraints) to offer other types of reasoning as well (i.e., commonsense reasoning, nonmonotonic reasoning with defaults, explanation generation for inconsistencies, and inference of missing cardinal directional relations). We prove the soundness and completeness of both NCDC-ASP and 3D-NCDC-ASP , comprehensively evaluate their computational efficiency, and illustrate their usefulness with applications in different domains ranging from underwater robotics to digital forensics
Item Type: Thesis
Uncontrolled Keywords: Qualitative Spatial Reasoning. -- Answer Set Programming. -- Cardinal Directional Calculus. -- 3D Space. -- Consistency Checking. -- Nitel Uzaysal Akıl Yürütme. -- Çözüm Kümesi Programlama. -- Ana Yönlerle Hesaplama. -- Üç Boyutlu Uzay. -- Tutarlılık Kontrolü.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 09 Nov 2020 15:27
Last Modified: 26 Apr 2022 10:35
URI: https://research.sabanciuniv.edu/id/eprint/41232

Actions (login required)

View Item
View Item