Scoring of alternative routes using implicit building topologies

Abstract

Currently navigation in indoor scenarios enjoys a highly increasing popularity. Besides that, there are numerous applications that utilize alternatives to a particular path. Think of a navigation system that proposes a mall's visitor three different routes: the fastest, a route passing restaurants, and a route traversing shops. Thus, the visitor is able to choose a route by personal preference or experience. Further users of alternative routes can be fire fighters, mobile robots, or nonplayer characters in video games. In contrast to navigation in road networks, there are several challenges to solve in indoor scenarios. First, the creation of alternative routes is not much discussed in literature. Second, due to the high degree of freedom there is a large number of alternative routes possible regarding a reference path. Third, there is no proper understanding of how to measure the meaningfulness or quality of an alternative route. This paper is a step towards the evaluation of alternative routes in indoor navigation scenarios and has got two main contributions. First, we propose to use the term congestion probability as a first common understanding to estimate the meaningfulness of alternative routes inside buildings. Most of the indoor use cases are looking for routes that either seek or avoid crowded areas - at least as one of multiple criteria. Additionally, we propose to score alternative routes based on a local and a global perception. The paper's second contribution is an algorithm that scores a set of alternative routes based on an ordinary floor plan. Thus, it compares a formerly non-valuated set of routes and creates a ranking regarding the congestion probability. Basically, the algorithm is based on the assumption that points on a map, that are frequently located on shortest paths, will also be frequently traversed. Due to the lack of appropriate data sets we discuss the algorithm's results in detail by means of four different indoor scenarios.