A Sample-Based Approach for Hierarchical Information-Theoretic Compression of Probabilistic Occupancy Grids

Zhenyu Jin; Daniel T. Larsson

cs.ROSep 23, 2026

A Sample-Based Approach for Hierarchical Information-Theoretic Compression of Probabilistic Occupancy Grids

Authors: Zhenyu Jin, Daniel T. Larsson

Organizations: Aerospace and Mechanical Engineering Department at the University of Arizona in Tucson, AZ, USA.

Abstract

We develop a sample-based framework for constructing information-driven hierarchical multi-resolution representations of probabilistic occupancy grids. Recent methods compute information-optimal abstractions via dynamic-programming-based exhaustive recursions, which become computationally prohibitive for large-scale grids and are ill-suited to robotics applications. To address this limitation, we introduce a sample-based strategy inspired by Monte Carlo Tree Search (MCTS) that incrementally constructs hierarchical abstractions through statistical estimation rather than exhaustive enumeration. The proposed method is anytime in nature, allowing computation to be terminated at any stage to produce a valid compressed representation. We compare our approach with the information-optimal Q-tree search algorithm and demonstrate its effectiveness in rapidly generating abstractions of large real-world probabilistic occupancy grids.

Figures & tables

Fig. 1: (left) $128\times 128$ example environment for comparison with Q-tree search. (middle) Abstraction obtained with Q-tree search. (Right) Abstraction obtained with sample-based method with $M=3000$ rollout budget. Abstractions obtained for $\alpha=0.0067$ .

Fig. 2: (top) Total reward obtained by executing Q-tree search and the sample-based approach for a variety of rollout budgets $M$ as a function of $\alpha$ . (middle) The difference in objective function value (error) between the optimal Q-tree search solution and our sample-based approach as a function of $\alpha$ . (bottom) the normalized information-plane showing the trade-off between compression (x-axis) and information-retention (y-axis) for each method. The curve is traced by varying $\alpha$ , where movement to the right (decreasing $\alpha$ ) corresponds to less compressed trees (more leaves) that retain more information.

Fig. 3: Comparison of the percentage of leaf nodes (top) and relevant information retention $I(T;Y)$ (bottom) between our sample-based method (SBM) and Q-tree search (QTS) for various values of $\alpha$ with $M=5000$ .

Fig. 4: (left) Probabilistic occupancy grid constructed from real-world LiDAR data with three regions of interest labeled as $R_{A}$ , $R_{B}$ , and $R_{C}$ shown. (middle) and (right) show example multi-resolution compressions of $R_{A}$ and $R_{B}$ , respectively, obtained by our sample based approach.

Fig. 5: Execution time and relevant information retention comparison between Q-tree search (QTS) and our proposed sample-based method (SBM) for $\alpha_{1}=0.0005$ , $\alpha_{2}=0.004$ , $\alpha_{3}=0.0067$ and $M=5500$ over the three regions $R_{A}$ , $R_{B}$ and $R_{C}$ .

Occupancy Grid Mapping

See all 17 papers

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping
Mar 23, 2026Benxu Tang, Yunfan Ren, Yixi Cai +6Occupancy Grid Mapping Simultaneous Localization and Mapping
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.
Efficient Hierarchical Any-Angle Path Planning on Multi-Resolution 3D Grids
Feb 24, 2026Victor Reijgwart, Cesar Cadena, Roland Siegwart +1Motion Planning
Autonomous Systems Lab, ETH Zürich, Switzerland
Performance-Driven Environment Abstraction with Multi-Timescale Learning
Jun 16, 2026Yue Guan, Dipankar Maity, Panagiotis TsiotrasMarkov Decision Processes Reinforcement Learning
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA · Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC, USA

Mar 23, 2026J/K move · Enter open · S save

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

Benxu Tang, Yunfan Ren, Yixi Cai, Fanze Kong+5

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.

Occupancy Grid Mapping Simultaneous Localization and Mapping

Open paper AskPDF arXiv

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.

Abstract

Occupancy Grid Mapping

Explore similar work

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

Efficient Hierarchical Any-Angle Path Planning on Multi-Resolution 3D Grids

Performance-Driven Environment Abstraction with Multi-Timescale Learning