Ergodic Coverage

• Also called: ergodic search, ergodic exploration, ergodic control
• Category: State estimation & navigation › Navigation
• Tags: coverage-planning, exploration, active-sensing, trajectory-optimization, search

A way of planning search paths so that the time a robot spends in each region matches how much information that region is expected to hold.

Definition

Ergodic coverage plans a robot's trajectory so that, over time, the fraction of time it spends in any region of the search area matches the probability mass a target distribution assigns to that region. The target distribution encodes where information is expected: likely locations of a missing person, a gas leak or a feature worth inspecting. A trajectory with this property is called ergodic with respect to the distribution, borrowing the term from dynamical systems, where it describes time averages that equal space averages.

The standard way to measure this was introduced by George Mathew and Igor Mezić in 2011. Both the trajectory's time-averaged statistics and the target distribution are expanded in a Fourier basis over the search area. The ergodic metric is a weighted sum of squared differences between the two sets of Fourier coefficients, with weights that decrease with frequency so that large-scale mismatches count more than fine detail. A value of zero means the trajectory is perfectly ergodic. The metric can be driven down with a feedback law, as in spectral multiscale coverage, or used as the cost in trajectory optimization, a line developed by Todd Murphey and colleagues.

Ergodic coverage sits between two simpler strategies. Pure exploitation sends the robot to the most likely spot and keeps it there; uniform coverage, such as a lawnmower pattern, ignores what is already known. An ergodic trajectory visits all areas with nonzero probability but spends longer where the distribution is higher, and it extends naturally to teams of robots whose combined time average is compared with the target. The main limitations are that the number of Fourier terms grows quickly with the dimension of the search space, and that results depend on the quality of the information map.

Why it matters

Search, inspection and environmental sensing rarely have a single best location to visit. Ergodic coverage gives a principled, tunable way to spread sensing effort according to prior knowledge, and it provides a single cost that can be combined with dynamics, time limits and multi-robot coordination.

Key applications

• Search and rescue with drones and ground robots
• Active sensing and target localization
• Environmental monitoring of gas, temperature or pollution fields
• Multi-robot coverage with shared information maps
• Exploratory motion for tactile or visual object inspection

In practice

A team running a drone search over a hillside builds a probability map of where a lost hiker is likely to be, from trails, terrain and last known position. They compute the map's Fourier coefficients up to a chosen order, then optimize a flight path that respects the drone's speed and acceleration limits while reducing the ergodic metric, for example with direct collocation over a fixed or free final time. The resulting path sweeps the likely trail sections repeatedly while still passing over the less likely ground. As camera detections come in, the map is updated, the coefficients are recomputed and the plan is re-optimized. With several drones, the combined time average of all paths is used in the metric so that they divide the work.

Common misconceptions

• Ergodic coverage means covering the whole area uniformly — it allocates time in proportion to the target distribution, so high-information areas receive more attention
• An ergodic trajectory goes straight to the most likely location — it deliberately keeps visiting lower-probability regions in proportion to their probability
• The metric scales easily to any number of dimensions — the Fourier basis grows exponentially with dimension, which limits direct use in high-dimensional spaces

Who should know this

• Drone and field robotics engineers planning search missions
• Researchers in active sensing and exploration
• Multi-robot coordination developers
• Trajectory optimization engineers

Related technologies

• Spectral Multiscale Coverage
• Trajectory Optimization
• Fourier Analysis
• Information-Theoretic Planning
• Lawnmower Coverage Patterns

Related terms

• Frontier-Based Exploration
• Trajectory Planning
• Direct Collocation
• UAV
• Swarm Robotics

Related projects

• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
• STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness