PaperlayerView exact revision on arXiv

Source-linked AI summary

UFOMap: An Efficient Probabilistic 3D Mapping Framework That Embraces the Unknown

Daniel Duberg, Patric Jensfelt

arXiv:2003.04749v1cs.RO

TL;DR

Robotic tasks such as navigation and exploration need 3D maps, but OctoMap represents unknown space implicitly and can be slow to update. UFOMap extends OctoMap with explicit occupied, free, and unknown states and faster data incorporation. The authors report faster collision checking in most tested cases and faster exploration than OctoMap.

  • Problem

    OctoMap represents unknown space implicitly, while accessing unknown space can be important in collision checking, path planning, and exploration.

    Source: §I · p. 1

  • Method

    UFOMap extends OctoMap with explicit occupied, free, and unknown states and new methods for incorporating data into the octree.

    Source: §I · p. 2

  • Results

    UFOMap is faster than OctoMap for collision checking in all tested cases except those with large voxels, and completed exploration in around 650 s while OctoMap reached 70% after 900 s.

    Source: C. Collision Checking · p. 6, B. Exploration · p. 8

  • Takeaways & Limitations

    Explicit unknown-space modeling and node indicators provide a performance benefit over OctoMap in use cases that extensively use unknown space.

    Source: §VII · p. 8

Abstract

from arXiv · show

3D models are an essential part of many robotic applications. In applications where the environment is unknown a-priori, or where only a part of the environment is known, it is important that the 3D model can handle the unknown space efficiently. Path planning, exploration, and reconstruction all fall into this category. In this paper we present an extension to OctoMap which we call UFOMap. UFOMap uses an explicit representation of all three states in the map, i.e., occupied, free, and unknown. This gives, surprisingly, a more memory efficient representation. Furthermore, we provide methods that allow for significantly faster insertions into the octree. This enables real-time colored volumetric mapping at high resolution (below 1 cm). UFOMap is contributed as a C++ library that can be used standalone but is also integrated into ROS.

I. INTRODUCTION

Robotic navigation, exploration, and related tasks rely on 3D maps, but OctoMap handles unknown space implicitly and can be slow to update. UFOMap extends OctoMap with explicit unknown-space representation and faster data incorporation.

I. INTRODUCTION

  • OctoMap's implicit unknown-space representation can bottleneck collision checking, path planning, and next-best-view exploration.Treating unknown space as free is a common workaround in collision checking and path planning, but increases collision probability.Source: §I · p. 1
  • OctoMap updates can take on the order of a second for a single point cloud, impeding real-time mapping and concurrent map use.During updates, consumers cannot simultaneously iterate over the map, so some applications copy the entire structure.Source: §I · p. 1
  • UFOMap explicitly represents occupied, free, and unknown space in an octree-based 3D mapping framework.The paper presents it as a memory-efficient framework built on OctoMap.Source: §I · pp. 1–2
  • UFOMap introduces faster octree data incorporation, overall efficiency improvements, and simultaneous insertion or deletion and iteration.The authors also report real-time colored mapping at higher resolution and support for algorithms using different map resolutions.Source: §I · p. 2
  • The paper validates UFOMap against OctoMap in volumetric mapping and exploration case studies.The supplied introduction identifies these evaluations but does not report their outcomes.Source: §I · p. 2

II. RELATED WORK

The related-work discussion motivates octrees as a flexible representation, and the framework section describes UFOMap's occupancy model, traversal aids, and exploration thresholds. It also explains Morton-code traversal.

II. RELATED WORK

  • Voxel grids can require a known mapping area and substantial memory at high resolution; voxel hashing allocates fixed-size blocks on demand.Voxblox combines voxel hashing with a signed distance field grid for planning or trajectory optimization.Source: §II · p. 2
  • Octrees support delayed grid initialization and queries at different resolutions, motivating the paper's choice to build on OctoMap.OctoMap is described as more memory efficient than Voxblox or fixed grids because it stores information at different resolutions without losing precision.Source: §II · p. 2

III. UFOMAP MAPPING FRAMEWORK

  • UFOMap stores probabilistic log-odds occupancy and prunes a node when all eight children are the same, reducing tree size.Sensor readings can be fused with additions, and the maximum child occupancy gives conservative queries at different resolutions.Source: §III · pp. 2–3
  • Free-space and unknown-space indicators let traversal skip branches, while a third indicator records whether all children are the same.The indicators support efficient traversal, including searches focused on unknown space.Source: §III · p. 3
  • UFOMap uses separate free and occupied thresholds, allowing nodes between them to remain unknown.The paper describes using these thresholds to alter exploration behavior without changing the exploration method.Source: §III · p. 3
  • Morton codes interleave coordinate bits so the three bits for a depth select the next octree child during traversal.The code is generated from the octree node-index tuple for the Cartesian coordinate.Source: §III · p. 3

IV. IMPLEMENTATION DETAILS

The section introduces implementation details and identifies differences from OctoMap.

IV. IMPLEMENTATION DETAILS

  • The section covers implementation details and highlights differences from OctoMap.Source: §IV · p. 3

A. Nodes

UFOMap distinguishes three node types and changes how inner-node children are stored relative to OctoMap.

A. Nodes

  • UFOMap has inner nodes, inner leaf nodes, and leaf nodes, while OctoMap has only the first two corresponding types.Source: A. Nodes · p. 3

1) Inner nodes:

  • UFOMap stores child nodes directly in an inner node's array, saving 64 bytes for an eight-child node compared with OctoMap.This layout requires a node to have either no children or all eight.Source: 1) Inner nodes · p. 3
  • On a 64-bit operating system, UFOMap inner nodes require 16 bytes, compared with 72 bytes for OctoMap.UFOMap's inner nodes also contain three indicators.Source: 1) Inner nodes · p. 3

2) Inner leaf nodes:

UFOMap distinguishes inner leaf nodes from leaf nodes, reducing memory use, and supports simultaneous tree insertion and traversal through a pruning strategy.

2) Inner leaf nodes:

3) Leaf nodes:

  • UFOMap reduces memory usage by a factor of 3 despite having more total nodes than OctoMap.Leaf nodes make up 71–81% of UFOMap’s nodes, and dedicated leaf structures plus direct child arrays account for the reduction.Source: 3) Leaf nodes · p. 4

B. Multi-threading

  • Disabling automatic pruning allows insertion and tree traversal at the same time; manual pruning can still keep memory consumption low.The ia indicator identifies inner nodes versus inner leaf nodes when automatic pruning is disabled.Source: B. Multi-threading · p. 4

C. Integrating Point Cloud Sensor Measurements

UFOMap offers progressively faster point-cloud integrators, from per-point ray tracing to a multi-depth method that trades accuracy for speed. All three update occupied nodes at the highest resolution.

1) Simple integrator:

2) Discrete integrator:

  • The discrete integrator traces once per node after discretizing the cloud, toward each node’s center.Results can differ from simple integration, but it is significantly faster for large clouds with many points in the same node; OctoMap also has this method.Source: 2) Discrete integrator · p. 4

3) Fast discrete integrator:

  • The fast discrete integrator traces at multiple depths, then finishes at leaf depth; parameters n and d trade speed against accuracy.It avoids clearing behind occupied space; d = 0 gives the discrete integrator, while n = 0 clears only at depth d.Source: 3) Fast discrete integrator · p. 4
  • All three integrators update occupied nodes at the highest resolution, so occupied space looks mostly the same across methods.Fig. 4 compares a single ray’s traced path and free/occupied cells for the integrators; its endpoint is marked both free and occupied.Source: 3) Fast discrete integrator · p. 4, Figure 4 · p. 4

D. Bounding Box

UFOMap speeds bounding-box operations, provides flexible data access and supports transition from OctoMap. The evaluation compares memory, insertion time and three use cases.

D. Bounding Box

  • Bounding boxes limit the octree subset searched and updated; UFOMap adjusts ray endpoints into the box so exploration can still clear free space.OctoMap integrates only rays whose beginnings and ends are both inside the box, which can leave free space uncleared for exploration.Source: D. Bounding Box · pp. 4–5

E. Accessing Data

  • UFOMap iterators can filter by spatial region and node type, including unknown nodes, while OctoMap cannot return unknown-only, occupied-only or free-only nodes.UFOMap supports bounding boxes, spheres and frustums; OctoMap supports bounding boxes.Source: E. Accessing Data · p. 5

F. Availability

  • The standalone C++ library has ROS packages and OctoMap file conversion, facilitating migration and use of both frameworks in one system.The paper provides functions to read and write OctoMap files and convert between the frameworks.Source: F. Availability · p. 5

V. EVALUATION

  • The evaluation compares UFOMap and OctoMap on memory consumption, insertion time and three use cases.Table I is a memory-consumption and node-count comparison on the OctoMap 3D scan dataset.Source: §V · p. 5, Table I · p. 5

A. Memory Consumption and Node Count

UFOMap uses less memory than OctoMap and its fast integrator substantially reduces insertion time, with the largest reported speedup at 2 cm voxel size.

A. Memory Consumption and Node Count

  • UFOMap uses around 38% of OctoMap’s memory despite containing more nodes.The reduction is attributed to smaller leaf data structures and storing child nodes directly in arrays rather than pointers.Source: A. Memory Consumption and Node Count · p. 5

B. Insertion

  • UFOMap’s discrete integrator is about two times faster than OctoMap in insertion, while its ray tracing is between 1 to 2 times faster.The difference grows as voxel size decreases, favoring UFOMap; at 4 cm voxel size and below, faster integrators become important.Source: B. Insertion · pp. 5–6
  • 26 times faster than OctoMap at 2 cm voxel size, UFOMap† scales better with resolution while still clearing free space.Table II compares insertion timings on the cow dataset at different voxel sizes.Source: Table II · p. 5, B. Insertion · p. 6

C. Collision Checking

The section compares UFOMap with OctoMap on pose and line-segment collision checks and information-gain computation. UFOMap is faster in the reported comparisons, though coarse-voxel pose checks are an exception.

C. Collision Checking

  • For conservative pose checks, UFOMap is faster than OctoMap except with large voxels; occupied-only checks are faster at all resolutions.The authors attribute the large-voxel exception most likely to UFOMap iterator-construction overhead.Source: C. Collision Checking · p. 6, Table IV · p. 6
  • Pose checks require a region to contain neither occupied nor unknown space, making the test conservative; about 50% of sampled poses were in collision.The evaluation sampled 1,000,000 poses with a 25 cm radius, each centered in free space.Source: C. Collision Checking · p. 6

D. Collision Checking Along a Line Segment

E. Calculate Information Gain

  • UFOMap computes information gain 1.5 to 15 times faster than OctoMap, depending on the UFOMap method.The standard method ray-traces at node depth and recurses when blocked; UFOMapfast ray-traces leaf nodes and provides a more approximate answer.Source: E. Calculate Information Gain · p. 7, Table VI · p. 7

VI. CASE STUDIES

The case studies include a real-time volumetric-mapping comparison with OctoMap. On the tested office sequence, UFOMap handled finer voxel sizes and colored mapping without missing point clouds.

VI. CASE STUDIES

A. Real-time Volumetric Mapping

  • UFOMap processed the 86 s office sequence at 2 Hz with color at 4 mm voxels, while OctoMap managed 3 cm voxels without color.UFOMap also handled 2 mm voxels without color without missing point clouds; OctoMap could not keep up at 2 cm.Source: A. Real-time Volumetric Mapping · p. 7
  • UFOMap supports octree depths from 1 to 21, while OctoMap’s current implementation fixes depth at 16 levels.At 1 mm voxels, the stated maximum coverage per dimension is 2097.152 m for UFOMap and 65.536 m for OctoMap.Source: A. Real-time Volumetric Mapping · p. 7

B. Exploration

The exploration case study compares UFOMap and OctoMap in receding-horizon next-best-view planning. UFOMap completed the power-plant exploration sooner, and its advantage increased as more space was classified as free.

B. Exploration

  • As exploration classified more space as free, UFOMap accelerated the planner’s calculations relative to OctoMap.The receding-horizon next-best-view setup checks sampled-node free space, path clearance, and scores RRT nodes using distance and information gain.Source: B. Exploration · p. 7
  • UFOMap completed power-plant exploration in around 650 s; OctoMap reached 70% after 900 s, the maximum allowed time.The test used 16 cm voxels; Fig. 6 compares exploration progress.Source: B. Exploration · p. 8, Figure 6 · p. 8
  • Without mutexes, both mapping frameworks crashed; UFOMap did not crash when indicator ia disabled automatic pruning.In that setting, nodes are not actually removed from the octree.Source: B. Exploration · p. 8

VII. CONCLUSION

  • UFOMap explicitly represents occupied, free, and unknown space, with node indicators for child-space types; this boosts performance when unknown space is heavily used.Source: §VII · p. 8
  • New octree data-integration methods significantly reduce the time to insert measurement data such as point clouds.Source: §VII · p. 8
  • UFOMap is an open-source C++ framework available as a standalone package or for ROS integration.Source: §VII · p. 8

Related papers

Loading 2003.04749v1…