What is qualitative spatial reasoning (QSR)?
According to (Renz y Nebel, 2007), "Qualitative reasoning is an approach for dealing with commonsense knowledge without using numerical computation. Instead, one tries to represent knowledge using a limited vocabulary such as qualitative relationships between entities or qualitative categories of numerical values [...] An important motivation for using a qualitative approach is that it is considered to be closer to how humans represent and reason about commonsense knowledge."
Freksa and Röhrig (1993) state that "Qualitative reasoning is based on comparative knowledge rather than on metric information."
Regarding space, this kind of reasoning involves relations among spatial entities, taking into account aspects such as topology, orientation and distance.
QSR is used in artificial intelligence, by and large applied in robots and represents an open research field in the realm of cognitive sciences.
What is a qualitative spatial calculus?
According to the SparQ user manual (p.7), "A qualitative calculus consists of a set of relations between objects from a certain domain
and operations defined on these relations."
For instance, the calculus proposed by Moratz, Renz y Wolter (2000), the dipole calculus, is based on relations between pairs of oriented segments. Such relations are jointly exhaustive and pairwise disjoint (JEPD), i.e. together they contain all the Universe and none of them contains an item (pair of dipoles) in common. The relations for this calculus are (Source: Moratz et al. 2000):
By means of checking consistency of given scenarios (constraints) one can reason discarding contradictory situations and taking possible situations. This approach is given by the aforementioned authors (section 6.) in a sample application of the calculus and it represents the basis of the algorithm we are proposing.
What is SparQ?
SparQ is a framework for QSR that collects several kinds of calculus proposed by the QSR community, such as the Cardinal Direction Calculus, OPRA, Panorama y Dipole Calculi. It is written in C++, distributed under GNU GPL and developed by the universities of Bremen and Freiburg in Germany.
The main objective of this exercise is to take a network consisting of dipoles (edges with a start and an end node) and to get a route by using QSR, specifically by means of the Dipole Calculus.
By and large, the algorithm consists of checking scenarios in which there is a current dipole, a set of candidate dipoles and a target dipole:
If one of the candidate dipoles holds a consistent scenario, it is subsequently taken as current dipole, and then the process starts again. More explicitly:
- A set of dipoles (in a graph data structure).
- Starting dipole (sd) to define the route.
- Target dipole (td) to define the route.
- SparQ modules: Qualify, Consistency.
- Constraint "(ells errs lere rele)" to check the consistency of scenarios in which it is likely that a candidate dipole is connected to td.
- Create the set next_dipoles and add sd.
- If next_dipoles has more than 0 dipoles, take the last one (the first time it runs, the last dipole is sd), else, go back to take an alternative dipole as current dipole (cd).
- Take one of the nodes of cd as current node (cn).
- Describe the relation cd-td: Qualify(cd, td)
- Get the dipoles connected to cn (candidate dipoles): graph.getEdges()
- Check if any of the candidate dipoles corresponds to td, if so, finish the process and return the route.
- If there is only one dipole, initialize next_dipoles as that dipole and go to 11. If there is more than one candidate go to 8.
- Initialize next_dipoles.
- For each candidate dipole (c) describe the relation c-cd: Qualify(c, cd).
- Check the consistency of the scenario given by: 4., 8. and the constraint "ells errs lere rele" between the current candidate and td. If it is consistent, add the candidate dipole to next_dipoles.
- Go back to 2.
There is a network file representing a small part of the road network of Münster, Germany (see Downloads section). By means of Python and QGIS the coordinates of each dipole are extracted and converted into a graph structure that was built to make easier the algorithm execution.
After getting the IDs of the starting and target dipoles some SparQ commands are called to get the description of the initial situation of the dipoles and discard candidate dipoles based upon the consistency of scenarios. The calculated route is converted into a memory Shapefile and shown in QGIS as a new layer on the map.
In summary, it was developed a QGIS plugin with no GUI, that gets a road network shapefile and the starting and target dipoles, calls SparQ commands to get the route and finally visualize it in QGIS.
For the execution of the plugin the road network layer has to be in the first position of the QGIS table of contents (TOC). Some information related to the process is printed in the Python console in QGIS.
The "Qualitative Spatian Reasoning for routing" plugin can be downloaded from this link. It is required to specify the SparQ directory installation in algorithm.py
SparQ can be accessed from http://www.sfbtr8.uni-bremen.de/project/r3/sparq/, where the user manual can be found indicating the installation process.
The network file (shapefile) for testing can be downloaded from this link.
The result is not necessarily the shortest nor the simplest route, it is just a route.
In order to avoid complexity, the algorithm does not take into account the dipoles' direction and gets the starting and target dipoles from IDs instead of supporting graphic selection of dipoles or even a couple of points as start and end.
The time spent doing the calculations is considerable, specially knowing that from the same information (coordinates) it is possible to use much more efficient algorithms such as Dijkstra or A* (A-Star).
Unfortunately, the algorithm was not exhaustively tested, only the given network and the selected dipoles were used. A second try to improve the algorithm could be done on demand. However, the algorithm can be taken as a basis for further work in the topic.
Christoph Mülligann, Joao Blasques, Jafar Hafiz, Sergio Clark, Talakisew Binor, Dian Melati, Avit Bhowmik, Yitea Getahun, Minu Limbu, Germán Carrillo.
This exercise was done for the "Qualitative Spatial Knowledge Reasoning and Representation" course, given by Malumbo Chipofya at the Institut für Geoinformatik (ifgi), Universität Münster, Germany.
- Freksa, C. and Röhrig, R. (1993). Dimensions of qualitative spatial reasoning, In N. P. Carrete and M. G. Singh, editors, Qualitative reasoning and decision technologies, Proc. QUARDET93, 483-492, Barcelona.
- Moratz, R., Renz, J. & Wolter, D. (2000). Qualitative spatial reasoning about line segments. ECAI, 2000, pp 234-238.
- Renz, J. and Nebel, B. (2007). Qualitative spatial reasoning using constraint calculi, In: Handbook of Spatial Logics, M. Aiello and I. E. Pratt-Hartmann and J. F.A.K. van Benthem (eds), pp. 161-215, Springer.
- Wallgrün, J., Frommberger, L., Dylla, F. and Wolter, D. (2010). SparQ User Manual V0.7. SFB/TR 8 Spatial Cognition - Project R3-[Q-Shape].