| Date: | 2015, June 3 |
| Time: | 11:00 |
| Author: | Mossakowski, Till |
| Title: | Left and Right are Harder Than West and East – Qualitative Spatial Reasoning About Relative Orientation |
Qualitative spatio-temporal reasoning abstracts from quanitative numerical values.
Instead, qualitative concepts know to humans are used, such as
“left”, “right”, “front”, “back”,
“West”, “East”, “inside”, “touches”, “before” etc.
We introduce the traditional approach to qualitative spatio-temporal reasoning
based on composition tables and algebraic closure.
While this approach works quite well for time, mereotopology and absolute directions,
it has severe limitations for reasoning about relative directions.
Indeed, the latter reasoning is computationally hard, namely as hard as deciding satisfiability
in the existential theory of the reals, which is located between NP and PSPACE.
We summarize a number of incomplete semi-decision procedures for relative orientation
and present the results of a benchmark illustrating the relative effectiveness and efficiency of these procedures.