Super ray based updates for occupancy maps

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.

Authors

• Youngsun Kwon
• Donghyuk Kim
• Sung-Eui Yoon

Keywords

• Three-dimensional displays
• Robot sensing systems
• Octrees
• Path planning
• Memory management
• Space heating
• Occupancy Map
• Grid Points
• Point Cloud
• Set Of Cells
• Map Representation
• Access Patterns
• Grid Map
• Update Function
• Update Process
• Update Method
• Frustum
• Cell State
• Exact Method
• 2D Plane
• Depth Camera
• Geometric Configuration
• Points In Cells
• Sensor Noise
• Prior Methods
• Various Levels Of Noise
• Efficient Update
• Occupied States
• Occupancy Probability
• Laser Ranging
• Large-scale Environments
• Maps Of Cells
• Test Configuration
• World Coordinate
• Huge Amount Of Time