occupancy grid
In plain wordsA robot's map of the world drawn as a grid of small squares or cubes, each marked with the chance that something solid is there, so the robot knows where it can safely go.
A spatial map that divides the environment into a regular grid of cells — 2D squares or 3D voxels — each storing the probability that the corresponding region is occupied by an obstacle. Cells are updated independently from range sensors such as sonar, lidarlidar, n.: A sensor that measures distances by firing laser pulses and timing their reflections, building a 3D picture of its surroundings out of millions of points; widely used on robots and self-driving cars. and depth cameras using an inverse sensor model: a beam passing through a cell is evidence that it is free, and a return is evidence that its endpoint is occupied. Probabilities are usually stored as log-odds, so each Bayesian update becomes an addition and repeated observations accumulate. Occupancy grids tolerate noisy sensors and unstructured environments, need no predefined landmarks and feed directly into grid-based path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.; their drawbacks are memory, which hierarchical octree structures reduce, and the assumption that cells are independent. Self-driving perception has extended the idea to occupancy networks, which predict the 3D occupancy, and sometimes motion, of every voxel around a vehicle directly from camera images.
The vacuum's occupancy grid marks the chair legs as occupied, so it plans around them.
Origin
Introduced by Hans Moravec and Alberto Elfes at Carnegie Mellon University in 'High Resolution Maps from Wide Angle Sonar' (ICRA 1985) and developed in Elfes's 'Using Occupancy Grids for Mobile Robot Perception and Navigation' (IEEE Computer, 1989). Armin Hornung and colleagues' OctoMap (2013) popularized 3D octree occupancy maps.
Related
- simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners.
- path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.
- lidarlidar, n.: A sensor that measures distances by firing laser pulses and timing their reflections, building a 3D picture of its surroundings out of millions of points; widely used on robots and self-driving cars.
- mobile robotmobile robot, n.: A robot that travels around by itself — on wheels, tracks, legs, propellers or thrusters — such as a robot vacuum, warehouse cart, delivery robot or planetary rover.
- sensor fusionsensor fusion, n.: Combining readings from several different sensors, such as cameras, radar, lidar, GPS and motion sensors, to get a more accurate and reliable picture than any one sensor gives alone.
- 3D reconstruction3D reconstruction, n.: Building a 3D model of an object or place, its shape and often its colors, from photos, video or depth-sensor scans.
Sources
- Moravec, H. & Elfes, A. (1985). High resolution maps from wide angle sonar. Proc. IEEE ICRA 1985.
- Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation. IEEE Computer 22(6), 46–57.
Mentioned in
lidarlidar, n.: A sensor that measures distances by firing laser pulses and timing their reflections, building a 3D picture of its surroundings out of millions of points; widely used on robots and self-driving cars., path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map., simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners.