A trajectory calculus for qualitative spatial reasoning using answer set programming
From MaRDI portal
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. This manuscript is under consideration for acceptance in TPLP.
Recommendations
- Answer Set Programming for Qualitative Spatio-temporal Reasoning: Methods and Experiments
- A Generalised Approach for Encoding and Reasoning with Qualitative Theories in Answer Set Programming
- A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems
- ASPMT(QS): Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
- Non-monotonic spatial reasoning with answer set programming modulo theories
Cites work
- A general qualitative spatio-temporal model based on intervals
- A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems
- A survey of complexity results for non-monotonic logics
- Abstract gringo
- Answer Set Programming for Qualitative Spatio-temporal Reasoning: Methods and Experiments
- Big data: algorithms, analytics, and applications
- Handbook of constraint programming.
- scientific article; zbMATH DE number 2044736 (Why is no real title available?)
- Non-monotonic spatial reasoning with answer set programming modulo theories
Cited in
(10)- Modal logic S5 in answer set programming with lazy creation of worlds
- ASPMT(QS): Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
- scientific article; zbMATH DE number 2044758 (Why is no real title available?)
- Modal logic S5 satisfiability in answer set programming
- scientific article; zbMATH DE number 7453140 (Why is no real title available?)
- A Generalised Approach for Encoding and Reasoning with Qualitative Theories in Answer Set Programming
- Reasoning about cardinal directions between 3-dimensional extended objects using answer set programming
- A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems
- Answer Set Programming for Qualitative Spatio-temporal Reasoning: Methods and Experiments
- Qualitative reasoning about 2D cardinal directions using answer set programming
This page was built for publication: A trajectory calculus for qualitative spatial reasoning using answer set programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4559799)
