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: Predicción y Planificación Teórica de Juegos mediante una Red de Selección de Jugadores

Información Básica

ID del Artículo: 2505.00213
Título: PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
Autores: Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (Universidad de Texas en Austin)
Clasificación: cs.RO (Robótica), math.OC (Optimización y Control)
Fecha de Publicación: 2025 (preimpresión en arXiv)
Enlace del Artículo: https://arxiv.org/abs/2505.00213

Resumen

Aunque los marcos de planificación teórica de juegos son efectivos en la modelación de interacciones multiagente, requieren resolver problemas de optimización de gran escala cuyas variables aumentan con el número de agentes, lo que resulta en tiempos de cálculo excesivos que limitan su aplicación en sistemas en tiempo real a gran escala. Para abordar este problema, el presente artículo propone: 1) PSN Game - un marco de predicción y planificación teórica de juegos basado en aprendizaje que reduce el tiempo de ejecución mediante el aprendizaje de una red de selección de jugadores (PSN); 2) una red de inferencia de objetivos (GIN) que permite que PSN se utilice en juegos de información incompleta donde las intenciones de los agentes son desconocidas. PSN genera una máscara de selección de jugadores que distingue entre jugadores influyentes y jugadores menos relevantes, permitiendo que el agente autónomo resuelva un juego enmascarado de menor escala que involucra solo a los jugadores seleccionados. Al reducir el número de jugadores en el juego y, por consiguiente, el número de variables en el problema de optimización correspondiente, PSN reduce directamente el tiempo de cálculo.

Antecedentes de Investigación y Motivación

Definición del Problema

El problema central que enfrentan los marcos de planificación teórica de juegos en sistemas multiagente es que la complejidad computacional crece cúbicamente con el número de agentes. Como se muestra en la Figura 2, al utilizar solucionadores existentes, el tiempo de cálculo crece según O(N³), donde N es el número de jugadores. Esto hace que los métodos teóricos de juegos sean impracticables en sistemas en tiempo real a gran escala.

Importancia de la Investigación

Requisitos de Tiempo Real: Aplicaciones como conducción autónoma y navegación robótica requieren replanificación frecuente, siendo la eficiencia computacional crítica
Desafíos de Escalabilidad: En escenarios reales, el número de agentes suele ser muy grande (como en entornos de tráfico denso)
Inspiración en Comportamiento Humano: La investigación demuestra que los conductores humanos en tráfico denso instintivamente priorizan los vehículos amenazantes cercanos en lugar de monitorear todos los vehículos

Limitaciones de Métodos Existentes

Los métodos actuales de selección de jugadores presentan los siguientes problemas:

Fuerte Dependencia de Información: Requieren información específica del juego como controles de entrada, funciones de costo, etc.
Ajuste de Parámetros Complejo: Necesitan ajustes de parámetros específicos del entorno
Estrategias de Selección Rígidas: Los métodos de clasificación basados en heurísticas simples (como distancia, gradiente) carecen de adaptabilidad

Contribuciones Principales

Propuesta de Red de Selección de Jugadores No Supervisada (PSN): Entrenada mediante un solucionador de juegos dinámicos diferenciable, que soporta retropropagación a través de máscaras de selección
Construcción de Red de Inferencia de Objetivos Supervisada (GIN): Infiere objetivos de agentes a partir de trayectorias históricas, permitiendo que PSN se aplique en escenarios con intenciones desconocidas
Desarrollo de Marco de Horizonte Temporal Decreciente: Utiliza PSN para identificar eficientemente estrategias de equilibrio resolviendo juegos de escala reducida
Validación Experimental: Verificada en simulaciones multiagente y conjuntos de datos de trayectorias humanas reales, PSN Game reduce efectivamente la escala del juego en 50%-75%, logrando aceleración significativa

Explicación Detallada del Método

Definición de la Tarea

Se considera un juego de Nash de horizonte temporal finito en tiempo discreto de bucle abierto con N agentes, donde cada agente i posee estado $x_k^i \in \mathbb{R}^n$ e entrada de control $u_k^i \in \mathbb{R}^m$ . La transición de estado de cada agente sigue la ecuación de dinámica: $x_{k+1}^i = f^i(x_k^i, u_k^i)$

El objetivo de cada agente es minimizar el costo acumulado: $J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)$

Arquitectura del Modelo

1. Red de Selección de Jugadores (PSN)

PSN es una red neuronal cuya tarea es inferir la máscara $M^i$ para equilibrar rendimiento y escasez. Se proporcionan dos variantes:

PSN-Completa: La entrada es el estado histórico completo de todos los agentes $x_{0:K}$
PSN-Parcial: La entrada es observación parcial $\{h(x_k)\}_{k=0}^K$ (como solo información de posición)

Estructura de la Red:

Utiliza codificador GRU (dimensión oculta 64) para procesar secuencias de K pasos de cada agente
Capas MLP: 256→128→32 (activación ReLU, dropout=0.3)
Capa de salida Sigmoid que produce máscaras continuas $m_j^i \in [0,1]$

2. Juego de Nash Enmascarado

Se define la máscara de selección de jugadores $M^i = (m_j^i) \in \{0,1\}^{N-1}$ , donde:

undefined