⚡ electrical engineering

Robust Receding Horizon Games with Additive Uncertainty

This paper proposes a robust receding horizon control framework for multi-agent linear systems with additive disturbances and coupled constraints, which guarantees recursive feasibility and ensures convergence of nominal states to a variational generalized Nash equilibrium while keeping actual states within a bounded neighborhood defined by the minimal robust positively invariant set.

Original authors: Dinesh Patra, Tanish Jain, Ashish R. Hota

Published 2026-07-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Dinesh Patra, Tanish Jain, Ashish R. Hota

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 a busy city intersection where dozens of self-driving cars (the "agents") need to get to their destinations. Each car wants to get there as fast and efficiently as possible, but they all have to follow the same traffic rules (shared constraints) and stay within their own lane (private constraints).

The problem is that the road is slippery and unpredictable (additive disturbances). A sudden gust of wind or a patch of ice could push a car off its intended path. If the cars just plan their route based on a perfect, dry road, they might crash into each other or hit the curb when the wind hits.

This paper proposes a new way for these cars to drive together safely and efficiently, even when the road is unpredictable. Here is how it works, broken down into simple concepts:

1. The "Ghost Car" and the "Safety Tube"

Instead of trying to predict the exact future path of a car (which is impossible because of the wind), the system uses a Ghost Car (the "nominal" state). This Ghost Car drives on a perfect, dry road with no wind.

Surrounding this Ghost Car is an invisible Safety Tube.

The Ghost Car plans its route to avoid traffic jams and stay in its lane.
The Safety Tube is a buffer zone around the Ghost Car. It is calculated to be wide enough to catch the real car if the wind pushes it off course.
The Rule: As long as the Ghost Car stays inside a "tightened" version of the lanes (leaving extra room for the tube), the real car is guaranteed to stay safe, even if it gets pushed around inside the tube.

2. The "Secret Handshake" (Privacy)

In a normal game, if you want to coordinate with neighbors, you might have to tell them your engine specs, your exact fuel limits, or your secret destination. That feels risky.

This paper introduces a clever Privacy-Preserving Protocol.

Instead of sharing their whole secret recipe, each car only whispers a single number to its neighbors: "I might need up to this much extra space because of the wind."
The neighbors use this number to tighten their own plans.
The Result: The cars coordinate perfectly without ever revealing their private data (like their specific engine type or exact cost functions). They only share the "worst-case" impact they might have on the group.

3. The "Game of Strategy" (The Equilibrium)

Since every car is trying to optimize its own trip, they are playing a game. The goal isn't for one car to win at the expense of others, but for everyone to reach a Generalized Nash Equilibrium.

Think of this as a "stable state" where no single driver can change their route to get a better deal without making the situation worse for themselves or breaking the traffic rules.
The paper proves that if everyone plays by these new rules, they will naturally settle into this stable, efficient pattern.

4. The "Safety Net" (Terminal Ingredients)

To make sure the cars don't just drive in circles forever, the system uses three special tools (called "terminal ingredients"):

The DARE Cost: A mathematical "scorecard" that encourages the cars to slow down and settle into a steady, safe cruising speed as they get closer to their goal.
The Invariant Set: A "safe zone" at the end of the planning horizon. Once a car enters this zone, it knows it can stay there safely forever, no matter what the wind does.
The Resource Split: A way to divide the "safe space" among neighbors so they don't fight over the same inch of road.

The Big Promise

The paper claims that with this system:

It never breaks: No matter how hard the wind blows (as long as it's within a known limit), the cars will always be able to find a valid plan for the next second. They will never get "stuck" with no legal moves.
It converges: Over time, the Ghost Cars will stop wandering and settle exactly into the perfect steady-state traffic flow.
The Real Cars are safe: The actual cars (with the wind pushing them) will stay in a small, safe neighborhood around that perfect flow. They won't crash; they will just wiggle slightly within their safety tubes.

In summary: The authors built a mathematical framework that lets self-driving agents play a game of strategy on a bumpy road. They use a "Ghost Car" to plan and a "Safety Tube" to handle the bumps, all while keeping their secrets private. The result is a system that is guaranteed to stay safe and eventually settle into a smooth, efficient rhythm.

Technical Summary: Robust Receding Horizon Games with Additive Uncertainty

Problem Formulation
This paper addresses the challenge of controlling multi-agent systems operating in shared, uncertain environments. The authors consider a setting with $N$ agents, each controlling a discrete-time linear system subject to bounded additive disturbances. The agents must satisfy both private state/input constraints and shared coupling constraints that depend on the states and inputs of neighboring agents.

Unlike cooperative distributed control, where agents minimize a global objective, this work focuses on Receding Horizon Games (RHG). Here, each agent is self-interested and seeks to minimize its own tracking cost (deviation from a steady-state target) while respecting constraints. The core difficulty lies in the fact that agents cannot disclose their private dynamics, costs, or constraints to others, yet they must collectively satisfy shared constraints under uncertainty. The goal is to design a distributed control framework that ensures recursive feasibility for all disturbance realizations and guarantees convergence to a game-theoretic equilibrium.

Methodology
The proposed framework integrates Tube-Based Model Predictive Control (MPC) with Generalized Nash Equilibrium (GNE) theory. The methodology proceeds through the following steps:

Tube-Based Decomposition:
The predicted state and input of each agent are decomposed into a nominal trajectory and an error component ( $x = s + e$ , $u = v + K_p e$ ). The nominal trajectory is the decision variable, while the error dynamics are governed by a pre-stabilizing feedback gain $K_p$ . This decomposition confines the actual state within a "tube" around the nominal trajectory, defined by a minimal Robust Positively Invariant (mRPI) set ( $Z^\infty_i$ ).
Constraint Tightening:
To ensure robust satisfaction of constraints despite disturbances, the original constraints are tightened:
- Private Constraints: The state and input sets are tightened by the mRPI set and the pre-stabilizing gain.
- Shared Constraints: The shared constraints are tightened by subtracting the worst-case contribution of the error terms from neighbors. Crucially, this is achieved via a privacy-preserving protocol where agents broadcast only scalar tightening terms (support functions of their mRPI sets) rather than their full dynamics or cost functions.
Terminal Ingredients:
To guarantee recursive feasibility and stability, the authors construct three specific terminal components:
- A terminal cost derived from a Discrete Algebraic Riccati Equation (DARE).
- A terminal control law based on the optimal feedback gain from the DARE.
- A decoupled positively invariant terminal set. To handle the coupling in the terminal constraint without requiring full coordination, the tightened shared bound is split into per-agent shares. Each agent enforces the most restrictive share required by its participation in various neighborhoods.
Game-Theoretic Solution:
At each time step, agents solve a finite-horizon optimization problem (a GNEP) in parallel. The cost function is a tracking cost toward a pre-computed steady-state Variational Generalized Nash Equilibrium (vGNE). The problem is solved using distributed operator-splitting algorithms, leveraging the fact that the game is a potential game.

Key Contributions
The paper makes three primary contributions:

Robust RHG Formulation: It formulates a robust receding horizon game for linear systems with additive disturbances and shared constraints. It introduces a tube-based constraint tightening scheme where agents only exchange scalar tightening terms, preserving the privacy of their local dynamics and costs, unlike cooperative schemes that exchange trajectories.
Recursive Feasibility Guarantees: The authors construct a specific set of terminal ingredients (DARE-based cost, decoupled invariant set, and resource-allocation scheme for shared constraints) that rigorously guarantee recursive feasibility for every bounded disturbance realization.
Stability and Convergence Analysis: By exploiting the potential-game structure of the GNEP, the paper establishes that the potential function acts as a joint Lyapunov function. This proves the asymptotic convergence of each agent's nominal state to the steady-state vGNE. Furthermore, it shows that the actual state converges to a neighborhood of the vGNE determined by the mRPI set.

Results
Theoretical analysis confirms that:

If the initial state is feasible, the optimization problem remains feasible at all future time steps for any realization of bounded disturbances (Recursive Feasibility).
The nominal trajectories of all agents converge asymptotically to the steady-state vGNE.
The actual closed-loop trajectories converge to a minimal robust positively invariant (RPI) neighborhood of the steady-state vGNE.
All original private and shared constraints are satisfied robustly for all disturbance realizations.

Significance and Claims
The authors position this work as the first rigorous investigation of receding horizon games under uncertainty with these specific guarantees. They highlight that previous works on RHGs relied on deterministic models or terminal equality constraints, while existing robust multi-agent MPC literature focused on cooperative settings.

The paper claims significance in bridging the gap between robust control and game theory for non-cooperative agents. It demonstrates that it is possible to achieve robust constraint satisfaction and stability in a distributed, self-interested setting without requiring agents to share sensitive model information. The authors modestly note that extending these results to general economic costs (where costs are coupled) or incorporating chance constraints remains an open challenge for future research.