Source-linked AI summary
Strategically Robust Game-Theoretic Multi-Agent Trajectory Optimization
Victor L. Qin, Nicolas Lanzetti, Saverio Bolognani, Hamsa Balakrishnan
TL;DR
Decentralized AAM flights need to avoid collisions while planning around other flights’ uncertain control inputs, a setting where standard equilibrium methods assume exact adherence. The paper adds a bounded fictitious adversary to trajectory planning and shows the robust game retains dynamic potential structure. Experiments find risk-sensitive trajectory changes with a modest runtime increase.
Problem
Game-theoretic collision-avoidance planners assume agents exactly follow equilibrium trajectories, despite uncertainty in other flights’ controls.
Source: §I · pp. 1–2Method
Each agent plans against a fictitious adversary that perturbs other agents’ control inputs within a bounded budget to minimize distance at each timestep.
Source: §I · p. 1, B. Strategically robust equilibria · p. 3Results
The robust game retains exact dynamic potential structure, while trajectories widen in concrete-risk scenarios, remain nearly unchanged in low-risk scenarios, and take 1.41×–2.01× nominal runtime across two to eight agents.
Source: §I · p. 2, A. Two-player system · p. 5, B. A multi-agent system · p. 6Takeaways & Limitations
The robustness budget directly tunes protection against control-input perturbations, with zero budget recovering the standard Nash equilibrium.
Source: B. Strategically robust equilibria · p. 3The analysis assumes identical dynamics, interagent costs, and robustness levels, and uses linear dynamics with SLSQP.
Source: §V · p. 6
Abstract
from arXiv · showhide
Aviation authorities worldwide expect Advanced Air Mobility (AAM) traffic management to be decentralized among service providers, requiring AAM flights to autonomously plan trajectories by predicting other flights' control inputs rather than relying on centralized coordination. Game-theoretic approaches that formulate multi-agent collision avoidance as an exact dynamic potential game can efficiently find open-loop equilibria, but they assume that agents exactly follow their equilibrium trajectories---an unrealistic assumption given uncertainties in actuation, perception, and computation. We propose a strategically robust formulation where each agent protects against a fictitious adversary that, for each timestep, perturbs other agents' control inputs within a bounded budget to minimize distance at that timestep. We show that, under reasonable assumptions on agents' distance cost and robustness levels, the strategically robust game remains an exact dynamic potential game and admits a quasi-closed-form solution to the inner adversarial problem for linear dynamics, which limits computational overhead. Experiments with up to eight agents using logarithmic distance costs show that strategic robustness selects more robust trajectories in high-collision-risk configurations while leaving low-risk trajectories nearly unchanged, with only a modest increase in runtime.
I. INTRODUCTION
Decentralized AAM flights must plan collision-avoiding trajectories despite uncertainty about other flights’ controls. The paper introduces bounded strategic robustness and examines how it fits game-theoretic trajectory optimization.
I. INTRODUCTION
- Decentralized AAM flights must avoid collisions by predicting others’ controls, but equilibrium planners assume exact adherence despite operational uncertainty.Deviations can arise from perception, computation, or partial information.Source: §I · p. 1
- Each agent plans against a fictitious adversary that perturbs other agents’ controls within a budget to minimize distance at each timestep.A zero budget recovers the standard Nash equilibrium; larger budgets allow protection against larger control perturbations.Source: §I · pp. 1–2
A. Related work
- Prior approaches address exogenous uncertainty, while the paper targets strategic uncertainty and asks whether robustness preserves dynamic potential-game tractability.Dynamic potential games reduce equilibrium computation to one optimization problem, but strategic robustness could alter that structure.Source: A. Related work · p. 2, §I · p. 2
II. STRATEGICALLY ROBUST TRAJECTORY OPTIMIZATION
- The trajectory model uses identical linear dynamics and separates private costs from pairwise interagent costs, which can capture collision avoidance.The paper’s contributions include retaining an exact dynamic potential game under natural distance-cost assumptions and quickly computing the adversarial maximization.Source: §II · pp. 2–3, §I · p. 2
A. Game-theoretic solution concept
The section defines open-loop Nash equilibrium and exact dynamic potential games. Under the potential-game structure, equilibrium computation can reduce to minimizing a single function.
A. Game-theoretic solution concept
- An open-loop Nash equilibrium is a strategy profile in which no agent can lower its cost by changing its own strategy while others’ strategies remain fixed.The definition applies given initial conditions and feasible joint trajectories.Source: A. Game-theoretic solution concept · p. 3
- Computing coupled nonlinear equilibrium equations is challenging, whereas a potential minimizer is an open-loop Nash equilibrium and can be found with one optimization when the potential attains its minimum.The text gives coercivity as an example condition for the potential to attain its minimum.Source: A. Game-theoretic solution concept · p. 3
- In an exact dynamic potential game, each agent’s cost change from unilaterally changing strategy matches the corresponding change in a shared potential.Equivalently, an agent’s cost can be represented as the potential plus a term independent of that agent’s own strategy.Source: A. Game-theoretic solution concept · p. 3
B. Strategically robust equilibria
Each agent evaluates a modified distance cost against a fictitious adversary that perturbs other agents’ nominal controls within a bounded budget. The resulting open-loop equilibrium protects against deviations while retaining the nominal Nash equilibrium when the budget is zero.
B. Strategically robust equilibria
- For each other agent and timestep, the fictitious adversary minimizes distance by perturbing nominal controls subject to a total deviation budget.The paper modifies the distance cost to protect against deviations in other agents’ control inputs.Source: B. Strategically robust equilibria · p. 3
- At zero budget the adversary must use nominal inputs, recovering the standard Nash equilibrium; larger budgets protect against larger perturbations.Source: B. Strategically robust equilibria · p. 3
- Under Assumption 2, the adversary’s reachable set is fixed and convex, centered at the nominal state, and the resulting distance cost is well defined and continuously differentiable.The cost depends on the two agents only through their relative position.Source: B. Strategically robust equilibria · p. 3
- An open-loop strategically robust equilibrium is feasible and no agent can lower its robust cost by unilaterally changing its strategy while others’ strategies remain fixed.Source: B. Strategically robust equilibria · pp. 3–4
- The adversary chooses a separate trajectory for each timestep, making it at least as powerful as one trajectory maximizing summed distance over the horizon with the same budget.The paper describes each per-timestep problem as a target-intercept problem.Source: B. Strategically robust equilibria · p. 4
III. COMPUTATION OF STRATEGICALLY ROBUST EQUILIBRIA
The section shows that strategic robustness preserves the nominal game’s potential structure. This preservation makes the robust game’s equilibria efficiently computable.
III. COMPUTATION OF STRATEGICALLY ROBUST EQUILIBRIA
- The strategically robust game preserves the potential structure of the nominal game.Source: §III · p. 4
- Potential-structure preservation makes the strategically robust game’s equilibria efficiently computable.Source: §III · p. 4
- The section’s computational result is that strategic robustness retains the structure used to compute equilibria efficiently.Source: §III · p. 4
A. Strategic robustness in exact dynamic potential games
Under the stated distance-cost and shared-robustness assumptions, strategic robustness preserves the exact dynamic potential-game structure. Relaxing assumptions may instead yield weighted or ordinal potential games under additional conditions.
A. Strategic robustness in exact dynamic potential games
- The interagent distance cost is assumed to be a monotone function of distance; the logarithmic distance penalty satisfies this assumption.The paper motivates this condition by collision avoidance, where costs should grow as agents approach one another.Source: A. Strategic robustness in exact… · p. 4
- The exact-potential result assumes all agents use the same robustness level at every time.The assumption sets ε_i,H = ε_j,H for all agents and times.Source: A. Strategic robustness in exact… · p. 4
- With symmetric robustness, the strategically robust game remains an exact dynamic potential game when the original game satisfies the conditions for exact potential structure.Every minimizer of its modified potential is a strategically robust equilibrium.Source: A. Strategic robustness in exact… · p. 4
- Allowing agent-dependent weights can yield a weighted dynamic potential game, while unequal robustness levels may yield an ordinal potential game under certain conditions.The paper notes convergence guarantees for ordinal and weighted potential games under appropriate assumptions.Source: A. Strategic robustness in exact… · p. 4
B. Fast computation of the strategically robust distance cost
Evaluating the strategically robust distance cost requires a worst-case optimization. The paper derives a quasi-closed-form approach using monotonicity, quadratic optimization, and dual-multiplier updates.
B. Fast computation of the strategically robust distance cost
- Evaluating the modified distance cost requires a worst-case optimization, for which the paper derives a computationally efficient quasi-closed-form solution.The solution is organized into three steps.Source: B. Fast computation of the… · p. 4
- Monotonicity reduces the inner problem to minimizing squared distance, and fixing the dual multiplier makes the control optimization quadratic with a closed-form solution.The resulting control deviation is computed using the dynamics-dependent matrix M_H.Source: B. Fast computation of the… · p. 4
- The dual multiplier is updated by checking whether zero is optimal and otherwise applying Newton iterations after an eigendecomposition.The algorithm also uses a decomposition that can be precomputed for each horizon step.Source: B. Fast computation of the… · pp. 4–5
IV. RESULTS
The experiments compare nominal, strategically robust, and wider-distance-cost planners across four trajectory scenarios with two, four, and eight agents. They use single-integrator dynamics and report computational time including initialization for the strategically robust method.
IV. RESULTS
- The evaluation covers four multi-agent scenarios with two, four, and eight agents.The scenarios include head-on and parallel two-agent cases, four agents crossing a region, and eight agents swapping antipodal positions on a circle.Source: §IV · p. 5
- The comparison includes nominal Nash equilibria, strategically robust equilibria with robustness parameter ε_j,H = 2, and Nash equilibria using an increased distance cost.The strategically robust method is initialized by first solving the nominal potential game.Source: §IV · p. 5
- All examples use single-integrator dynamics in R2 with A = I, B = 0.1I, and T = 20, and the reported robust-method runtime includes nominal initialization.The problems use direct single shooting with SLSQP; positions, times, and budgets are in normalized units.Source: §IV · p. 5
A. Two-player system
In two-agent scenarios, strategic robustness adjusts trajectories more in the head-on case than in the parallel case, unlike simply increasing the collision parameter. Tests with up to eight agents show a modest runtime increase, while the conclusion notes assumptions and solver boundaries.
A. Two-player system
- In head-on and parallel two-agent scenarios, strategically robust trajectories are wider than nominal trajectories because agents protect against others’ misbehavior.The measured runtime increase over solving the nominal trajectory is described as modest.Source: A. Two-player system · pp. 5–6
- Strategic robustness deviates 2.3× more from the nominal trajectory in the head-on scenario than in the parallel one, while increasing the collision parameter shifts both comparably.In the parallel case, robust trajectories are nearly unchanged; strategic robustness instead produces significantly wider paths in the head-on case.Source: A. Two-player system · pp. 5–6
B. A multi-agent system
- Across two to eight agents, strategic robustness takes 1.41× to 2.01× nominal trajectory-solving time, and this factor does not grow with agent count.The multi-agent tests include four- and eight-agent cases.Source: B. A multi-agent system · p. 6
V. CONCLUDING REMARKS
- The approach assumes identical agent dynamics, interagent costs, and robustness levels, which the authors expect could be relaxed for weighted or ordinal dynamic potential games.The implementation also assumes linear dynamics and uses SLSQP; dedicated solvers are suggested as a route toward nonlinear dynamics and constraints.Source: §V · p. 6
A. Proof of Theorem 1
The proof establishes the dynamic potential property by relating each modified agent cost to the modified potential and showing the required terms are independent or identical under the stated assumptions.
A. Proof of Theorem 1
- The proof defines Θ_i as the modified cost ˜J_i minus the modified potential ˜Φ.Source: A. Proof of Theorem 1 · p. 7
- Because dynamics are decoupled, Θ_i is independent of γ_i(x_0), so the modified costs form an exact dynamic potential game by Lemma 1.Source: A. Proof of Theorem 1 · p. 7
- Given Assumptions 1 and 3, identical dynamics and robustness levels make problems (10) and (11) the same.The proof states the resulting equality for all H in [0, T].Source: A. Proof of Theorem 1 · p. 7
B. Details on Section III-B
The inner adversarial problem is solved through a dual parameter: the input minimizer has a convex closed-form step, and the dual is maximized over nonnegative values.
B. Details on Section III-B
- For λ_H > 0, strict convexity lets the adversarial input minimizer be obtained by setting the objective gradient to zero.Source: B. Details on Section III-B · p. 7
- The controllability Gramian can be eigendecomposed offline, allowing the λ_H-dependent expression to be formed quickly online.Source: B. Details on Section III-B · p. 7
- When λ_H = 0, the problem reduces to least squares and the method selects the minimum-norm input using the Moore–Penrose pseudoinverse.Source: B. Details on Section III-B · p. 7
- The concave dual function q(λ_H) is maximized over λ_H ≥ 0; an interior maximizer satisfies the stated condition.A unique positive root exists only when P_l / σ_l,H > ϵ_j,H^2; otherwise λ_H = 0 is optimal, with exact interception iff z_H is in range(M_H).Source: B. Details on Section III-B · p. 7