Occupancy grid maps are a type of representation of an environment, and is commonly used by mobile robots for tasks such as path planning, localization, tracking, and many more. This article is an introduction to occupancy grid maps.
Occupancy grid maps are used to represent a robot workspace as a discrete grid. They can be thought of as an architectural floorplan, which store an image-based representation of occupied and unoccupied space in an area. Occupied space can include walls and objects in the environment, while unoccupied space are areas the robot can move through, such as walkways.
The process of mapping such an environment involves probabilistic algorithms for mobile robots, which generally compute approximate posterior estimates for each obstacle in the environment. Both 2D and 3D occupancy grid maps can be generated.
Some examples of sensors used in collecting data for mapping can be:
Algorithms to generate occupancy grid maps are filtering problems that receive noisy, uncertain sensor measurement data, with the assumption that the robot pose is known. This is the opposite of a localization problem.
Mathematically, an occupancy grid map follows a probabilistic algorithm, formulated as:
In an algorithmic form, it may be implemented as the following pseudo code:
occupancy_grid_mapping(l_t-1, x, z): for m in cells: if m in perceptual field of z: l_t = l_t-1 + inv_sensor_model(m, x, z) - l_0 # cell update else l_t = l_t-1 return l_t Inverse Sensor Model: Specifies a distribution over a binary state variable as a function of the measurement zt.
A binary occupancy grid uses true and false values to represent occupied and free spaces respectively. The map assumes every area corresponding to a cell is either completely free or occupied. The grid shows where obstacles are in the environment, and whether the robot can navigate through it. Binary grid maps are used when memory constraints are a concern.
In general, binary representations will follow:
This model also assumes that the world is static (most mapping systems make this assumption) and each cell is independent of each other.
Sample Binary Occupancy Grid Map (source: MATLAB)
Probability occupancy grids uses probability values to generate a more detailed map than binary representations. This is usually the preferred method for using occupancy grids and is commonly referred to as simply an occupancy grid. Instead of binary 0 and 1 values, probabilistic occupancy grid maps have cells represented by a probability score of how likely that cell contains an obstacle. Probabilistic values can give better fidelity of objects in the space.
Sample Occupancy Grid Map (source: MATLAB)
The grid map cells in a 3D representation are voxels, and map information is stored as probabilistic values in an octree data structure. Similarly, these probability values represent the occupancy of locations in the environment.
Sample 3D Occupancy Grid Map (source: MATLAB)
Octree Data Structure: A hierarchical tree structure used for recursive subdivision of an environment into 8 cubic volumes (children), known as voxels, until it reaches a desired resolution (voxel size). Each node stores the probability values for locations in the map. There are point-region (PR) octrees and matrix-based (MX) octrees.
Published: October 19, 2023
Reinforcement Learning (RL) is a subtopic in Artificial Intelligence, which uses a more organic learning approach. It is vastly different from traditional Machine Learning and Deep Learning, which are dependent on swaths of highly prepared data. In contrast, RL models learn primarily through simulation and experience, much like humans. This article covers the very basic concepts used across RL topics.
Published: August 15, 2023
Segmentation is a popular vision problem that is concerned with analysis and object or scene understanding of the contents of a given input scene. Most commonly, this is used with images, but segmentation can also be performed on a range of datatypes such as videos or 2D and 3D point clouds. The ability of segmentation models to detect objects and identify their location makes these models incredibly useful in projects involving autonomous machines and mapping and localization.
Published: July 19, 2023
The Robot Operating System (ROS), in short, is a communication tool used in robotics to facilitate transfer of messages or data in a multi-device system. In this article, I go through the very basics of ROS and how to get started with it.
Published: May 26, 2023
Docker is a useful tool widely used today to facilitate software development and shipping code. This article covers a comprehensive overview of docker containers and how to use them.
