GPU-accelerated Incremental Euclidean Distance Transform for Online Motion Planning of Mobile Robots
Authors: Yizhou Chen, Shupeng Lai, Jinqiang Cui, Biao Wang, Ben M. Chen
Organizations: Department of Mechanical and Automation Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong 999077 · Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117583 · Peng Cheng Laboratory, Nanshan, Shenzhen, Guangdong, China 518055 · College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu, and Peng Cheng Laboratory, Nanshan, Shenzhen, Guangdong, China 518055
In this letter, we present a volumetric mapping system that effectively calculates Occupancy Grid Maps (OGMs) and Euclidean Distance Transforms (EDTs) with parallel computing. Unlike these mappers for high-precision structural reconstruction, our system incrementally constructs global EDT and outputs high-frequency local distance information for online robot motion planning. The proposed system constructs OGM with massive amount of data from multiple types of sensor inputs. Using GPU programming techniques, the system quickly computes EDT in parallel within local volume. The new observation is continuously integrated into the global EDT using the parallel wavefront algorithm while preserving the historical observations. Experiments with datasets have shown that our proposed approach outperforms existing state-of-the-art robot mapping systems and is particularly suitable for mapping unexplored areas. In its actual implementations on aerial and ground vehicles, the proposed system achieves real-time performance with limited onboard computational resources.
Figures & tables
Fig. 1: Framework of the proposed system
Fig. 2: An illustration of distance functions in AUXSCAN(). When a voxel Vx,y,z (the red dot) is inspected by the current thread, it will be assigned to one parabola segment given the lower envelope (pink curve). The blue dots denote the possible positions of the nearest obstacle of Vx,y,z .
Fig. 3: Limited observation and dynamic obstacle problems. Batch EDT is computed within green dotted line. The obstacles are painted in the dark red grids. The color shade in the observed space represents the distance value. The blue grids are unobserved area.
Fig. 4: EDT operation speed with different environmental change score.
Method
Average Updating Time (ms)
Original
46
Coalescing
19
TABLE I: Batch EDT time with and without coalesced memory access
Method
Average Updating Time (ms)
CPU bucket heap
790
GPU bucket heap
2035
GPU priority queue
3020
GPU Bellman-Ford
250
GPU Prefix Sum BFS
22
Ours
10
TABLE II: Global EDT integration time with different propagation algorithms
Fig. 5: The mapping results of different mappers on different platforms. The bold line in each center of the bar is the standard deviation of time throughout the run.
Fig. 6: The RMS error in different parameter settings.
Fig. 7: The average speed and RMS error measured in the entire map.
Fig. 8: The snapshots and the constructed maps when an MAV flying through obstacles. The movement is limited to a 2D plane since only a 2D LiDAR is used.
Fig. 9: OGM and EDT constructed by a UGV in narrow corridors.
Semantic occupancy mapping supports embodied perception during exploration and detailed scene understanding afterward, giving rise to two complementary requirements: online incremental mapping for maintaining an up-to-date global map under causal constraints, and offline global map refinement for improving the completed scene representation with additional computation. We present VEOcc++, a unified voxel-centric framework that connects both stages through a persistent sparse voxel feature map. During exploration, the map expands with newly observed regions and integrates aligned local features through reliability-guided updates, while context-aware decoding produces the current semantic occupancy map. After exploration, cached local features are consolidated as complementary evidence and combined with the completed online representation for multi-scale spatial refinement. On EmbodiedOcc-ScanNet, VEOcc++ achieves 67.12% IoU and 58.40% mIoU, establishing new state-of-the-art performance for online incremental mapping. With the local predictor fixed, our online mapping pipeline outperforms VEOcc fusion by 3.70 IoU and 3.74 mIoU points, demonstrating substantial gains from the proposed global mapping design. Offline global map refinement further improves the completed map to 67.79% IoU and 59.37% mIoU using only the observations acquired during exploration. Zero-shot deployment on a mobile robot further demonstrates transferability to unseen environments, onboard feasibility, and scalability to large-scale indoor mapping. Project page: https://wryzju.github.io/VEOccpp/.
Ruoyu Wang, Jiahan Li, Yong Liu +1
APRIL Lab, Institute of Cyber-Systems and Control, Zhejiang University, China
In real-time Visual SLAM systems, local mapping must operate under strict latency constraints, as delays degrade map quality and increase the risk of tracking failure. GPU parallelization offers a promising way to reduce latency. However, parallelizing local mapping is challenging due to synchronized shared-state updates and the overhead of transferring large map data structures to the GPU. This paper presents TurboMap, a GPU-parallelized and CPU-optimized local mapping backend that holistically addresses these challenges. We restructure Map Point Creation to enable parallel Keypoint Correspondence Search on the GPU, redesign and parallelize Map Point Fusion, optimize Redundant Keyframe Culling on the CPU, and integrate a fast GPU-based Local Bundle Adjustment solver. To minimize data transfer and synchronization costs, we introduce persistent GPU-resident keyframe storage. Experiments on the EuRoC and TUM-VI datasets show average local mapping speedups of 1.3x and 1.6x, respectively, while preserving accuracy.
Parsa Hosseininejad, Kimia Khabiri, Shishir Gopinath +3
Real-time volumetric mapping for a planning robot is dominated by the cost of integrating and storing information at the finest resolution, yet only a small fraction of any map ever lies on or near a path the planner actually considers. We exploit this with a tiered-resolution mapping mechanism that integrates LiDAR into a single map structure at two resolutions simultaneously: fine inside a corridor around the robot's current plan, and coarse everywhere else. As opposed to traditional navigation pipelines where path planning uses the mapping result and provides no feedback, we propose a feedback loop where planning also informs mapping to dynamically integrate information at different leaf resolutions. Across two real-world teleoperated datasets, replayed and scored offline against an independent full-resolution map, the tiered maps are 13-15x smaller and require 6-8x less integration CPU time than a uniform fine map, while producing paths at a similar cost per meter as the ones generated from fine resolution maps on both scenarios. A uniform coarse map reaches the same size savings but its path quality collapses (+210% cost per meter) on the harder scenario, because it over-discretizes terrain the robot must traverse. Tiering approximates the coarse map's cheapness without its failure mode.
Afonso E. Carvalho, David Portugal, Paulo Peixoto +1
Institute of Systems and Robotics, University of Coimbra, Coimbra, Portugal · Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA