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.