A Player Selection Network for Scalable Game-Theoretic Prediction and Planning

1. Problem Statement

Game-theoretic planning frameworks are powerful for modeling multi-agent interactions (e.g., autonomous driving, pedestrian navigation) by computing Nash equilibrium strategies. However, they face a critical scalability bottleneck:

• Computational Complexity: The number of optimization variables scales with the number of agents ($N$). Solvers (typically Newton-style) exhibit cubic complexity ($O(N^3)$) relative to the total state and control variables, making real-time planning infeasible for large-scale scenarios (e.g., dense traffic with $>10$ agents).
• Limitations of Existing Selection Methods: Prior approaches to reduce game size rely on:
  • Threshold-based methods: Rely on fixed distance thresholds, requiring manual tuning and failing to generalize across densities.
  • Ranking-based methods: Select a fixed number ($k$) of agents based on heuristics (e.g., nearest neighbor). These can be too aggressive (missing critical agents) or too conservative (including irrelevant ones) and often require access to unavailable data (e.g., control inputs, cost functions) or online parameter tuning.
• Incomplete Information: In many real-world scenarios, the intentions (goals) or cost functions of other agents are unknown, further complicating game-theoretic planning.

2. Methodology: PSN Game

The authors propose PSN Game, a learning-based framework that dynamically reduces the game size by selecting only the most influential agents. The system consists of two core neural networks integrated into a receding-horizon planning loop:

A. Player Selection Network (PSN)

The PSN is a neural network that outputs a player selection mask ($M_i$) to distinguish influential players from irrelevant ones.

• Input: Past trajectories of the ego agent and surrounding agents. It supports two variants:
  • PSN-Full: Uses full state trajectories (position, velocity).
  • PSN-Partial: Uses only partial observations (e.g., position only), making it robust to sensor limitations.
• Output: A mask where entries indicate whether an agent is included in the game.
• Training Mechanism:
  • The network is trained using a differentiable dynamic game solver (Sun, 2025).
  • To enable backpropagation through the discrete selection process, the authors relax the binary mask to continuous values $m_{ij} \in [0, 1]$.
  • The shared cost function is reweighted by these continuous values: $\hat{c}^i_{s,k} = \sum m_{ij} c^i_{s,k}$.
  • Loss Functions:
    • For Prediction: Combines binary convergence ($L_{Binary}$), sparsity ($L_{Sparsity}$), and trajectory similarity to ground truth ($L_{Similarity}$).
    • For Planning: Combines binary convergence, sparsity, and game cost minimization ($L_{Cost}$).
  • At runtime, a threshold converts the continuous output back to a binary mask.

B. Goal Inference Network (GIN)

To handle incomplete-information games where agents' objectives are unknown:

• The GIN infers the 2D goal positions ($\hat{p}_g$) of other agents based on their past trajectories.
• It is trained supervisedly on datasets containing ground-truth Nash trajectories.
• The inferred goals are used to parameterize the masked game, allowing the PSN to function without prior knowledge of other agents' intentions.

C. Receding-Horizon Framework

The system operates in a loop (Algorithms 1 & 2):

1. Observe: Collect past $K$ steps of trajectories.
2. Infer: Use GIN to estimate goals of other agents (if unknown).
3. Select: Use PSN to generate a mask identifying key agents.
4. Solve: Solve a Masked Nash Game involving only the ego agent and the selected subset.
5. Plan: Execute the first control input and update the state.

3. Key Contributions

1. Objective-Driven PSN: A novel network trained via backpropagation through a differentiable game solver to learn optimal player selection masks, balancing performance with computational sparsity.
2. Goal Inference (GIN): A supervised network enabling the framework to operate in incomplete-information settings by inferring agent goals from trajectories.
3. Flexible Data Usage: Unlike prior methods, PSN requires no control inputs, cost functions, or game-specific parameters at runtime. It relies solely on trajectory observations (full or partial).
4. No Online Tuning: The method eliminates the need for manual threshold tuning or environment-specific parameter adjustment.
5. Scalability: The framework reduces game size by 50% to 75% while maintaining competitive performance.

4. Experimental Results

The authors evaluated PSN Game in simulated environments (4, 10, and 20 agents) and on the real-world CITR pedestrian dataset.

• Prediction Performance:

  • PSN (both Full and Partial variants) achieved competitive or superior Average Displacement Error (ADE) and Final Displacement Error (FDE) compared to baselines (Distance, kNN, Gradient, Hessian, Cost Evolution, BF, CBF).
  • In 20-agent scenarios (trained on 10), PSN remained robust when paired with a simple nearest-neighbor pre-filter.
  • On the CITR dataset, PSN achieved the best ADE, outperforming full-game solvers.

• Planning Performance:

  • PSN achieved the best safety metrics (lowest Collision Cost, highest Minimum Distance) in both 4 and 10-agent scenarios.
  • It maintained high Selection Consistency (temporal stability), avoiding the "flickering" of selected agents seen in some baselines.
  • Trajectory smoothness and length were comparable to or better than full-game solvers.

• Incomplete Information:

  • When paired with GIN, PSN maintained top-tier performance in scenarios with unknown agent goals, validating Hypothesis 3.

• Efficiency:

  • The method significantly reduced the number of players included in the optimization (e.g., selecting ~1.3–2.8 agents in a 4-agent game, and ~2.7–2.9 in a 10-agent game), directly addressing the $O(N^3)$ complexity issue.

5. Significance

This work provides a practical solution to the scalability bottleneck in game-theoretic multi-agent planning. By learning to select relevant agents based on spatio-temporal trajectory patterns rather than static heuristics, PSN Game enables:

• Real-time deployment of game-theoretic planners in dense, large-scale environments (e.g., urban autonomous driving).
• Robustness in scenarios where sensor data is partial or agent intentions are unknown.
• Generalization across different agent counts and real-world datasets without retraining.

The framework bridges the gap between the theoretical rigor of game theory and the computational constraints of real-world robotics, offering a mechanism to integrate scalable, safe, and efficient planning into existing multi-agent systems.