Qualitative reasoning about 2D cardinal directions using answer set programming

Izmirlioglu, Yusuf and Erdem, Esra (2023) Qualitative reasoning about 2D cardinal directions using answer set programming. Journal of Artificial Intelligence Research, 77 . pp. 1371-1453. ISSN 1076-9757

Full text not available from this repository. (Request a copy)


We introduce a formal framework (called NCDC-ASP ) for representing and reasoning about cardinal directions between extended spatial objects on a plane, using Answer Set Programming (ASP). NCDC-ASP preserves the meaning of cardinal directional relations as in Cardinal Directional Calculus (CDC), and provides solutions to all consistency checking problems in CDC under various conditions (i.e., for a complete/incomplete set of basic/disjunctive CDC constraints over connected/disconnected spatial objects). In particular, NCDC-ASP models a discretized version of the consistency checking problem in ASP, over a finite grid (rather than a plane), where we provide new lower bounds on the grid size to guarantee that it correctly characterizes solutions for the consistency checking in CDC. In addition, NCDC-ASP has the following two novelties important for applications. NCDC-ASP introduces default CDC constraints to represent and reason about background or commonsense knowledge that involves default qualitative directional relations (e.g., "the ice cream truck is by default to the north of the playground"or "the keyboard is normally placed in front of the monitor"). NCDC-ASP introduces inferred CDC constraints to allow inference of missing CDC relations and to provide them as explanations. We illustrate the uses and usefulness of NCDC-ASP with interesting scenarios from the real-world. We design and develop a variety of benchmark instances, and comprehensively evaluate NCDC-ASP from the perspectives of computational efficiency.
Item Type: Article
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Esra Erdem
Date Deposited: 27 Sep 2023 14:44
Last Modified: 27 Sep 2023 14:44
URI: https://research.sabanciuniv.edu/id/eprint/48096

Actions (login required)

View Item
View Item