Homotopy and Alternative Routes in Indoor Navigation Scenarios
Our paper Homotopy and Alternative Routes in Indoor Navigation Scenarios has been accepted and presented at the 5th International Conference on Indoor Positioning and Indoor Navigation (IPIN 2014) in Busan, Korea. We are very proud that the paper received the Best Paper Award this year. This post is intended to give some additional material related to our paper.
The main contribution of the paper is a working definition of alternative routes in indoor navigation scenarios. Therefore, we employ the topological concept of homotopy (in a simplified form, which can efficiently be calculated). We define two routes having the same start and end point to be alternative if they do not share the same homotopy class. But if they do, we call them equivalent. This equivalence relation is then approximately calculated by a scanline polygon filling algorithm for the two-dimensional case. Further, we provide an algorithm to efficiently enumerate these classes and a data structure which can be used to store a useful subset of homotopy classes, the One-Patchings. A one-patching is a concatenation of two shortest paths and models alternative ways by specifying the one point which is neither the start nor the endpoint. Further, we implemented an indoor version of the well-known Penalty algorithm, that is used in street maps to find alternative routes. See for example "Evolution and Evaluation of the Penalty Method for Alternative Graphs" by Kobitzsch et al., a recent paper that provides a first viable implementation of the algorithm.
When evaluating our algorithms we got two side-products. The first one is a represenation of the given indoor scenario we called reference map.
You can read it as follows: Let's say you choose one of the red points as a supporting point, i.e. you walk the shortest path from start to that particular point and from that point a shortest path to the goal. If you would choose one of the other red points as a supporting point, you get a one-patching route that is considered as equivalent to the first one. Thus, they are two different routes from "class red", not alternative to each other in the sense of the homotopy relation. Additionally, you see on the left hand side another color (green) as well as on the right hand side (orange). This means, you have alternative routes to the ones straight through the two obstacles, namely passing to the left or right, respectively. To put it in other words: We inserted a semantic into the formerly binary floormap. This map can be used in higher layer applications to quickly generate alternative routes and to understand the topology of the building relative to the used starting point and end point.
Another side-product was the heatmap created by the Penalty algorithm.
The penalty algorithm generally works by calculating the shortest path from start to the goal and, afterwards, penalizing all the edges of this path by incrementing their weights. This is continued until a certain number of iterations is reached or a certain number of different paths is found. The figure is again useful to understand the internal semantics of a floormap. One can clearly see that there is a door that connects the west part of the building with the east part. This means, each of the alternative routes has to pass this area. Further, the color indicates how often a specific area was part of a shortest penalty route. This seems to correctly detect relevant bottlenecks, which can - of course - be used for navigation and positioning.