Time-optimal ergodic search: Multiscale coverage in minimum time

Search and exploration capabilities are essential for robots to inspect hazardous areas, support scientific expeditions in extreme environments, and potentially save human lives in natural disasters. The variability of scale in these problems requires robots to reason about time alongside their dynamics and sensor capabilities to effectively assess and explore for information. Recent advances in ergodic search methods have shown promise in supporting trajectory planning for exploration in continuous, multiscale environments with dynamics consideration. However, these methods are still limited by their inability to effectively reason about and adapt the time to explore in response to their environment. This ability is crucial for adapting exploration to variable-resolution information-gathering tasks. To address this limitation, this paper poses the time-optimal ergodic search problem and investigates solutions for fast, multiscale, and adaptive robotic exploration trajectories. The problem is formulated as a minimum-time problem with an ergodic inequality constraint whose upper bound specifies the amount of coverage needed. We show the existence of optimal solutions using Pontryagin’s conditions of optimality, and we demonstrate effective, minimum-time coverage numerically through a direct transcription optimization approach. The efficacy of the approach in generating time-optimal search trajectories is demonstrated in simulation under several nonlinear dynamic constraints, and in a physical experiment using a drone in a cluttered environment. We find that constraints such as obstacle avoidance are readily integrated into our formulation, and we show through an ablation study the flexibility of search capabilities at various scales. Last, we contribute a receding-horizon formulation of time-optimal ergodic search for sensor-driven information-gathering and demonstrate improved adaptive sampling capabilities in localization tasks.