🔢 mathematics

Joint Chance Constrained Safe-Optimal Control

This paper proposes a novel approach to joint chance-constrained optimal control that minimizes the expected cost of only safe trajectories to prevent policies from exploiting unsafe low-cost paths, demonstrating that this problem can be solved via dynamic programming on an augmented state space with derived safety bounds and empirical validation.

Original authors: Niklas Schmid, Jared Miller, Tristan Zeller, Marta Fochesato, Tobias Sutter, John Lygeros

Published 2026-07-01

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Niklas Schmid, Jared Miller, Tristan Zeller, Marta Fochesato, Tobias Sutter, John Lygeros

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 the captain of a delivery drone. Your boss gives you two rules:

Get the package to the destination.
Don't crash.

However, the weather is unpredictable (stochastic uncertainty). Sometimes the wind blows you off course. You need a computer program (a controller) to decide how to fly.

The Old Way: "The Risky Shortcut"

Traditionally, engineers programmed the drone to minimize the total battery usage of every single flight, whether it crashed or not.

Here's the problem: The drone realizes that if it flies straight through a dangerous storm cloud, it uses very little battery. If it flies around the cloud, it uses a lot.

If the drone flies through the cloud, there's a 40% chance it crashes (and the package is lost).
But if it crashes, the "cost" of that flight is just the battery used before the crash.
If it flies safely around, it uses a huge amount of battery.

The old math told the drone: "Hey, if I crash 40% of the time, my average battery usage across all flights is super low. So, I'll just fly through the storm!"

The drone would intentionally take risky shortcuts, accepting that some packages would be lost, just to save battery on the ones that made it. The paper calls this "exploiting low-cost unsafe trajectories."

The New Way: "The Safe-Optimal Approach"

The authors of this paper say: "Wait a minute. If the drone crashes, the battery usage is irrelevant. We don't care about the battery on a crashed drone; we care about the battery on the drones that actually deliver the package."

They propose a new rule: Only minimize the battery usage of the flights that successfully deliver the package. Ignore the battery cost of the crashes entirely.

The Result: The drone no longer has an incentive to fly through the storm. It knows that if it crashes, that flight's cost doesn't count toward its "score." So, it chooses the longer, safer route around the cloud to ensure the package arrives.
The Trade-off: The average battery usage of all flights (including crashes) might go up slightly, but the battery usage of the successful flights goes down significantly because the drone isn't taking stupid risks anymore.

How They Solved It

The authors had to invent a new way to teach the drone this logic.

The "Augmented" Memory: They gave the drone a special "memory state." It tracks two things: where it is, and how much battery it has used so far.
The "Ghost" Step: At the very end of the flight, they added a virtual step. If the drone is safe, it counts the battery used. If the drone crashed, it sets the cost to zero (or ignores it).
The Math: They proved this new problem can be solved using standard "Dynamic Programming" (a method for solving complex problems by breaking them into smaller steps) and also tested it with "Reinforcement Learning" (AI that learns by trial and error).

The Experiments

They tested this on a simulated 2D robot (like a unicycle) trying to reach a target in a room full of obstacles.

Old Method (Standard JCC): The robot would sometimes take a risky path through a narrow gap. If it hit the wall, it didn't matter; it saved battery on the "average" flight.
New Method (Safe-Optimal): The robot avoided the risky gap. It took a slightly longer path, but it was much more likely to reach the target. When it did reach the target, it had used less energy than the old method's successful flights.

The Bottom Line

The paper argues that for critical tasks (like medical devices or self-driving cars), you shouldn't optimize for the "average" outcome if the "bad" outcomes are disasters. Instead, you should optimize strictly for the successful outcomes.

They showed that by changing the math to ignore the cost of failures, you get a smarter, safer robot that doesn't gamble with disaster just to save a few pennies.

Technical Summary: Joint Chance Constrained Safe-Optimal Control

Problem Formulation
The paper addresses the limitations of standard Joint Chance Constrained (JCC) optimal control for stochastic systems. In traditional JCC formulations, the objective is to minimize the expected cost of all trajectories (both safe and unsafe) subject to a constraint that the probability of remaining within a safe set exceeds a threshold $\alpha$ . The authors argue that this standard approach creates a perverse incentive: the controller may deliberately violate safety constraints to exploit low-cost, unsafe trajectories, provided the overall probability of safety remains above $\alpha$ . This behavior is undesirable in applications where constraint violations are catastrophic and irreversible (e.g., aircraft crashes, medical device failures), as the cost of a failed trajectory should not contribute to the optimization objective.

To address this, the paper proposes a Joint Chance Constrained Safe-Optimal Control problem. The objective is modified to minimize the expected cost of only the safe trajectories, while still enforcing the joint chance constraint that the probability of safety is at least $\alpha$ . Unsafe trajectories are effectively assigned a cost of zero in the objective function, removing the incentive to "sacrifice" safety for cost savings.

Methodology
The core methodological contribution is the reformulation of this non-Markovian problem into a solvable framework:

Augmented State Space MDP: The authors demonstrate that the Safe-Optimal Control problem can be cast as a Constrained Markov Decision Process (CMDP) over an augmented state space $Z = X \times C$ , where $X$ is the original state space and $C$ represents the accumulated cost.
- The state evolution includes a deterministic cost accumulator.
- An additional virtual time-step and binary input are introduced to handle the trajectory weighting function $a(\cdot)$ , which selects whether a trajectory contributes to the cost/constraint based on its safety and total cost.
- This transformation allows the use of standard Dynamic Programming (DP) techniques, which are not directly applicable to the original formulation due to its dependence on the full trajectory history.
Approximation and Error Bounds: For systems with continuous state spaces, the authors employ a gridding abstraction to discretize the state, cost, and action spaces. They derive theoretical bounds on the safety error introduced by this discretization. Specifically, they show that if a policy achieves safety $\alpha$ on the discretized MDP, the safety on the original continuous system is bounded below by $\alpha - N h_x M_x \mu \Delta x$ , where parameters relate to the grid size, Lipschitz constants of the transition kernel, and the number of time steps. This allows for the tightening of constraints on the discretized problem to guarantee safety on the continuous system.
Solution Approaches: The paper evaluates two solution methods:
- Dynamic Programming (DP): Solves the Lagrange dual of the CMDP using value iteration and bisection on the dual multiplier $\lambda$ .
- Reinforcement Learning (RL): Implements a lexicographic learning framework using the Soft-Actor-Critic (SAC) algorithm. This involves a two-stage training process: first maximizing reach-avoid probability, then tuning the Lagrange multiplier to meet the specific safety threshold $\alpha$ .

Key Contributions

Novel Problem Definition: Introduction of a control problem that minimizes the cost of safe trajectories only, decoupling the cost of unsafe trajectories from the optimization objective.
Theoretical Reformulation: Proof that the Safe-Optimal Control problem is equivalent to a constrained MDP on an augmented state space, enabling the use of DP.
Safety Guarantees: Derivation of explicit bounds on policy safety when solving the problem via gridding approximations in continuous state spaces.
Empirical Validation: Comprehensive numerical experiments comparing the proposed approach against standard JCC control and RL solutions.

Experimental Results
The authors validate their approach on a simulated 2D unicycle system in cluttered reach-avoid environments.

Behavioral Differences: Standard JCC policies (minimizing cost of all trajectories) were observed to "give up" on reaching the target to avoid high-cost safe routes, often resulting in low-cost trajectories that remain near the initial state or take unsafe shortcuts. In contrast, the proposed Safe-Optimal policies exclusively optimize for successful, safe trajectories.
Performance Metrics: In Monte-Carlo simulations, the Safe-Optimal approach achieved lower actuation costs for safe trajectories compared to standard JCC, while maintaining the required safety probability. Standard JCC achieved a lower overall expected cost only because it included the costs of many low-cost, unsafe (or non-reaching) trajectories.
DP vs. RL: DP generally outperformed RL in finding optimal policies, particularly in complex environments (e.g., "Simple-Slit"), where RL converged to locally optimal, conservative solutions. However, RL demonstrated the ability to handle the problem structure, though it required significantly longer computation times (90–130 minutes vs. <2 minutes for DP). The authors note that while DP scales exponentially with state dimension, RL is often preferred for high-dimensional real-world problems where DP is infeasible.

Significance and Claims
The paper claims that the standard JCC formulation is fundamentally flawed for systems with irreversible constraints because it incentivizes constraint violations to reduce costs. By shifting the objective to minimize the cost of safe trajectories only, the proposed method aligns with practical intuition: the cost of a crashed vehicle or a failed medical procedure is irrelevant to the operational cost of successful missions. The authors assert that their formulation avoids the "giving up" behavior of standard controllers and provides a mathematically rigorous framework (via CMDP reformulation and DP) to achieve safe, cost-optimal control. They conclude that while DP is currently the superior solver for the proposed formulation in low-dimensional settings, the framework opens avenues for applying these principles to broader temporal logic constraints and real-world systems.