Qualitative Spatial Reasoning Based on Algebraic Topology

Several formalisms have been proposed for qualitativereasoning about regions and their topological relations in space. Theseformalisms, based on pairwise relations, do not allow sufficientlypowerful inferences to be used for spatial reasoning tasks such asplanning a collision-free path. In this paper, I show how consideringrelations between region triples, much more powerful reasoningtechniques become possible. I show in particular that in twodimensions, purely topological reasoning is sufficient to compute aminimal place graph which represents all minimal and maximal regioncombinations, as well as all minimal paths between them. I illustratehow this could be applied to motion planning, showing that in spite ofits qualitative nature, the formalism is powerful enough to solveproblems of practical interest