2025-11-12T02:22:29.481811

PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network

Qiu, Ouano, Palafox et al.

While game-theoretic planning frameworks are effective at modeling multi-agent interactions, they require solving large optimization problems where the number of variables increases with the number of agents, resulting in long computation times that limit their use in large-scale, real-time systems. To address this issue, we propose 1) PSN Game: a learning-based, game-theoretic prediction and planning framework that reduces runtime by learning a Player Selection Network (PSN); and 2) a Goal Inference Network (GIN) that makes it possible to use the PSN in incomplete information games where agents' intentions are unknown. A PSN outputs a player selection mask that distinguishes influential players from less relevant ones, enabling the ego player to solve a smaller, masked game involving only selected players. By reducing the number of players in the game, and therefore reducing the number of variables in the corresponding optimization problem, PSN directly lowers computation time. The PSN Game framework is more flexible than existing player selection methods as it 1) relies solely on observations of players' past trajectories, without requiring full state, action, or other game-specific information; and 2) requires no online parameter tuning. Experiments in both simulated scenarios and human trajectory datasets demonstrate that PSNs outperform baseline selection methods in 1) prediction accuracy; and 2) planning safety. PSNs also generalize effectively to real-world scenarios in which agents' objectives are unknown without fine-tuning. By selecting only the most relevant players for decision-making, PSN Game offers a general mechanism for reducing planning complexity that can be seamlessly integrated into existing multi-agent planning frameworks.

academic

PSN Game : Prédiction et Planification Théorique des Jeux via un Réseau de Sélection de Joueurs

Informations Fondamentales

ID de l'article : 2505.00213
Titre : PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
Auteurs : Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (Université du Texas à Austin)
Classification : cs.RO (Robotique), math.OC (Optimisation et Contrôle)
Date de publication : 2025 (prépublication arXiv)
Lien de l'article : https://arxiv.org/abs/2505.00213

Résumé

Bien que les cadres de planification théorique des jeux soient efficaces pour modéliser les interactions multi-agents, ils nécessitent de résoudre de grands problèmes d'optimisation dont le nombre de variables augmente avec le nombre d'agents, ce qui entraîne des temps de calcul excessifs et limite les applications dans les systèmes temps réel à grande échelle. Pour résoudre ce problème, cet article propose : 1) PSN Game - un cadre d'apprentissage pour la prédiction et la planification théorique des jeux qui réduit le temps d'exécution en apprenant un réseau de sélection de joueurs (PSN) ; 2) un réseau d'inférence d'objectifs (GIN) qui permet au PSN d'être utilisé dans les jeux à information incomplète où les intentions des agents sont inconnues. Le PSN génère un masque de sélection de joueurs qui distingue les joueurs influents des joueurs moins pertinents, permettant à l'agent autonome de résoudre un jeu masqué de plus petite taille impliquant uniquement les joueurs sélectionnés. En réduisant le nombre de joueurs dans le jeu et, par conséquent, le nombre de variables dans le problème d'optimisation correspondant, le PSN réduit directement le temps de calcul.

Contexte et Motivation de la Recherche

Définition du Problème

Le problème fondamental auquel font face les cadres de planification théorique des jeux dans les systèmes multi-agents est que la complexité de calcul croît de manière cubique avec le nombre d'agents. Comme le montre la figure 2, avec les solveurs existants, le temps de calcul croît selon O(N³), où N est le nombre de joueurs. Cela rend les méthodes théorique des jeux impratiques dans les systèmes temps réel à grande échelle.

Importance de la Recherche

Exigences de temps réel : Les applications telles que la conduite autonome et la navigation robotique nécessitent une replanification fréquente, rendant l'efficacité de calcul cruciale
Défis d'échelle : Dans les scénarios réels, le nombre d'agents est souvent très important (par exemple, dans les environnements de circulation dense)
Inspiration du comportement humain : La recherche montre que les conducteurs humains dans la circulation dense donnent naturellement la priorité aux véhicules menaçants à proximité plutôt que de surveiller tous les véhicules

Limitations des Méthodes Existantes

Les méthodes existantes de sélection de joueurs présentent les problèmes suivants :

Forte dépendance informationnelle : Nécessitent des informations spécifiques au jeu telles que les contrôles, les fonctions de coût, etc.
Complexité du réglage des paramètres : Nécessitent des ajustements de paramètres spécifiques à l'environnement
Stratégies de sélection figées : Les méthodes de classement basées sur des heuristiques simples (distance, gradient) manquent d'adaptabilité

Contributions Principales

Proposition d'un réseau de sélection de joueurs non supervisé (PSN) : Entraîné avec un solveur de jeu dynamique différentiable, supportant la rétropropagation via des masques de sélection
Construction d'un réseau d'inférence d'objectifs supervisé (GIN) : Déduit les objectifs des agents à partir des trajectoires historiques, permettant au PSN de s'appliquer aux scénarios où les intentions sont inconnues
Développement d'un cadre d'horizon temporel décroissant : Utilise le PSN pour identifier efficacement les stratégies d'équilibre en résolvant des jeux de taille réduite
Validation expérimentale : Sur des simulations multi-agents et des ensembles de données de trajectoires humaines réelles, PSN Game réduit efficacement la taille du jeu de 50%-75%, réalisant une accélération significative

Détails de la Méthode

Définition de la Tâche

Considérez un jeu de Nash en boucle ouverte à horizon fini en temps discret avec N agents, où chaque agent i possède un état $x_k^i \in \mathbb{R}^n$ et une entrée de contrôle $u_k^i \in \mathbb{R}^m$ . La transition d'état de chaque agent suit l'équation dynamique : $x_{k+1}^i = f^i(x_k^i, u_k^i)$

L'objectif de chaque agent est de minimiser le coût cumulatif : $J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)$

Architecture du Modèle

1. Réseau de Sélection de Joueurs (PSN)

Le PSN est un réseau de neurones dont la tâche est de déduire un masque $M^i$ pour équilibrer la performance et la parcimonie. Deux variantes sont proposées :

PSN-Full : L'entrée est l'historique d'état complet de tous les agents $x_{0:K}$
PSN-Partial : L'entrée est l'observation partielle $\{h(x_k)\}_{k=0}^K$ (par exemple, informations de position uniquement)

Structure du réseau :

Utilise un encodeur GRU (dimension cachée 64) pour traiter la séquence de K étapes de chaque agent
Couches MLP : 256→128→32 (activation ReLU, dropout=0,3)
Couche de sortie Sigmoid produisant un masque continu $m_j^i \in [0,1]$

2. Jeu de Nash Masqué

Définissez le masque de sélection de joueurs $M^i = (m_j^i) \in \{0,1\}^{N-1}$ , où :

undefined