User Preferences and the Shortest Path
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Constraint-Aware Route Recommendation from Natural Language via Hierarchical LLM Agents
Route recommendation aims to provide users with optimal travel plans that satisfy diverse and complex requirements. Classical routing algorithms (e.g., shortest-path and constraint-aware search) are efficient but assume …
Spatial ReasoningA Hierarchical Optimizer for Recommendation System Based on Shortest Path Algorithm
Top-k Nearest Geosocial Keyword (T-kNGK) query on geosocial network is defined to give users k recommendations based on some keywords and designated spatial range, and can be realized by shortest path algorithms. However…
Structuring the Environment Nudges Participants Toward Hierarchical Over Shortest Path Planning
Effective planning is crucial for navigating complex environments and achieving goals efficiently. In this study, we investigated how environmental structure influences the selection of planning strategies. Forty-two par…
Decision MakingGeneralized Shortest Path Kernel on Graphs
We consider the problem of classifying graphs using graph kernels. We define a new graph kernel, called the generalized shortest path kernel, based on the number and length of shortest paths between nodes. For our exampl…
General ClassificationGraph ClassificationEdge types vs privacy in K-anonymization of shortest paths
Information breaches in social networks and other published data have caused many concerns of privacy issues in recent years. Since information in networks can be modeled as graphs, various techniques have been propose…