Review of “Qualitative Spatial Representation and Reasoning” (A. G. Coh and J. Renz, 2007)
Now that I have a better understanding of QSR and the theory behind it, I thought it would be a good idea to reread some articles. I often find, that I can gain greater understanding about research by re-reading articles. This particular article by Cohn and Renz part of a book on Knowledge Representation (KR) (A. G. Cohn and J. Renz, Qualitative Spatial Representation and Reasoning, in: F. van Hermelen, V. Lifschitz, B. Porter, eds., Handbook of Knowledge Representation, Elsevier, 551-596, 2008. ). I had already reread sections 1.1 and 1.2 when I thought of writing about it, so my thoughts on those sections will come at a later point.
Section 1.3 Spatial Reasoning
I didn’t notice this particular paragraph the first time around:
… For some purposes it is enough to have a representation for spatial knowledge, but what makes intelligent systems intelligent is their ability to reason about given knowledge. There are different reasoning tasks an intelligent system might have to perform. These include deriving new knowledge from the given information, checking consistency of given information, updating the given knowledge, or finding a minimal representation. Even though these reasoning problems are quite idfferent, they can be transformed into each other, and algorithms developed for one reasoning problem can often easily be modified to solving other reasoning problems.
That is very good news for me. How I could have missed it the first time, I don’t know, but it shows that it pays to revisit some papers. I spend several days learning how to reason with RCC-8. The results of which you can read in my post on RCC-8. This section re-iterates for me what I discovered while learning about RCC-8. Additionally, this section covers deduction. For me to note here was the fact that modal logic encodings of RCC-8 led to a classical propositional encoding which opened up the possibility of using modern SAT solvers. The authors also discuss composition and the composition table. I also learned that in some cases, weak composition must be used. For example, the RCC-8 composition table is actually a weak composition table.
The authors move on to discuss constraint-based spatial reasoning. The path-consistency algorithm is the best known constraint propagation algorith for spatial CSP. However, when the composition table is only weak-composition, then the algebraic-closure algorithm should be used instead. There is discussion regarding backtracking algorithms and how to improve performance of the algorithm. I will need to explore the backtracking algorithm in more detail, especially to gain better understanding of how to improve the performance.
It seems that there is still considerable research necessary until we have efficient algorithms for spatial constrainted based reasoning. Among these are:
- Algorithms to determine if a given arbitrary subset istractable.
- Algorithms to find candidate subsets.
- Proving that subsets are maximal tractable
Work has been done in this area and I’m off investigating their usefulness for our project.
For some reason, I have trouble keeping maximum and maximal straight in my head. Here’s an example Cormen uses in Introduction to Algorithms, it has helped me remember the differences. “For example, in a collection of different-sized boxes there may be several maximal boxes that don’t fit inside any other box, yet no single “maximum” box into which any other box will fit”.
Are there any examples you use for similar issues?
March 4, 2009 15:25 
Subscribe