A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming
Spatial information is often expressed using qualitative terms such as natural language expressions instead of coordinates; reasoning over such terms has several practical applications, such as bus routes planning. Representing and reasoning on trajectories is a specific case of qualitative spatial reasoning that focuses on moving objects and their paths. In this work, we propose two versions of a trajectory calculus based on the allowed properties over trajectories, where trajectories are defined as a sequence of non-overlapping regions of a partitioned map. More specifically, if a given trajectory is allowed to start and finish at the same region, 6 base relations are defined (TC-6). If a given trajectory should have different start and finish regions but cycles are allowed within, 10 base relations are defined (TC-10). Both versions of the calculus are implemented as ASP programs; we propose several different encodings, including a generalised program capable of encoding any qualitative calculus in ASP. All proposed encodings are experimentally evaluated using a real-world dataset. Experiment results show that the best performing implementation can scale up to an input of 250 trajectories for TC-6 and 150 trajectories for TC-10 for the problem of discovering a consistent configuration, a significant improvement compared to previous ASP implementations for similar qualitative spatial and temporal calculi. This manuscript is under consideration for acceptance in TPLP.
Code (1)
Tasks
Spatial ReasoningSimilar Papers 제목 키워드 기반
QSTRBench: a New Benchmark to Evaluate the Ability of Language Models to Reason with Qualitative Spatial and Temporal Calculi
We introduce an extensive qualitative spatial and temporal reasoning (QSTR) benchmark for evaluating large language models (LLMs). We pose questions concerning compositional reasoning (using composition tables, CT), conv…
Algebraic Properties of Qualitative Spatio-Temporal Calculi
Qualitative spatial and temporal reasoning is based on so-called qualitative calculi. Algebraic properties of these calculi have several implications on reasoning algorithms. But what exactly is a qualitative calculus? A…
General ClassificationFine-grained Qualitative Spatial Reasoning about Point Positions
The ability to persist in the spacial environment is, not only in the robotic context, an essential feature. Positional knowledge is one of the most important aspects of space and a number of methods to represent these i…
Spatial ReasoningAn Evaluation of ChatGPT-4's Qualitative Spatial Reasoning Capabilities in RCC-8
Qualitative Spatial Reasoning (QSR) is well explored area of Commonsense Reasoning and has multiple applications ranging from Geographical Information Systems to Robotics and Computer Vision. Recently many claims have be…
Spatial ReasoningReasoning about Qualitative Direction and Distance between Extended Objects using Answer Set Programming
In this thesis, we introduce a novel formal framework to represent and reason about qualitative direction and distance relations between extended objects using Answer Set Programming (ASP). We take Cardinal Directional C…
Negation