A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming

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

T2 - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 3-4

ER -