Homotopy and alternative routes in indoor navigation scenarios

Martin Werner, Sebastian Feld

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

There are lots of innovative use cases possible that build on a shortest route between two locations together with a set of alternatives that are highly different yet short. Imagine, for example, a complicated building like an airport, where passengers can consult a computer terminal to get navigation advices to a desired goal. By scanning the boarding card the calculation of alternatives can be made context-sensitive. Based on gender, amount of time, or shopping preferences, for example, the terminal can display different routes regarding floors traversed, or shops and restaurants passed. Furthermore, the building operator can control the presentation of alternatives in order to influence visitor flows in real time. Therefore, we propose to use the topological concept of homotopy in order to decide if two routes should be considered equivalent or alternative. Basically, the homotopy relation identifies equivalence classes. We propose that a representative of an equivalence class is an alternative regarding another equivalence class. We concatenate the two routes in question and thus, create a polygon. If there is an obstacle inside, the routes are non-homotopic and we consider them as proper alternatives. For this situation, we propose two fundamentally different approaches that are able to find alternative routes with respect to homotopy. The input is a building plan in form of an occupancy grid. Bitmaps allow for fast calculation of the homotopy relation and can be generated from almost any type of environmental model. The first approach aims for enumerating routes that have to visit a special supporting point. This concatenation of two shortest paths leads to alternatives very fast. The second approach is orthogonal to that in the sense that it generates alternatives roughly ordered by their length. Finally, we evaluate and discuss the approaches' feasibility based on different metrics in several scenarios.

Original languageEnglish
Title of host publicationIPIN 2014 - 2014 International Conference on Indoor Positioning and Indoor Navigation
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages230-238
Number of pages9
ISBN (Electronic)9781467380546
DOIs
StatePublished - 2014
Externally publishedYes
Event5th International Conference on Indoor Positioning and Indoor Navigation, IPIN 2014 - Busan, Korea, Republic of
Duration: 27 Oct 201430 Oct 2014

Publication series

NameIPIN 2014 - 2014 International Conference on Indoor Positioning and Indoor Navigation

Conference

Conference5th International Conference on Indoor Positioning and Indoor Navigation, IPIN 2014
Country/TerritoryKorea, Republic of
CityBusan
Period27/10/1430/10/14

Fingerprint

Dive into the research topics of 'Homotopy and alternative routes in indoor navigation scenarios'. Together they form a unique fingerprint.

Cite this