⚡ electrical engineering

Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

This paper proposes a scalable control architecture that combines Model Predictive Control with Markov Decision Process-based Dynamic Programming to maximize reach-avoid probabilities in high-dimensional linear stochastic systems by optimally updating reference signals online while robustly handling approximation errors.

Original authors: Niklas Schmid, Jaeyoun Choi, Oswin So, Chuchu Fan

Published 2026-01-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Niklas Schmid, Jaeyoun Choi, Oswin So, Chuchu Fan

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 trying to guide a very clumsy, wind-blown drone through a complex maze filled with walls. Your goal is to get the drone to a specific "finish line" area without it crashing into any walls. The problem is that the wind is unpredictable; sometimes it pushes the drone left, sometimes right. You want to maximize the chance of success, not just hope for the best.

This paper presents a new "brain" for the drone that combines two different ways of thinking to solve this problem more effectively than previous methods.

The Two-Brain System

The authors propose a control architecture that splits the job into two layers, like a general and a pilot:

1. The Pilot (Model Predictive Controller - MPC)
Think of the MPC as a highly skilled, reactive pilot sitting in the cockpit.

What it does: It looks at where the drone is right now and where the wind is blowing. It makes tiny, split-second adjustments to the controls to keep the drone safe and on a specific path.
The limitation: The pilot is very good at following instructions, but it doesn't know the "big picture" of the maze. It doesn't know which path has the most wind or which route is safest overall. It just follows the path it is given.

2. The General (Dynamic Programming - DP)
Think of the DP as a strategic general standing on a hill, looking at a map of the entire maze.

What it does: The General doesn't touch the controls. Instead, it tells the Pilot, "Hey, aim for this specific spot next." It calculates the best "reference path" to maximize the odds of winning.
The innovation: Instead of trying to calculate every single possible wind gust for the whole maze (which is too hard for computers), the General only decides where the Pilot should aim next. It updates this target constantly based on the current situation.

The "Clumsy" Problem and the Solution

The Challenge:
If the drone is in a continuous space (it can be anywhere in the room), calculating the perfect path is mathematically impossible because there are infinite possibilities. Previous methods either simplified the problem too much (making the drone play it too safe and never reaching the goal) or only worked for very simple, small systems.

The Paper's Trick:
The authors use a "grid" to simplify the world.

Imagine the maze floor is tiled with square tiles. The General doesn't care if the drone is in the exact center of a tile or the corner; it treats the whole tile as one "state."
The Safety Net: Because the drone is clumsy (stochastic), it might drift from the center of a tile to the edge. The authors built a "robust" system that assumes the worst-case drift. They shrink the "safe zones" and "goal zones" slightly to account for this drift. This ensures that even if the drone wanders a bit within its tile, it still stays safe.

How It Works in Practice

The Setup: The drone starts in a maze. The General looks at the current tile the drone is in.
The Decision: The General picks a "command" (a target direction) from a list of 100 possibilities. It chooses the one that, statistically, leads to the highest chance of reaching the goal.
The Execution: The General sends this command to the Pilot. The Pilot takes over, steering the drone to follow that path while dodging immediate obstacles.
The Loop: A few seconds later, the General checks again: "Where is the drone now? Which tile is it in?" It picks a new command.

The Results

The team tested this on a simulated 12-dimensional drone (imagine a drone with position, speed, and rotation all at once) in a cluttered maze.

Success: In a "Labyrinth" scenario, their method achieved a 40% success rate.
Comparison: In other complex scenarios (like a "Zigzag" path), the math predicted a very low success rate (0.3%), but the actual drone performed much better (44%). This shows the math is very cautious (conservative) to guarantee safety, but the actual system performs well.
Flexibility: They also showed they could tweak the system. Instead of just trying to win, they could tell the drone, "Try to win, but also try to stay in the middle of the room and not fly too fast." The system balanced these goals perfectly.

The Bottom Line

This paper doesn't just say "use AI." It builds a specific, mathematically proven bridge between strategic planning (the General) and reactive control (the Pilot). By treating the strategic planner as a "reference generator" for the pilot, they can handle complex, high-dimensional systems (like drones) that were previously too difficult to control safely in unpredictable environments. They provide a "certificate" (a mathematical guarantee) that the drone will stay safe, even with the math being slightly conservative.

Technical Summary: Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Problem Formulation
The paper addresses the challenge of maximizing the reach-avoid probability for linear stochastic systems over a finite time horizon. The system is defined by dynamics containing both deterministically evolving states ( $x_d$ ) and probabilistically evolving states ( $x_s$ ), subject to additive i.i.d. noise. The control objective is to find a policy that maximizes the probability of the system reaching a target set $T$ while remaining within a safe set $S$ for a duration $[0, T]$ , all while satisfying deterministic constraints $G$ (such as input limits and state bounds) at all times.

Existing methods face a trade-off: statistical bound-based approaches (e.g., stochastic tubes, scenario MPC) offer scalability but often yield conservative performance, while direct optimization methods (e.g., Markov Decision Processes) provide tight guarantees but are computationally intractable for high-dimensional or continuous state spaces.

Methodology
The authors propose a layered control architecture that combines the scalability of Model Predictive Control (MPC) with the optimality of Dynamic Programming (DP). The core innovation lies in treating the closed-loop system (plant + MPC) as a Markov Decision Process (MDP) where the "actions" are reference signals sent to the MPC, rather than direct control inputs.

Layered Architecture:
- Lower Layer (MPC): A Model Predictive Controller tracks reference signals generated by the upper layer. The MPC is designed to be agnostic to the stochastic reach-avoid objective; its sole purpose is to ensure the system satisfies the deterministic constraints $G$ and input limits $U$ . To bridge the gap between discrete-time MPC optimization and continuous-time constraint satisfaction, the authors derive constraint tightening techniques (Lemma III.1) that account for system dynamics and noise over the sampling interval.
- Upper Layer (DP Reference Generator): A DP-based policy operates at fixed time intervals ( $\Delta t$ ). It selects reference sequences (commands) for the MPC to maximize the probability of reaching the target while avoiding unsafe regions. The state space of this MDP is the system state $x_k$ , and the action space consists of a finite set of reference trajectories.
Handling Continuous State Spaces and Abstraction:
Since the state space is continuous, the authors employ a finite gridding abstraction to make the DP computationally tractable. To ensure theoretical guarantees are preserved despite this discretization, they introduce a robustification framework:
- Robust MPC (RMPC): The MPC is modified to generate input sequences that are invariant to the specific initial state within a grid cell (partition). This is achieved by initializing the MPC prediction from the grid center rather than the measured state, ensuring that the same control sequence is applied to all states within a partition.
- Robust Value Iteration: The safe and target sets are tightened by a radius $r$ (derived from the maximum deviation of trajectories within a time step) to account for abstraction errors. The DP algorithm is modified to compute a lower bound on the reach-avoid probability by considering worst-case transitions within the neighborhood of each grid cell.

Key Contributions

Control Architecture: The paper introduces a novel architecture that reduces the dimensionality of the DP planning space from the full state dimension $n$ to the dimension of the probabilistically evolving component $n_s$ . This is achieved by leveraging the deterministic evolution of $x_d$ and the tracking capabilities of the MPC.
Theoretical Guarantees: The authors provide formal certificates for the approach. They prove that the robustified architecture ensures continuous-time constraint satisfaction and that the value computed by the robust DP algorithm serves as a strict lower bound on the actual reach-avoid probability achieved by the system (Theorem IV.4).
Scalability and Flexibility: The method is demonstrated to be scalable to higher-dimensional systems (specifically a 12D quadcopter model) and flexible enough to handle complex, cluttered environments.

Results
The approach was validated on a perturbed 12D quadcopter model navigating various cluttered environments (e.g., labyrinths, zigzag paths, and obstacle fields).

Performance: In a labyrinth scenario, the architecture achieved a success rate of 40%, significantly outperforming conservative baselines.
Comparison: Across multiple scenarios, the empirical reach-avoid probability ( $V_0(x_0)$ ) consistently met or exceeded the lower bound computed by the robust value iteration ( $\tilde{V}_0(x_0)$ ), validating the theoretical guarantees. For instance, in a "zigzag" environment, the empirical success rate was 44% compared to a theoretical lower bound of 0.3%.
Trade-offs: The paper also demonstrates the architecture's ability to solve constrained optimal control problems. By adjusting a Lagrange multiplier, the system can trade off path cost (keeping the trajectory close to a center) against the reach-avoid probability, generating a Pareto front of solutions.

Significance and Claims
The paper claims that this work bridges the gap between the theoretical optimality of MDP-based methods and the practical scalability of MPC. By decoupling the safety enforcement (handled by the robust MPC) from the probabilistic optimization (handled by the DP reference generator), the authors achieve a control strategy that is both computationally feasible for higher-dimensional systems and capable of providing formal reach-avoid certificates without resorting to overly conservative statistical bounds. The authors emphasize that their method provides formal certificates for stochastic systems, a feature often lacking in scalable heuristic approaches, while avoiding the computational intractability of full-state MDP solutions.