IEEE International Conference on Robotics and Automation (ICRA) 2016

Super Ray-based Updates for Occupancy Maps

Super Ray-based Updates for Occupancy Maps

by Youngsun Kwon, Donghyuk Kim, and Sung-Eui Yoon

Korea Advanced Institute of Science and Technology (KAIST)


We present a novel approach, Super Ray, for efficiently updating map representations such as grids and octrees with point clouds. In this paper, we define a super ray for points as a representative ray to them with an associated frustum. A super ray is constructed in a way that updating those points has the same set of cells accessed during the map update process. As a result, we can perform the update process with a super ray in a single traversal on the map, resulting in performance improvement without compromising any representation accuracy of the map. For constructing super rays efficiently, we propose mapping lines for handling 2-D and 3-D cases from an observation that edges or grid points branch out the access pattern of updating the map. Our method is general enough to be applied for variety of occupancy map structures based on axis-aligned space subdivisions such as grids and octrees. We test our method into indoor and outdoor benchmarks, and achieve 2.5 times on average (up to 3.5 times) performance improvement over the state-of-the-art update method for OctoMap and grid maps.

These figures represent occupancy probabilities of cells after updating each ray to the octree-based occupancy map representation using each update method. This figure shows a concept of super ray, which is a representative ray to rays travering the same cells of map representation.

The left figure shows the indoor dataset. The right figure shows the update speed of two update methods according to various resolution. Our method shows from 1.6 to 3.2 times higher performance over the prior method.


Paper: PDF (1.2MB)
Source Code: GitHub page
Spotlight Talk: PDF (1.4MB)
Interactive Talk: PDF (3.9MB)
Poster: PDF (0.6MB)

Related links

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

Ray Distribution to Parallel Batching-based Updates


	title={Super ray based updates for occupancy maps},
	author={Kwon, Youngsun and Kim, Donghyuk and Yoon, Sung-eui},
	booktitle={Robotics and Automation (ICRA), 2016 IEEE International Conference on},