Time Optimal Ergodic Search

Authors: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

Minimise search time subject to an upper bound γ on the ergodic metric: one parameter sets how thorough coverage is, and the optimiser picks the trajectory duration.

Why it matters

For search and rescue or survey flights, the operator can specify how thorough a sweep must be and get the fastest trajectory that meets it, instead of guessing a duration. Constraints such as speed limits and obstacle barriers sit in the same optimisation, and the planned times carried over to a real quadrotor within 1.5 s.

Problem

Ergodic search plans continuous trajectories that spend time in each region in proportion to its information, but existing methods fix the planning horizon in advance, so the user cannot trade search thoroughness against time. Minimising time while minimising the ergodic metric is ill-posed, because a trajectory only becomes fully ergodic as time goes to infinity.

Proposed solution

The ergodic metric becomes an inequality constraint E ≤ γ inside a minimum-time problem, so γ sets how coarse or fine the coverage must be and the final time tf is a decision variable. The authors prove local optimality conditions with Pontryagin's maximum principle using an 'extended ergodic state', then solve the problem in practice by direct transcription over N knot points (Δt = tf/N) with a custom augmented-Lagrangian solver. Obstacles are handled with discrete control barrier function constraints.

Key insights

Treating ergodicity as a bound rather than an objective makes minimum-time search well-posed; as γ → 0 the optimal time grows without limit, matching ergodic theory
Lowering γ by two orders of magnitude (0.1 to 0.001) on a four-peak information map roughly doubled the optimal time (9.86 s to 19.59 s), while even the coarse plan still visited every peak
Time-normalised control effort is higher in the middle of the γ range, where the trajectory must trade coverage against time, than at either extreme
Smooth initial guesses (linear interpolation) give consistent solutions; noisy or random initial trajectories fall into equally ergodic local minima with longer times

Main results

Uniform coverage with a 2-D point mass: varying γ gives trajectories of 5–10 s with coverage equivalent to a fixed-horizon 10 s ergodic trajectory (E = 0.007)
Non-uniform information map: optimal times of 9.86 s at γ = 0.1 and 19.59 s at γ = 0.001
Sensitivity at γ = 0.05: varying initial tf from 4 to 8 s gives an optimal time of 4.97 ± 0.23 s; varying knot points N from 50 to 600 gives 5.45 ± 0.39 s
Cluttered 2-D environment with control barrier functions: optimal times from 7.79 s at γ = 0.2 to 11.85 s at γ = 0.002, with the barrier constraints keeping trajectories away from every obstacle
Drone experiments at γ = 0.1, 0.05 and 0.01: executed flight times were within 1.5 s of the optimised times; the Fig. 1 trajectory covers the cluttered area in 13.5 s
The solver also produced uniform coverage trajectories for a nonlinear 3-D aircraft model among random ellipsoid obstacles

Limitations

The authors state solutions are only locally optimal, because the ergodic metric is highly nonlinear and non-convex
The authors found the Pontryagin optimality conditions numerically unstable for long horizons, so the practical solver is a direct transcription method
Planning is offline with known obstacles; the authors list real-time planning with unknown obstacles and environmental uncertainty as future work
Results depend on the initial trajectory and on N; the solver stops returning solutions for very small γ, where the required time becomes very large
The authors note computational cost grows with the dimension of the exploration space

Field impact

Winner of the RSS 2023 Best Paper Award. The authors release code at github.com/ialab-yale/time_optimal_ergodic_search and a multimedia demonstration page.

Abstract

Robots with the ability to balance time against the thoroughness of search have the potential to provide time-critical assistance in applications such as search and rescue. Current advances in ergodic coverage-based search methods have enabled robots to completely explore and search an area in a fixed amount of time. However, optimizing time against the quality of autonomous ergodic search has yet to be demonstrated. In this paper, we investigate solutions to the time-optimal ergodic search problem for fast and adaptive robotic search and exploration. We pose the problem as a minimum time problem with an ergodic inequality constraint whose upper bound regulates and balances the granularity of search against time. Solutions to the problem are presented analytically using Pontryagin's conditions of optimality and demonstrated numerically through a direct transcription optimization approach. We show the efficacy of the approach in generating time-optimal ergodic search trajectories in simulation and with drone experiments in a cluttered environment. Obstacle avoidance is shown to be readily integrated into our formulation, and we perform ablation studies that investigate parameter dependence on optimized time and trajectory sensitivity for search.

Open Source Robotics