A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming

George Baryannis, Ilias Tachmazidis, Sotiris Batsakis, Grigoris Antoniou, Mario Alviano, Timos Sellis, Pei Wei Tsai

Research output: Contribution to journalArticle

1 Citation (Scopus)
42 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)355-371
Number of pages17
JournalTheory and Practice of Logic Programming
Volume18
Issue number3-4
DOIs
Publication statusPublished - 1 Jul 2018

Fingerprint

Qualitative Spatial Reasoning
Answer Set Programming
Calculus
Trajectories
Trajectory
Encoding
Reasoning
Route Planning
Scale-up
Spatial Information
Term
Moving Objects
Natural Language
Cycle
Planning
Path
Configuration

Cite this

@article{2d1f8d450b634e569d5a2b1ce03d2791,
title = "A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming",
abstract = "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.",
keywords = "Answer Set Programming, Spatial Reasoning, Qualitative Reasoning, Trajectory",
author = "George Baryannis and Ilias Tachmazidis and Sotiris Batsakis and Grigoris Antoniou and Mario Alviano and Timos Sellis and Tsai, {Pei Wei}",
note = "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. {\circledC} Cambridge University Press 2018",
year = "2018",
month = "7",
day = "1",
doi = "10.1017/S147106841800011X",
language = "English",
volume = "18",
pages = "355--371",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "3-4",

}

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.

In: Theory and Practice of Logic Programming, Vol. 18, No. 3-4, 01.07.2018, p. 355-371.

Research output: Contribution to journalArticle

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 -