Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping
Benxu Tang, Yunfan Ren, Yixi Cai, Fanze Kong, Wenyi Liu, Fangcheng Zhu, Longji Yin, Liuyu Shi
Abstract
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.
AI Impact Assessments
(3 models)Scientific Impact Assessment: Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping
1. Core Contribution
The paper introduces a fundamentally new representation for occupancy grid maps that stores only 2D boundary voxels instead of the full 3D volume. The key insight is elegant: occupied voxels naturally form surfaces, and free space can be implicitly represented by the interior of a closed boundary formed by occupied voxels, frontier voxels (boundary between free and unknown), and boundary interior voxels (free voxels adjacent to non-free voxels). Occupancy state queries for arbitrary 3D locations are resolved by searching along a projection axis to find the nearest boundary voxel, then applying simple classification rules (Theorems 1-2).
The approach bridges a real gap: existing methods either sacrifice memory (grid-based), query/update efficiency (octree-based), or dynamic environment handling (D-Map). This work achieves all three simultaneously.
2. Methodological Rigor
Theoretical foundations are solid. The paper provides formal definitions of boundary voxel types, proves correctness of occupancy state determination (Theorems 1-2), establishes O(1) average query complexity (Theorem 3), and proves correctness of the slide-in region reconstruction (Theorems 4-5). The proofs in the appendices are rigorous and well-structured.
The data structure design is clever. Projecting boundary voxels onto a 2D hash-based grid map, with sorted arrays per cell enabling binary search, is an efficient implementation that naturally supports the query algorithm. The 32-bit encoding (30 bits for z-coordinate, 2 bits for type) is compact.
Experimental evaluation is comprehensive. Seven sequences across four datasets (Ford AV, KITTI, two private datasets) are tested at multiple resolutions (0.05m–0.8m), comparing against five baselines (Uniform Grid, Hash Grid, Octomap, UFOMap, D-Map). Four metrics are evaluated: memory, update time, query time, and accuracy. The breakdown analysis (Figure 13) and the projection axis analysis (Table 6) add depth.
Minor concerns: The O(1) average query complexity relies on the assumption that boundary voxels scale as O((D/d)²) in typical environments—while reasonable, this is not formally guaranteed. The proof in Appendix C explicitly acknowledges the worst case is O((D/d)³). The accuracy evaluation uses Octomap as ground truth rather than an independent reference, though this is standard practice.
3. Potential Impact
Direct applications: The method enables occupancy mapping on memory-constrained platforms (MAVs, small robots) in large-scale environments—a genuine bottleneck for autonomous exploration, search-and-rescue, and large-scale inspection tasks. The real-world MAV demonstration (1.25km flight in a multi-level building) is compelling.
Memory savings are substantial and practical: 89-92% reduction vs. UFOMap on Ford AV sequences at 0.1m resolution; up to 99% reduction vs. Uniform Grid. These aren't marginal improvements—they enable scenarios that were previously infeasible on constrained hardware.
Broader influence: The boundary representation concept could inspire similar dimensional-reduction approaches in other spatial data structures (ESDF maps, TSDF maps, semantic maps). The frontier detection efficiency (boundary exterior unknown voxels are directly accessible) is a practical bonus for exploration planners.
Multi-agent potential: As the authors note, the compact representation is well-suited for map transmission between agents—a significant open problem in multi-robot systems.
4. Timeliness & Relevance
The paper addresses a current bottleneck as autonomous systems push toward larger operational envelopes with higher-resolution sensors. The proliferation of lightweight MAVs and legged robots with limited compute budgets makes memory-efficient mapping increasingly critical. The method's compatibility with standard LiDAR-based pipelines (ray casting, log-odds updates, clamping) ensures practical adoptability.
5. Strengths & Limitations
Key Strengths:
Notable Limitations:
6. Additional Observations
The paper is well-written with clear figures (especially Figures 2-8). The real-world MAV experiment is more than a token demonstration—it validates practical utility in a genuinely challenging scenario. The comparison against D-Map on dynamic sequences (Figure 21) effectively highlights the advantage of maintaining ray-casting-based updates.
The scalability argument is particularly compelling: as resolution doubles, memory grows ~4× for boundary maps vs. ~8× for volumetric methods—this gap widens dramatically at finer resolutions.
Generated Mar 24, 2026
Comparison History (36)
Paper 1 addresses a timely, high-impact problem in VLA models, which are central to current robotics and AI research. Its novel semantic anchoring approach yields substantial, quantified improvements (+18.7% in-distribution, +21.5% OOD) and is plug-and-play across multiple backbones, offering broad applicability. Paper 2 presents a solid, rigorous engineering contribution to memory-efficient mapping with open-source code, but addresses a more incremental, specialized problem with narrower field impact. Paper 1's relevance to foundation-model-driven robotics gives it greater breadth and timeliness.
Paper 2 has higher estimated impact due to its timely, broadly relevant integration of Transformer sequence modeling and predictive supervision for agile humanoid locomotion, demonstrated with large performance gains and real-robot validation. The approach generalizes across diverse terrains with a single policy, making it influential for robotics, RL, and sequence modeling communities. Paper 1 is methodologically solid and useful for large-scale mapping, but its contribution is more specialized (occupancy representations/data structures) with narrower cross-field reach compared to advances in embodied AI control and learning.
Paper 2 addresses a critical bottleneck in general-purpose robotics by integrating Vision-Language-Action models with Embodied Chain-of-Thought. Its introduction of the largest embodied CoT corpus and a novel training paradigm (using CoT as representation-shaping supervision rather than test-time decoding) offers broader cross-disciplinary impact across AI, NLP, and robotics. While Paper 1 provides a valuable memory optimization for 3D mapping, Paper 2 demonstrates higher scalability, timeliness, and potential to drive foundational advances in autonomous, generalizable robot manipulation.
Paper 1 addresses a highly challenging and impactful problem—autonomous dexterous skill acquisition from a single video—combining foundation models, sim-to-real transfer, and reinforcement learning. This tackles a major bottleneck in robot learning (data collection), offering high novelty and significant potential to scale real-world robotic manipulation. While Paper 2 presents a valuable memory-efficient mapping technique, Paper 1 represents a broader paradigm shift in robotic skill acquisition with greater timeliness and broader potential applications.
Paper 2 introduces a fundamentally novel representation principle (2D boundary surfaces instead of 3D volumes) with rigorous theoretical foundations, substantial practical memory savings (89-99%), and comprehensive experimental validation. Its dimensional reduction concept is broadly applicable beyond occupancy mapping. Paper 1, while timely and practical, is primarily a systems integration contribution combining existing components without fundamental algorithmic novelty, and suffers from small sample sizes and lack of statistical rigor in evaluation.
Paper 1 has higher likely scientific impact due to a more fundamentally novel mapping representation (dimensional reduction by storing only boundaries), stronger methodological rigor (formal correctness/complexity analyses plus broad multi-dataset evaluation), and wider applicability across robotics subfields (mapping, planning, exploration, multi-robot sharing) with clear scalability benefits. Paper 2 is timely and practically useful for low-latency manipulation, but is more incremental, has more heuristic elements (ReNoise), narrower evaluation/baseline scope, and likely more domain-specific impact.
Paper 2 has higher likely scientific impact: it introduces a fundamentally different, theoretically grounded occupancy-map representation (boundary-only) with clear, broadly applicable gains (order-of-magnitude memory reduction) and strong methodological rigor (correctness theorems, complexity analysis, extensive multi-dataset benchmarking, real-world MAV demo, open-source). Its contributions generalize across robotics (mapping, exploration, multi-robot communication) and are timely for large-scale autonomy. Paper 1 is a strong systems contribution but is more domain/platform-specific and more integrative/incremental, with narrower generalizability and less formal grounding.
Paper 1 introduces a fundamentally novel dimensional-reduction principle for occupancy grid mapping (2D boundary vs 3D volume) with substantial practical memory savings (89-99%), rigorous theoretical analysis, comprehensive experiments across multiple datasets and baselines, and real-world validation. Paper 2 provides a solid but incremental integration of Koopman operators with conformal prediction, with notable theoretical gaps (exchangeability assumption, a posteriori conditions) and limited experimental scope. Paper 1's broader applicability, larger performance gains, and stronger methodological rigor give it higher impact potential.
Paper 1 offers a more fundamental and broadly applicable mapping representation (2D boundary-only storage for 3D occupancy queries) with strong theoretical guarantees, comprehensive multi-dataset benchmarking, and large practical gains (order-of-magnitude memory reduction) enabling deployments previously infeasible on constrained robots. Its impact spans robotics mapping, planning, exploration, and multi-robot communication. Paper 2 is timely and useful but is more integration-focused, shows moderate gains with limited statistical rigor, and appears specialized to pick-and-place with unquantified runtime overhead, likely narrowing breadth and longevity of impact.
Paper 1 has higher impact potential due to a more novel core idea (dimensional reduction of 3D occupancy storage to a 2D boundary representation), strong methodological rigor (formal theorems, complexity analysis, comprehensive multi-dataset benchmarking), and immediate broad applicability across robotics mapping, planning, exploration, and multi-robot communication. Its large, demonstrated memory savings directly enable previously infeasible large-scale high-resolution mapping on constrained platforms. Paper 2 is timely and useful as a framework/benchmark, but ABPT is more incremental, baseline coverage and quantitative sim-to-real evidence are limited, and broader cross-field impact is less clear.