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: Predizione e Pianificazione Game-Teorica tramite una Rete di Selezione dei Giocatori

Informazioni Fondamentali

  • ID Articolo: 2505.00213
  • Titolo: PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
  • Autori: Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (University of Texas at Austin)
  • Classificazione: cs.RO (Robotica), math.OC (Ottimizzazione e Controllo)
  • Data di Pubblicazione: 2025 (preprint arXiv)
  • Link dell'Articolo: https://arxiv.org/abs/2505.00213

Riassunto

Sebbene i framework di pianificazione game-teorica siano efficaci nella modellazione delle interazioni multi-agente, richiedono la risoluzione di problemi di ottimizzazione di grandi dimensioni, con il numero di variabili che aumenta con il numero di agenti, causando tempi di calcolo eccessivi e limitando l'applicazione in sistemi real-time su larga scala. Per affrontare questo problema, il presente articolo propone: 1) PSN Game - un framework di predizione e pianificazione game-teorica basato su apprendimento, che riduce il tempo di esecuzione attraverso l'apprendimento di una rete di selezione dei giocatori (PSN); 2) una rete di inferenza degli obiettivi (GIN), che consente a PSN di essere utilizzata in giochi a informazione incompleta dove gli intenti degli agenti sono sconosciuti. PSN produce una maschera di selezione dei giocatori che distingue i giocatori influenti da quelli meno rilevanti, permettendo all'agente autonomo di risolvere giochi mascherati di dimensioni ridotte che coinvolgono solo i giocatori selezionati. Riducendo il numero di giocatori nel gioco e, di conseguenza, il numero di variabili nel corrispondente problema di ottimizzazione, PSN riduce direttamente il tempo di calcolo.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il problema fondamentale affrontato dai framework di pianificazione game-teorica nei sistemi multi-agente è la crescita cubica della complessità computazionale con il numero di agenti. Come mostrato nella Figura 2, utilizzando risolutori esistenti, il tempo di calcolo cresce secondo O(N³), dove N è il numero di giocatori. Ciò rende i metodi game-teorici impraticabili nei sistemi real-time su larga scala.

Importanza della Ricerca

  1. Requisiti di Real-Time: Applicazioni come la guida autonoma e la navigazione robotica richiedono una repianificazione frequente, rendendo l'efficienza computazionale cruciale
  2. Sfida di Scalabilità: Negli scenari reali, il numero di agenti è spesso molto elevato (ad esempio, in ambienti di traffico denso)
  3. Ispirazione dal Comportamento Umano: La ricerca dimostra che i conducenti umani in traffico denso danno istintivamente priorità ai veicoli minacciosi nelle vicinanze, piuttosto che monitorare tutti i veicoli

Limitazioni dei Metodi Esistenti

I metodi attuali di selezione dei giocatori presentano i seguenti problemi:

  1. Forte Dipendenza dall'Informazione: Richiedono informazioni specifiche del gioco come ingressi di controllo, funzioni di costo, ecc.
  2. Complessa Sintonizzazione dei Parametri: Richiede regolazioni dei parametri specifiche dell'ambiente
  3. Strategie di Selezione Fisse: I metodi di ordinamento basati su euristiche semplici (come distanza, gradiente) mancano di adattabilità

Contributi Principali

  1. Propone una Rete di Selezione dei Giocatori Non Supervisionata (PSN): Addestrata utilizzando un risolutore di giochi dinamici differenziabili, supporta la retropropagazione attraverso maschere di selezione
  2. Costruisce una Rete di Inferenza degli Obiettivi Supervisionata (GIN): Inferisce gli obiettivi degli agenti dalle traiettorie storiche, rendendo PSN applicabile a scenari con intenti sconosciuti
  3. Sviluppa un Framework di Orizzonte Temporale Decrescente: Utilizza PSN per identificare efficientemente strategie di equilibrio risolvendo giochi di dimensioni ridotte
  4. Verifica Sperimentale: Convalidata su simulazioni multi-agente e dataset di traiettorie umane reali, PSN Game riduce efficacemente la dimensione del gioco del 50%-75%, realizzando un'accelerazione significativa

Dettagli del Metodo

Definizione del Compito

Si consideri un gioco di Nash in forma aperta a orizzonte finito e tempo discreto con N agenti, dove ogni agente i possiede uno stato xki∈Rnx_k^i \in \mathbb{R}^n e un ingresso di controllo uki∈Rmu_k^i \in \mathbb{R}^m. La transizione di stato di ogni agente segue l'equazione dinamica: xk+1i=fi(xki,uki)x_{k+1}^i = f^i(x_k^i, u_k^i)

L'obiettivo di ogni agente è minimizzare il costo cumulativo: Ji(x,u;θi)=∑k=0Tcki(xk,uk;θi)J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)

Architettura del Modello

1. Rete di Selezione dei Giocatori (PSN)

PSN è una rete neurale il cui compito è inferire una maschera MiM^i per bilanciare le prestazioni con la sparsità. Vengono fornite due varianti:

  • PSN-Full: L'ingresso è lo stato storico completo di tutti gli agenti x0:Kx_{0:K}
  • PSN-Partial: L'ingresso è l'osservazione parziale {h(xk)}k=0K\{h(x_k)\}_{k=0}^K (ad esempio, solo informazioni di posizione)

Struttura della Rete:

  • Utilizza un codificatore GRU (dimensione nascosta 64) per elaborare la sequenza di K passi di ogni agente
  • Strati MLP: 256→128→32 (attivazione ReLU, dropout=0.3)
  • Strato di uscita Sigmoid che produce maschere continue mji∈[0,1]m_j^i \in [0,1]

2. Gioco di Nash Mascherato

Si definisce la maschera di selezione dei giocatori Mi=(mji)∈{0,1}N−1M^i = (m_j^i) \in \{0,1\}^{N-1}, dove:

1, & \text{l'agente j è incluso nel gioco} \\ 0, & \text{l'agente j è escluso} \end{cases}$$ Il gioco mascherato $\Gamma^i(\tilde{x}_0, \tilde{f}; \theta, M^i)$ mantiene solo i parametri e gli stati degli agenti più rilevanti per l'agente i. #### 3. Rete di Inferenza degli Obiettivi (GIN) GIN è una rete guidata dai dati che inferisce gli obiettivi degli agenti $p_g^i$ dalle osservazioni di traiettorie parziali: - Ingresso: Traiettoria storica $\{h(x_k)\}_{k=0}^K$ - Uscita: Posizione obiettivo 2D $p_g^i$ - Funzione di perdita: Errore quadratico medio $L_{Goal} = \frac{1}{|D| \cdot N}\sum_{d \in D}\sum_{i \in [N]} \|p_{g,ref}^i - G_\phi(x_{0:K})\|$ ### Progettazione della Funzione di Perdita L'addestramento di PSN utilizza una funzione di perdita composita: **Compito di Predizione**: $$L_{Pred} = L_{Binary} + \sigma_1 L_{Sparsity} + \sigma_2 L_{Similarity}$$ **Compito di Pianificazione**: $$L_{Plan} = L_{Binary} + \sigma_3 L_{Sparsity} + \sigma_4 L_{Cost}$$ Dove: - $L_{Binary} = \frac{1}{N}\sum_{j=1}^N m_j^i(1-m_j^i)$: Promuove la binarizzazione delle maschere - $L_{Sparsity} = \frac{\|M^i\|_1}{N}$: Incoraggia la selezione di meno agenti - $L_{Similarity}$: Incoraggia la selezione di sottoinsiemi di agenti che recuperano le traiettorie osservate - $L_{Cost}$: Incoraggia la selezione di agenti appropriati per minimizzare il costo del gioco ### Implementazione dell'Orizzonte Temporale Decrescente L'algoritmo ad ogni passo temporale $k$: 1. Inferisce gli obiettivi degli agenti tramite GIN 2. Ottiene la maschera adattiva $M_k^i$ utilizzando PSN 3. Risolve il gioco mascherato per ottenere la strategia OLNE 4. Esegue il primo ingresso di controllo e aggiorna lo stato ## Configurazione Sperimentale ### Dataset **Scenari di Simulazione**: - Scenario a 4 agenti: ambiente 5m×5m - Scenario a 10 agenti: ambiente 7m×7m - Scenario a 20 agenti: ambiente 7m×7m (test di scalabilità) **Dati Reali**: - Dataset di Pedoni CITR: ambiente 7.5m×25.5m, 10 pedoni **Configurazione del Gioco**: - Spazio di stato: 4 dimensioni (posizione + velocità) - Dinamica: Modello di doppio integratore - Funzione di costo: Include tracciamento dell'obiettivo, penalità di velocità, costo di controllo e evitamento delle collisioni ### Metriche di Valutazione **Compito di Predizione**: - ADE (Average Displacement Error): Errore di spostamento medio - FDE (Final Displacement Error): Errore di spostamento finale - Consistency: Coerenza della selezione **Compito di Pianificazione**: - Navigation Cost: Costo di navigazione - Collision Cost: Costo di collisione - Control Cost: Costo di controllo - Minimum Distance: Distanza minima - Trajectory Smoothness: Levigatezza della traiettoria - Trajectory Length: Lunghezza della traiettoria ### Metodi di Confronto 1. **Varianti PSN**: PSN-Threshold, PSN-Rank 2. **Metodi Basati su Distanza**: Distance, kNNs 3. **Metodi Basati su Gradiente**: Gradient, Hessian, Cost Evolution 4. **Metodi Vincolati**: BF (Barrier Function), CBF (Control Barrier Function) ## Risultati Sperimentali ### Risultati Principali #### Prestazioni di Predizione (Tabella 2) Nello scenario a 4 agenti: - PSN-Full ADE: 0.1834m (ottimale) - PSN-Partial ADE: 0.1876m - Migliore baseline (Cost Evolution) ADE: 0.1861m Nello scenario a 10 agenti: - PSN-Partial ADE: 0.2213m (ottimale) - PSN-Full ADE: 0.2314m - Migliore baseline (kNNs) ADE: 0.2343m #### Prestazioni di Pianificazione (Tabella 3) PSN mostra prestazioni eccellenti negli indicatori di sicurezza: - **Costo di Collisione**: Raggiunge l'optimum negli scenari a 4 e 10 agenti - **Distanza Minima**: Tra i primi tre in entrambi gli scenari - Degradazione minore della sicurezza rispetto al gioco completo ### Adattabilità ai Giochi a Informazione Incompleta In scenari con obiettivi sconosciuti (Tabelle 4-5), PSN combinato con GIN: - Mantiene gli indicatori di predizione tra i primi due - Tutti gli indicatori di pianificazione sono tra i primi tre - Gli indicatori di sicurezza rimangono ottimali ### Verifica della Scalabilità Utilizzando PSN addestrato su 10 agenti nello scenario a 20 agenti: - PSN-Full ADE: 0.3108m (ottimale) - PSN-Partial ADE: 0.3152m (secondo) - Adatta a scenari di scala maggiore senza necessità di riaddestrare ### Generalizzazione su Dati Reali Nel dataset di pedoni CITR: - PSN-Partial ADE: 0.4931m (ottimale) - PSN-Full ADE: 0.4966m - Supera persino le prestazioni della risoluzione del gioco completo ## Lavori Correlati ### Pianificazione Game-Teorica I metodi esistenti si concentrano principalmente su ambienti di piccola scala (≤5 agenti), utilizzando risolutori di tipo Newton per risolvere iterativamente. La complessità cresce cubicamente con il numero di giocatori, rappresentando un ostacolo fondamentale per i sistemi real-time su larga scala. ### Metodi di Selezione dei Giocatori **Metodi Basati su Soglia**: Selezionano agenti basandosi su soglie di distanza predefinite, richiedendo una vasta sintonizzazione dei parametri. **Metodi Basati su Ordinamento**: Selezionano i top-k agenti più influenti, ma la selezione di un numero fisso potrebbe essere eccessivamente aggressiva o conservativa. **Vantaggi del Presente Lavoro**: 1. Richiede solo osservazioni di traiettorie storiche, senza informazioni privilegiate 2. Non richiede sintonizzazione dei parametri online 3. Selezione adattiva del numero di agenti ## Conclusioni e Discussione ### Conclusioni Principali 1. PSN Game riduce con successo la dimensione del gioco del 50%-75%, realizzando un'accelerazione computazionale significativa 2. Supera i metodi baseline esistenti in termini di accuratezza di predizione e sicurezza di pianificazione 3. Possiede buone capacità di generalizzazione, adattandosi a scenari di scala maggiore e dati reali ### Limitazioni 1. **Approssimazione di Maschera Continua**: Utilizza maschere continue per supportare la retropropagazione, richiedendo la soglia di conversione durante l'esecuzione 2. **Dipendenza dai Dati di Addestramento**: Richiede dati di addestramento generati da giochi completi 3. **Assunzioni di Modello Dinamico**: Gli esperimenti si basano principalmente sul modello di doppio integratore ### Direzioni Future 1. Estensione a modelli dinamici più complessi 2. Ricerca su altri tipi di inferenza dei parametri del gioco 3. Esplorazione di strategie di addestramento end-to-end ## Valutazione Approfondita ### Punti di Forza 1. **Importanza del Problema**: Affronta il collo di bottiglia computazionale fondamentale nella pianificazione game-teorica 2. **Innovazione del Metodo**: Prima combinazione di apprendimento profondo e teoria dei giochi per la selezione dei giocatori 3. **Completezza Sperimentale**: Copre simulazioni e dati reali, verificando molteplici ipotesi 4. **Valore Pratico**: Fornisce un meccanismo generico direttamente integrabile nei framework esistenti ### Carenze 1. **Mancanza di Analisi Teorica**: Non fornisce garanzie teoriche sulla convergenza o errore di approssimazione 2. **Sovraccarico Computazionale**: Sebbene riduca il tempo di risoluzione del gioco, aggiunge il sovraccarico dell'inferenza di rete 3. **Limitazioni dello Scenario**: Principalmente verificato su compiti di navigazione, l'applicabilità ad altri tipi di giochi è sconosciuta ### Impatto 1. **Contributo Accademico**: Fornisce un nuovo approccio per sistemi multi-agente su larga scala 2. **Applicazione Pratica**: Ha valore di applicazione diretta in campi come la guida autonoma e i gruppi di robot 3. **Riproducibilità**: Fornisce dettagli di implementazione e impostazioni di parametri dettagliati ### Scenari Applicabili 1. **Ambienti Multi-Agente Densi**: Come traffico urbano e navigazione di folle 2. **Sistemi con Elevati Requisiti di Real-Time**: Ambienti dinamici che richiedono repianificazione frequente 3. **Scenari Parzialmente Osservabili**: Giochi a informazione incompleta dove gli intenti degli agenti sono sconosciuti ## Bibliografia L'articolo cita 35 riferimenti correlati, coprendo principalmente: - Metodi di pianificazione game-teorica [8, 28, 9, 15] - Modellazione di interazioni multi-agente [17, 20, 21, 24] - Metodi euristici di selezione dei giocatori [2, 27, 30] - Meccanismi di attenzione e selezione dei vicini [3, 6, 32] --- Questo articolo fornisce un contributo importante nel risolvere la complessità computazionale della pianificazione game-teorica, migliorando significativamente l'efficienza computazionale dei sistemi multi-agente attraverso la selezione dei giocatori guidata dall'apprendimento, aprendo la strada alle applicazioni real-time su larga scala.