Qualitative Topological Reasoning

Spatial reasoning is a major field of study in Artificial Intelligence, especially in Knowledge Representation. This field has gained a lot of attention during the last few years as it extends to a plethora of areas and domains that include, but are not limited to, ambient intelligence, dynamic GIS, cognitive robotics, and spatiotemporal design. In this context, an emphasis has been made on qualitative spatial reasoning which relies on qualitative abstractions of spatial aspects of the common-sense background knowledge, on which our human perspective on the physical reality is based. The concise expressiveness of the qualitative approach provides a promising framework that further boosts research and applications in the aforementioned areas and domains.

A subset of the Region Connection Calculus (RCC), namely RCC-8, is the dominant Artificial Intelligence approach for representing and reasoning about topological relations. RCC can be used to describe spatial regions that are non-empty regular subsets of some topological space by stating their topological relations to each other.

Within TELEIOS we have developed PyRCC8, an open source, efficient reasoner for RCC-8 written in pure Python. PyRCC8 is implemented using PyPy, a fast, compliant implementation of the Python 2 language. To the best of our knowledge, PyRCC8 is the first implementation of a RCC-8 reasoner on top of a trace-based JIT compiler. Previous implementations have used either static compilers, e.g., Renz’s solver and GQR, or method-based JIT compilers, e.g., the RCC-8 reasoning module of the description logic reasoner PelletSpatial. The advantage of trace-based JIT compilers is that they can discover optimization opportunities in common dynamic execution paths, that are not apparent to a static compiler or a method-based JIT compiler. PyRCC8 was found to exhibit excellent experimental results and demonstrate the advantages of this particular implementation, but also the potential benefits of trace-based JITs over static compilers. Finally, PyRCC8 has served as the basis for a reasoner for chordal RCC-8 networks, called PyRCC8-TRIANGLE, that we have also developed within TELEIOS taking on a different research direction. PyRCC8-TRIANGLE further boosts the consistency checking process of sparse RCC-8 networks by making their underlying constraint graphs chordal rather than complete as is the case with the state of the art reasoners including PyRCC8.

See the paper Consistency of Chordal RCC-8 Networks for more details.