Measurement Maximizing Adaptive Sampling with Risk Bounding Functions

Benjamin J. Ayton, Brian Williams, Richard CamilliAAAI 2019 · DOI

Abstract

Autonomous exploration in uncertain environments, such as underwater drone missions, requires a delicate balance between seeking high-reward information and avoiding catastrophic collisions. Traditional path planning often employs static risk budgets, which fail to capture the nuanced decision-making required when high-value discoveries justify increased risk. This paper presents a novel approach to adaptive sampling using "risk bounding functions" within a Chance Constrained Markov Decision Process (CCMDP) framework. Our method, the Vulcan algorithm, allows agents to dynamically trade risk for reward while providing provable safety guarantees.

Introduction

In autonomous exploration, high-reward areas—such as hydrothermal vents or mineral deposits—are frequently located near hazardous obstacles. Standard autonomous agents typically operate under a fixed risk constraint (e.g., a 1% maximum probability of failure). However, this rigid approach is suboptimal; a human scientist might accept a higher risk for a groundbreaking discovery while demanding extreme caution for routine measurements. The challenge lies in developing an adaptive policy that can update its plan in real-time based on new measurements, dynamically trade off risk versus reward, and guarantee that overall chance constraints are satisfied.

Methodology

The authors frame the exploration task as a Chance Constrained Markov Decision Process (CCMDP). The core of the approach involves several integrated components:

Gaussian Processes (GP)

GPs are utilized to model unknown environmental fields (e.g., temperature or chemical concentrations). The GP provides a predictive mean for unsampled locations and a measure of uncertainty, which guides the agent's information-gathering strategy.

Risk Bounding Functions ($\Delta$)

The central innovation is the definition of risk as a function of expected reward, $\Delta(x)$. Typically non-decreasing and concave, this function dictates that an agent can "spend" more risk to acquire higher rewards, but the marginal cost of risk increases as rewards grow. This mimics human decision-making—becoming "braver" when the stakes are high and "cautious" when there is little to gain.

Figure 1: Illustration of adaptive behavior where (a) high reward gradients justify closer proximity to obstacles compared to (b) uniform low-reward environments.

The Vulcan Algorithm

Vulcan is an extension of Monte Carlo Tree Search (MCTS) designed for adaptive sampling. It constructs a search tree of potential future actions and observations, pruning any branches that violate the risk bounding function. To maintain computational tractability and ensure safety, the algorithm verifies the existence of a "worst-case state history"—a sequence of future actions that remains safe regardless of future measurement outcomes.

Experimental Evaluation

The framework was evaluated using real-world bathymetric data from NOAA survey H10992 (East of Boston Harbor), providing a realistic and complex obstacle field. Synthetic measurement fields were overlaid to test the agent's response to varying reward signals.

Safety and Performance Results

To statistically verify safety guarantees, 10,000 randomized Monte Carlo trials were conducted. In a test with a risk bounding function of $\Delta(x) = 0.001x$, the expected cumulative reward allowed for a 6.49% failure rate. The actual measured failure rate was only 2.08%, proving the method is safe and appropriately conservative. Agents utilized about 32% to 63% of their "permitted risk," showing that they only take risks when the environment's geometry and rewards demand it.

Figure 5: Agent trajectory in a complex bathymetric environment using a linear risk bounding function $\Delta(x) = 0.0001x$.

Conclusion

The proposed framework successfully demonstrates that linking risk to reward allows for more efficient autonomous exploration without compromising safety. While the current use of Boole’s Inequality for risk approximation is somewhat conservative, the Vulcan algorithm provides a robust foundation for anytime planning in high-stakes environments. Future work will explore methods to reduce conservatism and extend the framework to multi-agent systems.

Summary updated

BibTeX
@inproceedings{ayton2019measurement,
  author = {Benjamin J. Ayton and Brian Williams and Richard Camilli},
  title = {{Measurement Maximizing Adaptive Sampling with Risk Bounding Functions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017511},
}
Figure