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...

Full description

Saved in:
Bibliographic Details
Published in:Theory and practice of logic programming 2018-07, Vol.18 (3-4), p.355-371
Main Authors: BARYANNIS, GEORGE, TACHMAZIDIS, ILIAS, BATSAKIS, SOTIRIS, ANTONIOU, GRIGORIS, ALVIANO, MARIO, SELLIS, TIMOS, TSAI, PEI-WEI
Format: Article
Language:English
Subjects:
Calculus
Cognition & reasoning
Mathematical programming
Natural language (computers)
Original Article
Qualitative reasoning
Reasoning
Spatial data
Trajectories
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1471-0684
1475-3081
DOI:10.1017/S147106841800011X