TY - JOUR
T1 - A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming
AU - Baryannis, George
AU - Tachmazidis, Ilias
AU - Batsakis, Sotiris
AU - Antoniou, Grigoris
AU - Alviano, Mario
AU - Sellis, Timos
AU - Tsai, Pei Wei
N1 - This article has been published in a revised form in Theory and Practice of Logic Programming [https://doi.org/10.1017/S147106841800011X]. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © Cambridge University Press 2018
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
KW - Answer Set Programming
KW - Spatial Reasoning
KW - Qualitative Reasoning
KW - Trajectory
UR - http://www.scopus.com/inward/record.url?scp=85051395424&partnerID=8YFLogxK
U2 - 10.1017/S147106841800011X
DO - 10.1017/S147106841800011X
M3 - Article
VL - 18
SP - 355
EP - 371
JO - Theory and Practice of Logic Programming
JF - Theory and Practice of Logic Programming
SN - 1471-0684
IS - 3-4
ER -