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
by
Youngsun Kwon and
Sung-Eui Yoon
Korea Advanced Institute of Science and Technology (KAIST)
Abstract
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.
Contents
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
 |
 |