Fact-checked by Grok 2 weeks ago

Occupancy grid mapping

Occupancy grid mapping is a probabilistic technique in mobile robotics that represents an environment as a discretized two-dimensional grid of cells, where each cell maintains an estimate of the probability that the corresponding spatial region is occupied by an obstacle or free space.^[1] This method discretizes the robot's surroundings into a uniform lattice, typically with cell sizes ranging from 5 to 50 cm, enabling efficient storage and updating of spatial information without relying on explicit features like landmarks.^[1] The concept was originally introduced by Hans Moravec and Alberto Elfes in 1985, who developed it to generate high-resolution maps from wide-angle sonar readings by integrating multiple sensor measurements into a probabilistic framework. Building on this foundation, Elfes further formalized occupancy grids in 1989 as a stochastic spatial representation that uses Bayesian updating to fuse sensor data, addressing challenges in perception and navigation under uncertainty. Key to the approach is the use of inverse sensor models to compute the likelihood of occupancy or emptiness for affected cells based on readings from devices like sonar, lidar, or infrared sensors, with updates often performed in log-odds form for computational efficiency and to avoid underflow issues in probability multiplication.^[1] Occupancy grids offer several advantages, including robustness to sensor noise through probabilistic averaging, the ability to incorporate heterogeneous sensor data into a unified map, and straightforward extension to tasks such as simultaneous localization and mapping (SLAM), path planning, and collision avoidance.^[2] In practice, they assume a static world but can be adapted for dynamic environments by incorporating temporal models, and they have been widely applied in autonomous vehicles, indoor navigation systems, and exploration robots due to their simplicity and scalability.^[3] Modern implementations, such as those in the Robot Operating System (ROS), continue to leverage occupancy grids for real-time mapping in unstructured settings.^[4]

Introduction

Definition and Purpose

Occupancy grid mapping is a probabilistic technique used in robotics to represent an environment as a discretized grid of cells, where each cell corresponds to a small 2D or 3D spatial region and stores a probability value indicating the likelihood of occupancy by an obstacle, typically ranging from 0 (free space) to 1 (fully occupied).^[5] This representation models the environment as a collection of binary random variables per cell, allowing for stochastic estimates that account for spatial uncertainty. The primary purpose of occupancy grid mapping is to enable mobile robots and autonomous systems to construct and maintain maps of unknown or partially known environments from sensor data, supporting essential tasks such as collision avoidance, path planning, and localization by breaking down continuous space into computationally tractable probabilistic units.^[6] By integrating measurements over time, it facilitates real-time decision-making in dynamic settings, where the robot's pose is assumed known or estimated separately.^[5] Key benefits include its ability to robustly handle sensor noise and inherent uncertainties in perception, providing a scalable framework for mapping that approximates cell independence to manage complexity without exhaustive state enumeration. For example, sonar or lidar sensors can populate grid cells by measuring distances to obstacles, updating probabilities based on beam endpoints and empty regions to reflect environmental structure.^[6] This probabilistic encoding underpins Bayesian updating procedures that refine the map with successive observations.^[5]

Historical Development

Occupancy grid mapping was first introduced by Hans Moravec and Alberto Elfes in their 1985 paper on high-resolution maps from wide-angle sonar readings, marking a foundational shift from binary maps to probabilistic encoding for robust perception in discretized space.^[7] Elfes further developed the approach with probabilistic sonar modeling in his 1987 paper. Building on this, Hans Moravec developed the concept of certainty grids in 1988, which provided a framework for sensor fusion and motion planning using grid-based confidence values for occupied and empty cells.^[8] The formalization of occupancy grids occurred in Elfes' 1989 publication, which detailed their use for mobile robot perception and navigation, integrating multiple sensor data into a unified probabilistic map.^[9] Key milestones in the 1990s included the integration of occupancy grids with simultaneous localization and mapping (SLAM) techniques, advanced by researchers like Sebastian Thrun, who explored grid-based mapping in probabilistic frameworks for real-time robot localization and environment modeling.^[10] Practical implementations emerged during this period, notably in NASA's Mars Pathfinder mission with the Sojourner rover in 1997, where occupancy grid methods supported autonomous hazard detection and path planning on extraterrestrial terrain.^[11] In the 2010s, the approach evolved to address dynamic environments through extensions like dynamic occupancy grids, which incorporated temporal changes and object tracking to handle moving obstacles beyond static assumptions.^[12] Sebastian Thrun's 2005 book on probabilistic robotics further extended the methodology, emphasizing Bayesian updates and integration with advanced estimation algorithms for scalable mapping. Open-source adoption accelerated post-2000, culminating in the incorporation of occupancy grid tools into the Robot Operating System (ROS) framework around 2010, facilitating widespread use in research and development.^[13]

Representation

Grid Structure

Occupancy grid mapping discretizes the environment into a lattice of fixed-size cells arranged in a Cartesian coordinate system, enabling a structured representation of spatial information. In two-dimensional applications, such as mobile robot navigation on flat terrains, the grid consists of square cells typically sized between 5 and 50 cm to balance detail and computational feasibility.^[1] For three-dimensional volumetric mapping, the structure extends to cubic voxels, allowing representation of height variations in environments like indoor spaces or uneven outdoor terrains.^[14] Boundary handling in occupancy grids often employs bounded layouts to manage finite computational resources, with the grid centered at a fixed origin or dynamically adjusted relative to the robot's pose for efficient tracking during exploration. While theoretically capable of infinite extension, practical implementations limit the grid to a predefined area, such as a rectangular region encompassing the operational environment, to avoid unbounded memory growth. This origin-centered approach facilitates seamless integration with robot localization systems, where pose updates shift the reference frame without reconstructing the entire grid.^[15] Resolution choices in grid design involve significant trade-offs: finer cell sizes, such as 5 cm, enhance mapping accuracy by capturing smaller obstacles but exponentially increase memory demands—for instance, a 100x100 grid at coarse resolution contrasts sharply with a 1000x1000 grid at finer scales, multiplying storage needs by a factor of 100. Coarser resolutions reduce computational overhead but may overlook fine details, potentially leading to navigation errors in cluttered spaces. These considerations are critical for resource-constrained robots, where grid dimensions must align with available hardware.^[16] Data storage for occupancy grids typically uses array-based structures, such as a two-dimensional matrix of floating-point values to hold occupancy estimates per cell, ensuring fast access during updates and queries. For expansive environments, sparse representations—employing data structures like hash maps or octrees—optimize memory by only allocating space for observed regions, avoiding storage of vast unoccupied areas. Each cell in these arrays may briefly reference probabilistic encodings to denote occupancy states, though the focus remains on the underlying geometric framework.^[15]^[17] As an illustrative example, mapping a 10 m × 10 m room with a cell size of 0.05 m results in a 200 × 200 grid, providing sufficient resolution for indoor robotics while maintaining manageable storage of approximately 40,000 cells.^[18]

Probabilistic Encoding

In occupancy grid mapping, each grid cell encodes the probability of occupancy, denoted as P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t}), where m_{i,j} is the state of cell (i,j) (1 for occupied, 0 for free), and z_{1:t}, x_{1:t} represent the sequence of sensor measurements and robot poses up to time t. This posterior probability ranges from 0 (certainly free) to 1 (certainly occupied), with unknown or unmeasured cells typically initialized to 0.5 to reflect maximum uncertainty.^[19] To facilitate efficient Bayesian updates, the probability is often transformed into a log-odds representation, defined as l_{t,i,j} = \log \left( \frac{P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t})}{1 - P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t})} \right). This formulation exploits the additive property of log-odds, allowing sequential updates to simply sum independent log-odds increments from new sensor data, which simplifies computations in multi-step mapping processes.^[20] An alternative encoding uses the odds ratio directly, where odds o_{i,j} = \frac{P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t})}{1 - P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t})}, related to log-odds by l_{t,i,j} = \log(o_{i,j}). Conversion between formats is straightforward; for instance, the probability can be recovered as P(m_{i,j} = 1 \mid z_{1:t}, x_{1:t}) = \frac{o_{i,j}}{1 + o_{i,j}}. This odds form provides an intuitive ratio of occupied to free likelihoods but is less common than log-odds due to the latter's numerical advantages.^[21] Grids are typically initialized with a uniform prior of P = 0.5 per cell, corresponding to log-odds l = 0 and odds o = 1, assuming no prior knowledge of the environment. During mapping, thresholds are applied to interpret cell states for practical use, such as classifying cells with P > 0.8 (or equivalently l > 1.39) as occupied and P < 0.2 (or l < -1.39) as free, with intermediate values indicating uncertainty.^[19]^[20] The log-odds representation is particularly valuable in multi-sensor fusion scenarios, as it converts multiplicative probability updates into additions, thereby avoiding numerical underflow issues that arise from repeated multiplications of small probabilities over numerous observations. This approach is widely implemented in open-source libraries, such as the GMapping module in OpenSLAM, which maintains occupancy grids in log-odds form for real-time robotic mapping.^[22]^[21]

Core Algorithm

Inverse Sensor Model

The inverse sensor model in occupancy grid mapping defines the conditional probability p(m \mid z, x), where m represents the occupancy state of a grid cell, z is a sensor measurement, and x is the robot's pose from which the measurement was taken. This model estimates how likely each cell is occupied or free based on the measurement, enabling probabilistic updates to the grid representation. Seminal formulations of this model were introduced in the probabilistic framework for occupancy grids, treating sensor data as evidence for cell states while accounting for sensor limitations. To facilitate efficient computation, the model is often expressed in log-odds form, where the update increment for a cell is l(m \mid z, x) = \log \frac{p(m \mid z, x)}{1 - p(m \mid z, x)}. This log-odds representation avoids underflow issues in iterative Bayesian updates and directly adds to prior log-odds values, approximating the normalizing constant in the likelihood for tractability. For continuous ray models, the probability is derived via integration along the beam path, approximating the likelihood of occupancy given the sensor's field of view.^[20] For range-based sensors such as lidar or sonar, the beam model implements the inverse sensor model through ray tracing. A ray is cast from pose x in the direction of measurement z, tracing through grid cells until reaching the endpoint, which corresponds to the detected range or maximum sensor limit. Cells along the ray up to the endpoint are modeled as free space, with low occupancy probability—often around 0.4 to reflect confidence in emptiness. At the endpoint cell, a sharp increase in occupancy probability occurs, typically around 0.9, indicating a likely obstacle hit. Beyond the endpoint, cells remain unaffected, preserving prior uncertainty. This approach captures the conical spread of sonar beams or the linear precision of lidar rays.^[20] Sensor noise is incorporated by modeling range errors as Gaussian distributions centered on the measured distance, with variance \sigma^2 reflecting the sensor's accuracy—e.g., spreading the occupied spike over nearby cells to account for measurement deviation. For ambiguous readings, such as those from wide-beam sensors where reflections could occur anywhere in the beam, multi-hypothesis tracking is applied: multiple possible endpoint locations are considered, each weighted by likelihood (e.g., higher for closer surfaces), and probabilities are averaged across hypotheses to update cells. This handles specular reflections or clutter without overcommitting to a single interpretation.

Bayesian Update Procedure

The Bayesian update procedure in occupancy grid mapping relies on recursive application of Bayes' theorem to estimate the posterior probability of occupancy for each grid cell based on sequential sensor measurements and the robot's pose. The core formulation expresses the map posterior at time t as proportional to the product of the measurement likelihood and the prior map estimate:

P(m_t \mid z_{1:t}, x_{1:t}) \propto P(z_t \mid m_t, x_t) \cdot P(m_t \mid z_{1:t-1}, x_{1:t-1}),

where m_t denotes the map state, z_{1:t} the sequence of measurements up to time t, and x_{1:t} the sequence of robot poses. This recursive structure enables sequential mapping by incorporating new evidence while propagating uncertainty from previous updates.^[20] To enhance computational efficiency and avoid underflow issues in probability multiplications, the update is typically performed in log-odds representation. The log-odds value for a cell, defined as l(m) = \log \frac{P(m)}{1 - P(m)}, transforms the multiplicative Bayesian update into an additive form:

l_t(m) = l_{t-1}(m) + \log \frac{P(z_t \mid m, x_t)}{P(z_t \mid \neg m, x_t)} - l(0),

where l(0) is the log-odds of the prior (often set to 0 for an uninformative uniform prior, effectively approximating the evidence normalization constant as 1). This approximation maintains tractability in real-time applications without explicit computation of the normalizing evidence term P(z_t \mid x_t).^[20]^[23] The procedure unfolds in four key steps for each new measurement: First, project the sensor ray (e.g., from a laser or sonar) into the grid to identify affected cells along the beam path. Second, for each intersected cell, compute the inverse sensor model to determine the log-odds delta \Delta l based on the measurement's implications for occupancy (e.g., free space decreases occupancy odds, while hits increase them). Third, add this delta to the cell's existing log-odds value. Finally, clamp the resulting log-odds to a bounded range (e.g., corresponding to probabilities in [0.001, 0.999]) to prevent saturation at extremes and retain residual uncertainty. These steps are applied independently to each cell, assuming conditional independence across grid cells given the current pose and measurement for computational tractability.^[20]^[1] This independence assumption simplifies the joint map posterior into a product over individual cell posteriors, enabling parallelizable updates but potentially overlooking spatial correlations in the environment. The procedure supports ongoing sequential mapping in dynamic scenarios by repeatedly integrating new data, with the log-odds form ensuring efficient handling of accumulating evidence over time.^[20]^[23]

Implementation

Computational Methods

Occupancy grid maps are typically implemented using 2D arrays for planar environments, where each cell stores probabilistic occupancy values, enabling efficient access and updates through simple indexing operations. For three-dimensional mapping, octree data structures are employed to represent sparse volumetric data, subdividing space hierarchically to reduce memory usage while preserving resolution in occupied regions. This approach, as detailed in the OctoMap framework, allows for probabilistic occupancy estimation across varying levels of detail, making it suitable for robotic applications requiring 3D perception.^[24] To integrate sensor measurements, such as laser scans, into the grid, ray-grid intersection algorithms like Bresenham's line algorithm are used to trace beams through cells, marking free space along the path until the endpoint, which is updated as occupied or unknown based on the measurement.^[25] This integer-based rasterization method ensures accurate discretization without floating-point operations, facilitating real-time updates on resource-constrained hardware.^[26] Efficiency in computation is achieved through incremental updates, where each new sensor scan modifies only the affected cells rather than recomputing the entire map, reducing complexity to linear in the number of beams.^[15] For large-scale environments, downsampling techniques subsample input scans or grid resolutions to limit processing overhead, maintaining mapping viability without excessive computational cost. Parallelization strategies leverage graphics processing units (GPUs) for ray tracing and update operations, with implementations using CUDA in the Robot Operating System (ROS) ecosystem accelerating map building by distributing beam traces across threads.^[27] These GPU-based methods can generate occupancy grids in milliseconds per scan, significantly outperforming CPU-only approaches on embedded systems.^[28] Memory management involves dynamic allocation to expand grids as the robot explores new areas, preventing fixed-size limitations in unknown environments.^[24] For sparse maps, compression via run-length encoding represents sequences of identical cell states compactly, achieving substantial reductions in storage requirements while supporting efficient querying.^[3] Log-odds arithmetic is often used in updates for its additive properties, enhancing numerical stability and speed. On embedded hardware, typical runtimes for processing a single laser scan range from 10 to 100 milliseconds, with 2010s optimizations achieving linear time complexity in the number of sensor beams and affected cells through streamlined ray casting and parallel execution.^[27]

Uncertainty Management

Occupancy grid mapping encounters several sources of uncertainty that can degrade map accuracy and reliability. Sensor noise arises from inherent measurement errors in devices like lidar or sonar, leading to imprecise range readings that affect cell occupancy probabilities. Motion distortion occurs when the robot moves during sensor acquisition, causing beam endpoints to shift relative to the intended pose. Dynamic obstacles introduce temporal variability, as moving objects may be captured inconsistently across scans, violating the static environment assumption common in basic grid models. Additionally, aliasing in low-resolution grids results from coarse discretization, where multiple environmental features map to the same cell, amplifying ambiguity in occupancy estimates.^[29]^[30]^[31] To mitigate these uncertainties, techniques such as confidence weighting are applied during grid updates, where sensor measurements are scaled by their reliability to modulate the impact on cell probabilities. Multi-sensor fusion further reduces errors by integrating complementary data streams; for instance, combining lidar for precise ranging with inertial measurement unit (IMU) data for motion compensation helps counteract distortion and noise. Bayesian priors can briefly initialize cell uncertainties to reflect initial map ignorance before updates refine them.^[32]^[33]^[20] Thresholding and decay mechanisms address ongoing uncertainties, particularly in assuming static environments. Time-based probability decay lowers occupancy values in cells over time to account for potential changes from unobserved dynamics, maintaining relevance under static assumptions. For path planning, erosion and dilation operations expand or shrink obstacle regions in the grid to incorporate safety margins, buffering against residual uncertainties in occupancy estimates.^[34]^[32] A key advancement in handling pose-related uncertainties involves particle filters, which propagate localization errors into the grid mapping process; this integration has been established since 2005 in probabilistic robotics frameworks using Rao-Blackwellized particle filters for simultaneous localization and mapping.^[35]^[20] Map confidence is evaluated using metrics like entropy per cell, which quantifies informational uncertainty by measuring the spread of occupancy probabilities within each grid element. Error bounds are assessed through Monte Carlo simulations, which sample pose and sensor variations to estimate probabilistic map inaccuracies and validate overall reliability.^[36]^[37]^[38]

Applications and Extensions

Occupancy grid maps serve as a critical input for path planning algorithms in robotic navigation, enabling efficient obstacle avoidance and trajectory generation. In global planning, these maps are integrated with search-based methods like the A* algorithm, which treats occupied cells as impassable to compute optimal paths from start to goal positions while minimizing traversal costs.^[6] For local reactive navigation, the Dynamic Window Approach (DWA) uses occupancy grids to evaluate feasible velocity commands in real-time, prioritizing those that maintain clearance from detected obstacles and align with the global path.^[39] Additionally, occupancy grids form the foundational representation in SLAM pipelines such as GMapping, introduced in 2007, where they facilitate simultaneous localization and mapping by incorporating scan-matching and particle filtering to build consistent environmental models during robot motion. In exploration tasks, occupancy grid mapping supports frontier-based strategies that identify boundaries between known and unknown regions, directing the robot toward unexplored areas to maximize mapping coverage. These frontiers are extracted as contours in the grid where free and occupied cells meet unknown spaces, allowing utility-based selection of next waypoints for autonomous discovery. Such approaches were prominently employed in the DARPA Grand Challenge and Urban Challenge competitions during the 2000s, where unmanned ground vehicles used occupancy grids derived from lidar and radar sensors to explore and navigate unstructured off-road and urban environments, achieving successful autonomous traversal over hundreds of kilometers. Practical implementations highlight the versatility of occupancy grid mapping in consumer and industrial robotics. Later models of the iRobot Roomba vacuum cleaner series, starting with the 900 series in 2015, have leveraged simplified occupancy grid representations—built from infrared and later lidar and camera sensors—to enable systematic room coverage and obstacle avoidance, allowing the robot to adapt cleaning paths based on detected furniture and walls.^[40]^[41] In autonomous vehicles, occupancy grids fuse multi-sensor data for pedestrian detection, classifying dynamic grid cells as potential human occupants to trigger evasive maneuvers, as demonstrated in real-world perception systems that process lidar point clouds into probabilistic maps for safe urban driving.^[42] Real-world performance of occupancy grid mapping in navigation often achieves update rates of 10-20 Hz, supporting fluid motion in dynamic settings through efficient Bayesian updates that enable low-latency obstacle detection and path replanning. A notable case study involves the Willow Garage PR2 robot in the 2010s, where occupancy grids integrated with ROS navigation stacks allowed the dual-armed mobile manipulator to autonomously navigate office environments, perform object manipulation tasks, and cover over 40 km in long-term deployments while avoiding collisions in cluttered spaces.^[43] The adoption of occupancy grid mapping extended to extraterrestrial robotics with NASA's Mars Science Laboratory mission, where the Curiosity rover, landing in 2012, employed grid-based terrain representations from stereo cameras and laser rangefinders for autonomous hazard avoidance and path planning across rocky Martian landscapes, facilitating safe traversal of Gale Crater over thousands of sols.^[44]

Advanced Variants

Advanced variants of occupancy grid mapping extend the foundational Bayesian update procedures to address challenges in dynamic environments, large-scale operations, and multi-modal sensor integration, enabling more robust representations for complex robotic tasks. These modifications incorporate time-dependent modeling, hierarchical structures, and volumetric extensions while maintaining probabilistic foundations. Dynamic occupancy grids introduce time-varying probabilities to handle moving objects, using decay models that gradually reduce occupancy estimates over time unless reinforced by new sensor data. This approach models environmental changes by applying exponential decay to cell probabilities, allowing grids to adapt to transient obstacles like pedestrians or vehicles in real-time mapping. For instance, Hähnel et al. (2003) proposed a method where mobile robots build maps in dynamic settings by distinguishing static and moving elements through temporal updates. Multi-resolution approaches employ hierarchical grids, such as quadtree variants, to manage large-scale mapping by using coarse-to-fine representations that allocate higher resolution only to detailed areas. Quadtrees partition the space recursively into quadrants, enabling efficient storage and updates for expansive environments while reducing computational overhead. This structure supports scalable path planning in outdoor settings, where uniform high-resolution grids would be infeasible due to memory constraints.^[45]^[46] Three-dimensional and volumetric extensions adapt occupancy grids for aerial robotics, such as drones and UAVs, by using octree-based structures to represent full 3D space with probabilistic occupancy for occupied, free, and unknown voxels. The OctoMap library, introduced in 2010, implements this framework, allowing efficient raycasting and integration with visual odometry for real-time 3D reconstruction in unstructured environments like forests or urban canyons. Fusion with visual odometry enhances pose estimation, achieving mapping errors below 5 cm in GPS-denied scenarios.^[47]^[24]^[48] The Bayesian Occupancy Filter (BOF), refined in 2013 applications for object tracking, extends dynamic grids by modeling multi-target motion at the cell level without explicit object hypotheses, using prediction and update steps to track multiple entities probabilistically. This filter addresses occlusion and association challenges in crowded scenes, enabling safer navigation by predicting obstacle trajectories with uncertainties propagated via Bayesian inference.^[49]^[50] Post-2020 integrations with deep learning enable semantic occupancy grids, where neural networks predict not just binary occupancy but class labels like "vehicle" or "pedestrian" from multi-sensor inputs, enhancing interpretability for autonomous systems. For example, BEV-fusion methods combine LiDAR and camera data via convolutional networks to generate dynamic semantic grids, improving detection recall by 15-20% in urban driving datasets compared to traditional probabilistic models.^[51]^[52] To address scalability limitations in outdoor environments, hybrid approaches combine discrete grids with Gaussian processes for continuous representations, modeling occupancy as a smooth latent field that interpolates sparse sensor data across large areas. Gaussian process occupancy maps reduce discretization errors and enable efficient inference in non-uniform terrains, with kernel-based regression achieving up to 10x faster updates than uniform grids in expansive outdoor mappings.^[53]^[54] Recent advancements as of 2024 include robocentric occupancy grid maps for efficient large-scale and high-resolution LiDAR-based motion planning, and humanoid occupancy networks integrating multimodal sensors for generalized representation in complex environments.^[55]^[56]

References

[1]
[PDF] Lecture 13: Occupancy Grids - Columbia CS
A Bit of History. • Occupancy grids were first popularized by Hans. Moravec and Alberto Elfes at CMU. • Kurt Konolige at SRI made a number of valuable.Missing: definition | Show results with:definition
[2]
[PDF] Learning Occupancy Grid Maps With Forward Sensor Models
This article presents a new algorithm for occupancy grid maps using forward models, solving the high-dimensional problem and maintaining dependencies between ...
[3]
ColMap: A memory-efficient occupancy grid mapping framework
Robustness with respect to sensor noise; · The ability to incorporate measurements from different types of sensor into a single map; · The ability to distinguish ...
[4]
[PDF] Occupancy Mapping
Occupancy Grid Mapping refers to a family of computer algorithms in probabilistic robotics for mobile robots which address the problem of generating maps ...
[5]
Occupancy Grids - MATLAB & Simulink - MathWorks
Occupancy grids are used to represent a robot workspace as a discrete grid. Information about the environment can be collected from sensors in real time.Overview · World, Grid, and Local... · Inflation of Coordinates
[6]
Sensor Fusion in Certainty Grids for Mobile Robots | AI Magazine
Jun 15, 1988 · Certainty grids have proven to be a powerful and efficient unifying solution for sensor fusion, motion planning, landmark identification, and many other ...
[7]
Using Occupancy Grids for Mobile Robot Perception and Navigation
An approach to robot perception and world modeling that uses a probabilistic tesselated representation of spatial information called the occupancy grid is ...
[8]
[PDF] Robotic Mapping: A Survey - Sebastian Thrun
9: (a) Occupancy grid map and (b) architectural blueprint of a recently constructed building. The blueprint is less accurate than the map in several locations.
[9]
[PDF] Autonomous Rover Technology for Mars Sample Return
Sojourner is the rover that was deployed on Mars in 1997. It is estimated ... occupancy grid analysis) 3D sensing modes; operated with pseudo-PM beacon ...
[10]
[PDF] Grid-Based Models for Dynamic Environments
Our model, called dynamic occupancy grid, is a generalization of a standard occupancy grid. Figure 1 illustrates the fundamental difference between these two ...<|control11|><|separator|>
[11]
nav_msgs/OccupancyGrid Message - ROS documentation
This represents a 2-D grid map, in which each cell represents the probability of occupancy. Header headerMissing: 2010 | Show results with:2010
[12]
[PDF] Variable Resolution Occupancy Mapping using Gaussian Mixture ...
Abstract—Occupancy mapping is fundamental for active per- ception systems to enable reasoning about known and unknown regions of the environment.
[13]
[PDF] An Efficient Robocentric Occupancy Grid Map for Large ... - arXiv
Feb 28, 2023 · The ROG-Map is a uniform grid-based OGM with two main parts in its update process, as shown in Alg.1: 1) Map sliding (Sec. IV-A), which involves ...
[14]
[PDF] Efficient Occupancy Grid Computation on the GPU with Lidar and ...
occupancy grids are computational intensive and there is a trade-off between the size and the resolution of the grid. The field of view is therefore ...
[15]
[PDF] Using occupancy grids for mobile robot perception and navigation
The occupancy grid framework ad- dresses the requirements and concerns outlined above through the development of spatial robot perception and reasoning.
[16]
Simplified Occupancy Grid Indoor Mapping Optimized for Low-Cost ...
One important decision for implementing an Occupancy Grid Map is defining the cell's size. Ideally, the smaller the size is, the more accurate the map will ...
[17]
(PDF) Using Occupancy Grids for Mobile Robot Perception and ...
Aug 5, 2025 · PDF | An approach to robot perception and world modeling that uses a probabilistic tesselated representation of spatial information called ...
[18]
[PDF] PROBABILISTIC ROBOTICS
Page 1. PROBABILISTIC. ROBOTICS. Sebastian THRUN. Stanford University. Stanford ... GRID AND MONTE CARLO LOCALIZATION. 187. 8.1 Introduction. 187. 8.2 Grid ...
[19]
[PDF] Improved Techniques for Grid Mapping with Rao-Blackwellized ...
Grisetti, C. Stachniss, and W. Burgard. Improving grid-based slam with Rao-Blackwellized particle filters by adaptive proposals and selective resampling. In ...Missing: GMapping | Show results with:GMapping
[20]
[PDF] Mapping 1 Occupancy Mapping
... log odds of the belief the square is filled over the belief it isn't filled, which we label lt(x). Using the log odds reduces numerical errors from.
[21]
[PDF] 12-occupancy-mapping.pdf - Uni Freiburg
▫ Log odds ratio is defined as. ▫ and with the ability to retrieve. Page 29 ... Occupancy Grid Mapping. ▫ Developed in the mid 80's by Moravec and ...
[22]
OctoMap - 3D occupancy mapping
The OctoMap library implements a 3D occupancy grid mapping approach, providing data structures and mapping algorithms in C++ particularly suited for robotics.
[23]
[PDF] Cell-based Update Algorithm for Occupancy Grid Maps and Hybrid ...
Cell-based Update Algorithm. The state-of-the-art algorithm for updating occupancy grid maps is the Bresenham line drawing algorithm [2]. The algorithm.
[24]
[PDF] Static Free Space Detection with Laser Scanner using Occupancy ...
The Bresenham's line algorithm [19] can determine the grid map cells that should be selected in order to form a close approximation to a straight line ...
[25]
[PDF] Efficient Occupancy Grid Computation on the GPU with Lidar and ...
A detailed description for the fast computation of accurate occupancy grids with laser range-finders on the GPU using the CUDA framework is given. It is shown ...
[26]
[PDF] Building an Efficient Occupancy Grid Map Based on Lidar Data ...
Aug 7, 2019 · G. Grisetti et al. [14] improved the algorithm proposed in [13] by using the scan matching procedure along with the odometry information.
[27]
[PDF] Occupancy Grid Mapping with Highly Uncertain Range Sensors ...
The proposed mapping method in this article is undertaken by detecting surfaces and approximating objects by distance using sensors with high localization ...Missing: seminal | Show results with:seminal
[28]
[PDF] Reducing Uncertainty by Fusing Dynamic Occupancy Grid Maps in a ...
May 5, 2020 · sensor measurements. To reduce uncertainty, an occupancy grid mapping algorithm may combine the measurements of multiple sensors. Often, a ...
[29]
[PDF] MONITORING OF DYNAMIC OBJECTS ON A 2D OCCUPANCY ...
Apr 26, 2023 · The paper deals with the construction of dynamic occupancy maps, where the grid cell can contain not only information about the.
[30]
[PDF] Grid-Based Multi-Sensor Fusion for On-Road Obstacle Detection
Nov 18, 2014 · The proposed solution consists on the low-level fusion of radar and lidar through the occupancy grid framework. Two inference theories are ...Missing: underflow | Show results with:underflow
[31]
Camera, LiDAR, and IMU Based Multi-Sensor Fusion SLAM: A Survey
Sep 22, 2023 · Multi-sensor fusion in SLAM uses visual, LiDAR, and IMU sensors due to their complementary sensing capabilities and to overcome limitations of ...Missing: occupancy confidence weighting
[32]
A Perception-Based Architecture for Autonomous Convoying in ...
Sep 18, 2025 · The resulting occupancy probability indicates whether a grid cell is likely to contain a static object. However, it does not specify whether ...
[33]
[PDF] Occupancy Grid Maps for Localization and Mapping
Jun 1, 2008 · Mapping is the problem of determining the representation, while localization is the problem of finding the robot's position. Many probabilistic ...
[34]
[PDF] Autonomous Robotic Exploration Using a Utility Function Based on ...
The map is an occupancy grid and its entropy is calculated using (3). The pose of the robot consists of a 2D position and orientation, and it is represented by ...
[35]
[PDF] Mutual Information-based Gradient-ascent Control ... - DSpace@MIT
For example, we evaluate our theoretical results in Section 4.4.3 using a Monte Carlo-based SLAM algorithm (Montemerlo et al., 2002) that employs the occupancy ...
[36]
(PDF) A Novel Measure of Uncertainty for Mobile Robot SLAM with ...
Aug 5, 2025 · In this paper we propose a new measure that takes the uncertainty in both the robot path and the map into account. Our approach relies on the ...
[37]
[PDF] The Dynamic Window Approach to Collision Avoidance 1 Introduction
This paper describes the dynamic window approach to reactive collision avoidance for mobile robots equipped with synchro-drives. The approach is derived ...
[38]
Your Roomba Is Also Gathering Data about the Layout of Your Home
Jul 25, 2017 · It's important to note that the kind of “rich map” Angle describes isn't created by every single Roomba sold since 2002, when the device hit the ...
[39]
[PDF] A Survey on Occupancy Perception for Autonomous Driving - arXiv
Each grid in this map is assigned a value that scores the probability of the grid space being occupied by obstacles. Semantic occupancy perception originates ...
[40]
[PDF] Object Discovery with a Mobile Robot - DukeSpace
Figure 2.1: A two-dimensional occupancy grid map. This map is of the interior of. Willow Garage (a general office environment, and the site of our experiments) ...Missing: demos | Show results with:demos
[41]
Autonomy for Mars Rovers: Past, Present, and Future - ResearchGate
Aug 5, 2025 · ... Since the 1990s, agencies such as NASA and JAXA have been using rover ... Occupancy grid mapping for rover navigation based on semantic ...
[42]
[PDF] Efficient Hierarchical Any-Angle Path Planning - Robotics
These planners and all RRT variants use wavemap's hi- erarchical occupancy map and multi-resolution ray tracer for fast traversability and visibility checking.
[43]
[PDF] building 2d and 3d adaptive-resolution occupancy maps using
Most existing occupancy grid mapping algorithms decompose the high-dimensional mapping problem into smaller one-dimensional problems by modelling the map as a ...<|separator|>
[44]
[PDF] OctoMap: A Probabilistic, Flexible, and Compact 3D Map ...
OctoMap is a probabilistic, flexible, and compact 3D map using octrees, modeling full 3D environments with free, unknown areas, and efficient updates.
[45]
an efficient probabilistic 3D mapping framework based on octrees ...
Our mapping approach is based on octrees and uses probabilistic occupancy estimation. It explicitly represents not only occupied space, but also free and ...
[46]
Dynamic Obstacle Avoidance Using Bayesian Occupancy Filter and ...
The goal of this paper is to solve the problem of dynamic obstacle avoidance for a mobile platform using the stochastic optimal control framework to compute ...
[47]
A Review of the Bayesian Occupancy Filter - PMC - NIH
Feb 10, 2017 · The paper presents the different parts of the sensor, including the formulation to provide a grid map representation from a multi-layer laser ...Missing: procedure | Show results with:procedure
[48]
Dynamic Occupancy Grid Map with Semantic Information Using ...
Apr 29, 2024 · 2.2. Dynamic Occupancy Grid Maps (DOGMs) · A DOGM is an environment perception technique used in robotics and autonomous driving applications.
[49]
[PDF] Predicting Semantic Map Representations From Images Using ...
We also qualitatively demonstrate how a Bayesian semantic occupancy grid framework can be used to accumulate map predictions across multiple cameras and ...Missing: post- | Show results with:post-
[50]
Gaussian process occupancy maps* - Simon T O'Callaghan, Fabio T ...
We introduce a new statistical modelling technique for building occupancy maps. The problem of mapping is addressed as a classification task where the ...Missing: hybrid | Show results with:hybrid
[51]
[PDF] Continuous Occupancy Maps Using Overlapping Local Gaussian ...
Nov 7, 2013 · Conventional occupancy grid maps [1] discretize the world into independent grid cells and update occupancy of each cell individually. This ...<|separator|>