Jump Over Dynamic Block (JODB): An Efficient Line-of-Sight Checker for Dynamic Grid/Voxel Maps with Sparse Obstacles
Main Article Content
Abstract
Background: Line-of-sight (LOS) checking plays a critical role in the computational cost of collision avoidance, particularly in large-scale maps with sparse obstacles, since it requires a cell-by-cell state traversal.
Objectives: To provide a general method for reducing the time cost of LOS checking and thus accelerating path and motion planning, we present an efficient LOS checker, JODB.
Methods: JODB partitions the traversable space into blocks. When our algorithm encounters the surface of a block, its LOS check skips cell-by-cell traversal inside the block and directly jumps to the opposite surface. To handle dynamic maps, we propose a novel data structure, the Space Dyadic Tree (SDT), inspired by quadtree and OctoMap, which recursively partitions the traversable space into blocks. In addition, SDT employs a decision-tree strategy to maximize block size by merging neighboring blocks whenever possible.
Results: Experimental results demonstrate that SDT can be updated in near real-time on large-scale 2D/3D maps with sparse obstacles, and that using SDT significantly reduces the time cost of LOS checking in such maps. Therefore, the time cost of path planning can be significantly reduced by applying SDT-accelerated LOS checking. Specifically, the time cost of LOS checking accelerated by SDT is approximately 40%–60% of that using a quadtree/OctoMap and 22%–70% of that using traditional LOS checking.
Conclusions: Compared with traditional quadtree/OctoMap, SDT is more efficient to initialize and update in dynamic environments, and it makes LOS checking more efficient. To facilitate further research within the community, we have made the source code of the proposed algorithm publicly available. Links to the source code can be found in the Results section.
Objectives: To provide a general method for reducing the time cost of LOS checking and thus accelerating path and motion planning, we present an efficient LOS checker, JODB.
Methods: JODB partitions the traversable space into blocks. When our algorithm encounters the surface of a block, its LOS check skips cell-by-cell traversal inside the block and directly jumps to the opposite surface. To handle dynamic maps, we propose a novel data structure, the Space Dyadic Tree (SDT), inspired by quadtree and OctoMap, which recursively partitions the traversable space into blocks. In addition, SDT employs a decision-tree strategy to maximize block size by merging neighboring blocks whenever possible.
Results: Experimental results demonstrate that SDT can be updated in near real-time on large-scale 2D/3D maps with sparse obstacles, and that using SDT significantly reduces the time cost of LOS checking in such maps. Therefore, the time cost of path planning can be significantly reduced by applying SDT-accelerated LOS checking. Specifically, the time cost of LOS checking accelerated by SDT is approximately 40%–60% of that using a quadtree/OctoMap and 22%–70% of that using traditional LOS checking.
Conclusions: Compared with traditional quadtree/OctoMap, SDT is more efficient to initialize and update in dynamic environments, and it makes LOS checking more efficient. To facilitate further research within the community, we have made the source code of the proposed algorithm publicly available. Links to the source code can be found in the Results section.
Article Details
Issue
Section
Articles