Scalable Multi-modal Model Predictive Control via Duality-based Interaction Predictions

Basic Information

• Paper ID: 2402.01116
• Title: Scalable Multi-modal Model Predictive Control via Duality-based Interaction Predictions
• Authors: Hansung Kim, Siddharth H. Nair, Francesco Borrelli
• Classification: cs.RO cs.LG cs.SY eess.SY
• Publication Date/Venue: arXiv preprint (submitted February 2024, last updated March 2025)
• Paper Link: https://arxiv.org/abs/2402.01116

Abstract

This paper proposes a hierarchical architecture for achieving scalable real-time model predictive control (MPC) in complex multi-modal traffic scenarios. The architecture comprises two key components: 1) RAID-Net, an attention-based recurrent neural network that uses Lagrangian duality to predict relevant interactions between autonomous vehicles and surrounding vehicles within the MPC prediction horizon; 2) a simplified stochastic MPC formulation that enhances computational efficiency by eliminating irrelevant collision avoidance constraints. The method is validated in simulated traffic intersection environments, achieving a 12-fold acceleration in motion planning problem solving.

Research Background and Motivation

Core Problem

In complex urban driving scenarios, autonomous vehicles must navigate safely in highly uncertain environments while observing and responding to the behavior of heterogeneous traffic participants (human-driven and autonomous vehicles). These traffic participants exhibit multi-modal prediction characteristics, and considering these factors in motion planning presents significant challenges.

Problem Significance

Existing motion planning methods face dual challenges of scalability and real-time performance:

1. Hierarchical prediction and planning approaches: While capable of handling multi-modal predictions, they lack real-time scalability in complex scenarios
2. Model-based integrated planning methods: Game-theoretic approaches suffer from excessive computational complexity in multi-vehicle scenarios
3. End-to-end learning approaches: While scalable, they lack interpretability and safety guarantees

Limitations of Existing Methods

• The number of constraints in traditional MPC grows exponentially with vehicle count and modality count (O(NM^V))
• In complex traffic scenarios, most collision avoidance constraints are actually inactive
• Lack of effective constraint screening mechanisms to identify truly relevant vehicle interactions

Core Contributions

1. Proposed RAID-Net architecture: An attention-based recurrent neural network capable of predicting relevant interactions between autonomous vehicles and surrounding vehicles within the MPC prediction horizon
2. Established duality-based interaction prediction theory: Utilizing Lagrangian duality and sensitivity analysis to identify active constraints
3. Designed hierarchical MPC framework: Significantly reduces computational complexity through constraint screening, achieving 12-fold solving acceleration
4. Constructed traffic intersection simulation environment: For training and evaluating the proposed algorithm

Methodology Details

Task Definition

Input: Current environmental observation $ob_t$, including ego vehicle state, surrounding vehicle states, and semantic information Output: Control input $u_t$ to safely guide the ego vehicle to the target location Constraints: State-input constraints and multi-modal collision avoidance constraints

Model Architecture

1. Stochastic MPC Problem Formulation

Considering V target vehicles, each with M modalities, yielding M^V scenario configurations. The optimization problem is:

$\min_{\theta_t} \sum_{m=1}^{M^V} \mathbb{E}\left[\sum_{k=t}^{t+N-1} \|Q(x_{k+1|t,m}-x^{ref}_k)\|_2^2 + \|R(u_{k|t,m}-u^{ref}_k)\|_2^2\right]$

Subject to:

• System dynamics constraints
• State-input constraints: $P((x_{k|t,m}, u_{k|t,m}) \notin XU_k) \leq \epsilon$
• Collision avoidance constraints: $P((x_{k|t,m}, o^i_{k|t,\bar{j}(i,m)}) \notin CA^i_{k|t,\bar{j}(i,m)}) \leq \epsilon$

2. Duality Theory Analysis

Converting the MPC problem into second-order cone programming (SOCP): $\min_{\theta_t} \frac{1}{2}\|Q_t\theta_t\|_2^2 + C_t^T\theta_t \quad \text{s.t.} \quad A_t\theta_t + R_t \in K$

The corresponding dual problem is: $\min_{\mu_t,\eta_t} [\mu_t^T \eta_t^T]R_t + \frac{1}{2}\|Q_t^{-1}(A_t^T[\mu_t^T \eta_t^T]^T - C_t)\|_2^2$

Through KKT conditions, if $[\mu_t^*]_s = 0$, the corresponding constraint can be eliminated.

3. RAID-Net Architecture Design

Input Encoding:

• Time-to-collision (TTC) based ego-centric graph encoding
• Transformer encoder generates scenario representation feature vector $f_i \in \mathbb{R}^{d_{em}}$

Network Structure:

• N decoder sequences with shared parameters
• Multi-head attention mechanism captures different types of vehicle interactions
• Gated recurrent units (GRU) process temporal dependencies
• MLP layers learn complex interaction patterns

Output: Binary classification prediction of dual variables $\tilde{\mu}_t \in \{0,1\}^{n_c}$

Technical Innovations

1. Duality-guided constraint screening: First application of Lagrangian duality theory to MPC constraint screening
2. Attention-based interaction modeling: Captures complex interaction patterns between vehicles through multi-head attention
3. Temporal independence of recursive architecture: Achieves independence from prediction horizon length through parameter sharing
4. Safety guarantees via sensitivity analysis: Quantifies constraint violation impact on cost through shadow price theory

Experimental Setup

Dataset

• Simulation Environment: Custom unsignalized traffic intersection environment
• Vehicle Configuration: 1 ego vehicle + 1-3 target vehicles
• Modality Settings: Total of 16 modality configurations, resulting in 624 collision avoidance constraints
• Data Scale: 120,315 data points, 85% training set, 15% test set

Evaluation Metrics

• Feasibility: Percentage of MPC problems with feasible solutions
• Collision Rate: Percentage of time steps with collisions against target vehicles
• Constraint Ratio: Average percentage of enforced constraints
• Solving Time: Average MPC problem solving time
• Task Completion Time: Normalized time to reach target location

Comparison Methods

• Full MPC: Complete MPC problem with all constraints
• MLP Baseline: Comparison method using multi-layer perceptron

Implementation Details

• Prediction Horizon: N = 14, sampling time Δt = 0.2s
• Network Parameters: Learning rate 0.001, batch size 1024, 3000 training epochs
• Loss Weights: wp = 4 (biased toward positive class prediction for improved safety)
• Solver: Gurobi for SOCP problem solving

Experimental Results

Main Results

Key Findings

1. 12-fold Acceleration: HMPC algorithm achieves 12-fold speedup in solving time
2. High Recall Rate: RAID-Net achieves 94% recall on test set, correctly predicting 98.1% of interaction dual variables
3. Conservative Prediction: 17.45% constraint enforcement rate compared to 1.52% actual active constraint rate reflects safety-oriented conservative strategy
4. Minor Safety Trade-off: 4% collision rate primarily caused by false negative classifications

Ablation Studies

RAID-Net demonstrates superior performance compared to standard MLP networks in loss distribution, validating the effectiveness of attention mechanisms and recursive structure.

Related Work

Main Research Directions

1. Hierarchical Prediction and Planning: Methods like Trajectron++ focusing on complex prediction models
2. Model-based Integrated Methods: Game-theoretic and joint optimization approaches
3. End-to-end Learning Methods: Deep learning approaches such as Social Attention

Advantages of This Work

Compared to existing methods, this work achieves significant computational efficiency improvements while maintaining safety and provides interpretable interaction prediction mechanisms.

Conclusions and Discussion

Main Conclusions

1. Proposed the first duality-theory-based MPC constraint screening framework
2. RAID-Net effectively predicts vehicle interactions, achieving real-time performance requirements
3. Achieves 12-fold computational acceleration in complex traffic scenarios

Limitations

1. Insufficient Safety Guarantees: Lacks theoretical safety guarantees for screened constraints
2. Policy Over-parameterization: Feedback policy in MPC may suffer from over-parameterization
3. Limited Generalization: RAID-Net's generalization capability to different intersection topologies requires further verification
4. Collision Risk: 4% collision rate requires further improvement

Future Directions

1. Utilize DAgger algorithm to address distribution shift in behavioral cloning
2. Test RAID-Net generalization performance on real traffic datasets
3. Apply duality-based interaction prediction to multi-vehicle coordinated path planning
4. Provide stronger theoretical safety guarantees

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Innovative application of Lagrangian duality theory to MPC constraint screening
2. Practical Value: Significant computational acceleration enables real-time MPC in complex scenarios
3. Architecture Design: Well-designed RAID-Net with attention mechanisms and recursive structure
4. Comprehensive Experiments: Thorough performance evaluation in simulation environments

Weaknesses

1. Safety Trade-off: 4% collision rate may be unacceptable for safety-critical applications
2. Simulation Limitations: Validation only in simplified traffic intersection scenarios, lacking complex urban environment testing
3. Insufficient Theoretical Analysis: Theoretical analysis and bounds on constraint screening errors need strengthening
4. Missing Real-world Validation: Lacks verification on actual vehicle platforms

Impact

This work provides novel solutions to real-time MPC problems in autonomous driving, and the application of duality theory may inspire efficient solving methods for other optimization problems.

Applicable Scenarios

• Autonomous driving decision-making at urban traffic intersections
• Multi-robot coordination control
• Other multi-agent systems requiring real-time optimization

References

The paper cites key works from multiple important domains, including:

• Trajectron++: Dynamically feasible trajectory prediction
• Stochastic MPC theoretical foundations
• Attention mechanisms and Transformer architectures
• Convex optimization and duality theory

This paper makes significant contributions in both theoretical innovation and practical value, providing effective solutions to real-time MPC problems in autonomous driving, though further improvements are needed in safety guarantees and practical deployment.