Organizations: Mechatronics and Robotic Systems (MaRS) Laboratory, Department of Mechanical Engineering, The University of Hong Kong, Hong Kong SAR, China. · Department of Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden.
Determining the occupancy status of locations in the environment is a fundamental task for safety-critical robotic applications. Traditional occupancy grid mapping methods subdivide the environment into a grid of voxels, each associated with one of three occupancy states: free, occupied, or unknown. These methods explicitly maintain all voxels within the mapped volume and determine the occupancy state of a location by directly querying the corresponding voxel that the location falls within. However, maintaining all grid voxels in high-resolution and large-scale scenarios requires substantial memory resources. In this paper, we introduce a novel representation that only maintains the boundary of the mapped volume. Specifically, we explicitly represent the boundary voxels, such as the occupied voxels and frontier voxels, while free and unknown voxels are automatically represented by volumes within or outside the boundary, respectively. As our representation maintains only a closed surface in two-dimensional (2D) space, instead of the entire volume in three-dimensional (3D) space, it significantly reduces memory consumption. Then, based on this 2D representation, we propose a method to determine the occupancy state of arbitrary locations in the 3D environment. We term this method as boundary map. Besides, we design a novel data structure for maintaining the boundary map, supporting efficient occupancy state queries. Theoretical analyses of the occupancy state query algorithm are also provided. Furthermore, to enable efficient construction and updates of the boundary map from the real-time sensor measurements, we propose a global-local mapping framework and corresponding update algorithms. Finally, we will make our implementation of the boundary map open-source on GitHub to benefit the community:https://github.com/hku-mars/BDM.
Figures & tables
Figure 1: MAV performing a long-range autonomous navigation task in an unknown multi-level building, utilizing the proposed mapping framework. (a) Accumulated point cloud and the MAV trajectory at the end of the task, also visualized from multiple viewpoints in (a1), (a2), and (a3). (b) Hardware configuration of the MAV platform used to perform the navigation task. (c) Overview of the resulting global boundary map, which forms a closed structure. As the viewpoint is external, the low-dimensional property of the map is not evident. To better illustrate its internal structure, the map is sliced along the orange plane. (d) Cross-sectional view revealing the hollow interior of the boundary map. Voxels stored in boundary map are classified into three types, visualized in distinct colors. The green voxels lie on the interior layer of the map, having an occupancy state of free. The grey and blue voxels are located on the exterior layer, with occupancy states of occupied and unknown, respectively.
Figure 2: (a) A uniform occupancy grid where each voxel is classified into one of three states: free, unknown, or occupied, represented by green, blue, and grey, respectively. For clarity, only the voxels along the cross-sectional plane are shown, with the remaining voxels represented by a simplified shape. (b) The boundary surface layer of the free space, highlighted in red, which separates the free regions from the adjacent occupied or unknown regions. (c) Our proposed boundary map, which includes the free, unknown and occupied voxels that neighboring the boundary surface layer.
Figure 3: The boundary map is composed by boundary voxels , which include boundary interior voxels ( bint ) and boundary exterior voxels ( bext ). Boundary interior voxels are free voxels neighboring unknown or occupied voxel(s), and are visualized in green. Boundary exterior voxels include boundary exterior (unknown) voxels ( bukn ) and boundary exterior (occupied) voxels ( bocc ), represented in blue and grey, respectively. Boundary exterior (unknown) voxels have an unknown occupancy state and neighboring free voxel(s). Boundary exterior (occupied) voxels are all voxels whose occupancy state is occupied.
Figure 4: Occupancy state determination based on our boundary map. The diagram shows the determination process for several example query voxels (nos. 1–5). If the query voxel is located exactly on the boundary map, the query voxel state can be determined by type of the boundary voxel directly (query voxel no. 1). Otherwise, we search along the z+ direction (i.e., a representative direction for illustration propose) to find the nearest boundary voxel on the boundary map, denoted as bnn . If bnn is a boundary interior voxel bint , the query voxel is determined as free (query voxels no. 2 and 3). If the bnn is a boundary exterior voxel bext (i.e., either unknown bukn or occupied bocc ), the query voxel is determined as unknown (query voxels no. 4 and 5). If bnn does not exist, the query voxel is determined as unknown too (query voxel no. 6).
Figure 5: The boundary map, which consists of boundary voxels in the three-dimension (3D), is maintained in a two-dimensional (2D) data structure. Without loss of generality, z -axis is selected as the projection axis for illustration purpose in the manuscript. The boundary map is projected along the z -axis onto the (x,y) -plane. Then a hash-based 2D grid map is maintained on the (x,y) -plane where each grid cell stores boundary voxels projected onto that cell. Each boundary voxel in the grid cell is represented by its z -coordinate and a type indicator indicating its type (i.e., bint , bukn , and bocc ). The numbers in the figure correspond to the z -coordinates of the boundary voxels.
Figure 6: Overview of the proposed global-local mapping framework. The system takes odometry and sensor scans as inputs. The pink block illustrates the map structure, consisting of a global map (the low-dimensional boundary map) and a local map (a dense uniform occupancy grid map). The mapping framework is updated once every new odometry and sensor data arrive. For each point in the new scan, the New Scan Ray Casting performs ray casting and probabilistic occupancy update on the local occupancy grid map. The new odometry is used to determine if the local map needs to slide and, if so, compute the slide-in region SI and slide-out region SO of the local map. If a slide occurs, the occupancy state within the slide-out region of the local map is updated to the global map by the Incremental Boundary Map Update (green block), while the occupancy state within the slide-in region of the local map is loaded from the global map via the Local Occupancy Grid Map Update (brown block).
Figure 7: Illustration of the local and global map update if a slide occurs in Figure 6 . (a) The global map (boundary map) and local map (a uniform occupancy grid map) before sliding, and the local map region before and after the sliding. (b) The local map slides to the new position and updates the occupancy state within the map region (including both slide-in region and the overlapped region) by ray casting all points in the new LiDAR scan ( New Scan Ray Casting ). Meanwhile, boundary voxels in the slide-out region are computed and updated to the global boundary map ( Incremental Boundary Map Update ). (c) From the global boundary map, occupancy states within the slide-in region are loaded. (d) The loaded occupancy states within the slide-in region are fused into the local map ( Local Occupancy Grid Map Update ).
Figure 8: Illustration of step (c) in Figure 7 : loading occupancy states within the slide-in region from the global boundary map. (a) Projecting the slide-in region SI to the (x,y) -plane, denoted as SI2d . (b) For each 2D grid cell within SI2d , retrieve the boundary voxels saved in the global boundary map. (c) Constructing a dense occupancy grid tile consisting of free voxels and occupied voxels above the 2D grid cell but within the slide-in region. Voxels not encoded in the tile are unknown voxels requiring no processing. (d) This procedure is repeated for all 2D grid cells within SI2d , resulting in a dense occupancy grid map within the slide-in region SI . This map contains only free and occupied voxels and is finally fused to the local map in step (d) in Figure 7 .
Figure 9: Illustration of the search direction selection in occupancy state querying in the proposed global-local mapping framework. The search direction is selected such that it does not intersect with the local map. For query voxels in regions I and II (voxel no. 1 and 3), the search direction can be selected as z+ or z− , as neither direction intersects with the local map. For query voxels in regions III and IV (voxel no. 2 and 5), only one direction can be chosen, which is the one not intersecting with the local map. For query voxels in region V (voxel no. 4), which lie within the local map, the occupancy state is directly retrieved from the local map.
Figure 10: The HKU private dataset hku_campus . (a) The trajectory and accumulated point cloud scans. The mapping results of our method are shown in (b) and (c), focusing on the boundary map (i.e., the global map). The mapped volume is referred to the volume enclosed by the boundary. (b) provides an overview of the boundary map, while (c) presents interior views alongside the corresponding real-world image. For visualization purposes, only boundary exterior voxels are rendered, including boundary exterior (unknown) voxels (colored in blue) and boundary exterior (occupied) voxels (colored in grey). Boundary interior voxels, which are adjacent to the boundary exterior voxels, are omitted to improve visual clarity.
Sequence
Environment Scale
Traveled
Number
Average Points
Mapped
Sensor
Local Map
(Bounding Box)
Distance
of
Number
Volume
Range
Size
( m3 )
( m )
Scans
(per scan)
( m3 )
( m )
( m3 )
ford_1
11,416×8,060×94
16,639
7,757
41,108
3,843,031
65
130×130×16
ford_2
11,584×8,027×102
24,064
10,713
40,241
4,781,935
65
130×130×16
ford_3
6,659×3,860×85
9,558
8,692
42,501
2,905,112
65
130×130×16
kitti_00
653×586×58
3,724
4,541
121,495
243,903
45
90×90×6
Table 1: Details of datasets used in the benchmark experiments.
Figure 11: Memory consumption (in MB) of UG (Uniform Grid), HG (Hash Grid), Octo (Octomap), UFO (UFOMap), D-Map, and our method on the ford_1 , ford_2 , ford_3 , kitti_00 , and kitti_02 sequences. The percentage shown in red indicates the memory reduction of our method relative to the best of the rest methods in comparison. For our method, we also show the memory breakdown of the local and global maps, respectively. N/A indicates that the method failed due to memory consumption exceeding the limit.
Figure 12: Continuation of Figure 11 : results on the remaining sequences, hku_campus and uav_flight .
ford_1
ford_2
ford_3
Resolution (m)
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
Uniform Grid
11.56
×
×
×
11.89
×
×
×
9.74
×
×
×
Hash Grid
12.08
33.16
×
×
11.38
30.46
×
×
12.36
36.04
196.23
×
Octomap
80.01
176.94
498.39
×
77.14
163.72
461.71
×
80.80
173.28
466.49
1353.29
UFOMap
61.69
119.20
246.68
511.86
58.39
113.10
278.57
480.39
62.60
122.40
249.38
528.85
D-Map
13.60
53.83
109.16
×
13.38
49.55
92.71
×
14.18
57.60
117.86
493.75
Table 2: Comparison of map update time (ms) at different resolutions. The best and second-best results in each setting are highlighted using distinct tint colors.
Figure 13: Breakdown of map update time of our method in sequence ford_2 , kitti_00 and hku_campus , respectively.
ford_1
ford_2
ford_3
Resolution (m)
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
Uniform Grid
10510.9
×
×
×
25133.8
×
×
×
41.18
×
×
×
Hash Grid
86.28
123.12
×
×
84.11
132.83
×
×
101.73
288.19
173169.0
×
Octomap
373.56
512.90
606.18
×
370.64
490.14
634.95
×
425.05
487.36
636.77
137039.0
UFOMap
174.16
227.98
314.85
39516.2
182.43
234.03
313.96
82606.9
155.77
211.11
295.76
567.18
D-Map
654.38
784.49
903.17
×
680.72
820.07
899.19
×
616.85
758.78
859.91
142607.3
Table 3: Comparison of average map query time (ns) at different resolutions.
ford_1
ford_2
ford_3
Resolution (m)
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
0.8
0.4
0.2
0.1
Ours
99.99
99.99
99.98
99.94
99.98
99.99
99.98
99.94
99.97
99.98
99.98
99.92
D-Map
94.27
95.66
96.06
×
95.10
96.48
96.55
×
93.66
95.42
95.19
94.70
Table 4: Map Accuracy (%) of our method and D-Map with Octomap as the ground truth.
Figure 14: Illustration of a long-range autonomous navigation task conducted in a multi-level building. Starting from an initial position, the MAV sequentially navigated to a series of manually defined goals, each specified after the previous one was reached. All goals were intentionally placed beyond the MAV’s current local map to enforce long-range navigation. In total, eight goals were assigned and visited. After reaching the final goal (Goal No.8), the MAV was instructed to autonomously plan and execute a return trajectory to the starting position. (a) Locations of the eight goals. Goals No.1–5 are located on level 1, while Goals No.6–8 are on level 2. The figure also demonstrates the accumulated point cloud and the MAV trajectory upon reaching Goal No.8, with the trajectory color-coded by altitude. (b) Return trajectory from Goal No.8 to the starting position, highlighted in orange. The MAV followed the shortest path computed using the A* search algorithm based on the proposed global-local mapping framework. The figure also illustrates the local map at a position selected on the return trajectory, highlighting its limited spatial range compared to the global map. (c) Sample images of the MAV captured during the mission, with their corresponding locations on the trajectory marked in (a) and (b). Images (c1)–(c3) were taken during the outbound flight to Goal No.8, with locations annotated in (a). Images (c4) and (c5) were captured during the return flight and correspond to locations indicated in (b).
Figure 15: Complete MAV flight trajectory, including the outbound trajectory to Goal No.8 and the return to the starting position, overlaid on a Google Maps satellite image. The trajectory is color-coded by altitude.
Figure 16: Illustration of how the MAV navigates itself to a long-range goal, using the segment from Goal No.2 to Goal No.3 as an example. (a) The accumulated point cloud and trajectory when reaching Goal No.2. (b) Visualization of the corresponding mapping framework at this moment, including the global map (i.e., boundary map) and the local map. The free, unknown and occupied voxels are colored by green, blue and grey, respectively. (c) Autonomous navigation process toward Goal No.3. The red dot marks the location of Goal No.3. The green dot indicates the selected target on the frontier. The green line shows the computed A* path to the frontier target. For clarity, both the global and local maps are rendered semi-transparent. (d) Accumulated point cloud and trajectory upon reaching Goal No.3.
Figure 17: (a) Illustration of the autonomous navigation process from Goal No.5 toward Goal No.6. (b) Visualization of the accumulated point cloud and the MAV trajectory upon reaching Goal No.6. The trajectory is color-coded by altitude.
Figure 18: Memory consumption (MB) of our method and other baselines during the flight.
Environment Scale (Bounding Box) ( m3 )
277×123×19
Travel Distance ( m )
1,247.5
Mapped Volume ( m3 )
29153.4
Number of Scans
8,291
Average Point Number (per scan)
16,252.1
Table 5: Details of the Real-world Flight
Figure 19: Map update time of our method and other baselines during the flight.
Projection Axis
Memory (MB)
Query (ns)
Nˉbv/q
x
637.48
82.84
33.47
y
669.44
73.45
21.82
z
1450.18
56.78
3.02
Table 6: Impact of different projection axis choices on memory consumption and query time for the kitti_02 sequence at a map resolution of 0.1m. The benchmark experiments in Section 8 use the z -axis as the projection axis.
Figure 20: Illustration of the relationship between occupancy probability and its log-odds value.
Figure 21: (a) Sample images from sequence 2011_09_29_drive_0071 , where dynamic objects (e.g., vehicles, pedestrians and bicycles) are highlighted by boxes. (b) Mapping results of the sequence obtained by Octomap, our method and D-Map, where all occupied voxels are visualized. Since the baseline methods including Uniform Grid, Hash Grid and UFOMap adopt the same update process as Octomap, they are expected to produce identical mapping results with Octomap.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 22: Illustration of the proof of Theorem 1 and Theorem 2 .
Figure 23: Illustration of boundary voxels distribution in the environment. (a) An idealized worst-case scenario. (b) A typical real-world scenario.
Efficient and scalable 3D occupancy mapping is essential for autonomous robot applications in unknown environments. However, traditional occupancy grid representations suffer from two fundamental limitations. First, explicitly storing all voxels in three-dimensional space leads to prohibitive memory consumption. Second, exhaustive ray casting incurs high update latency. A recent representation alleviate memory demands by maintaining only the voxels on the two-dimensional boundary, yet they still rely on full ray casting updates. This work advances the boundary-based framework with a highly efficient update scheme. We introduce a truncated ray casting strategy that restricts voxel traversal to the exterior of the boundary, which dramatically reduces the number of updated voxels. In addition, we propose a direct boundary update mechanism that removes the need for an auxiliary local 3D occupancy grid, further reducing memory usage and simplifying the map update pipeline. We name our framework as D-BDM. Extensive evaluations on public datasets demonstrate that our approach achieves significantly lower update time and reduced memory consumption compared with the baseline methods, as well as the prior boundary-based approach.
Benxu Tang, Yixi Cai, Fanze Kong +2
Mechatronics and Robotic Systems (MaRS) Laboratory, Department of Mechanical Engineering, The University of Hong Kong · Department of Robotics, Perception, and Learning, KTH Royal Institute of Technology
Crucial for autonomous exploration, online 3D occupancy prediction and mapping incrementally constructs dense spatial representations on the fly. However, recent Gaussian-centric methods struggle with structural boundary fidelity and rely heavily on predefined scene-size priors, fundamentally limiting their operational efficiency. In this work, we present VEOcc, a voxel-centric framework formulated as a recursive perception-and-assimilation paradigm. By eliminating the need for initial scale estimation, VEOcc enables highly streamlined, open-ended map expansion. Furthermore, to robustly aggregate noisy temporal observations within the discrete voxel space, we propose a Spatio-Temporal-Aware Online Update Strategy. It integrates Cross-Temporal Logit Aggregation (TLA) for temporal consistency, Reliability-Aware Confidence Modulation (RCM) for spatial uncertainty calibration, and Confidence-Driven Incremental State Update (CSU) for robust global state assimilation. % Extensive experiments on Occ-ScanNet and EmbodiedOcc-ScanNet demonstrate that VEOcc establishes new state-of-the-art performance in both local and embodied settings, providing an accurate and efficient solution for real-world exploration. Extensive experiments on Occ-ScanNet and EmbodiedOcc-ScanNet demonstrate that VEOcc establishes new state-of-the-art performance in both local and embodied settings. Notably, zero-shot evaluations on self-collected video sequences further confirm its robust out-of-distribution generalization capability in completely unseen real-world environments. Ultimately, our framework provides an accurate and highly efficient solution for autonomous exploration. Code and supplementary visualizations are available on our project page: https://wryzju.github.io/VEOcc/.
Ruoyu Wang, Yong Liu, Sheng Tao +2
Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou, China.
Continuous occupancy mapping methods that learn spatial representations from sensor observations support predictions at arbitrary locations, but training a single global model can become computationally expensive as the amount of training data grows during large-scale mapping. Constructing local continuous occupancy submaps reduces the size of individual learning problems, but relative pose errors can cause inconsistent predictions in overlapping regions. We address these challenges by formulating large-scale continuous occupancy mapping as a submap joining problem. Each local submap is represented by a relevance vector machine regressing a continuous average log-odds field. Repeated observations within each cell are summarized by their average log-odds and observation count, yielding a Gaussian likelihood with count-dependent precision and enabling Gaussian-conjugate inference. The resulting local fields provide predictive means, variances, and analytical spatial derivatives. We then formulate submap joining as a joint pose--field optimization problem, with consistency constraints weighted by the predictive uncertainty of overlapping local submaps. With uncertainty weights held fixed within each Gauss--Newton iteration, our joint pose--field system can be reduced to an equivalent pose-only system. After the optimized submap poses are obtained, the global field value at any covered location can be recovered in closed form through variance-weighted fusion of predictions from the corresponding local submaps, without training an additional global model. Experiments on simulated and real-world 2D LiDAR datasets demonstrate improved pose and occupancy-map accuracy over the evaluated baselines, reduced map storage and joining time, and improved map-construction scalability.
Zhuhua Bai, Yingyu Wang, Liang Zhao +1
Robotics Institute, University of Technology Sydney, Australia · School of Informatics, University of Edinburgh, UK