We study reasoning about relative position, orientation and distance of moving objects in 2D space. We first construct a new hybrid calculus HOPA by augmenting qualitative distance and quantitative constraints into Oriented Point Relation Algebra (OPRA). Then we develop a framework for consistency checking and reasoning with HOPA using Answer Set Programming. This framework can also explain the source of inconsistency, infer new knowledge and generate a layout of objects and their orientation in the discrete space. The framework is capable of reasoning with (un)certain, heterogenous and presumed information. We evaluate efficiency and scalability of our method by computational experiments, and illustrate its applications with sample scenarios from robotic perception and marine navigation.

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.

Abstract We propose a novel formal framework (called 3D-NCDC-ASP) to represent and reason about cardinal directions between extended objects in 3-dimensional (3D) space, using Answer Set Programming (ASP). 3D-NCDC-ASP extends Cardinal Directional Calculus (CDC) with a new type of default constraints, andNCDC-ASP to 3D. 3D-NCDC-ASP provides a flexible platform offering different types of reasoning: Nonmonotonic reasoning with defaults, checking consistency of a set of constraints on 3D cardinal directions between objects, explaining inconsistencies, and inferring missing CDC relations. We prove the soundness of 3D-NCDC-ASP, and illustrate its usefulness with applications.

We propose a novel method for representing and reasoning about an incomplete set of constraints about basic/disjunctive qualitative direction relations over simple/connected/disconnected regions, using Answer Set Programming, and prove its correctness with respect to cardinal direction calculus. We extend this method further with default qualitative direction constraints, and discuss its usefulness with some sample scenarios.

The multi-agent meeting (MAM) problem asks for a meeting location for multiple heterogeneous agents such that the agents can get together within a given time or budget, possibly using different modes of transportation, subject to some constraints and preferences to visit specific locations on their ways to the meeting location. We mathematically model MAM as a graph problem, prove its intractability, and introduce a novel formal method to solve it and its variations using logic-based AI methods. We experimentally evaluate our approach with artificial benchmarks randomly generated over a grid, and show its real world applicability with instances generated over maps of Istanbul and Hong Kong.