Game-theoretic planners

Exogenous uncertainty

Strategically robust game theory

We consider a finite horizon open-loop trajectory optimization problem with horizon \( T\) , where agent \( i\) decides on a strategy \( \gamma^i(x_0) = \{ u^i_k \}_{k\in [0, T-1]} \in \Gamma^i\) , a sequence of control inputs that generates a trajectory \( x^i = \{ x^i_k \}_{k \in [0, T]}\) such that \( (x^i, \gamma^i(x_0) ) \in C^i\) , with the initial state \( x^i_0\) given by \( x_0\) . The joint strategy of all players is \( \gamma(x_0) = (\gamma^1(x_0), \dots, \gamma^N(x_0))\) , where \( \Gamma=\prod_{i \in \mathcal{N}} \Gamma^i\) is the space of all joint strategies; we will write \( \gamma^i(x_0, k) = u^i_k\) . We write the cost to an agent as \( J^i(x_0, \{ \gamma^i(x_0), \gamma^{-i}(x_0) \})\) , where the trajectory \( x\) is generated from \( x_0\) by the strategies in the second argument.

The computation of open-loop Nash equilibria involves solving nonlinear equations coupled between players and is therefore computationally challenging. However, if the interagent costs satisfy symmetry properties—i.e., \( L^{ij}_k(x^i_k,x^j_k)=L^{ji}_k(x^j_k,x^i_k)\) —then the game admits a potential function; see [9, 7, 6] and the proof of our Theorem 1 below for details.

If a game is an exact dynamic potential game, every minimizer of the potential function is an open-loop Nash equilibrium. Thus, whenever the potential attains its minimum (e.g. when it is coercive), an equilibrium exists and can be found by solving a single optimization problem [6, 7]. Dynamic potential games can also be defined as games where we can represent \( J^i\) as the sum of a potential function and a term that is independent of the agent’s own strategy; see [[9, Lemma 3]] and [[26, Theorem 2.1]] for more details.

The Nash equilibrium is a natural solution concept for such a multi-agent decision problem, but in practice agents might fear misbehavior from others, i.e., deviations in their control inputs. We seek protection against such deviations by modifying the distance cost between ego agent \( i\) and agent \( j\) at time \( H \in [1,T]\) as follows: At \( H=0\) , \( \hat{x}^{j,0}_0 = x^j_0\) , so \( \tilde{L}^{ij}_0 = L^{ij}_0\) and we recover the nominal cost.

Each agent \( i \in \mathcal{N}\) evaluates the distance cost against a fictitious adversary. This adversary selects, for each agent \( j \in \mathcal{N} \setminus \{i\}\) and timestep \( H \in [1, T]\) , an open-loop policy \( \hat{\gamma}^{j,H}\) with the goal of maximizing the distance cost for agent \( i\) at each timestep \( H\) (equivalently, minimizing the distance between agents \( i\) and \( j\) at time \( H\) ), but cannot deviate in total by more than \( \epsilon^{j,H}\) from the nominal control inputs \( u^j_k, k\in [0, H-1]\) . The budget constrains deviations from \( \{u^j_k\}_{k=0}^{H-1}\) , so the adversary’s reachable set at time \( H\) is fixed, convex, and centered at \( x^j_H\) . Equivalently, under Assumption 2, (8) below depends on agents \( i\) and \( j\) only through the relative position \( z_H = x^i_H - x^j_H\) . Hence \( \tilde{L}^{ij}_H\) is well defined as written and continuously differentiable (since squared distance to a convex set is). As described in Section 1, \( \epsilon^{j,H}\) is the robustness level: at \( \epsilon^{j,H}=0\) the adversary is constrained to the nominal inputs \( u^j_k\) and we recover the standard Nash equilibrium, while larger values protect against larger perturbations.

Given this robust distance cost, the strategically robust control cost of each agent \( i\) is

With this, we can define strategically robust equilibria in our context as follows:

Note that our fictitious adversary is solving a target intercept problem with a separate adversarial trajectory \( \hat{\gamma}^{j,H}\) given deviation budget \( \epsilon^{j,H}\) for each timestep \( H\) . This is deliberate: a collision between two aircraft at any one timestep is catastrophic. Our fictitious adversary is at least as powerful as one committing to a single trajectory maximizing the more standard formulation of a summed distance cost over the entire horizon \( [0, T]\) , given the same budget.

We make two further assumptions. First, we assume the interagent cost is a monotone function of the distance between agents. Only the collision-relevant components of the state enter the distance cost; formally, \( \Vert D(x^i_H - x^j_H) \Vert^2\) for a fixed selection matrix \( D\) . We take \( D = I\) to lighten notation.

This assumption is natural for collision avoidance, where the cost should grow as agents approach one another. The logarithmic distance penalty from Section 2, \( L^{ij}_k(x^i_k, x^j_k) = -c \ln(\Vert x^i_k - x^j_k\Vert^2 + \eta)\) , satisfies this assumption.

Second, we assume players have the same robustness level.

Our main theoretical result follows.

We prove Theorem 1 in Appendix 5.1. Because the strategically robust costs \( \tilde{J}^i\) form an exact dynamic potential game, every minimizer of the potential function (7) is a strategically robust equilibrium. Finally, two comments on the symmetry. First, Assumption 2 implies \( L^{ij}_H(x^i_H, x^j_H) = L^{ji}_H(x^j_H, x^i_H)\) . Relaxing this assumption in certain ways (e.g., allowing agent-dependent weights) would still yield a weighted dynamic potential game [7]. Second, we also hypothesize that relaxing Assumption 3 such that \( \epsilon^{i,H} \neq \epsilon^{j,H}\) under certain conditions could yield an ordinal potential game. Ordinal and weighted potential games, with appropriate assumptions, have convergence guarantees [8].

Pan/Zoom

Pan/Zoom

Pan/Zoom

Pan/Zoom

While attractive, minimizing the potential still entails a computational challenge: the mere evaluation of \( \tilde L^{ij}_H\) requires solving an optimization problem. We now derive a quasi-closed-form and computationally efficient solution to this worst-case problem in three steps:

Step 1 (Monotonicity) By monotonicity of \( \mu\) , we can maximize the distance cost by minimizing the squared distance in (5) for a given \( j, H\) . Define the relative position \( z_H = x^i_H - x^j_H\) , and the deviations \( \delta z^{j,H}_k = x^j_k - \hat{x}^{j,H}_k\) and \( \delta u^{j,H}_k = u^j_k - \hat{u}^{j,H}_k\) . Plugging into (5) gives

where we used the monotonicity of \( \mu\) . Thus, we can focus on solving the inner minimization. The inner minimization satisfies Slater’s condition for \( \epsilon^{j, H} > 0\) , so strong duality holds. For fixed dual multiplier \( \lambda_H\geq 0\) , we therefore write its Lagrangian relaxation, with \( \delta z^{j,H}_{0}=0\) :

Step 2 (Optimal Control) For fixed dual multiplier \( \lambda_H\geq 0\) , (8) is a quadratic optimization problem that gives us \( \delta u^{j,H}_k\) and \( \delta z^{j,H}_H\) in closed form, where \( M_H = [A^{H-1}B, \dots, AB, B]\) (see Appendix 5.2):

Here \( {}^{\dagger}\) denotes the Moore–Penrose pseudoinverse, which equals the ordinary inverse when \( \lambda_H>0\) . We then decompose \( M_H {M_H}^\top\) into its eigendecomposition \( Q_H \Sigma_{\sigma_H} {Q_H}^\top\) , which can be precomputed for all \( H\) .

Step 3 (Updating \( \lambda_H\) ) We can efficiently compute the dual multipliers \( \lambda_H\) by first testing whether \( \lambda_H=0\) is optimal; otherwise, we take the eigendecomposition of \( M_H {M_H}^\top\) and solve the first-order condition of the dual using Newton iterations, as shown in Appendix 5.2. The final algorithm is summarized in Algorithm 1.

We consider the two scenarios in Figure 3, Figure 4, where two agents are traveling either head-on or in parallel. To start, we observe that the strategically robust trajectories are wider compared to the nominal trajectories. This is a direct consequence of strategic robustness: since agents protect against misbehavior by other agents, they commit to wider trajectories to reduce the collision risk.

Increasing the collision parameter

Runtime

Finally, we test our strategically robust trajectory planner for four and eight agents. We plot only the nominal and strategically robust methods for clarity. The resulting trajectories are shown in Figure 5, Figure 6, and the computational times are listed in Table 3. Strategic robustness takes between \( 1.41\times\) and \( 2.01\times\) the time of solving the nominal trajectory across two to eight agents, and the factor does not grow with the number of agents \( N\) .

It suffices to show that \( \tilde{L}^{ij}_H(x^i_H, x^j_H) = \tilde{L}^{ji}_H(x^j_H, x^i_H)\) for all \( i < j \in \mathcal{N}, \, H \in [0, T]\) , because then the terms of \( \tilde{\Phi}\) from (7) involving agent \( i\) are exactly \( \tilde{J}^i\) . Define \( \Theta^i \mathrm{:=} \tilde{J}^i - \tilde{\Phi}\) :

Because dynamics are decoupled, \( \Theta^i\) is a dummy function independent of \( \gamma^{i}(x_0)\) . Thus \( \{\tilde{J}^i\}_{i \in \mathcal{N}}\) forms an exact dynamic potential game by Lemma 1. Next, we show \( \tilde{L}^{ij}_H(x^i_H, x^j_H) = \tilde{L}^{ji}_H(x^j_H, x^i_H)\) using Assumption 2, Assumption 3. Recall \( \tilde{L}^{ij}_H(x^i_H, x^j_H)\) given by (5):

Define \( \delta z^{j,H}_k = x^j_k - \hat{x}^{j,H}_k\) and \( \delta u^{j,H}_k = u^j_k - \hat{u}^{j,H}_k\) to rewrite the dynamics as

with the initial condition \( \delta z^{j,H}_{0}=0\) as \( \hat{x}^{j,H}_0=x^j_0\) . Since \( z_H = x^i_H - x^j_H\) is constant with respect to the adversarial optimization of (9), we can rewrite it as

Second, we consider \( \tilde{L}^{ji}_H(x^j_H, x^i_H)\) , defined similarly to (9). Following similar steps, define \( \delta z^{i,H}_k = \hat{x}^{i,H}_k-x^i_k\) and \( \delta u^{i,H}_k = \hat{u}^{i,H}_k-u^i_k\) , so that \( x_H^j-\hat x_H^{i,H}=-z_H-\delta z_H^{i,H}\) (the sign flip ensures a match with the definition of \( z_H\) above). Then, we can rewrite \( \tilde{L}^{ji}_H(x^j_H, x^i_H)\) as

The case \( H=0\) is trivial by \( \hat{x}^{j,0}_0 = x^j_0\) . Given that \( \epsilon^{i,H} = \epsilon^{j,H}\) by Assumption 3 and \( (A, B)\) are identical by Assumption 1, the problems (10) and (11) are the same, which implies that \( \tilde{L}^{ij}_H(x^i_H, x^j_H) = \tilde{L}^{ji}_H(x^j_H, x^i_H)\) for all \( H \in [0, T]\) .

Step 2 (Optimal Control) Consider (8) for timesteps \( H \in [1, T]\) , assuming \( \epsilon^{j,H} > 0\) with fixed \( \lambda_H \geq 0\) and \( \delta z^{j,H}_0 = 0\) . Let \( M_H = [A^{H-1}B, \dots, AB, B]\) and \( \delta u^{j,H} \) be the vertical concatenation of \( \delta u^{j,H}_0, \dots, \delta u^{j,H}_{H-1}\) , so that \( \delta z^{j,H}_H = M_H \delta u^{j, H}\) . We can rewrite (8) as

For \( \lambda_H > 0\) , the objective is strictly convex, and setting its gradient to zero gives the unique input minimizer:

Substituting into \( \delta z^{j,H}_H\) gives

The matrix \( M_H {M_H}^\top\) is the positive semidefinite controllability Gramian. We can compute its eigendecomposition offline as \( Q_{H} \Sigma_{\sigma_H}{Q_{H}}^\top\) , where \( \Sigma_{\sigma_H} = \text{diag}(\sigma_{1,H}, \dots, \sigma_{n,H})\) , \( \sigma_{l,H}\geq 0\) , and \( Q_H\) is an orthogonal matrix. For \( \lambda_H > 0\) , we can then rewrite \( \delta z^{j,H}_H\) as

where \( \Sigma_{\frac{\sigma_H}{\lambda_H + \sigma_H}}\) is quickly formed online.

If \( \lambda_H = 0\) , the problem reduces to least squares. We select the minimum-norm input \( \delta u^{j,H}= -M_H^{\dagger} z_H\) , giving \( \delta z^{j,H}_H = -M_H M_H^{\dagger} z_H\) , where \( M_H^{\dagger}\) is the Moore–Penrose pseudoinverse. We can also derive this using the limit as \( \lambda_H \to 0^+\) and following the singular value decomposition.

Step 3 (Updating \( \lambda_H\) ) We maximize the dual function \( q(\lambda_H)\) over \( \lambda_H \geq 0\) . Substituting \( \delta u^{j,H}\) from Step 2 into the Lagrangian and simplifying gives, for \( \lambda_H > 0\) ,

Let \( w={Q_H}^\top z_H\) . As \( \lambda_H \to 0^+\) , the ratio \( \lambda_H/(\lambda_H + \sigma_{l,H})\) becomes one for \( \sigma_{l,H}=0\) and zero otherwise, so \( q(0) = \sum_{l:\sigma_{l,H} = 0} w_l^2\) , the squared residual in unreachable directions. The dual function \( q(\lambda_H)\) is concave on \( \lambda_H \geq 0\) . An interior maximizer satisfies

This unique positive root exists if and only if \( \sum_{l:\sigma_{l,H}>0} w_l^2/\sigma_{l,H} > {\epsilon^{j,H}}^2\) . Then we can compute the root using Newton’s method, initialized at \( \lambda_H > 0\) with \( q'(\lambda_H) > 0\) . Otherwise, \( \lambda_H=0\) is optimal, and the adversary exactly intercepts the agent if and only if \( z_H\in\operatorname{range}(M_H)\) .