### Abstract

Original language | English |
---|---|

Pages (from-to) | 355-371 |

Number of pages | 17 |

Journal | Theory and Practice of Logic Programming |

Volume | 18 |

Issue number | 3-4 |

DOIs | |

Publication status | Published - 1 Jul 2018 |

### Fingerprint

### Cite this

*Theory and Practice of Logic Programming*,

*18*(3-4), 355-371. https://doi.org/10.1017/S147106841800011X

}

*Theory and Practice of Logic Programming*, vol. 18, no. 3-4, pp. 355-371. https://doi.org/10.1017/S147106841800011X

**A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming.** / Baryannis, George; Tachmazidis, Ilias; Batsakis, Sotiris; Antoniou, Grigoris; Alviano, Mario; Sellis, Timos; Tsai, Pei Wei.

Research output: Contribution to journal › Article

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 -