Stein Variational Ergodic Search

Darrick Lee, Cameron Lerch, Fabio Ramos, Ian Abraham

Introduction

Robotic exploration requires a delicate balance between thorough area coverage and rapid adaptation to new information or dynamic obstacles. This paper introduces Stein Variational Ergodic Search, a framework that treats exploration as a probabilistic inference problem. By integrating ergodic search—which aligns time spent in a region with its information density—with Stein Variational Gradient Descent (SVGD), the authors enable robots to optimize a diverse distribution of trajectories in parallel.

Traditional ergodic search methods typically optimize a single path. This approach suffers from two primary limitations:

  1. Singularity: A single path lacks redundancy. If the environment changes or the path becomes blocked, the robot has no immediate alternative.
  2. Computational Complexity: Finding a diverse set of paths is difficult due to the non-convex nature of the problem. Standard optimization often leads to "mode collapse," where multiple candidate paths converge into the same suboptimal solution.

Methodology: Bridging Ergodic Search and SVGD

The proposed method redefines the search for a trajectory as the search for a posterior distribution.

  • Ergodic Search as Inference: The likelihood of a trajectory is defined by its ergodic cost, representing how effectively it covers the target space.
  • Stein Variational Gradient Descent (SVGD): Instead of a single path, the algorithm evolves a set of "particles," where each particle represents a complete trajectory. SVGD applies a repulsive force via a kernel function to keep these trajectories distinct, ensuring the robot maintains multiple unique exploration strategies.
  • Markov Kernels: To manage the high dimensionality of trajectories, the authors employ a "Markov RBF kernel." This leverages temporal structure to maintain diversity without the computational overhead typically associated with high-dimensional Stein methods.
  • Parallelization: The particle-based approach is highly parallelizable. Using GPU acceleration (via JAX), the system can reason about over 50 different strategies simultaneously in milliseconds, making it suitable for real-time Model-Predictive Control (MPC).

Experimental Validation

The framework was evaluated across several simulated and physical benchmarks, including 2D/3D coverage simulations, a 100m x 100m forest environment with obstacles, and scenarios involving dynamic obstacles with unknown velocities.

Physical validation using a Crazyflie quadcopter, demonstrating multiple exploration trajectories in a 3D environment with obstacles.

The approach was further validated using a Crazyflie 2.1 nano-quadcopter. In a 3D space with physical obstacles tracked by a Lighthouse VR system, the drone successfully executed diverse exploration paths as seen in the light-trail visualization above.

Key Results

The Stein Variational approach demonstrated significant improvements over baseline methods:

  • Prevention of Mode Collapse: As shown in the diversity metrics, the Stein approach maintains a high log-determinant of the kernel matrix, indicating a diverse set of solutions. In contrast, vanilla ergodic optimization quickly collapses into a single trajectory.
  • Real-time Adaptation: In dynamic environments, the controller successfully switched between redundant coverage strategies online, maintaining safety and efficiency.
  • Superior Mapping: When integrated with sonar-based mapping, the method outperformed myopic planners across Gaussian Process metrics (SMSE, MSLL), proving that diverse, long-horizon planning leads to more accurate maps.
Comparison of trajectory diversity (Log Det. Kernel) between Stein Variational Ergodic Search and vanilla ergodic optimization, showing the prevention of mode collapse.

Conclusion and Future Work

Stein Variational Ergodic Search provides a robust, parallelizable solution for multi-modal robotic exploration. While highly effective in 2D and 3D spaces, future work includes scaling the Fourier-based ergodic cost functions to higher-dimensional spaces (e.g., >10D) and developing automated methods for online kernel hyperparameter tuning. Additionally, applying these methods to systems with complex contact dynamics remains an open area for research.

Summary updated

Abstract

Exploration requires that robots reason about numerous ways to cover a space in response to dynamically changing conditions. However, in continuous domains there are potentially infinitely many options for robots to explore which can prove computationally challenging. How then should a robot efficiently optimize and choose exploration strategies to adopt? In this work, we explore this question through the use of variational inference to efficiently solve for distributions of coverage trajectories. Our approach leverages ergodic search methods to optimize coverage trajectories in continuous time and space. In order to reason about distributions of trajectories, we formulate ergodic search as a probabilistic inference problem. We propose to leverage Stein variational methods to approximate a posterior distribution over ergodic trajectories through parallel computation. As a result, it becomes possible to efficiently optimize distributions of feasible coverage trajectories for which robots can adapt exploration. We demonstrate that the proposed Stein variational ergodic search approach facilitates efficient identification of multiple coverage strategies and show online adaptation in a model-predictive control formulation. Simulated and physical experiments demonstrate adaptability and diversity in exploration strategies online.
BibTeX
@inproceedings{lee2024stein,
  author = {Darrick Lee and Cameron Lerch and Fabio Ramos and Ian Abraham},
  title = {{Stein Variational Ergodic Search}},
  booktitle = {Robotics: Science and Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=9UtAbCZ4AL},
}
Figure