⚡ electrical engineering

Steering with Contingencies: Combinatorial Stabilization and Reach-Avoid Filters

This paper introduces a tractable control framework that enforces combinatorial stabilization and reach-avoid requirements for steering toward a primary target while guaranteeing the ability to divert to at least $r$ out of $p$ alternative sites, utilizing optimization-based filters with only $p+1$ constraints to prevent combinatorial explosion and enable safe real-time switching.

Original authors: Yana Lishkova, Pio Ong, Sander Tonkens, Sylvia Herbert, Aaron D. Ames

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yana Lishkova, Pio Ong, Sander Tonkens, Sylvia Herbert, Aaron D. Ames

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are driving a car on a long road trip. Your main goal is to get to City A (your target). However, you know that traffic jams, road closures, or running out of gas could happen. So, a smart driver doesn't just aim for City A; they constantly make sure they are close enough to City B and City C just in case they need to turn around and go there instead.

This paper is about teaching robots and autonomous systems (like self-driving cars or drones) how to do exactly that. It solves a very tricky math problem: How do you steer toward one goal while guaranteeing you can still reach at least two (or more) other backup goals, without the computer getting overwhelmed by too many calculations?

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Combinatorial Explosion"

Imagine you have 10 possible landing spots for a drone ( $p=10$ ), and you want to make sure that no matter where the drone flies, it can always reach at least 3 of them ( $r=3$ ).

If you tried to check every single combination of 3 spots out of 10, the computer would have to check 120 different scenarios simultaneously. If you had 20 spots, the number of combinations would be in the thousands. This is called a "combinatorial explosion." It's like trying to solve a puzzle where the number of pieces doubles every second; the computer would freeze, and the drone would crash.

2. The Solution: The "Magic Filter"

The authors created a special "filter" (a set of rules the computer follows) that acts like a traffic cop. Instead of checking every single combination of backup plans, the filter uses a clever mathematical trick to check only $p+1$ things (in our example, just 11 things).

Think of it like this:

Old Way: You ask, "Can I reach Combo 1? Combo 2? Combo 3? ... Combo 120?" (Too slow!)
New Way: You ask, "Am I in a zone where I can reach at least 3 spots?" (Fast and easy!)

The filter ensures the robot stays inside a "safe bubble" that guarantees this condition is always met.

3. Two Different Tools for Two Different Jobs

The paper offers two versions of this filter, depending on the situation:

A. The "Stability" Filter (For steady cruising)

The Analogy: Imagine a marble rolling down a bowl. The bottom of the bowl is your target. The "Control Lyapunov Function" (CLF) is like a map of the bowl's shape.
How it works: The robot wants to roll into the target bowl. But, the filter makes sure the robot never rolls so far up the side that it falls out of three other bowls nearby. It keeps the robot in a "super-bowl" where it can slide into the main target, but if the main target suddenly disappears (like a hazard appearing), the robot can instantly slide into one of the backup bowls without falling off the edge.

B. The "Time-Bomb" Filter (For finite resources)

The Analogy: Imagine you are running out of battery. You have 10 charging stations, but your battery is dying. As time passes, the "reachable area" for each station shrinks.
How it works: This uses something called "Hamilton-Jacobi Reachability." It's like a shrinking bubble. The filter constantly checks: "Is my current location inside the shrinking bubbles of at least 3 charging stations?" If the battery gets low, the bubbles get smaller. The filter steers the robot so it never gets stuck in a spot where it can only reach 2 stations. It forces the robot to stay in the "safe zone" where 3 options are still alive.

4. Why This is a Big Deal

Safety First: In the past, if a robot was heading to a target and an obstacle appeared, it might have to stop and recalculate everything, which takes time. This new method keeps the "backup plans" alive while the robot is moving.
Real-Time Switching: Because the math is so efficient (only $p+1$ constraints), the robot can switch targets instantly. If the robot is aiming for Target 1, but Target 1 becomes unsafe, it can instantly switch to Target 2 without crashing, because it was already staying close enough to Target 2 the whole time.
No Crashes: The paper shows simulations where a normal robot crashes into obstacles because it was too focused on its main target. The robot using this new filter successfully dodges obstacles and lands safely on a backup runway.

Summary

This paper gives robots a "Plan B, C, and D" mindset. Instead of blindly driving toward a goal, the robot is taught to drive in a way that keeps multiple escape routes open at all times. It does this using a smart, fast mathematical filter that prevents the computer from getting bogged down in complex calculations, ensuring the robot stays safe even when things go wrong.

1. Problem Statement

The paper addresses a critical challenge in autonomous systems (e.g., spacecraft landing, autonomous vehicle navigation): contingency planning. In dynamic environments, a system must steer toward a primary target while maintaining the ability to divert to at least $r$ out of $p$ alternative targets if conditions change (e.g., hazards detected, battery depletion, or resource constraints).

Key Challenges:

Combinatorial Complexity: Naive formulations require checking all $\binom{p}{r}$ combinations of targets, leading to computational intractability ("combinatorial blow-up").
Logical Constraints: Standard Control Barrier Functions (CBFs) enforce an "AND" logic (all constraints must be satisfied). The problem requires an "at least $r$ -out-of- $p$ " logic, which is non-smooth and difficult to enforce in real-time optimization.
Conflicting Objectives: The system must simultaneously stabilize toward a specific equilibrium (or reach a target within a horizon) while ensuring the state remains within the "safe region of attraction" (or reach-avoid set) of multiple alternative targets.

2. Methodology

The authors propose two complementary frameworks to solve this problem, both resulting in Quadratic Programming (QP) filters with only $p+1$ constraints, avoiding combinatorial explosion.

A. Combinatorial Stabilization (Infinite Horizon)

Foundation: Uses Control Lyapunov Functions (CLFs) for stability and Combinatorial Control Barrier Functions (CBFs) for safety.
Mechanism:
1. CLFs: For each of the $p$ candidate equilibria, a local CLF ( $V_j$ ) defines a certified Region of Attraction (ROA).
2. CBF Construction: These CLFs are converted into barrier functions ( $h_j = c_j - V_j$ ).
3. Combinatorial Logic: A "pivot function" $\tilde{h}(x) = \text{max}^{(r)}\{h_j(x)\}$ is defined, representing the $r$ -th largest value among the $p$ barriers. The goal is to keep $\tilde{h}(x) \geq 0$ .
4. Relaxation: To ensure feasibility when the system is far from the selected target, a relaxation term involving an auxiliary variable $\omega$ is introduced. This allows non-critical constraints to be temporarily violated while ensuring at least $r$ remain satisfied.
5. Filter: A QP is solved at each time step to minimize deviation from a nominal controller subject to:
  - One CLF constraint for the selected target.
  - $p$ combinatorial CBF constraints for the contingency set.

B. Combinatorial Reach-Avoid (Finite Horizon)

Foundation: Uses Hamilton-Jacobi Reachability (HJR) analysis, which is better suited for finite-horizon problems and resource depletion (e.g., shrinking ROAs due to fuel/battery).
Mechanism:
1. Value Functions: Instead of CLFs, the method uses Reach-Avoid Value Functions ( $V_j(x, \tau)$ ) derived from HJR, which encode the ability to reach a target while avoiding obstacles within a time horizon $\tau$ .
2. Dynamic Horizons: The framework accounts for time-varying horizons ( $\tau_1$ for the active target, $\tau_2$ for contingency targets) that may shrink over time.
3. Combinatorial Set: Similar to the stabilization case, a combinatorial set is defined where the state must remain within the reach-avoid sets of at least $r$ targets.
4. Filter: A QP-based filter is constructed to ensure the system reaches the selected target while maintaining membership in the combinatorial reach-avoid set.

3. Key Contributions

Formalization of Combinatorial Contingency: The paper formally defines "Combinatorial Stabilization" and "Combinatorial Targeting," requiring the system to maintain reachability to $r$ -out-of- $p$ alternatives while pursuing a primary goal.
Tractable QP Filters: The authors derive filters that enforce this complex logical requirement using only $p+1$ constraints (1 for the active target, $p$ for the combinatorial safety set). This prevents the exponential scaling associated with mixed-integer programming (MIP).
Relaxation for Feasibility: The introduction of auxiliary variables ( $\omega$ ) and relaxation terms (using ReLU and $\rho$ functions) ensures the QP remains feasible even when the system is outside the strict region of attraction of the selected target, provided it is within the combinatorial set.
Continuity Guarantees: The paper proves that under standard regularity conditions (Slater's condition), the resulting QP controller is continuous, ensuring well-posed closed-loop dynamics and preventing chattering.
Real-Time Switching: The framework enables safe, real-time switching between targets. If the primary target becomes unsafe or infeasible, the controller can instantly switch to a contingency target without violating safety guarantees.

4. Results and Simulations

The framework was validated on two distinct examples:

Example 1: Linear System (CLF-based):
- A 2D linear system with 3 targets and 3 obstacles.
- Scenario: The system steers toward Target 1 ( $r=2$ ). At $t=0.5s$ , the target switches to Target 2. Later, $r$ is increased to 3.
- Outcome: The unfiltered (nominal) controller violated obstacle constraints. The proposed filter kept the trajectory within the safe regions of at least 2 (and later 3) targets, allowing for safe target switching without collision.
Example 2: Airplane Landing (HJR-based):
- A simplified 5-state aircraft model navigating between building obstacles to 6 runway targets.
- Scenario: The aircraft must land on a specific runway while keeping $r$ alternative runways reachable as the time horizon ( $\tau$ ) shrinks.
- Outcome:
  - With $r=0$ , the nominal controller crashed.
  - With $r=2$ , the filter forced the aircraft to stay within reach of two runways, resulting in a safer, more conservative path.
  - When the primary target became infeasible due to a shortened horizon, the filter successfully switched to a contingency runway (Target 2) without violating safety.

5. Significance

This work bridges the gap between stability theory (CLFs) and safety theory (CBFs/HJR) in the context of logical contingency planning.

Scalability: By reducing the constraint count from exponential ( $\binom{p}{r}$ ) to linear ( $p+1$ ), it makes real-time contingency planning feasible for systems with many potential alternatives.
Robustness: It provides a mathematical guarantee that a system will not "paint itself into a corner"; even if the primary plan fails, the system is guaranteed to have $r$ viable backup plans available at all times.
Applicability: The dual approach (CLF for infinite horizon, HJR for finite horizon/resource limits) makes the framework applicable to a wide range of autonomous tasks, from drone swarms to spacecraft landing and autonomous driving.

In summary, the paper provides a rigorous, computationally efficient method to ensure that autonomous systems can pursue goals aggressively while retaining the flexibility to abort and divert to safe alternatives, a critical requirement for high-stakes autonomy.