⚡ electrical engineering

Hierarchical Decision-Making under Uncertainty: A Hybrid MDP and Chance-Constrained MPC Approach

This paper proposes a hierarchical decision-making framework for autonomous driving under uncertainty that integrates Hybrid Markov Decision Processes for multi-modal environmental prediction with a chance-constrained Model Predictive Control approach to ensure safety and efficiency through theoretically guaranteed recursive feasibility and stability.

Original authors: Siyuan Li, Chengyuan Liu, Wen-Hua Chen

Published 2026-03-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Siyuan Li, Chengyuan Liu, Wen-Hua Chen

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 busy highway. You aren't just driving alone; you are surrounded by other cars, trucks, and maybe even a cyclist. The big challenge for self-driving cars isn't just seeing these other vehicles; it's guessing what they will do next.

Will that car in the next lane stay there, or will it suddenly cut in front of you? Will the truck ahead slow down for a red light, or speed up to merge?

This paper presents a new "brain" for self-driving cars that handles this guessing game much better than current methods. Here is how it works, broken down into simple concepts and analogies.

1. The Problem: The "Crystal Ball" vs. The "Gambler"

Most current self-driving systems try to predict the future in two separate ways:

The "What?" (Maneuver): "Is that car going to change lanes?"
The "How?" (Dynamics): "If it changes lanes, how fast will it be moving?"

The problem is that these systems often treat these two questions separately. It's like trying to guess the weather by looking at the clouds (maneuver) and then separately guessing the temperature (dynamics), without realizing that the clouds cause the temperature change. This leads to confused decisions.

2. The Solution: The "Hybrid Brain" (HMDP)

The authors created a new model called a Hybrid Markov Decision Process (HMDP). Think of this as a super-weather forecast for traffic.

Instead of just saying "Car A will change lanes," this model says:

"There is a 70% chance Car A will change lanes, and if it does, it will likely speed up."
"There is a 20% chance it will stay put, but if it does, it might slow down."
"There is a 10% chance it will do something weird."

It creates a "fan" of possibilities (multi-modal prediction). It doesn't just predict one future; it predicts a whole set of plausible futures, keeping the most likely ones and ignoring the impossible ones (like a car flying into the sky).

3. The Decision Maker: The "Chess Player" (MPC)

Once the car has these "fans" of possible futures, it needs to decide what to do. The paper uses a method called Model Predictive Control (MPC).

Imagine you are playing Chess.

Old Way (Rule-Based): You have a rulebook: "If the opponent moves a pawn, I move a knight." It's rigid. If the opponent does something unexpected, you panic.
This Paper's Way (MPC): You look 5 moves ahead. You simulate: "If I move here, they might do X, Y, or Z. If they do X, I'm safe. If they do Y, I crash. So, I will choose the move that keeps me safe no matter what they do."

The car runs this "simulation" thousands of times per second. It asks: "What is the best move for me that keeps me safe, even if the other drivers do the worst-case scenario within reason?"

4. The Safety Net: The "Bubble" (Chance Constraints)

This is the cleverest part. The car doesn't need to be 100% sure of the other drivers' actions (because that's impossible). Instead, it uses Chance Constraints.

Think of this as driving with a safety bubble around your car.

The bubble isn't a solid wall; it's a probabilistic shield.
The car says: "I will drive in a way that there is a 99% chance I won't pop the bubble, even if the other car makes a sudden move."
If the other car is very unpredictable, the bubble gets bigger, and the car slows down or waits. If the other car is predictable, the bubble shrinks, and the car drives more efficiently.

This allows the car to be bold but safe. It doesn't stop completely just because there's a tiny chance of danger; it calculates the risk and proceeds if the odds are in its favor.

5. Real-World Results: The "Smart Driver" vs. The "Robot"

The authors tested this in simulations on highways and in cities.

The Old Way (Rule-Based): Like a nervous robot. If a car speeds up behind it, the robot might freeze or make a jerky, sudden stop because it didn't anticipate the speed change. It often ends up stuck in the passing lane, unable to merge back.
The New Way (HMDP-MPC): Like a confident, experienced human driver.
- It sees a car behind it speeding up.
- It predicts, "That car is likely to catch me soon."
- It proactively moves back to the middle lane before it gets too close, creating a smooth flow of traffic.
- It doesn't panic; it just adjusts its plan based on the "fan" of possibilities.

Summary

In short, this paper teaches self-driving cars to stop guessing and start planning for multiple possibilities at once.

Old Tech: "I think that car will stay there. I will pass it." (If the car moves, crash).
New Tech: "That car might stay, or it might move. I will plan a path that is safe if it stays, AND safe if it moves. I will also keep a safety bubble that grows if the situation gets risky."

This makes self-driving cars safer, smoother, and less likely to cause traffic jams because they can anticipate human behavior rather than just reacting to it.

1. Problem Statement

Autonomous systems, particularly in driving scenarios, operate in environments shared with humans and other intelligent agents. These environments are characterized by dual-layer uncertainty:

Maneuver-level uncertainty: High-level strategic intentions (e.g., lane changes, route choices, task assignments).
Dynamic-level uncertainty: Low-level physical variations (e.g., velocity fluctuations, heading deviations, pose errors).

Existing approaches often treat these two levels as decoupled subproblems. Traditional methods either rely on rigid rule-based heuristics (lacking adaptability) or learning-based models (lacking interpretability and safety guarantees). Furthermore, standard Model Predictive Control (MPC) frameworks often separate high-level maneuver selection from low-level dynamic feasibility, failing to explicitly constrain maneuvers by the agent's physical capabilities or to incorporate multi-modal environmental predictions directly into the optimization.

The core challenge is to develop a unified decision-making framework that:

Jointly models maneuver and dynamic uncertainties for surrounding agents (SAs).
Integrates these multi-modal predictions into the ego agent's (EA) decision process.
Ensures safety and dynamic feasibility through a single optimization process with theoretical guarantees.

2. Methodology

The authors propose a Hierarchical Decision-Making Framework that combines Hybrid Markov Decision Processes (HMDPs) with Chance-Constrained Model Predictive Control (MPC).

A. Environment Modeling (Surrounding Agents)

Surrounding agents are modeled using HMDPs to capture both uncertainty types simultaneously:

Maneuver Level: Modeled as a discrete MDP where states represent high-level intents (e.g., "Lane 1, Accelerating"). Transitions are governed by a probabilistic policy $\pi$ .
Dynamic Level: The physical state evolution follows an affine dynamic model driven by the selected maneuver. Stochastic process noise (Gaussian) is added to account for dynamic deviations.
Probabilistic Filtering: To manage computational complexity, a likelihood-based filtering mechanism prunes low-probability maneuver branches. Only high-likelihood action sequences are retained to form a multi-modal reachability set representing plausible future states of the SAs.

B. Ego Agent Decision Making

The Ego Agent (EA) uses a similar HMDP structure but treats it as a decision structure rather than a generative model:

Discrete Actions: Maneuver options (e.g., lane change, cruise) are treated as decision variables.
Coupling: Each discrete maneuver is explicitly linked to the EA's continuous dynamic model. This ensures that a selected maneuver is only considered if it is dynamically feasible.
Optimization: The EA solves a finite-horizon optimization problem to select a sequence of maneuvers that minimizes a cost function (balancing efficiency and comfort) while satisfying constraints.

C. Safety via Joint Chance Constraints

To bridge environmental predictions and decision-making, the framework employs Joint Chance Constraints:

The multi-modal predictions of SAs (reachability sets) are incorporated into the MPC formulation.
The constraint ensures that the probability of the EA violating safety margins (e.g., collision) across all retained plausible SA scenarios is below a user-defined risk threshold $\epsilon$ .
Deterministic Reformulation: Under affine-Gaussian assumptions, these probabilistic constraints are transformed into deterministic algebraic inequalities involving the predicted means and covariances, making them computationally tractable for real-time MPC.

D. Theoretical Guarantees

The paper provides rigorous proofs for:

Recursive Feasibility: If a feasible solution exists at the initial time, the MPC scheme guarantees a feasible solution exists at all subsequent time steps.
Asymptotic Stability: The system is proven to converge to a goal state (e.g., reaching a target lane or speed) under the proposed receding-horizon policy.

3. Key Contributions

Unified HMDP Environment Model: Development of an HMDP framework for SAs that jointly captures maneuver-level and dynamic-level uncertainties, generating structured, multi-modal predictions.
Integrated HMDP-MPC Framework: A novel decision architecture for the EA that couples high-level maneuver selection with low-level dynamic feasibility within a single optimization loop, eliminating inconsistencies between planning and control.
Probabilistic Safety Integration: The use of joint chance constraints to embed multi-modal environmental predictions directly into the MPC, ensuring safety across all plausible interaction scenarios with a tunable risk threshold.
Theoretical Validation: Establishment of formal guarantees for recursive feasibility and asymptotic stability.
Comprehensive Evaluation: Extensive simulations in highway and urban scenarios demonstrating superior performance over rule-based baselines.

4. Results

The framework was evaluated in autonomous driving simulations involving highway and urban environments:

Case 1 (Lateral Uncertainty): The EA successfully anticipated and adapted to uncertain lane-change behaviors of surrounding vehicles. It dynamically adjusted its path (e.g., changing lanes to follow a faster vehicle) while maintaining safety, demonstrating robust handling of lateral interaction uncertainty.
Case 2 (Longitudinal Uncertainty): The EA adapted to velocity variations of surrounding agents. Unlike a rule-based baseline (IDM/MOBIL) which reacted late to a rapidly accelerating vehicle behind it (causing abrupt braking by the other car), the proposed framework proactively adjusted its speed and lane position to maintain safety margins, resulting in smoother trajectories and higher overall efficiency.
Case 3 (Risk Threshold Analysis): The study demonstrated that the risk parameter $\epsilon$ allows explicit tuning of the trade-off between conservatism and efficiency. Lower $\epsilon$ values led to earlier, more conservative maneuvers, while higher values allowed for more aggressive, efficient driving.
Comparison with Baselines: Compared to a rule-based approach, the proposed framework showed:
- Higher Efficiency: Covered greater distances in the same time due to proactive planning.
- Better Autonomy: Avoided "deadlock" situations (e.g., staying in an overtaking lane) by optimizing globally rather than reacting locally.
- Safety: Prevented collisions through predictive constraint satisfaction rather than reactive emergency maneuvers.

5. Significance

This work represents a significant advancement in autonomous decision-making by:

Bridging the Gap: It successfully unifies high-level strategic reasoning (maneuvers) with low-level physical constraints (dynamics) and environmental uncertainty in a single mathematical framework.
Safety-Certainty Trade-off: It offers a principled way to regulate risk through chance constraints, allowing operators to tune the system's aggressiveness based on the environment.
Theoretical Robustness: Unlike many learning-based or heuristic approaches, this framework provides formal guarantees of stability and feasibility, which are critical for the deployment of autonomous systems in safety-critical domains.
Scalability: The use of probabilistic filtering and deterministic reformulation of chance constraints makes the approach computationally feasible for real-time applications despite the complexity of multi-modal predictions.

In conclusion, the proposed HMDP-MPC framework offers a robust, interpretable, and theoretically sound solution for autonomous decision-making in uncertain, dynamic environments, outperforming traditional rule-based systems in both safety and efficiency.