Game-Theoretic Area Coverage Control with Cooperative-Adversarial Multi-Agent Systems

Sintesi Tecnica: Controllo della Copertura Areale Teoria-dei-Giochi con Sistemi Multi-Agente Cooperativi-Avversari

Formulazione del Problema
Questo lavoro affronta il problema del controllo della copertura areale per sistemi multi-agente reinterpretandolo come un gioco a somma zero a due giocatori tra due gruppi distinti di agenti: agenti "ordinari" e agenti "avversari". A differenza del controllo della copertura convenzionale, in cui la densità di rischio ambientale è un campo statico, predefinito e non influenzato dal comportamento degli agenti, questo framework postula che il campo di rischio sia generato dinamicamente dagli agenti avversari. Gli agenti ordinari mirano a massimizzare la copertura di rilevamento (minimizzare una metrica di copertura), mentre gli agenti avversari mirano a degradare tale copertura (massimizzare la stessa metrica).

Lo spazio di lavoro $\Omega$ è una regione bidimensionale convessa e limitata. Lo stato collettivo degli agenti ordinari è indicato da $P(t)$ e quello degli avversari da $S(t)$. La dinamica del sistema segue modelli a integratore singolo. La metrica di copertura $H(P, S, V)$ funge da payoff del gioco, definita come l'integrale della funzione di prestazione di rilevamento (distanza quadratica) degli agenti ordinari, pesata dalla densità di rischio collettiva generata dagli avversari. Il problema è formulato come un'ottimizzazione maximin:
$$\max_{S \in \Omega} \min_{P \in \Omega} H(P, S, V)$$
soggetto alle dinamiche degli agenti.

Metodologia
Gli autori propongono un design di controllo basato su algoritmi di Gradient Descent-Ascent (GDA).

1. Agenti Ordinari: Utilizzano una strategia di gradient descent (algoritmo di Lloyd) per minimizzare la metrica di copertura. La loro legge di controllo guida ogni agente verso il baricentro della propria cella di Voronoi, pesata dalla densità di rischio.
2. Agenti Avversari: Utilizzano una strategia di gradient ascent per massimizzare la metrica di copertura. La loro legge di controllo li guida verso posizioni che massimizzano la densità di rischio pesata rispetto alla prestazione di rilevamento degli agenti ordinari.

L'accoppiamento tra i due gruppi deriva dal fatto che la partizione di Voronoi (che determina i baricentri degli agenti ordinari) dipende dalla densità di rischio, la quale a sua volta dipende dalle posizioni degli avversari. Viceversa, l'input di controllo avversario dipende dalla densità di rischio pesata, che è influenzata dalle posizioni degli agenti ordinari.

Contributi Principali
Il documento presenta tre contributi primari:

1. Riformulazione Teoria-dei-Giochi: Il problema della copertura areale viene riformulato come un gioco di Nash a somma zero in cui la densità di rischio non è statica, ma è un output adattivo delle strategie degli agenti avversari. Ciò cattura scenari realistici di sorveglianza e difesa in cui gli avversari evadono attivamente il rilevamento.
2. Dinamiche Accoppiate e Analisi delle Biforcazioni: Gli autori derivano controller accoppiati gradient-descent-ascent e analizzano la stabilità del sistema. Attraverso una riduzione a bassa dimensionalità (un agente ordinario e un avversario su un dominio 1D), dimostrano che il sistema subisce una biforcazione di Hopf. Il comportamento del sistema è dettato dal rapporto tra i guadagni di controllo $\gamma = k_p / k_s$ (dove $k_p$ è il guadagno dell'agente ordinario e $k_s$ il guadagno dell'avversario).
   • Quando $\gamma$ è piccolo (dominanza avversaria), il sistema esibisce dinamiche periodiche di inseguimento-evasione (cicli limite).
   • Quando $\gamma$ è grande (dominanza dell'agente ordinario), il sistema converge verso una configurazione spaziale fissa.
3. Caratterizzazione dell'Equilibrio di Nash: Il documento stabilisce le condizioni per l'esistenza di un equilibrio di Nash. Si dimostra che, sotto specifiche condizioni (relative alla diffusione della densità Gaussiana rispetto alla dimensione dello spazio di lavoro), la configurazione fissa corrisponde a un equilibrio di Nash locale dove gli agenti ordinari formano una tassellazione di Voronoi centroidale e gli agenti avversari si assestano sui rispettivi baricentri di equilibrio.

Risultati

• Stabilità e Convergenza: Utilizzando l'analisi di Lyapunov, gli autori dimostrano che se il rapporto dei guadagni di controllo $\gamma$ supera una soglia critica $\gamma_c$, le traiettorie del sistema convergono verso l'insieme invariante più grande dove gli agenti si allineano con i rispettivi baricentri ($p_i = c^p_i$ e $s_j = c^s_j$).
• Biforcazione: Nel caso a bassa dimensionalità, l'analisi conferma che, al diminuire di $\gamma$ al di sotto di un valore critico (specificamente quando $\mu_4 > \mu_2$, relativo ai momenti della densità Gaussiana), il punto fisso perde stabilità tramite una biforcazione di Hopf, dando origine a un ciclo limite.
• Condizioni di Equilibrio di Nash: L'esistenza di un equilibrio di Nash locale nel punto fisso richiede che l'Hessiana della funzione di payoff soddisfi specifiche condizioni di definitezza ($H_{pp} \succeq 0$ e $H_{ss} \preceq 0$). Gli autori mostrano che ciò dipende dal parametro adimensionale $\epsilon = (b-a)/(2\sigma)$, che rappresenta il rapporto tra la metà della lunghezza dello spazio di lavoro e la deviazione standard della densità di rischio. Una diffusione sufficientemente ampia ($\epsilon < \epsilon_c \approx 1.37$) assicura che le condizioni di equilibrio siano soddisfatte.
• Simulazioni: Simulazioni numeriche del sistema ad alta dimensionalità (3 agenti contro 3 avversari) validano i risultati teorici.
  • Con $\gamma=1$ (dominanza avversaria), le traiettorie esibiscono oscillazioni periodiche sostenute.
  • Con $\gamma=3$ (dominanza ordinaria), il sistema converge a una configurazione fissa.
  • Simulazioni variando la covarianza $\sigma$ dimostrano che, sebbene il sistema possa convergere a un punto fisso, esso costituisce un equilibrio di Nash solo se la diffusione della densità di rischio è sufficientemente ampia rispetto allo spazio di lavoro.

Significatività e Rivendicazioni
Il documento sostiene di fornire un nuovo framework per comprendere la copertura areale in ambienti competitivi dove il "rischio" non è una caratteristica ambientale statica, ma una variabile dinamica controllata da un avversario. La significatività risiede in:

• Generalizzazione: Superamento dei campi di rischio statici verso campi di rischio adattivi generati dagli agenti.
• Intuizione Dinamica: Identificare che le capacità fisiche relative (autorità di attuazione, tassi di rilevamento) dei due gruppi, racchiuse nel rapporto di guadagno $\gamma$, alterano fondamentalmente il comportamento qualitativo del sistema da una copertura stabile a un'evasione periodica.
• Caratterizzazione dell'Equilibrio: Fornire condizioni sufficienti affinché la configurazione stabile risultante sia un vero equilibrio di Nash, distinguendo tra la mera convergenza delle dinamiche e l'ottimalità della teoria dei giochi.

Gli autori osservano che, sebbene l'analisi a bassa dimensionalità fornisca un equilibrio di Nash globale, il caso ad alta dimensionalità produce generalmente al massimo un equilibrio di Nash locale a causa della natura non convessa della metrica di copertura in contesti generali. Si suggerisce come lavoro futuro l'estensione di questo framework a scenari con informazioni incomplete o incerte.