License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.GIScience.2021.II.11
URN: urn:nbn:de:0030-drops-147700
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14770/
Kreller, Isabella ;
Ludwig, Bernd
User Preferences and the Shortest Path
Abstract
Indoor navigation systems leverage shortest path algorithms to calculate routes. In order to define the "shortest path", a cost function has to be specified based on theories and heuristics in the application domain. For the domain of indoor routing, we survey theories and criteria identified in the literature as essential for human path planning. We drive quantitative definitions and integrate them into a cost function that weights each of the criteria separately. We then apply an exhaustive grid search to find weights that lead to an ideal cost function. "Ideal" here is defined as guiding the algorithm to plan routes that are most similar to those chosen by humans. To explore which criteria should be taken into account in an improved pathfinding algorithm, eleven different factors whose favorable impact on route selection has been established in past research were considered. Each factor was included separately in the Dijkstra algorithm and the similarity of thus calculated routes to the actual routes chosen by students at the University of Regensburg was determined. This allows for a quantitative assessment of the factors’ impact and further constitutes a way to directly compare them. A reduction of the number of turns, streets, revolving doors, entryways, elevators as well as the combination of the aforementioned factors was found to have a positive effect and generate paths that were favored over the shortest path. Turns and the combination of criteria turned out to be most impactful.
BibTeX - Entry
@InProceedings{kreller_et_al:LIPIcs.GIScience.2021.II.11,
author = {Kreller, Isabella and Ludwig, Bernd},
title = {{User Preferences and the Shortest Path}},
booktitle = {11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-208-2},
ISSN = {1868-8969},
year = {2021},
volume = {208},
editor = {Janowicz, Krzysztof and Verstegen, Judith A.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14770},
URN = {urn:nbn:de:0030-drops-147700},
doi = {10.4230/LIPIcs.GIScience.2021.II.11},
annote = {Keywords: Pedestrian Navigation Systems, Wayfinding, Computation of Optimal Paths, User Preferences for Best Routes}
}
|
Keywords: |
|
Pedestrian Navigation Systems, Wayfinding, Computation of Optimal Paths, User Preferences for Best Routes |
|
Collection: |
|
11th International Conference on Geographic Information Science (GIScience 2021) - Part II |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
14.09.2021 |
