So far, I’ve concluded that I needed spatial qualitative reasoning (instead of qualitative reasoning); I have decided on my spatial entities (regions) and topology (to describe the relationships among my entities) and I have defined my basic relationships between my entities (binary relations). So let’s go on, what other factors do I need to consider?

It has been shown, that there are three primitives necessary to define a theory, how they are defined will depend on the notions for “connection” used. We need to define Connection, Parthood and Fusion. All of these use a notion of “connected”; are these three notions the same or different? Actually, the first question should be: Is there a difference between connection and parthood? If you think of a region as being a set of “things”, these “things” are held together and connected; is that the same kind of “connection” that happens when to regions touch? Should you define connection and parthood based on the same connection primitive or not? Is everything within a region connected the same way as regions that connect?

There are three definitions each for Connection (C), Parthood (P) and Fusion(\sigma). We can describe what theory we are going to use by the triple <i,j,k>. For exaple, <3,1,2> means that uses C3 to define topological connection, C1 to define Parthood and C2 to define Fusion. C1 means that to sets are connected iff they share an element. C2 means that two sets are connected iff one set shares an element with the closure of another. C3 means that tow sets are connected iff the sets closures share an element. We can now define Connection, Parthood and Fusion, independent from,  dependent on or anything in between each other. <3,1,2>  is on of six theories that uses three independent primitives. There are three uniform theories and six theories where Parthood is defined in terms of topological connection, but fusion is an indpendent primitive.Depending on the type chosen, a few more axioms may be necessary, check page 11 of the paper for details.

You will also need to decide if boundaries matter or not. When two objects touch and  you zoom in really, really, really close, what does it look like:  Object A ends, Object B starts; or Object A ends, “the boundary”, Object B starts?

As it turns out <i,i,i> type theories don’t work well with boundaries. So if you wanted a <2,2,2> theory and boundaries  you will need to go back through the paper and figure out where your requirements collide.  Additionally, it actually seems that <2,1,1> is the only viable theory which will work with boundaries.

I believe that boundary-free theories are the way to go. I need a theory to solve a real-world problem. So I want a theory that makes sense for my problem. I also believe that a workable theory should not be hard to find, hence boundary-tolerant doesn’t seem as promising as boundary-free.

On the other hand, most existing boundary-free theories  are uniformely typed. My believe is that there is a difference between connection and parthood. For our problem I think we should be looking at <3,1,k> or possible <1,3,k> theories. Unfortunately, there are not many others; on the bright side, fewer papers for me to read.

Thus ends the discussion about mereotopological representation for qualitative spatial reasoning. The paper contineues, however, and covers other theories such as topology via “n-interections”, as well as theories between mereotopology and fully metric spatial representation.

The question is now, out of the possible set of relations out which one should you choose? Different sets have different advantages and disadvantages. Understanding these will help in choosing a proper theory for your problem. I might even find that my present course of action is not the best, maybe RCC-8 will not allow me to represent my problem properly.

Varzi showed that mereology is not sufficient by itself, but that integrating mereology and topology will. Hence we arrive at mereotopology. Given that topology already deals with spatial entities and as such is a necessary component, how should we work in these topology theories? Three general strategies are available:

1. Generalize mereology by adding topological primitives.
2. Topology is the primary theory and mereology is secondary.
3. Mereology is primary theory and topology is secondary.

To paraphrase: “An important familiy of theories steam from the intuition that parthood and connection cannot be defined in terms of each other.”

For now, I’m going to take a detour and explore mereotopology in more detail to ensure that I fully understand these implications. Please subscribe to my feed to hear about my next adventure.

Deciding whether or not to use QSR to solve a particular problem is an important first step. Do you need to do spatio-temporal reasoning about objects in space? Are you looking for qualitative information, such as “Object A is close to Object B and partially covers Object C” or are you looking for detailed quantitative information, such as “Object A is 5 mm from Object B”? QSR deals with qualitative information.

Let’s assume that qualitative spatial reasoning will suffice for your research problem, how do you decide what theory to use.  This paper gives you an overview of the current (2007) state of affairs in QSR and will help you figure out where to start your reading.

Here are some questions you will need to answer:

1. What kind of spatial entities will exist in your representation?
   1. points?
   2. Lines?
   3. Regions?
   4. Physical Objects?
   5. Geographic Regions?
      
2. How will you describe the relationships between these entities?
   1. Topology?
   2. Sizes?
   3. Distances?
   4. Relative Orientation?
   5. Shape?

Most of the QSR community takes regions as the primitive spatial entity, if your problem requires dealing with lines and points, keep reading to see if you can find a theory that fits your requirements.

Read this paper to find a few more questions that you should answer, which will lead you toward one or another theory.

Consider this: what primitive non logical symbols should be allowed/be in your theory without needing definition? Can you constrain them in terms of a set of axioms? To make it mathematically elegant and to have a system with a simply set of symbolic inferences, it is necessary to make the set of primitive non logical systems small. Unless you agree with Hayes and want a more complicated, but larger, richer and more natural set of symbolic inferences and thus set of primitives. An example class of primitives are relations between entities.

Reasoning over a chosen spatial entity, is the equivalent of finding the particular set of relations among all possible sets. There are an infinite number of set of relations unless we restrict ourselves to JEPD (Jointly exhaustive and pairwise disjoint). That is, each pair of entities can belong to exactly one of the JEPD relations (assuming binary relations). EC(a,b) means, that Externally Connect is a to b. A relation contains a number of tuples, one for each pair of entities that belong to it. An infinite number of squares lined up side by side would be EC{(a,b),(b,c),(c,d),….} and EQ{(a,a),(b,b),(c,c),(d,d),… } (eq = equal).

How will you represent and describe these relations among entities, what will you use? Come back tomorrow for those answers and more.

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?

Before I talk about the theory behind RCC-8, I think an example is in order. If you can’t wait for my next write-up on RCC-8 go ahead and check out the wikipedia page. I’m also going to borrow the example from the page, but I’m going to show how the path-consistency algorithm works and how the composition table is used.

Consider two houses with a road connecting them. Each house is on its own property.  The first house (h1) may or may not be touching the boundary of its property (p1) , the second house (h2)  definitely does not touch the boundary. What can we say about the second property (p2)  in regards to the road (r)?

Let’s start with what we know:

• {DC}(h1, h2)
• {TPP, NTPP}(h1, p1)
• {DC, EC}(h1, p2)
• {EC}(h1, r)
• {DC, EC}(h2, p1)
• {NTPP}(h2, p2)
• {EC}(h2, r)
• {EC, DC, PO, EQ, TPP, TPPi, NTPP, NTPPi}(r, p1)
• {EC, DC, PO, EQ, TPP, TPPi, NTPP, NTPPi}(r, p2)
• {DC, EC}(p1, p2)

The composition table can be used to find more facts about our problem. R(a, b);S(b,c) can be used to find T(a,c) (we use ; to indicate composition). To use the composition table find the entry for each element of the Cartesian product and take the union of all those. I think an example will make it clearer. Let R(a,b) = {DC, EC}(h1, p2) and S(b,c) = {DC,EC}(p2, p1). The inverse of DC = DC and the inverse of EC = EC, so if {DC, EC}(p1, p2) is true, then so is {DC, EC}(p2, p1) (the inverse of TPP/NTPP are TPPi/NTPPi). T(a,c) = {?, ?}(h1, p1).  The elements of the Cartesian product of {DC, EC}x{DC, EC} are {{DCxDC}, {DCxEC}, {ECxDC}, {ECxEC}}. Looking up those combinations in the composition table and taking the union of all is {*}, where * is the universal relation.  In this case we didn’t learn anything more, actually we already know more about the relation between h1 and p1.

What we really want is to find more information about (r, p2).  For that we can try {EC}(r, h2) and {NTPP}(h2, p2). The result is {PO, TPP, NTPP}(r, p2). Now we have greatly reduced the possibly relations for (r, p2) from eight to three.  We can continue to use the composition table to find new information about the relations.  Try using the compostion table yourself and see what other information about these relations you can find.

The next part to answering our query is using past-consistency. Given three relations R(xy), S(y,z) and T(x,z) we can find new information by applying path-consistency = {(R; S) intersect T} (x,z). That is we use the composition table to find (R; S) and then the intersection with T. Let’s look at an example. R(x, y)= {EC}(r, h2), S(y,z) ={NTPP}(h2, p2) and T(x, z) = {PO, TPP, NTPP}(r, p2). {R;S} = {PO, TPP, NTPP} intersect {PO, TPP, NTPP} = {PO, TPP, NTPP}. If the intersection is the empty set, you’ve found an inconsistency.

Your overall approach to using the composition table and applying path-consistency should be similar to this:

1. Create all useful combinations of possible relations using the composition table. For example, make sure that there is a relations for(h1, h2), (h1, p1), (h1, p2), (h1, r) …  You don’t need to write down both directions i.e. (h1, h2) and (h2, h1), but only need to remember the inverses of the eight relations.
2. Create and list all possible pairs of relations: (h1, h2)(h2,p1), (h1, h2)(h2, p2), (h1,h2)(h2, r) … and use path consistency to learn new information. Here is an example, (h2, p2)(p2, p1) intersect (h2, p1) = NTPP; {DC, EC} intersect {DC, EC} = {DC} intersect {DC, EC} = {DC}. Now we know that (h2, p1) is not {DC, EC}, but is really only {DC}.
3. Make a note of all relations which have changed due to step 2.
4. Continue until you reach the end of the list or find an inconsistency. If you reach the end without an inconsistency, then go back through the list and check all path-consistencies involving of the relations marked in step 3.
5. Repeat steps 2 – 4 until all relations remain unchanged.

For more mathematical details check out these lecture slides form the University of Leeds.

I will share what I learn and hopefully you will find it useful in your own research. The goal of Qualitative Reasoning (QR) is to enable computers/programs to reason about physical systems without the need for precise quantitative information [1]. Numerical simulations, for example, use precise data. QR is concerned with representing, problem solving and reasoning about the (physical) world.  QR is something all of us do at some point during the day:  merging into traffic (we do not know the exact speed other cars are traveling at or exactly how far away they are, yet we are able to merge without accidents). In determining whether it is save to merge, we use qualitative knowledge instead of precise quantitative knowledge. Despite of having imprecise data and sometimes even missing data, we are able to navigate the roads successfully.

QSR is an subfield o QR that is concerned with qualitative reasoning in space. For example, imagine you are at the zoo, talking to a friend about birds in the cage. Clearly, you are unable to measure exact distanced, but you are able to describe what you are looking at by saying things like “The blue bird on the top, left back of the cage.” This would be a QSR representation of the location of the blue bird.

QSR is used by geographical information systems (GIS), robotic vision, bio-informatics and many others.  Next, I will talk about some existing languages that are used in QSR, particularly, RCC-8. What other areas of reasearch make use of QR and/or QSR? Can you imagine some other applications?

This paper has been accepted at IEEE WCNC 2009. Feel free to read it  here and leave me your feedback.

Using partitioning in sensor networks to create clusters used for routing, data management and other protocols has been proven as a way to ensure scalability and to deal with shortcomings of sensor networks such as limited communication ranges and energy. Cluster heads use additional energy for their responsibilities and that burden needs to be carefully passed around. Many existing clustering protocols choose cluster heads either randomly or use nodes with the highest remaining energy. We introduce the energy constrained minimum dominating set (ECDS) problem to model the problem of optimally choosing cluster heads with energy constrains. We show its applicability to sensor networks and give an approximation algorithm of O(log n) for solving the ECDS problem. We propose a distributed algorithm for the constrained dominating set and experimentally show that it outperforms the greedy algorithm. We show experimentally that our heuristics are good approximations in random networks.

A paper has been submitted to IEEE MASS 2009.  The current version of this paper is here. If you read it and have any corrections/suggestions for improvment, I would appreciate the feedback.