Weighted octree-based 3D indoor pathfinding for multiple locomotion types

Accurate 3D pathfinding for multiple locomotion types is crucial for indoor applications. Many of the existing methods rely on the correct topology or the rich semantics of the indoor space, which restricts their usage in unstructured and semantic-less environments. Though space-decomposition methods, such as voxelization, have been applied to support 3D pathfinding, two major defects remain: the first is that voxelization of a coarse resolution brings about discretization artifacts, which is detrimental to the accessibility of wheeled platforms. The second is that the movement behaviors of different locomotion types were not modeled and integrated with a consistent world representation. This paper employs the octree to reconstruct the indoor spaces in multi -resolution, especially to differentiate between slopes and steps. A height-related spatial weighting is proposed for modeling the 3D movement cost. The behaviors of typical locomotion types are modeled by the variable-length search in continuous coordinate space and compose a unified hybrid A* pathfinding algorithm. Experiments show this method is robust and can be applied to both structured and unstructured building models. The results are accurate 3D paths conforming to the movement behaviors of multiple locomotion types.

Automated summary

Accurate 3D pathfinding for multiple locomotion types is crucial for indoor applications. This paper proposes a method using octree to reconstruct indoor spaces, modeling movement cost with a height-related spatial weighting, and a unified pathfinding algorithm. Experiments show the effectiveness of this method in both structured and unstructured building models.