Active Calibration of Reachable Sets Using Approximate Pick-to-Learn

1. Problem Statement

In safety-critical dynamical systems (e.g., autonomous drones), reachability analysis is essential for providing safety guarantees. Traditionally, these methods rely on precise, pre-specified models. However, modern approaches use learned models (e.g., neural networks or Gaussian Processes) to estimate reachable sets, which introduces two major challenges:

1. Model Error: Learned models may be inaccurate, especially near the boundaries of the reachable set, potentially misclassifying unsafe states as safe.
2. Calibration Cost: To provide probabilistic safety guarantees, the learned reachable set must be "calibrated" using ground-truth samples. Standard calibration methods (like scenario optimization) often require a large number of expensive samples to achieve strong guarantees. Furthermore, existing methods often assume samples are independent and identically distributed (IID), which is violated when the sampling process is adaptive (i.e., where the next sample depends on previous results).

The Core Question: How can we calibrate a learned reachable set efficiently (using fewer samples) while maintaining rigorous probabilistic guarantees, even when the sampling strategy is adaptive?

2. Methodology: Approximate Pick-to-Learn

The authors propose a framework that treats reachable set calibration as an Active Learning problem. Instead of sampling randomly, the system actively chooses the most informative data points to minimize error. The methodology consists of three key components:

A. Framing Calibration as Active Learning

The authors define the calibration process as iteratively selecting states $x$ to query the ground-truth value function $V(x, T)$. The goal is to reduce the error of the hypothesis $h$ (the learned value function) across the state space until it falls below a threshold $\omega$ with high probability.

B. Adapting "Pick-to-Learn" for Active Settings

The paper adapts the Pick-to-Learn algorithm (originally designed for offline supervised learning) to the active learning setting.

• Standard Pick-to-Learn: Iteratively selects the data point where the current hypothesis performs worst (maximizes error) to build a "compressed" dataset that guarantees generalization bounds.
• The Challenge: In active learning, the true error $e_h(z)$ is unknown for unlabeled data, so the "worst" point cannot be identified directly.
• The Solution (Approximate Pick-to-Learn): The authors introduce an approximate error function $\hat{e}_{h,\eta}(x)$ that estimates the true error. The algorithm selects the next sample by maximizing this approximate error:
  $$\bar{x} = \arg\max_{x \in D \setminus Q} \hat{e}_{h,\eta}(x)$$
  where $D$ is a pool of candidate states and $Q$ is the set of already sampled states.

C. Conformal Prediction for Guarantees

To ensure the approximate error $\hat{e}_{h,\eta}$ is a valid proxy for the true error $e_h$, the authors employ Conformal Prediction.

• They use a separate calibration set $C$ to compute a scaling factor $\lambda$.
• This factor adjusts the heuristic error estimate $a_{h,\eta}$ into a statistically valid upper bound $\hat{e}_{h,\eta} = a_{h,\eta} + \lambda \mu_{h,\eta}$.
• Theoretical Guarantee: Theorem 1 proves that with probability at least $1-\alpha$, the true error of the final hypothesis on unseen states is bounded by a function of the size of the compressed set $|Q|$. This holds even though the samples were chosen adaptively, overcoming the IID assumption limitation of prior works.

3. Key Contributions

1. Active Learning Framework for Reachability: The first method to frame reachable set calibration as an active learning problem, allowing the selection of only necessary samples rather than random sampling.
2. Approximate Pick-to-Learn Algorithm: A novel extension of the Pick-to-Learn meta-algorithm that incorporates conformal prediction to handle the unknown true error in active settings.
3. Rigorous Probabilistic Guarantees: Theoretical proof that the method provides tight generalization bounds for the learned reachable set, ensuring safety guarantees hold with high probability despite the adaptive sampling process.
4. Sample Efficiency: Demonstrated ability to achieve high-accuracy reachable sets with significantly fewer samples compared to baseline methods.

4. Experimental Results

The method was evaluated in a simulated drone racing scenario (12-dimensional state space) where an ego-drone must overtake another drone while avoiding collisions.

• Baselines: Compared against "LB Iterative" (iterative level-set adjustment) and "LB Robust" (robust scenario optimization).
• Metrics: Number of samples required, False Positive Rate (FPR), False Negative Rate (FNR), and the tightness of the probabilistic bound ($\bar{\epsilon}$).
• Findings:
  • Sample Efficiency: The proposed method required fewer samples to calibrate the model compared to the baselines.
  • Accuracy: It achieved lower FPR and FNR, particularly in complex scenarios (e.g., "Slice 2" in the paper) where the learned value function was less accurate and baseline level-set adjustments failed.
  • Trade-offs: The method effectively balanced the trade-off between sample complexity and the strength of the safety guarantee. While "LB Robust" could achieve a slightly tighter bound ($\epsilon$) in some cases, it required a prohibitive number of samples to do so.
  • Scalability: The method scaled to higher dimensions (3D and 4D slices), though performance required tuning of confidence parameters ($\alpha$) to manage the trade-off between sample count and error rates.

5. Significance and Impact

• Bridging Learning and Safety: This work provides a critical bridge between data-driven learning and formal safety verification. It allows safety-critical systems to utilize learned models without sacrificing rigorous guarantees.
• Overcoming Adaptivity: By using conformal prediction to calibrate the sampling strategy rather than just the set, the authors solve the theoretical hurdle of non-IID (adaptive) sampling, which has limited previous active learning applications in safety.
• Practical Application: The reduction in sample complexity is vital for real-world applications (like autonomous aviation or robotics) where collecting ground-truth data (e.g., crashing a drone to test a boundary) is expensive or dangerous.
• Future Direction: The authors suggest this framework can be extended beyond calibration to the synthesis of reachable sets themselves and propose future hardware experiments to validate these findings in physical systems.

In summary, the paper presents a mathematically rigorous, sample-efficient framework for ensuring the safety of learned control policies by actively identifying and correcting the most critical errors in the reachable set estimation.