Accurate and Efficient Indoor Pathfinding Based on Building Information Modeling Data

Abstract

Pathfinding is a fundamental problem for many areas, e.g., robotics, automation, computer-aided design, and computer graphics. Although outdoor pathfinding is fledged, indoor pathfinding remains a challenge due to the lack of indoor maps. Currently, some efforts have utilized building information modeling (BIM) to generate either the grid-based map or the topological map. However, either the grid-based map or the topological map is not sufficient to provide accurate and efficient pathfinding service. This article proposes a novel grid-topological map and develops an accurate and efficient indoor pathfinding scheme based on BIM. The grid-topological map is modeled jointly adopting the advantages of both the grid-based map and the topological map. First, the grid-based map is generated using the BIM data by extracting and mapping geometric and semantic data into planar grids. Second, a grid thinning algorithm is proposed to produce the topological map directly using the grid-based map. Third, a grid-topological map is presented by combining both the grid-based map and topological map. On top of the grid-topological map, an accurate and efficient pathfinding algorithm is developed. Empirical studies proved the effectiveness of the grid-topological map, as well as the accuracy and efficiency of the proposed indoor pathfinding algorithm.