Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M2 Maps and Costmaps / M2-T6

Navigation · Theory · M2

M2-T6 — Traversability and 3D Maps

When the floor is not flat, free or occupied is not enough. A cell can be passable, steep, rough or a step too tall.

  • Lesson 6 of 6
  • Module 2: Maps and Costmaps
  • Theory
  • About 6 minutes to read

Hospital floors are flat; the loading dock, the car park and the garden path are not. Outdoors, and in any building with ramps, thresholds and kerbs, the question for a cell is how hard it is to cross. That answer comes from the shape of the terrain, and it needs a map that stores heights.

Learning objectives

After this lesson, you should be able to:

  • Derive slope, step height and roughness from an elevation map.
  • Combine them into a traversability cost with limits from the robot.
  • Compare 2.5D elevation maps, voxel grids and octrees by memory and capability.
  • Say when a 2D costmap is enough and when it is not.

The intuition

A wheelchair user reads a street without any numbers: a kerb with a dropped edge is fine, a flight of steps is not, a steep ramp is risky, loose gravel is slow. Each judgement uses one property of the ground. A robot makes the same judgements from a map of heights, and the properties are slope, step height and roughness.

The map that stores them is usually a 2.5D elevation map: a grid where every cell holds one height. It is cheap and enough for terrain. It is not enough for a space with something above the floor that matters, such as a table, a low doorway or a tree canopy. That needs a voxel map, which stores occupancy in 3D, at much higher cost.

Slope, step and roughnessA side view of terrain with a ramp, a step and a rough patch, with the slope angle, step height and roughness marked. slope θ = atan(rise / run) step height h roughness: spread of heights A robot reads the map cell by cell and needs three numbers per cell: slope, step and roughness.
The three quantities that decide whether a cell is passable: slope of the surface, the step to its neighbour, and roughness within the cell.

The mathematics

Terrain properties from heights

slope
θ=arctan⁡((∂z∂x)2+(∂z∂y)2)\theta =\arctan (\sqrt{(\frac{\partial z}{\partial x})^{2}+(\frac{\partial z}{\partial y})^{2}})
from differences of neighbouring heights / cell size
step
h=max⁡ over neighbours of ∣zcell−zneighbour∣h=\max \,\text{over neighbours of}\,\lvert z_{\text{cell}}-z_{\text{neighbour}}\rvert
roughness σ=standard deviation of heights in a window around the cell\text{roughness}\,\sigma =\text{standard deviation of heights in}\,a\,\text{window around the cell}

A traversability cost

Each property is compared with the limit of the robot and the worst ratio rules:

Traversability cost
c=max⁡(θθmax⁡, hhmax⁡, σσmax⁡)c=\max (\frac{\theta }{\theta _{\max}},\,\frac{h}{h_{\max}},\,\frac{\sigma }{\sigma _{\max}})
c≥1: not traversablec\ge 1:\,\text{not traversable}
0≤c<1: cost proportional to c0\le c<1:\,\text{cost proportional to}\,c
θmax
steepest slope the robot can climb and descend safely.
hmax
tallest step the wheels or legs can cross (about the wheel radius for wheels).
σmax
roughest ground it tolerates at working speed.

Choosing a map

MapStoresMemory for 20 × 20 m at 0.1 mGood forLimit
2D occupancyFree / occupied40 000 cellsFlat floorsNo heights
2.5D elevationOne height per cell (and variance)40 000 cells × a few valuesTerrain, ramps, stepsCannot represent overhangs
Voxel gridOccupancy per 3D cell1.2 million voxels for 3 m of heightDrones, arms, overhangsMemory grows with height
Octree (OctoMap)Occupancy in an adaptive treeFar less, where space is emptyLarge 3D scenesSlower lookups, tree maintenance

A worked example

Two numbers from a ramp. A ramp rises 0.15 m over 1.0 m. Its slope is atan(0.15 / 1.0) = 8.53°, a grade of 15%. The accessibility standard for building ramps is a maximum of 1:12 (8.33%, 4.76°), so this ramp is steeper than a ramp intended for wheelchairs, and a robot with θmax = 10° can use it at a cost of 8.53 / 10 = 0.85.

A cell. The robot has θmax = 10°, hmax = 0.06 m and σmax = 0.05 m. A cell has slope 6°, a step of 0.04 m to its neighbour and roughness 0.02 m. The ratios are 0.60, 0.67 and 0.40, so the cost is the largest, 0.67, set by the step. A step of 0.07 m would make the ratio 1.17 and the cell impassable, whatever its slope.

Memory. A 20 m × 20 m area at 0.1 m resolution is 200 × 200 = 40 000 cells in 2D. In 3D, three metres of height at 0.1 m add 30 layers: 1.2 million voxels. At one byte each that is 1.2 MB against 40 kB, thirty times more, which is why drones and arms use octrees and ground robots mostly use elevation maps.

Engineering implications and limitations

Elevation maps depend on localization

Heights are measured relative to the robot’s own estimated pose. A pose error of a few degrees in pitch turns flat ground into a slope. Terrain mapping systems carry the uncertainty with the heights (Fankhauser et al.).

Limits come from the robot, and from speed

The roughness a robot tolerates falls with speed. Make the limits a function of the speed command, or use a conservative speed on rough ground.

Legs and wheels

Legged robots can step over obstacles that block wheels, so their hmax is much larger and their cost often depends on foothold quality as well. The principle is the same; the limits and the extra properties differ.

Hand over to the 2D stack

A common design converts the elevation map into a 2D cost layer using the formula above, and then uses the normal costmap pipeline: layers, inflation and planners. Terrain becomes one more layer.

Common misconceptions

“Slope is the only thing that matters.”

A flat surface with a 10 cm step is impassable for a small wheel, and a gentle slope of loose gravel is slow. Slope, step and roughness are separate limits.

“3D maps are always better.”

They cost far more memory and time. Use a 2.5D map unless something above the floor matters.

“A traversability cost is a fact about the ground.”

It is a fact about the ground for one robot, at one speed.

“Height maps cannot represent tunnels or tables.”

A single-height map cannot. Multi-level surface maps or voxel maps can.

Engineering takeaways

  1. Slope, step height and roughness are separate properties derived from a map of heights.
  2. Traversability is the worst ratio of each property to the robot’s limit.
  3. 2.5D elevation maps are cheap and cover terrain; voxel maps and octrees cover overhangs at a high memory cost.
  4. Heights inherit the localization error, especially in pitch.
  5. Convert terrain into a layer of the costmap so the usual planners can use it.

References and further reading

Terrain mapping and 3D map references.

  • P. Fankhauser, M. Bloesch and M. Hutter, “Probabilistic Terrain Mapping for Mobile Robots with Uncertain Localization”, IEEE Robotics and Automation Letters, 3(4), 2018.
  • A. Hornung, K. Wurm, M. Bennewitz, C. Stachniss and W. Burgard, “OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees”, Autonomous Robots, 34(3), 2013.
  • M. Wermelinger et al., “Navigation Planning for Legged Robots in Challenging Terrain”, IEEE/RSJ IROS, 2016.
  • US Access Board, “ADA Standards for Accessible Design”, section 405 (ramps), 2010.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A ramp rises 0.30 m over 1.0 m. What is its slope in degrees, and is it within a robot limit of 15°?

Explanation

atan(0.30) = 16.7°. It exceeds 15°, so the robot may not use it.

Question 2

Why can a 2.5D elevation map not represent the space under a table?

Explanation

It stores one height per cell, so a cell cannot be both a tabletop and free floor underneath. A voxel map stores occupancy at several heights per cell.

Question 3

A cell has ratios 0.5 (slope), 0.9 (step) and 0.3 (roughness). What is its traversability cost, and which property limits the robot?

Explanation

The cost is the largest ratio, 0.9, and the step height limits the robot.

What’s next

That completes the maps. Next module: finding a route through them with graph search.

Next lesson

M3-T1 — Search Problems on Grids and Graphs

Define a search problem (states, actions, costs, goal) and compare 4- and 8-connected grids.

Nothing below is required to finish this lesson.