From Global to Local: Hierarchical Probabilistic Verification for Reachability Learning

The gist The authors propose a hierarchical probabilistic verification framework for reachability learning that bridges offline global certification and online local refinement to provide scalable safety guarantees in high-dimensional systems.

Hierarchical Verification Framework

The proposed framework is a multi-tier structure that couples probabilistic global certification with adaptive local refinement, integrating a learned reachability policy with a model-based controller for safe goal-reaching The framework features three tiers of control logic detailed in Algorithm 2.

1 Tier 0: Target Maintenance Mode, which applies a fast MPPI controller if the state is in the target set T.

Tier 1: Global Verification Mode, where the learned policy πlp is used if the state lies within Vglobal.

Tier 2: Local Refinement Mode, which utilizes the “reclaimed” local refinement from Algorithm 1 if xt is in V / global but also in Vlocal.

Tier 3: Safe Recovery Mode, where a recovery MPPI controller warm-started by πlp is used if the state cannot be certified by either the global or local verification.

Scenario-Based Local Expansion

The framework uses scenario optimization to provide an efficient method for safe set expansion, recovering regions that would otherwise be discarded by conservative global verification.

1 Scenario Optimization Theory is employed to solve the constraint min z∈Z c⊤z s.t. P∆ h(z, ∆) > 0 ≤ ϵ.

The scenario approach replaces the chance constraint with N deterministic constraints sampled from ∆, leading to the program z∗N = arg min z∈Z c⊤z s.t. N i=1 h(z, δ(i)) ≤ 0.

Theorem 1 provides a bound on the number of deterministic constraints N required to achieve a probabilistic guarantee.

Probabilistic Safety Guarantees

The framework provides theoretical guarantees for both globally and locally verified sets, ensuring safety under local refinement.

Proposition 1 states that for the global certificate, if x ∈ Vglobal, a probabilistic guarantee is achieved: PS1(PX¯ Vγ(xt) < 0 ∩ Vˇγ(¯xt, T) ≥ 0 ≤ ϵ) ≥ 1 − β.

If xt ∈ V / global but xt ∈ Vlocal, the local certificate provides the guarantee: PS2(PVlocal (sup t∈[0,T] gγ(ξπlp x (j) 0, t) ≤ 0) ≤ ϵ) ≥ 1 − β.

Probabilistic Dynamics Bounding

For global verification of the RA set, the authors estimate a trajectory deviation quantity ∆x∗t using samples to alleviate conservatism.

They collect N i.i.d. scenario pairs and solve the scenario program ∆x∗t = min ∆xt∈R s.t. N i=1 x(i)t − x¯(i)t 2 ≤ ∆xt.

By Theorem 1, the trajectory deviation remains bounded by ∆x∗t with probability 1 − ε and confidence 1 − β.

Theorem 2 establishes that for states in Vglobal, the failure probability for safely reaching T is bounded by ϵ with confidence 1 − β.

Local Growth Iterative Refinement

To reclaim safe regions misclassified as unsafe, the method presents a quickly computed, high-resolution local refinement on the boundary of Vglobal.

The refinement radius r∗ is obtained by solving a scenario program to find the maximum verifiable radius r s.t. N j=1 sup t∈[0,T] gγ(ξπlp x (j) 0, t) > 0, ∀x(j) 0 ∈ Br(ˇxt).

Theorem 1 is used to obtain a guarantee on the local growth refinement: PS2(PVlocal (sup t∈[0,T] gγ(ξπlp x (j) 0, t) ≤ 0) ≤ ϵ) ≥ 1 − β.

Empirical Validation

Simulation results in drone racing demonstrate improved success rates in safe overtaking compared to baseline methods.

Hypothesis 1 shows that the reachability-based guidance of our method leads to a higher success rate than soft- and hardconstrained model-based controllers or RL policies.

Hypothesis 2 highlights the necessity of both the switching mechanism and the reachability policy as none of the other baselines achieved the same rate of success as our hierarchical framework.

The results show that our method achieves a higher rate of success than its safe counterparts in drone racing simulations.

Conclusion

In this work, the authors propose an efficient hierarchical probabilistic verification framework for reachability learning that unifies global, local, offline, and online verification. By combining a coarse global certificate via scenario optimization with local convex refinement, the approach reduces conservatism while focusing computation on critical regions. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control. The framework provides probabilistic safety guarantees and improves performance in safety-critical tasks, as demonstrated in drone racing simulations. Future work includes hardware validation and extension to more complex multi-agent settings and uncertain real-world environments. The switching mechanism between learned and model-based controllers ensures safe and efficient control.

1. No longer constrained by conservative global certification, the system can utilize Scenario-Based Local Expansion to recover regions that would otherwise be discarded by conservative global verification. This allows for a more aggressive exploration of safe states near boundaries while maintaining probabilistic guarantees.

2. The AI system gains adaptive control capability through the Hierarchical Safe, Target-Reaching Framework, which switches between a learned reachability policy and a model-based controller. When the state is outside the reach-avoid set, it employs a warm-started MPPI controller to produce a safer control action.

3. The system can perform high-resolution verification locally by using Iterative Growth Iterative Refinement to define a refined local safe set, even if it is not in the coarse global set. This allows the agent to reclaim safe regions that may be misclassified unsafe, reducing conservatism in critical areas.

4. The system achieves enhanced goal-reaching success rates by integrating verification tiers, where Tier 0: Target Maintenance Mode uses a fast MPPI controller when the state is in the target set T, and Tier 2 leverages Local Refinement Mode to utilize the 'reclaimed' local refinement from Algorithm 1.

5. In safety-critical tasks like drone racing, the system can demonstrate superior performance by balancing safety and goal-reaching. Empirical results show that the framework achieves a higher success rate than baselines because it demonstrates more robust collision avoidance during overtaking.

Hamilton-Jacobi (HJ) reachability provides formal safety guarantees for nonlinear systems. However, it becomes computationally intractable in high-dimensional settings, motivating learning-based approximations that may introduce unsafe errors or overly optimistic safe sets. In this work, we propose a hierarchical probabilistic verification framework for reachability learning that bridges offline global certification and online local refinement. We first construct a coarse, conservative under-approximation of the reach-avoid safe set using scenario optimization, providing an efficient global probabilistic certificate. We then introduce an online local refinement module that is structurally anchored to the global certificate and recovers regions excluded by the global verification. This refinement reduces conservatism while focusing computation on critical regions of the state space. Integrated with a condition-based switching mechanism between a learned reachability policy and a model-based controller, the proposed framework improves success rates in goal-reaching tasks with safety constraints, as demonstrated in drone-racing simulation experiments.