An Efficient Approximation Algorithm for Multi-criteria Indoor Route Planning Queries
A route planning query has many real-world applications and has been studied extensively in outdoor spaces such as road networks or Euclidean space. Despite its many applications in indoor venues (e.g., shopping centres, libraries, airports), almost all existing studies are specifically designed for outdoor spaces and do not take into account unique properties of the indoor spaces such as hallways, stairs, escalators, rooms etc. We identify this research gap and formally define the problem of category aware multi-criteria route planning query, denoted by CAM, which returns the optimal route from an indoor source point to an indoor target point that passes through at least one indoor point from each given category while minimizing the total cost of the route in terms of travel distance and other relevant attributes. We show that CAM query is NP-hard. Based on a novel dominance-based pruning, we propose an efficient algorithm which generates high-quality results. We provide an extensive experimental study conducted on the largest shopping centre in Australia and compare our algorithm with alternative approaches. The experiments demonstrate that our algorithm is highly efficient and produces quality results.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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…
Embedding and generation of indoor climbing routes with variational autoencoder
Recent increase in popularity of indoor climbing allows possible applications of deep learning algorthms to classify and generate climbing routes. In this work, we employ a variational autoencoder to climbing routes in a…
A data-driven approach to predict decision point choice during normal and evacuation wayfinding in multi-story buildings
Understanding pedestrian route choice behavior in complex buildings is important to ensure pedestrian safety. Previous studies have mostly used traditional data collection methods and discrete choice modeling to understa…
Implementation of a Blind navigation method in outdoors/indoors areas
According to WHO statistics, the number of visually impaired people is increasing annually. One of the most critical necessities for visually impaired people is the ability to navigate safely. This paper proposes a navig…
NavigateOptimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
Loading reusable skill documents into a bounded context window is now the primary way large language model (LLM) agents acquire task-specific capabilities, which makes skill selection a first-order determinant of task pe…