Literature
Display
← All papers

MultiNash-PF: A Particle Filtering Approach for Computing Multiple Local Generalized Nash Equilibria in Trajectory Games

Maulik Bhatt · Iman Askari · Yue Yu · Ufuk Topcu · Huazhen Fang · Negar Mehr

· IROS 2025 ↗

Robotics5 min text · CondensedOriginal paper ↗
Contents

At a glance

MultiNash-PF searches for several locally stable joint trajectories in a constrained multi-agent game. A potential-game formulation turns equilibrium search into one constrained optimization problem. Implicit particle filtering locates promising trajectory groups, clustering provides initial guesses, and a nonlinear solver refines each group. In a two-agent obstacle example, recovering six modes takes 3.36 seconds versus 6.71 seconds for repeated random solver initialization. A small human–robot experiment demonstrates choosing between two precomputed passing modes; the method does not guarantee finding every equilibrium.

I Introduction

When two agents pass each other, yielding on either side may work, but incompatible choices can cause a conflict. A robot therefore benefits from considering several outcomes and identifying the other agent’s preference. The proposed pipeline aims to find multiple useful local equilibria efficiently. Its finite sampled search should be distinguished from complete enumeration of all possible behaviors or from knowing that a human will follow the assumed game model.

Refer to caption
Fig. 1: Snapshot of an interaction between a robot and a human when they exchange positions. Using MultiNash-PF, the robot can compute both modes of interaction. At t=2t=2, the robot is uncertain about the preferred mode of the human since the human trajectory’s distance from both equilibria is almost the same. At t=4t=4, the human trajectory is closer to the yield-right GNE; therefore, the robot chooses the corresponding GNE and avoids collision with the human.

II Related Works

Game-theoretic planners compute interactive trajectories using best responses, local approximations, constrained solvers, or potential games [11]. A single optimization initialization usually returns only one local solution. Repeating random starts can recover more modes but often revisits the same solution. Bayesian trajectory inference and implicit particle filtering [31] motivate a more focused initialization strategy.

III Constrained Potential Trajectory Games

Each agent has continuously differentiable dynamics and a quadratic cost for tracking its reference trajectory and limiting control effort. Individual costs depend only on that agent’s states and controls; shared constraints couple the agents through collision avoidance and other bounds. This restricted cost/constraint structure is what enables the potential-game reduction. It does not represent arbitrary strategic preferences or general-sum games.

Equations 1–3
xt+1i=fi​(xti,uti),x_{t+1}^{i}=f^{i}(x_{t}^{i},u_{t}^{i}), (1)
g⁡(xt,ut)≤0c,g(x_{t},u_{t})\leq{0}_{c}, (2)
‖xτi−x^τi‖Qτi2+∑t=0τ−1‖xti−x^ti‖Qi2+∑t=0τ‖uti‖Ri2\left\lVert x_{\tau}^{i}-\hat{x}_{\tau}^{i}\right\rVert_{Q^{i}_{\tau}}^{2}+\sum_{t=0}^{\tau-1}\left\lVert x_{t}^{i}-\hat{x}_{t}^{i}\right\rVert_{Q^{i}}^{2}+\sum_{t=0}^{\tau}\left\lVert u_{t}^{i}\right\rVert_{R^{i}}^{2} (3)

III-A Local Generalized Nash Equilibrium Trajectories

A local generalized Nash equilibrium is a feasible joint trajectory for which no individual agent can improve its cost by a sufficiently small feasible unilateral change. Because the costs are separable, their sum forms a potential whose local constrained minima are sufficient to produce such equilibria. The retained theorem and proof establish this direction, drawing on the cited potential-game result.

The reverse direction is not guaranteed: finding all local minima of this potential need not find all equilibria of the original game. In addition, the proposed sampled algorithm need not find every potential minimum. The paper acknowledges the first limitation; the demonstrated mode counts are empirical results for specified examples.

Equations 4–6
𝒢:=(𝒩,{Qi}i∈𝒩,{Qτi}i∈𝒩,{Ri}i∈𝒩,g,f,x^0:τ).\mathcal{G}:=\left(\mathcal{N},\{Q^{i}\}_{i\in\mathcal{N}},\{Q^{i}_{\tau}\}_{i\in\mathcal{N}},\{R^{i}\}_{i\in\mathcal{N}},g,f,\hat{x}_{0:\tau}\right).
min{x0:τi,u0:τi}\displaystyle\min_{\{x_{0:\tau}^{i},u_{0:\tau}^{i}\}} ‖xτi−x^τi‖Qτi2+∑t=0τ−1‖xti−x^ti‖Qi2+∑t=0τ‖uti‖Ri2\displaystyle\left\lVert x_{\tau}^{i}-\hat{x}_{\tau}^{i}\right\rVert_{Q^{i}_{\tau}}^{2}+\sum_{t=0}^{\tau-1}\left\lVert x_{t}^{i}-\hat{x}_{t}^{i}\right\rVert_{Q^{i}}^{2}+\sum_{t=0}^{\tau}\left\lVert u_{t}^{i}\right\rVert_{R^{i}}^{2}
s.t\displaystyle\mathrm{s.t}\quad x0i=x^0i,xt+1i=fi​(xti,uti),0≤t≤τ−1,\displaystyle x^{i}_{0}=\hat{x}^{i}_{0},\enskip x^{i}_{t+1}=f^{i}(x^{i}_{t},u^{i}_{t}),\enskip 0\leq t\leq\tau-1,
g⁡(x~t,u~t)≤0c,0≤t≤τ,\displaystyle g(\tilde{x}_{t},\tilde{u}_{t})\leq{0}_{c},\enskip 0\leq t\leq\tau, (4)
x~t\displaystyle\tilde{x}_{t} ≔[(xt1⋆)⊤(xt2⋆)⊤⋯(xti−1⋆)⊤(xti)⊤(xti+1⋆)⊤⋯(xtN⋆)⊤]⊤,\displaystyle\coloneqq\begin{bmatrix}({x}_{t}^{1^{\star}})^{\top}&({x}_{t}^{2^{\star}})^{\top}&\cdots&({x}_{t}^{{i-1}^{\star}})^{\top}&(x_{t}^{i})^{\top}&({x}_{t}^{{i+1}^{\star}})^{\top}&\cdots&({x}_{t}^{N^{\star}})^{\top}\end{bmatrix}^{\top},
u~t\displaystyle\tilde{u}_{t} ≔[(ut1⋆)⊤(ut2⋆)⊤⋯(uti−1⋆)⊤(uti)⊤(uti+1⋆)⊤⋯(utN⋆)⊤]⊤.\displaystyle\coloneqq\begin{bmatrix}({u}_{t}^{1^{\star}})^{\top}&({u}_{t}^{2^{\star}})^{\top}&\cdots&({u}_{t}^{{i-1}^{\star}})^{\top}&(u_{t}^{i})^{\top}&({u}_{t}^{{i+1}^{\star}})^{\top}&\cdots&({u}_{t}^{N^{\star}})^{\top}\end{bmatrix}^{\top}.
min{x0:τ,u0:τ}\displaystyle\min_{\{x_{0:\tau},u_{0:\tau}\}} ‖xτ−x^τ‖Qτ2+∑t=0τ−1‖xt−x^t‖Q2+∑t=0τ‖ut‖R2\displaystyle\left\lVert x_{\tau}-\hat{x}_{\tau}\right\rVert_{Q_{\tau}}^{2}+\sum_{t=0}^{\tau-1}\left\lVert x_{t}-\hat{x}_{t}\right\rVert_{Q}^{2}+\sum_{t=0}^{\tau}\left\lVert u_{t}\right\rVert_{R}^{2}
s.t\displaystyle\mathrm{s.t}\quad x0=x^0,xt+1=f⁡(xt,ut),0≤t≤τ−1,\displaystyle x_{0}=\hat{x}_{0},\enskip x_{t+1}=f(x_{t},u_{t}),\enskip 0\leq t\leq\tau-1,
g⁡(xt,ut)≤0c,0≤t≤τ,\displaystyle g(x_{t},u_{t})\leq{0}_{c},\enskip 0\leq t\leq\tau, (5)
∑i=1N(‖xτi−x^τi‖Qτi2+∑t=0τ−1‖xti−x^ti‖Qi2+∑t=0τ‖uti‖Ri2).\sum_{i=1}^{N}\left(\left\lVert x_{\tau}^{i}-\hat{x}_{\tau}^{i}\right\rVert_{Q^{i}_{\tau}}^{2}+\sum_{t=0}^{\tau-1}\left\lVert x_{t}^{i}-\hat{x}_{t}^{i}\right\rVert_{Q^{i}}^{2}+\sum_{t=0}^{\tau}\left\lVert u_{t}^{i}\right\rVert_{R^{i}}^{2}\right). (6)
Original figure
Fig. 2: When using MultiNash-PF on a difficult two agent trajectory game, we first employ an implicit particle filter to obtain coarse estimates of GNEs.

IV Identifying Local Nash Equilibria via Bayesian Inference

The trajectory optimization problem is recast as a virtual state-estimation problem. Reference states act as measurements, and a soft constraint-violation term favors feasible trajectories. Gaussian disturbance models connect high-posterior trajectories to low-cost solutions under the stated assumptions. This inference stage supplies approximate candidates; it does not replace the final constrained solver’s feasibility check.

Each particle describes a complete trajectory. Rather than sample indiscriminately, an implicit map steers samples toward high-probability regions. A bank of unscented Kalman filters supplies local Gaussian approximations to make that map tractable. The approach can reduce particle degeneracy and resampling, but local approximations and finite particles remain sources of missed modes.

Trajectories are clustered using Fréchet distance, with hierarchical clustering or density-based clustering suggested. Each cluster’s mean initializes IPOPT [24], which refines a constrained local solution. Clustering thresholds and mode coverage affect how many distinct solutions are recovered. Algorithm 1 retains the original PDF’s line grouping and indentation.

Equations 7–10
min{vt,wt,ηt}t=0τ\displaystyle\min_{\{v_{t},w_{t},\eta_{t}\}_{t=0}^{\tau}} ‖vτ‖Qτ2+∑t=0τ−1‖vt‖Q2+∑t=0τ(‖wt‖R2+‖ηt‖Qη2),\displaystyle\left\lVert v_{\tau}\right\rVert_{Q_{\tau}}^{2}+\sum_{t=0}^{\tau-1}\left\lVert v_{t}\right\rVert_{Q}^{2}+\sum_{t=0}^{\tau}\left(\left\lVert w_{t}\right\rVert_{R}^{2}+\left\lVert\eta_{t}\right\rVert^{2}_{Q_{\eta}}\right),
s.t\displaystyle\mathrm{s.t}\quad [xt+1ut+1]=[f⁡(xt,ut)0m]+[0nwt],\displaystyle\begin{bmatrix}x_{t+1}\\ u_{t+1}\end{bmatrix}=\begin{bmatrix}f(x_{t},u_{t})\\ 0_{m}\end{bmatrix}+\begin{bmatrix}0_{n}\\ w_{t}\end{bmatrix},
[yx,tyg,t]=[xtψ⁡(g⁡(xt,ut))]+[vtηt],\displaystyle\begin{bmatrix}y_{x,t}\\ y_{g,t}\end{bmatrix}=\begin{bmatrix}x_{t}\\ \psi\left(g(x_{t},u_{t})\right)\end{bmatrix}+\begin{bmatrix}v_{t}\\ \eta_{t}\end{bmatrix},
[x0u0]=[x^0wt−1],0≤t≤τ,\displaystyle\begin{bmatrix}x_{0}\\ u_{0}\end{bmatrix}=\begin{bmatrix}\hat{x}_{0}\\ w_{t-1}\end{bmatrix},\quad 0\leq t\leq\tau, (7)
ψ⁡(g⁡(xt,ut))=1α​ln⁡(1+exp⁡(g⁡(xt,ut))),\psi\left(g(x_{t},u_{t})\right)=\frac{1}{\alpha}\ln\left(1+\exp\left(g\left(x_{t},u_{t}\right)\right)\right), (8)
x¯t+1=f¯​(x¯t)+w¯t,y¯t=h¯​(x¯t)+v¯t,\displaystyle\bar{x}_{t+1}=\bar{f}(\bar{x}_{t})+\bar{w}_{t},\;{\bar{y}}_{t}=\bar{h}(\bar{x}_{t})+\bar{v}_{t}, (9)
x¯t\displaystyle\bar{x}_{t} =[xtut],y¯t=[yx,tyg,t],w¯t=[0nwt],\displaystyle=\begin{bmatrix}x_{t}\\ u_{t}\end{bmatrix},\>\bar{y}_{t}=\begin{bmatrix}y_{x,t}\\ y_{g,t}\end{bmatrix},\>\bar{w}_{t}=\begin{bmatrix}0_{n}\\ w_{t}\end{bmatrix},
v¯t=[vtηt],f¯​(CLOSE\displaystyle\bar{v}_{t}=\begin{bmatrix}v_{t}\\ \eta_{t}\end{bmatrix},\;\bar{f}( OPENx¯t)=[f⁡(xt,ut)0m],h¯​(x¯t)=[xtψ⁡(g⁡(xt,ut))],\displaystyle\bar{x}_{t})=\begin{bmatrix}f(x_{t},u_{t})\\ {0}_{m}\end{bmatrix},\;\bar{h}(\bar{x}_{t})=\begin{bmatrix}x_{t}\\ \psi(g\left(x_{t},u_{t}\right))\end{bmatrix},
v¯t∼𝒩⁡(0n+c,Q¯),v¯τ∼𝒩⁡(0n+c,Q¯τ),w¯t∼𝒩⁡(0n+m,R¯),\bar{v}_{t}\sim\mathcal{N}(0_{n+c},\bar{Q}),\;\bar{v}_{\tau}\sim\mathcal{N}(0_{n+c},\bar{Q}_{\tau}),\;\bar{w}_{t}\sim\mathcal{N}(0_{n+m},\bar{R}),
y¯t=[x^t0c],0≤t≤τ.\bar{y}_{t}=\begin{bmatrix}\hat{x}_{t}\\ {0}_{c}\end{bmatrix},0\leq t\leq\tau.
x¯0:τ⋆=argmaxx¯0:τlogp(x¯0:τ|y¯0​τ).\displaystyle\bar{x}_{0:\tau}^{\star}=\arg\max_{\bar{x}_{0:\tau}}\>\log p(\bar{x}_{0:\tau}\,|\,\bar{y}_{0\tau}).
p(x¯0:τ|y¯0:τ)≈∑j=1Jwτjδ(x0:τ−x0:τj),p(\bar{x}_{0:\tau}\,|\,\bar{y}_{0:\tau})\approx\sum_{j=1}^{J}w_{\tau}^{j}\delta\left(x_{0:\tau}-x_{0:\tau}^{j}\right), (10)
Refer to caption
Fig. 3: MultiNash-PF identifies all the local GNE trajectories for a challenging two-agent trajectory game where two agents swapped positions while avoiding an obstacle. In this scenario, the obstacle radius is greater than the collision avoidance radius of the two agents, leading to the discovery of 6 distinct Nash equilibria. MultiNash-PF effectively obtains coarse estimates of local GNEs through implicit particle filtering, which are then refined using IPOPT to obtain local GNEs.
Equations 11–12
p(x¯0:t|y¯0:t)=p(y¯t|x¯t)p(x¯t|x¯t−1)p(x¯0:t−1|y¯0:t−1),p(\bar{x}_{0:t}\,|\,\bar{y}_{0:t})=p(\bar{y}_{t}\,|\,\bar{x}_{t})p(\bar{x}_{t}\,|\,\bar{x}_{t-1})p(\bar{x}_{0:t-1}\,|\,\bar{y}_{0:t-1}), (11)
F⁡(xti)−min⁡F⁡(xti)=G⁡(γti)−min⁡G⁡(γti),F(x_{t}^{i})-\min F(x_{t}^{i})=G(\gamma_{t}^{i})-\min G(\gamma_{t}^{i}), (12)
p(x¯tj|y¯0:t)∼𝒩(m^tj,Σ^tx,j),p(\bar{x}_{t}^{j}|\bar{y}_{0:t})\sim\mathcal{N}\left(\hat{m}_{t}^{j},\hat{\Sigma}_{t}^{x,j}\right),
x¯tj=m^tj+Σ^tx,j​γtj,\bar{x}_{t}^{j}=\hat{m}_{t}^{j}+\sqrt{\hat{\Sigma}_{t}^{x,j}}\gamma_{t}^{j},
Algorithm 1 MultiNash-PF: Multiple local GNEs based on particle filter
Original Algorithm 1 body, including indented filtering steps, restored from PDF page 6.

V Numerical Simulations

The simulations use two unicycle agents with position, heading, linear velocity, and angular velocity states. Inputs change the two velocities, and quadratic costs favor straight reference paths. With mutual collision avoidance alone, the experiment recovers left-passing and right-passing equilibria.

A second scenario adds a central obstacle of radius four metres, larger than the three-metre agent separation radius, plus control bounds. Fifty particles recover six reported modes: two pass on opposite sides of the obstacle, and four pass on the same side with different yielding orders. Spatially overlapping curves can still avoid collision because agents traverse them at different times. The evidence is limited to these two-agent scenarios.

Equations 13–14
pt+1i\displaystyle p^{i}_{t+1} =pit+Δt⋅νitcosθit,qit+1=qit+Δt⋅νitsinθit\displaystyle=p^{i}_{t}+\Delta t\cdot\nu^{i}_{t}\cos{\theta^{i}_{t}},\;q^{i}_{t+1}=q^{i}_{t}+\Delta t\cdot\nu^{i}_{t}\sin{\theta^{i}_{t}}
θt+1i\displaystyle\theta^{i}_{t+1} =θti+Δ​t⋅ωi,νt+1i=νti+Δ​νti,ωt+1i=ωti+Δ​ωti,\displaystyle=\theta^{i}_{t}+\Delta t\cdot\omega_{i},\;\nu^{i}_{t+1}=\nu^{i}_{t}+\Delta\nu^{i}_{t},\;\omega^{i}_{t+1}=\omega^{i}_{t}+\Delta\omega^{i}_{t},
xti=[ptiqtiθtiνtiωti]⊤,uti=[Δ​νtiΔ​ωti]⊤.x^{i}_{t}=\begin{bmatrix}p^{i}_{t}&q^{i}_{t}&\theta^{i}_{t}&\nu^{i}_{t}&\omega^{i}_{t}\end{bmatrix}^{\top},\enskip u^{i}_{t}=\begin{bmatrix}\Delta\nu^{i}_{t}&\Delta\omega^{i}_{t}\end{bmatrix}^{\top}.
Qi=0.6​Q^,Qτi=100​Q^,Ri=d​i​a​g​(8,4).\displaystyle Q^{i}=0.6\hat{Q},\;Q^{i}_{\tau}=100\hat{Q},\;R^{i}=diag(8,4). (13)
gc​(xt,ut)≔−d⁡(xt1,xt2)+rcol≤0,\displaystyle g_{c}(x_{t},u_{t})\coloneq-d(x^{1}_{t},x^{2}_{t})+r_{\text{col}}\leq 0, (14)
Refer to caption
Fig. 4: The Nash equilibrium trajectories found by MultiNash-PF when two unicycle agents change their positions. First, we use the implicit particle filter to discover the coarse estimates of two different equilibria, and then utilize them as a warm start for IPOPT to obtain the two Nash equilibrium trajectories.
Refer to caption
(a) Histogram of the number of IPOPT runs required to obtain all six equilibria.
Refer to caption
(b) Histogram of the solve time comparison of MultiNash-PF and the baseline.
Fig. 5: Comparison of MultiNash-PF with the baseline for the experiment shown in Fig. 3.
(a) For the baseline, the average number of IPOPT runs required to obtain all six different equilibria is 18.64±7.5718.64\pm 7.57, while for MultiNash-PF, this is always 66. MultiNash-PF requires 3 times fewer IPOPT runs. (b) MultiNash-PF reduces the solve time by about 50%50\% compared to the baseline while giving a much lower variance on the solve time.

V- 1 Comparison with Baseline

Over one hundred Monte Carlo runs of the obstacle case, random initialization needs 18.64 ± 7.57 IPOPT solves to recover the six known modes, while the proposed method uses six refinement solves. Total measured time falls from 6.71 ± 2.83 seconds to 3.36 ± 0.59 seconds, approximately a 50% reduction. Filtering accounts for 0.37 ± 0.072 seconds and refinement for 2.99 ± 0.57 seconds. This comparison stops when six previously identified modes have been recovered; it is not a proof of exhaustive equilibrium discovery or a general scaling study.

VI Hardware Experiment

A TurtleBot 4 and one human exchange positions, with both modeled using unicycle dynamics and tracked by Vicon motion capture. The robot precomputes two passing equilibria, then replans with a five-second horizon and 0.1-second discretization during a ten-second interaction. It compares the observed human trajectory with the two candidate human paths using Fréchet distance and selects a mode once their distance difference exceeds a threshold.

In ten trials with the human instructed to choose left or right randomly, the robot identifies the mode, avoids collision, and reaches its goal. This supports the two-mode demonstration but supplies no broad human-subject evaluation, uncertainty calibration, or safety guarantee. The several-second multi-equilibrium search is performed in advance; these trials do not establish real-time recomputation of all modes at every control step.

VII Conclusion

The contribution is a practical initialization pipeline for discovering multiple local interaction modes before constrained refinement. Its strengths are lower repeated-solver cost in the tested example and a physical demonstration of mode adaptation. Coverage depends on sampling and clustering, the equilibrium reduction requires the specified game structure, and larger populations or more complex human behavior are not evaluated.

Concept demonstration

Open image ↗