IEEE International Conference on Robotics and Automation (ICRA) 2017
Workshop on Robotics and Vehicular Technologies for Self-driving cars

Ray Distribution to Parallel Batching-based Updates

Ray Distribution to Parallel Batching-based Updates

by Youngsun Kwon and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)


We propose a novel approach to distribute rays associated with point clouds for efficiently updating treebased occupancy maps in parallel. In this paper, we utilize threads to batch a set of cells independently, although some of those cells are overlapped among threads, for exploiting the high computational power of multi-threading. To compensate redundant updates caused by having the overlapped cells, we propose a k-d tree based method to distribute rays for minimizing the redundant updates. In addition, we define a workload that each thread processes as the number of cells to be batched. Based on the definition, our method distributes the workload to threads uniformly for efficiently performing the batching process in parallel. We test our method into a corridor benchmark, and achieve 5.2 times performance improvement on batching process using 8-threads, resulting in up to 2.0 times performance improvement on overall updates, over the stateof- the-art update method for octree-based occupancy maps.

These figures show an example process to cluster given points in the spherical coordinate using our criterion on workload. b) represents the first step of clustering given points shown in a). We create a bounding box of the points, and then partition the box into two boxes using our criterion. c) recursively repeats the process using the points clustered in the first step. The final output is shown in d) represented by four green boxes, where rays associated with the points within each box are assigned to each thread.

These figures show performance of updating an octree-based occupancy maps in the indoor dataset using 8-threads. We measure the average performance according to various resolutions for different methods in figure a). Also, we report the average breakdown of the total time taken for updating the map with 0.6m resolution in figure b). WB indicates our workload balancing method.


Paper: PDF (173KB)
Source Code: GitHub page
Spotlight Talk: PDF (1.0MB)

Related links

Super Rays and Culling Region for Real-Time Updates on Grid-based Occupancy Maps

Super Ray-based Updates for Occupancy Maps