RAnGE: Reachability Analysis for Guaranteed Ergodicity

Henry P. Berger, Ian Abraham

Abstract

This paper investigates performance guarantees on coverage-based ergodic exploration methods in environments containing disturbances. Ergodic exploration methods generate trajectories for autonomous robots such that time spent in an area is proportional to the utility of exploring in the area. However, providing formal performance guarantees for ergodic exploration methods is still an open challenge due to the complexities in the problem formulation. In this work, we propose to formulate ergodic search as a differential game, in which a controller and external disturbance force seek to minimize and maximize the ergodic metric, respectively. Through an extended-state Bolza-form transform of the ergodic problem, we demonstrate it is possible to use techniques from reachability analysis to solve for optimal controllers that guarantee coverage and are robust against disturbances. Our approach leverages neural-network based methods to obtain approximate value function solutions for reachability problems that mitigate the increased computational scaling due to the extended state. As a result, we are able to compute continuous value functions for the ergodic exploration problem and provide performance guarantees for coverage under disturbances. Simulated and experimental results demonstrate the efficacy of our approach to generate robust ergodic trajectories for search and exploration with external disturbance force.

Introduction

Autonomous robots are increasingly deployed for ergodic exploration, a strategy where a robot's time spent in a region is proportional to the "information density" or utility of that region. This is critical for applications like search-and-rescue or environmental monitoring. While ergodic control is effective in static, predictable environments, it lacks formal performance guarantees in the presence of real-world disturbances like wind or current.

Ergodic coverage goal: matching time-averaged statistics (grey) to the spatial information density (red).

Traditional ergodic controllers may fail to visit high-priority areas if external forces push the robot off course. This work introduces RAnGE (Reachability Analysis for Guaranteed Ergodicity), a framework that applies reachability analysis—a verification technique typically used for safety—to ensure mission performance and coverage goals are met even under worst-case disturbances.

Methodology

To make ergodic reachability mathematically tractable, the authors introduced several innovations:

1. State Augmentation

The ergodic metric is inherently history-dependent, as it compares the distribution of the entire trajectory to a target map. This does not fit the standard Bolza form required for reachability analysis. RAnGE addresses this by introducing an augmented-state variable ($z$) that tracks the Fourier coefficients of the robot's spatial distribution over time. This transforms a trajectory-wide metric into a terminal cost problem.

2. Differential Game Formulation

The problem is modeled as a zero-sum differential game. The controller acts as a player attempting to minimize the ergodic error, while the disturbance (e.g., wind) acts as an adversary attempting to maximize it. By solving for the Nash equilibrium of this game, the system identifies a controller that is robust against the worst possible disturbance.

3. Neural HJI Solver

The resulting Hamilton-Jacobi-Isaacs (HJI) partial differential equations are subject to the "curse of dimensionality." To solve them, the authors utilize a neural-network-based approach (DeepReach) using periodic activation functions to approximate the continuous Value Function. This Value Function provides a "performance floor," mapping the best possible coverage error the robot can guarantee from any given state.

Results and Discussion

The RAnGE framework was validated through both high-fidelity simulations and physical hardware experiments.

Experimental setup: A Crazyflie drone executing an ergodic trajectory while resisting disturbances from external fans.

Simulation Performance

In 1D double-integrator simulations with bimodal information maps, RAnGE consistently outperformed standard Model Predictive Control (MPC) and robust variants (reMPC) when subjected to "smart" disturbances. While standard controllers might achieve lower error in noise-free environments, RAnGE maintained a strict upper bound on error even when the disturbance actively tried to push the robot away from high-information zones.

Hardware Validation

Real-world experiments were conducted using a Bitcraze Crazyflie 2.1 quadrotor. The drone was tasked with exploring a 1D space while fans provided constant and variable wind disturbances. The neural-network-based controller successfully generated real-time trajectories that satisfied ergodic requirements, demonstrating the practical feasibility of the reachability-based approach on resource-constrained hardware.

Conclusion

RAnGE provides a rigorous mathematical foundation for guaranteeing robot mission performance in uncertain environments. By treating coverage as a reachable goal, it ensures that autonomous systems can complete complex exploration tasks despite external interference. Future work will focus on scaling the framework to higher-dimensional search spaces and incorporating dynamic obstacles into the reachability calculations.

Summary updated

Abstract

This paper investigates performance guarantees on coverage-based ergodic exploration methods in environments containing disturbances. Ergodic exploration methods generate trajectories for autonomous robots such that time spent in an area is proportional to the utility of exploring in the area. However, providing formal performance guarantees for ergodic exploration methods is still an open challenge due to the complexities in the problem formulation. In this work, we propose to formulate ergodic search as a differential game, in which a controller and external disturbance force seek to minimize and maximize the ergodic metric, respectively. Through an extended-state Bolza-form transform of the ergodic problem, we demonstrate it is possible to use techniques from reachability analysis to solve for optimal controllers that guarantee coverage and are robust against disturbances. Our approach leverages neural-network based methods to obtain approximate value function solutions for reachability problems that mitigate the increased computational scaling due to the extended state. As a result, we are able to compute continuous value functions for the ergodic exploration problem and provide performance guarantees for coverage under disturbances. Simulated and experimental results demonstrate the efficacy of our approach to generate robust ergodic trajectories for search and exploration with external disturbance force.
BibTeX
@misc{berger2024range,
  author = {Henry P. Berger and Ian Abraham},
  title = {{RAnGE: Reachability Analysis for Guaranteed Ergodicity}},
  year = {2024},
  eprint = {2404.03186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.03186},
}
Figure