Indoor venues accommodate many people who collectively form crowds. Such crowds in turn influence people's routing choices, e.g., people may prefer to avoid crowded rooms when walking from A to B. This paper studies two types of crowd-aware indoor path planning queries. The Indoor Crowd-Aware Fastest Path Query (FPQ) finds a path with the shortest travel time in the presence of crowds, whereas the Indoor Least Crowded Path Query (LCPQ) finds a path encountering the least objects en route. To process the queries, we design a unified framework with three major components. First, an indoor crowd model organizes indoor topology and captures object flows between rooms. Second, a time-evolving population estimator derives room populations for a future timestamp to support crowd-aware routing cost computations in query processing. Third, two exact and two approximate query processing algorithms process each type of query. All algorithms are based on graph traversal over the indoor crowd model and use the same search framework with different strategies of updating the populations during the search process. All proposals are evaluated experimentally on synthetic and real data. The experimental results demonstrate the efficiency and scalability of our framework and query processing algorithms.
翻译:室内人群聚集最快的路径查询(FPQ) 找到一条在人群聚集最短的旅行时间路径,而室内最拥挤的路径查询(LCPQ) 发现一条路径,每条路径都遇到最不固定的对象。为了处理查询,我们设计了一个统一的框架,其中有三个主要组成部分。首先,室内人群模型组织室内人口表层学和捕捉不同房间的物体流动。第二,一个时间变化的人口估计器为未来时间戳提供房间人口,以支持在询问处理过程中进行人群聚集最晚的路径计算。第三,两种精确和两种大致的查询处理算法过程,所有算法都基于室内人群模型的图表穿透,并使用相同的搜索框架,在搜索过程中采用不同的搜索策略更新人群。所有建议都用真实的合成算法和合成算法框架。所有建议都通过实验性的方法评估了我们搜索结果和合成算法的可操作性。