Dynamic Adversarial Resource Allocation: the dDAB Game

1. Introduzione e Definizione del Problema

Il lavoro introduce il gioco dDAB (Dynamic Defender-Attacker Blotto), un'estensione dinamica del classico gioco statico "Colonel Blotto" applicata alla allocazione di risorse su grafi.

• Contesto: Il problema riguarda l'allocazione di risorse (robot, sensori) in un ambiente dinamico rappresentato da un grafo diretto $G=(V, E)$, dove i nodi sono posizioni fisiche e gli archi definiscono la percorribilità.
• Attori:
  • Difensore (Blu): Deve mantenere la superiorità numerica rispetto all'attaccante su un insieme di nodi chiave ($V_{key}$).
  • Attaccante (Rosso): Cerca di infiltrarsi nei nodi chiave allocando più risorse del difensore.
• Dinamica: Il gioco è discreto nel tempo. Le risorse possono muoversi al massimo di un "hop" (un arco) per passo temporale. A differenza dei modelli statici, le risorse devono viaggiare fisicamente attraverso il grafo.
• Condizione di Vittoria: L'attaccante vince se, in qualsiasi momento $t$, esiste un nodo chiave $i$ tale che $[y_t]_i > [x_t]_i$ (risorse attaccanti > risorse difensori). Il difensore vince se previene questa condizione per un orizzonte temporale $T$ (o indefinitamente).
• Struttura Informativa: Il gioco è sequenziale a turni. Il difensore agisce per primo, l'attaccante osserva la nuova allocazione del difensore e reagisce, poi viene valutato l'esito.

2. Metodologia e Approccio Teorico

Il cuore della metodologia risiede nell'analisi di insiemi raggiungibili e nella costruzione di insiemi sicuri (Safe Sets) tramite programmazione dinamica insiemistica.

A. Insiemi Raggiungibili e Politopi

Gli autori definiscono l'insieme raggiungibile $R(x_t)$ come l'insieme di tutti gli stati che il difensore può raggiungere al passo successivo partendo da $x_t$, dato il vincolo di movimento sul grafo.

• Viene dimostrato che $R(x_t)$ è un politopo (inviluppo convesso di azioni estreme).
• Viene introdotto l'insieme Richiesto ($P_{req}$): l'insieme di allocazioni del difensore necessarie per garantire la difesa al passo successivo, indipendentemente da come l'attaccante si muova dal suo stato corrente.

B. Insiemi Sicuri k-passi (Q-Set)

Per gestire la natura sequenziale e avversaria del gioco, viene definito l'insieme sicuro k-passi $Q^{(i)}_k$.

• Un stato $x_t$ appartiene a $Q^{(i)}_k$ se esiste una strategia del difensore che garantisce la difesa per $k$ passi contro un attaccante che inizia concentrato sul nodo $i$ e non divide le sue risorse (strategia "no-splitting").
• Ricorsione: L'insieme è definito ricorsivamente:
  $$Q^{(i)}_k = \{ x \mid x \in P_{req}(y^{(i)}) \land \forall j \in N_i, R(x) \cap Q^{(j)}_{k-1} \neq \emptyset \}$$
  Questo garantisce che, dopo il movimento dell'attaccante verso un vicino $j$, il difensore possa ancora raggiungere un insieme sicuro per i passi rimanenti.

C. Generalizzazione alla Divisione delle Risorse (Splitting)

Un risultato fondamentale è la dimostrazione che l'attaccante non ha incentivo a dividere le proprie risorse.

• Teorema: Se il difensore ha risorse sufficienti per difendersi contro qualsiasi strategia "no-splitting" (risorse concentrate), allora può difendersi contro qualsiasi strategia, incluse quelle in cui l'attaccante divide le risorse in sottogruppi.
• Strategia di Sottosquadra: Il difensore può trattare ogni sottogruppo di risorse dell'attaccante come un'entità indipendente e applicare la strategia calcolata per il caso "no-splitting", sommando le risposte tramite il principio di sovrapposizione.

D. Algoritmo di Calcolo

Viene sviluppato un algoritmo basato su Programmazione Dinamica su Insiemi (Algorithm 1: Q-Prop) per calcolare iterativamente i Q-set fino alla convergenza (per la difesa indefinita) o fino all'orizzonte temporale $T$.

• L'algoritmo utilizza la proprietà che l'insieme raggiungibile inverso è equivalente all'insieme raggiungibile su un grafo invertito, permettendo un calcolo efficiente dei politopi.
• Viene anche presentato un metodo per estrarre azioni concrete (matrici di transizione) dai Q-set risolvendo un programma lineare.

3. Risultati Chiave

1. Rapporto Critico delle Risorse (CRR - Critical Resource Ratio):

   • Viene definito $\alpha_T$ come il minimo rapporto moltiplicativo tra le risorse del difensore ($X$) e quelle dell'attaccante ($Y$) necessario per garantire la vittoria.
   • $\alpha_T = \max_i \min_{x \in Q^{(i)}_T} \mathbf{1}^\top x / Y$.
   • Il paper dimostra che il CRR per un attaccante generico (che può dividere) è identico a quello per un attaccante "no-splitting".

2. Strategie di Feedback:

   • Vengono sintetizzate strategie di feedback ottimali per il difensore. Il difensore non segue una traiettoria predefinita, ma reagisce allo stato corrente dell'attaccante, mantenendo le proprie risorse all'interno del Q-set appropriato.
   • Se $X \ge \alpha_\infty Y$, il difensore può garantire una difesa indefinita.

3. Proprietà del CRR:

   • Il CRR non è necessariamente un numero intero (es. 3.5 risorse possono essere sufficienti in certi scenari a orizzonte finito).
   • Il CRR dipende fortemente dalla topologia del grafo. L'aggiunta di archi può paradossalmente aumentare o diminuire il CRR a seconda della struttura (es. anelli diretti vs grafi fortemente connessi).

4. Convergenza:

   • Per grafi fortemente connessi e non diretti, l'algoritmo di propagazione dei Q-set converge tipicamente entro $N$ iterazioni (dove $N$ è il numero di nodi).

4. Validazione Sperimentale

L'efficacia dell'approccio è stata verificata attraverso:

• Simulazioni Numeriche: Analisi di grafi a 3, 5 e 6 nodi, dimostrando la convergenza degli insiemi sicuri e il calcolo del CRR (inclusi casi con valori non interi).
• Esperimenti Hardware (Robotarium):
  • Implementazione su una piattaforma robotica multi-agente reale.
  • Scenario 1: Difesa di un'area esterna con 7 nodi. Dimostrato che 8 robot difensori possono respingere indefinitamente 2 attaccanti, mentre la rimozione di un robot porta a una violazione calcolata.
  • Scenario 2: Sorveglianza interna in un edificio a 9 stanze. 4 robot difensori mantengono la sorveglianza continua contro un singolo attaccante, posizionandosi sempre nella stanza dell'attaccante o nelle stanze adiacenti.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella teoria dei giochi dinamici e nel controllo multi-agente:

• Transizione da Statico a Dinamico: Colma il divario tra i giochi Blotto classici (allocazione istantanea) e le applicazioni reali dove il movimento delle risorse richiede tempo e vincoli di connettività.
• Garanzie di Sicurezza: Fornisce condizioni necessarie e sufficienti per la sicurezza in sistemi critici (es. reti elettriche resilienti, sorveglianza di incendi, difesa perimetrale), offrendo garanzie matematiche contro avversari intelligenti.
• Robustezza: Dimostra che la strategia di difesa basata su Q-set è robusta anche contro strategie di attacco complesse (divisione delle risorse), semplificando notevolmente la progettazione del sistema difensivo.
• Applicabilità Pratica: La validazione su robot reali conferma che la teoria, basata su risorse continue, può essere adattata efficacemente a sistemi discreti (robot indivisibili) tramite strategie di allocazione discreta.

In sintesi, il paper offre un quadro teorico completo e algoritmi pratici per progettare sistemi difensivi autonomi capaci di garantire la sicurezza di una rete contro attacchi dinamici e adattivi.