Forecast-Aware Cooperative Planning on Temporal Graphs under Stochastic Adversarial Risk

1. Il Problema

Il lavoro affronta la pianificazione cooperativa per missioni multi-robot in ambienti dinamici dove i costi di attraversamento non sono statici, ma evolvono nel tempo a causa della presenza di avversari stocastici (es. pattuglie nemiche o pericoli mobili).

• Contesto: In missioni come il soccorso o la protezione di convogli, i robot devono navigare su grafi dove le regioni a rischio cambiano dinamicamente.
• Sfida Principale: La coordinazione di supporto (dove un robot rallenta o si ferma per coprire un compagno che attraversa una zona pericolosa) è efficace solo se il team può anticipare quando e dove i rischi si manifesteranno.
• Limitazione degli approcci esistenti: I framework attuali (es. TCGRE) assumono rischi statici o deterministici. Non riescono a cogliere le tendenze temporali prevedibili dell'evoluzione del rischio, portando a decisioni di supporto subottimali (troppo anticipate, tardive o in luoghi non più a rischio), con conseguenti costi di missione elevati e percorsi ridondanti.

2. Metodologia

Gli autori propongono un framework di pianificazione cooperativa "consapevole delle previsioni" (forecast-aware) basato su grafi temporali. Il metodo si articola in tre fasi principali (pipeline):

A. Modellazione e Previsione del Rischio (Adversary-Induced Edge Risk Forecast)

• Dinamica degli Avversari: Gli avversari sono modellati come processi di Markov del primo ordine con dinamiche "stai-muovi" (stay-move) sugli archi del grafo.
• Propagazione: Utilizzando una matrice di transizione tra gli archi, il sistema propaga le distribuzioni iniziali degli avversari in avanti nel tempo.
• Output: Si generano previsioni temporali del rischio sugli archi ($\rho_{uv}(t)$), ovvero la probabilità che un avversario occupi un arco specifico a un tempo $t$ futuro.

B. Allocazione Consapevole delle Previsioni (Forecast-aware Support Allocation)

Invece di assegnare posizioni di supporto fisse basate sul rischio iniziale, il sistema seleziona dinamicamente i nodi di supporto in base all'evoluzione prevista del rischio.

• Selezione dei Candidati: Vengono identificati gli archi che diventeranno a rischio entro l'orizzonte temporale di pianificazione.
• Punteggio dei Nodi (Scoring): Per ogni arco a rischio, si valuta un insieme di nodi candidati vicini. Ogni nodo riceve un punteggio basato su due fattori:
  1. Sovrapposizione del percorso ($\hat{P}$): Quanti robot passeranno attraverso quel nodo (basato sui percorsi più brevi previsti).
  2. Potenziale di rischio ($\hat{R}$): L'intensità cumulativa del rischio previsto sull'arco da coprire, pesata per la distanza dal nodo.
• Obiettivo: Assegnare i nodi di supporto ai punti che massimizzano la copertura del rischio atteso lungo i percorsi ad alto traffico.

C. Pianificazione Giocata (Risk-aware Joint Planning)

• Grafo Temporale: I robot pianificano su un grafo temporale dove i costi degli archi sono variabili nel tempo, calcolati come la somma del costo base più la penalità attesa per il rischio (moltiplicata per la probabilità di presenza dell'avversario e ridotta se è attivo il supporto).
• Algoritmo: Viene utilizzato un Lazy A* (A* con espansione pigra) che valuta i rischi solo quando un arco viene considerato durante la ricerca, mantenendo l'efficienza computazionale.
• Ottimizzazione: L'obiettivo è minimizzare il costo atteso cumulativo del team, sostituendo le realizzazioni incerte degli avversari con le loro previsioni probabilistiche.

3. Contributi Chiave

1. Formulazione del Problema: Definizione formale della traversata cooperativa su grafi temporali sotto rischio avversario stocastico, dove i costi evolvono dinamicamente.
2. Meccanismo di Allocazione: Introduzione di un meccanismo di allocazione del supporto che utilizza le transizioni di movimento degli avversari per anticipare il rischio e allocare proattivamente le posizioni di supporto più efficaci.
3. Validazione Sperimentale: Dimostrazione che l'approccio proposto riduce costantemente il costo atteso del team rispetto a baseline non anticipatorie (come TCGRE o allocazione casuale), avvicinandosi alle prestazioni di un pianificatore "oracolo" (che conosce il futuro).

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su grafi casuali di diverse dimensioni (5-20 nodi) con configurazioni variabili di robot (2-4) e avversari (4), testando diverse probabilità di "stazionamento" degli avversari.

• Riduzione dei Costi: Il metodo Forecast-aware ha ottenuto sistematicamente il costo atteso più basso tra tutte le strategie di allocazione del supporto.
• Confronto con Baseline:
  • Supera significativamente l'approccio TCGRE (che usa solo il rischio iniziale) e l'allocazione Casuale, specialmente su grafi più grandi dove la scelta casuale fallisce nel posizionare il supporto in punti critici futuri.
  • In scenari statici (avversari che non si muovono), le prestazioni convergono con quelle dei metodi statici, confermando la correttezza del modello.
• Efficienza Computazionale: Il metodo è stato l'unico a completare la pianificazione entro i limiti di tempo (90s) in scenari complessi (es. 4 robot su grafi da 20 nodi), mentre altri metodi fallivano per timeout a causa dell'incapacità di trovare percorsi validi senza un supporto ben posizionato.
• Calibrazione: Le simulazioni Monte Carlo hanno mostrato che il costo previsto ($J_{exp}$) è strettamente allineato al costo reale ($J_{real}$), con deviazioni minime, confermando l'accuratezza del modello di previsione.
• Caso Studio: In un esempio visivo, l'uso delle previsioni ha permesso ai robot di attraversare zone a rischio prima che diventassero critiche, riducendo il costo del team del 42% e il tempo di completamento di un passo temporale rispetto all'approccio "senza supporto".

5. Significato e Impatto

Questo lavoro rappresenta un passo avanti significativo rispetto alla pianificazione multi-robot tradizionale:

• Transizione da Statico a Dinamico: Sposta il paradigma dalla gestione di rischi fissi alla gestione di rischi stocastici ed evolutivi, rendendo i sistemi robotici più robusti in ambienti reali e imprevedibili.
• Coordinazione Proattiva: Dimostra che l'anticipazione (basata su modelli di previsione) è cruciale per l'efficacia della cooperazione. Non basta reagire al rischio presente; bisogna prepararsi per il rischio futuro.
• Scalabilità: L'approccio mantiene l'efficienza computazionale anche in scenari complessi, rendendolo applicabile a missioni reali con squadre di robot.

Limitazioni e Lavori Futuri:
L'attuale metodo richiede la conoscenza a priori delle dinamiche degli avversari e una pianificazione centralizzata. I lavori futuri mirano a integrare la stima online dei rischi (per apprendere le dinamiche avversarie durante l'esecuzione) e a estendere il framework alla coordinazione decentralizzata.