A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Riepilogo Tecnico: Un Gioco di Evasione dalla Sorveglianza con Ricollocazione Continua dei Sensori tramite Ottimizzazione Bilevel

Formulazione del Problema
Il documento affronta la sfida critica di sicurezza relativa allo sfruttamento, da parte dei Sistemi Aerei Senza Equipaggio (UAS), delle lacune spazio-temporali nei perimetri dei sensori per infiltrarsi in spazi aerei ristretti senza essere rilevati. Gli autori modellano questa interazione come un gioco differenziale a somma zero a due giocatori tra un UAS avversario (attaccante) e una rete eterogenea di sensori (difensore) composta sia da sensori direzionali che omnidirezionali.

A differenza degli approcci precedenti che spesso limitano i difensori a grafi di posizionamento discreti, configurazioni fisse o assumono una copertura omnidirezionale statica, questo lavoro formula il problema su spazi di strategia continui. L'attaccante cerca una traiettoria spazio-temporale priva di collisioni da un punto di partenza a un punto di destinazione che minimizzi la probabilità cumulativa di rilevamento. Al contrario, il difensore mira a massimizzare tale probabilità ottimizzando il posizionamento spaziale dei sensori. Una complessità chiave deriva dall'uso da parte del difensore di sensori direzionali rotanti, che creano regioni di copertura variabili nel tempo e non convesse e lacune prevedibili che un avversario intelligente può sfruttare. Gli autori notano che trovare un punto di sella globale è intrattabile a causa della natura ad alta dimensionalità e non convessa degli spazi di strategia congiunti e delle discontinuità introdotte dai campi di vista (FOV) rotanti dei sensori. Di conseguenza, l'obiettivo è calcolare un Equilibrio di Nash Locale (LNE), uno stato in cui nessun giocatore può migliorare il proprio guadagno attraverso deviazioni unilaterali infinitesimali.

Metodologia
La soluzione proposta impiega un framework di ottimizzazione bilevel iterativo che alterna la risoluzione dei sottoproblemi di miglior risposta dell'attaccante e del difensore fino al raggiungimento di un LNE.

1. Miglior Risposta dell'Attaccante:
   Dato un posizionamento fisso dei sensori, l'attaccante risolve un problema di programmazione non lineare (NLP) per minimizzare la probabilità di rilevamento. Per gestire il paesaggio di rilevamento non convesso, gli autori utilizzano un approccio in due fasi:

   • Inizializzazione: L'algoritmo Space-Time Probabilistic Rapidly-exploring Random Tree (STP-RRT*) genera una traiettoria iniziale fattibile e priva di collisioni che naviga attorno alle regioni dinamiche di copertura dei sensori.
   • Raffinamento: Un solver NLP basato sul gradiente (IPOPT) affina questa traiettoria per minimizzare la probabilità cumulativa di rilevamento. Il modello di rilevamento utilizza una funzione sigmoide liscia per approssimare la visibilità, garantendo la differenziabilità per l'ottimizzazione basata sul gradiente.

2. Miglior Risposta del Difensore:
   Data la traiettoria ottimizzata dell'attaccante, il difensore risolve un problema di ricollocazione continua dei sensori per massimizzare la probabilità di rilevamento.

   • Ricollocazione Continua: A differenza dei metodi basati su grafi discreti, ai sensori è consentito scivolare liberamente lungo i confini degli edifici poligonali convessi.
   • Vincoli Lisci: Per abilitare l'ottimizzazione basata sul gradiente su questi confini, gli autori impongono vincoli di posizionamento utilizzando un'approssimazione liscia log-sum-exp della distanza segno dal bordo dell'edificio più vicino. Questa tecnica preserva la differenziabilità ai vertici dei poligoni, superando la non differenziabilità dei vincoli di confine rigidi.

3. Schema Iterativo:
   Il framework alterna la minimizzazione dell'attaccante e la massimizzazione del difensore. Il processo termina quando i residui del gradiente per entrambi i giocatori scendono al di sotto di una tolleranza prescritta, soddisfacendo le condizioni di stazionarietà del primo ordine per un LNE. Se l'algoritmo entra in un ciclo limite (oscillazione non decrescente), il difensore viene reinizializzato da un nuovo posizionamento casuale per recuperare la convergenza.

Contributi Chiave
Il documento apporta tre contributi principali:

• Formulazione del Gioco: Una formulazione di gioco differenziale a somma zero a due giocatori che modella regioni di rilevamento variabili nel tempo e non convesse di sensori direzionali rotanti su spazi di strategia continui.
• Ricollocazione Continua: Una nuova formulazione per il difensore che consente ai sensori di scivolare continuamente lungo i confini fisici degli edifici, imposta tramite un vincolo differenziabile log-sum-exp, abilitando l'ottimizzazione basata sul gradiente.
• Ottimizzazione Bilevel Iterativa: Un framework algoritmico che converge a un Equilibrio di Nash Locale ottimizzando alternativamente il posizionamento dei sensori e le traiettorie dell'attaccante, con condizioni analitiche di stazionarietà del primo ordine derivate per entrambi i giocatori.

Risultati e Validazione
Il framework è stato valutato attraverso simulazioni numeriche e una dimostrazione sperimentale fisica:

• Simulazione Monte Carlo: Una simulazione di 500 prove ha dimostrato che il framework proposto ottiene un miglioramento di 4 volte nella probabilità di rilevamento del difensore rispetto al posizionamento casuale dei sensori (la linea di base naturale). Il metodo ha raggiunto un tasso di convergenza del 96,8% verso un Equilibrio di Nash Locale. Nello stato convergente, la probabilità di rilevamento del difensore è aumentata significativamente (da una media di ~0,103 a ~0,419), mentre il tasso di successo dell'attaccante è diminuito.
• Comportamento di Convergenza: L'ottimizzazione alternata si è stabilizzata tipicamente in un plateau, con residui numerici che decadono fino a circa $10^{-6}$. Il comportamento di ciclo limite è stato osservato in solo 1 su 500 prove (2%), risolto con successo tramite reinizializzazione.
• Dimostrazione Sperimentale: Il framework è stato testato in un ambiente fisico in scala ridotta che simulava uno scenario di difesa aeroportuale con un canyon urbano. Utilizzando un Crazyflie 2.1 come attaccante e telecamere PTZ come difensori, gli esperimenti hanno validato che l'ottimizzazione bilevel produce miglioramenti coerenti della strategia. La strategia LNE ($a^*, d^*$) ha risultanto in un costo di rilevamento ($J$) di 0,9451, significativamente più alto del posizionamento euristico iniziale ($J=0,6847$) e superiore a scenari in cui solo un giocatore ottimizzava la propria strategia.

Significato e Affermazioni
Gli autori collocano questo lavoro come una linea di base deployabile per i posizionamenti di sensori eterogenei nelle missioni di Contrasto agli UAS (CUAS). Affermano che il significato risiede nel colmare tre lacune nella letteratura esistente: la mancanza di ricollocazione continua dei sensori lungo i confini degli edifici, l'assenza di modellazione probabilistica del FOV direzionale nei contesti di teoria dei giochi e il passaggio dagli spazi di strategia discreti all'ottimizzazione bilevel basata sul gradiente.

Il documento presenta modestamente il proprio contributo come l'instaurazione di un primo passo necessario isolando il contributo della topologia di dispiegamento, riconoscendo che il problema più complesso di accoppiamento tra calendario e posizionamento rimane per lavori futuri. I risultati confermano che l'ottimizzazione del posizionamento dei sensori in uno spazio continuo, tenendo conto della natura dinamica dei sensori direzionali, migliora significativamente la sicurezza del perimetro contro avversari intelligenti rispetto alle linee di base statiche o casuali.