Document Open Access Logo

User Preferences and the Shortest Path

Authors Isabella Kreller, Bernd Ludwig

PDF
Thumbnail PDF

File

LIPIcs.GIScience.2021.II.11.pdf
  • Filesize: 0.95 MB
  • 15 pages

Document Identifiers

Author Details

Isabella Kreller
  • University of Regensburg, Germany
Bernd Ludwig
  • University of Regensburg, Germany

Cite As Get BibTex

Isabella Kreller and Bernd Ludwig. User Preferences and the Shortest Path. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.GIScience.2021.II.11

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.

Subject Classification

ACM Subject Classification
  • Human-centered computing
  • Human-centered computing → Empirical studies in ubiquitous and mobile computing
Keywords
  • Pedestrian Navigation Systems
  • Wayfinding
  • Computation of Optimal Paths
  • User Preferences for Best Routes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Imad Afyouni, Cyril Ray, and Claramunt Christophe. Spatial models for context-aware indoor navigation systems: A survey. Journal of Spatial Information Science, 1(4):85-123, 2012. Google Scholar
  2. Gary L Allen. Cognitive abilities in the service of wayfinding: A functional approach. The Professional Geographer, 51(4):555-561, 1999. Google Scholar
  3. Iro Armeni and Konstantinos Chorianopoulos. Pedestrian navigation and shortest path: Preference versus distance. In Intelligent environments (workshops), pages 647-652, 2013. Google Scholar
  4. Michael Brown and James Pinchin. Exploring human factors in indoor navigation. In The European Navigation Conference, 2013. Google Scholar
  5. Beatrix Brunner-Friedrich and Verena Radoczky. Active landmarks in indoor environments. In International Conference on Advances in Visual Information Systems, pages 203-215. Springer, 2005. Google Scholar
  6. David Caduff and Sabine Timpf. On the assessment of landmark salience for human navigation. Cognitive processing, 9(4):249-267, 2008. Google Scholar
  7. Ruth Alison Conroy. Spatial navigation in immersive virtual environments. PhD thesis, Citeseer, 2001. Google Scholar
  8. Ruth Conroy Dalton. The secret is to follow your nose: Route path selection and angularity. Environment and Behavior, 35(1):107-131, 2003. Google Scholar
  9. Daniel Delling, Andrew V Goldberg, Moises Goldszmidt, John Krumm, Kunal Talwar, and Renato F Werneck. Navigation made personal: Inferring driving preferences from gps traces. In Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information systems, pages 1-9, 2015. Google Scholar
  10. Edsger W Dijkstra et al. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  11. Matt Duckham and Lars Kulik. “simplest” paths: automated route selection for navigation. In International Conference on Spatial Information Theory, pages 169-185. Springer, 2003. Google Scholar
  12. Ioannis Giannopoulos, Peter Kiefer, Martin Raubal, Kai-Florian Richter, and Tyler Thrash. Wayfinding decision situations: A conceptual model and evaluation. In International Conference on Geographic Information Science, pages 221-234. Springer, 2014. Google Scholar
  13. Sabine Gillner and Hanspeter A Mallot. Navigation and acquisition of spatial knowledge in a virtual maze. Journal of cognitive neuroscience, 10(4):445-463, 1998. Google Scholar
  14. Reginald G Golledge. Path selection and route preference in human navigation: A progress report. In International conference on spatial information theory, pages 207-222. Springer, 1995. Google Scholar
  15. Joy Goodman, Phil Gray, Kartik Khammampad, and Stephen Brewster. Using landmarks to support older people in navigation. In International Conference on Mobile Human-Computer Interaction, pages 38-48. Springer, 2004. Google Scholar
  16. E Grum and AU Frank. Risk of getting lost: Optimize a path to minimize risk. corp, vienna. Competence Center for Urban and Regional Planning, 2005. Google Scholar
  17. Viddit Haria, Yashvi Shah, Vanya Gangwar, Vansh Chandwaney, Tarang Jain, and Yash Dedhia. The working of google maps, and the commercial usage of navigation systems. International Journal of Innovative Research in Technology, 6(5), 2019. Google Scholar
  18. Christoph Hölscher, Tobias Meilinger, Georg Vrachliotis, Martin Brösamle, and Markus Knauff. Up the down staircase: Wayfinding strategies in multi-level buildings. Journal of Environmental Psychology, 26(4):284-299, 2006. Google Scholar
  19. Christoph Hölscher, Thora Tenbrink, and Jan M Wiener. Would you follow your own route description? cognitive strategies in urban route planning. Cognition, 121(2):228-247, 2011. Google Scholar
  20. Alycia M Hund, Martin Schmettow, and Matthijs L Noordzij. The impact of culture and recipient perspective on direction giving in the service of wayfinding. Journal of Environmental Psychology, 32(4):327-336, 2012. Google Scholar
  21. Oliver Jan, Alan J Horowitz, and Zhong-Ren Peng. Using global positioning system data to understand variations in path choice. Transportation Research Record, 1725(1):37-44, 2000. Google Scholar
  22. Bin Jiang and Xintao Liu. Computing the fewest-turn map directions based on the connectivity of natural roads. International Journal of Geographical Information Science, 25(7):1069-1082, 2011. URL: https://doi.org/10.1080/13658816.2010.510799.
  23. Daniel Kahneman. Maps of bounded rationality: Psychology for behavioral economics. American economic review, 93(5):1449-1475, 2003. Google Scholar
  24. Panayotis Kikiras, Vassileios Tsetsos, and Stathes Hadjiefthymiades. Ontology-based user modeling for pedestrian navigation systems. In ECAI 2006 Workshop on Ubiquitous User Modeling (UbiqUM), Riva del Garda, Italy, pages 1-6, 2006. Google Scholar
  25. Alexander Klippel, Heike Tappe, Lars Kulik, and Paul U Lee. Wayfinding choremes—a language for modeling conceptual route knowledge. Journal of Visual Languages & Computing, 16(4):311-329, 2005. Google Scholar
  26. Shohei Koide and Masami Kato. 3-d human navigation system considering various transition preferences. In 2005 IEEE International Conference on Systems, Man and Cybernetics, volume 1, pages 859-864. IEEE, 2005. Google Scholar
  27. Benjamin Kuipers. Modeling spatial knowledge. Cognitive science, 2(2):129-153, 1978. Google Scholar
  28. Carol A Lawton. Gender and regional differences in spatial referents used in direction giving. Sex Roles, 44(5):321-337, 2001. Google Scholar
  29. Kevin Lynch. The image of the city (vol. 11), 1960. Google Scholar
  30. Bharadwaj RK Mantha, Carol C Menassa, Vineet R Kamat, and Clive R D’Souza. Evaluation of preference-and constraint-sensitive path planning for assisted navigation in indoor building environments. Journal of Computing in Civil Engineering, 34(1):04019050, 2020. Google Scholar
  31. David M Mark. Automated route selection for navigation. IEEE Aerospace and Electronic Systems Magazine, 1(9):2-5, 1986. Google Scholar
  32. Richar E Mayer. Visual aids to knowledge construction: Building mental representations from pictures and words. In Advances in psychology, volume 108, pages 125-138. Elsevier, 1994. Google Scholar
  33. Tobias Meilinger, Markus Knauff, and Heinrich H Bülthoff. Working memory in wayfinding—a dual task experiment in a virtual city. Cognitive Science, 32(4):755-770, 2008. Google Scholar
  34. Daniel R Montello. Spatial orientation and the angularity of urban routes: A field study. Environment and Behavior, 23(1):47-69, 1991. Google Scholar
  35. Daniel R Montello and Martin Raubal. Functions and applications of spatial cognition. In Handbook of Spatial Cognition, page 249–264. American Psychological Association, 2013. Google Scholar
  36. Manuel Müller, Christina Ohm, Florin Schwappach, and Bernd Ludwig. The path of least resistance. KI-Künstliche Intelligenz, 31(2):125-134, 2017. Google Scholar
  37. Michael J O'Neill. Effects of familiarity and plan complexity on wayfinding in simulated buildings. Journal of Environmental Psychology, 12(4):319-327, 1992. Google Scholar
  38. Arto Puikkonen, Ari-Heikki Sarjanoja, Merja Haveri, Jussi Huhtala, and Jonna Häkkilä. Towards designing better maps for indoor navigation: experiences from a case study. In Proceedings of the 8th international conference on mobile and ubiquitous multimedia, pages 1-4, 2009. Google Scholar
  39. Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello. The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city. In Proceedings of the 25th ACM conference on Hypertext and social media, pages 116-125, 2014. Google Scholar
  40. Kai-Florian Richter and Alexander Klippel. You-are-here maps: Wayfinding support as location based service. GI-Technologien für Verkehr und Logistik. Beiträge zu den Münsteraner GI-Tagen, 20:21, 2002. Google Scholar
  41. Edward K Sadalla and Daniel R Montello. Remembering changes in direction. Environment and Behavior, 21(3):346-363, 1989. Google Scholar
  42. Wilson Sakpere, Michael Adeyeye-Oshin, and Nhlanhla BW Mlitwa. A state-of-the-art survey of indoor positioning and navigation systems and technologies. South African Computer Journal, 29(3):145-197, 2017. Google Scholar
  43. Masashi Soeda, Noriko Kushiyama, and Ryuzo Ohno. Wayfinding in cases with vertical motion. Proceedings of MERA, 97:559-564, 1997. Google Scholar
  44. Robert J Sternberg. Metaphors of mind: Conceptions of the nature of intelligence. Cambridge University Press, 1990. Google Scholar
  45. Mathieu Taillade, Bernard N'Kaoua, and Hélène Sauzéon. Age-related differences and cognitive correlates of self-reported and direct navigation performance: the effect of real and virtual test conditions manipulation. Frontiers in Psychology, 6:2034, 2016. Google Scholar
  46. YingLi Tian, Xiaodong Yang, Chucai Yi, and Aries Arditi. Toward a computer vision-based wayfinding aid for blind persons to access unfamiliar indoor environments. Machine vision and applications, 24(3):521-535, 2013. Google Scholar
  47. turn. Cambridge Dictionary. Cambridge University Press, 2021. URL: https://dictionary.cambridge.org/dictionary/english/turn.
  48. Alasdair Turner. The role of angularity in route choice. In International Conference on Spatial Information Theory, pages 489-504. Springer, 2009. Google Scholar
  49. Manuel Ullmann. Datengetriebene optimierung präferenzadaptiver fußwegrouten durch gebäudekomplexe, September 2020. URL: https://epub.uni-regensburg.de/43697/.
  50. Ann Vanclooster, Nina Vanhaeren, Pepijn Viaene, Kristien Ooms, Laure De Cock, Veerle Fack, Nico Van de Weghe, and Philippe De Maeyer. Turn calculations for the indoor application of the fewest turns path algorithm. International Journal of Geographical Information Science, 33(11):2284-2304, 2019. Google Scholar
  51. Ann Vanclooster, Pepijn Viaene, Nico Van de Weghe, Veerle Fack, and Philippe De Maeyer. Analyzing the applicability of the least risk path algorithm in indoor space. In ISPRS Acquisition and Modelling of Indoor and Enclosed Environments 2013 (Indoor 3D), volume 2, pages 19-26. International Society for Photogrammetry and Remote Sensing (ISPRS), 2013. Google Scholar
  52. Liping Yang and Michael Worboys. Similarities and differences between outdoor and indoor space from the perspective of navigation. Poster presented at COSIT, 2011. Google Scholar
  53. John Zacharias. Pedestrian behavior pedestrian behavior and perception in urban walking environments. Journal of planning literature, 16(1):3-18, 2001. Google Scholar
  54. Shanjiang Zhu and David Levinson. Do people use the shortest path? an empirical test of wardrop’s first principle. PloS one, 10(8):e0134322, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact