Coverage Games

1. Introduzione e Definizione del Problema

Il paper introduce e studia i Coverage Games (Giochi di Copertura), un nuovo quadro teorico per la pianificazione multi-agente in contesti in cui un sistema controlla diversi agenti ma non ha il controllo totale su di essi, oppure interagisce con un ambiente composto da più agenti.

Il Modello di Gioco:

• Giocatori: Il gioco è un gioco a due giocatori:
  • Coverer (Copritore): Controlla un insieme di $k$ agenti. Ha un insieme di obiettivi $\beta = \{\alpha_1, \dots, \alpha_m\}$.
  • Disruptor (Sovvertitore): Rappresenta l'ambiente ostile o le condizioni incerte. Segue un'unica strategia contro tutti gli agenti del Coverer.
• Meccanica: Il gioco si svolge su un grafo di gioco $G$. All'inizio, $k$ gettoni (uno per ogni agente del Coverer) sono posizionati sul vertice iniziale. Ogni agente interagisce con il Disruptor generando una "play" (traiettoria infinita).
• Obiettivo del Coverer: Vince se ogni obiettivo in $\beta$ è soddisfatto da almeno uno degli agenti. Formalmente, l'unione degli obiettivi soddisfatti dalle $k$ play deve coprire l'intero insieme $\beta$.
• Obiettivo del Disruptor: Vince se esiste una strategia tale che, per qualsiasi strategia del Coverer, almeno un obiettivo in $\beta$ non viene soddisfatto da nessuna delle $k$ play generate.
• Problemi di Decisione:
  1. Problema di Copertura (Coverage): Esiste una strategia di copertura per il Coverer?
  2. Problema di Sovversione (Disruption): Esiste una strategia di sovversione per il Disruptor?

Differenze Chiave rispetto ai Giochi Tradizionali:
A differenza dei giochi a due giocatori standard con obiettivi multipli (dove un singolo agente deve soddisfare tutti gli obiettivi), qui gli obiettivi possono essere distribuiti dinamicamente tra gli agenti. Inoltre, il gioco non è necessariamente determinato: può accadere che né il Coverer né il Disruptor abbiano una strategia vincente.

2. Metodologia e Strumenti Teorici

Gli autori analizzano la complessità computazionale e le proprietà teoriche dei giochi di copertura, concentrandosi su obiettivi di tipo Büchi (visitare un insieme di vertici infinitamente spesso) e co-Büchi (evitare un insieme di vertici infinitamente spesso).

Concetti Fondamentali:

• Decomponibilità degli Obiettivi: Una sfida centrale è capire se gli obiettivi $\beta$ possono essere partizionati a priori tra gli agenti. Il paper dimostra che, in generale, una decomposizione statica non è sufficiente; la strategia vincente richiede spesso una decomposizione dinamica basata sullo stato del gioco.
• Forks (Forche): Un concetto tecnico cruciale introdotto per caratterizzare le strategie vincenti. Un vertice $v$ è una "fork" se il Coverer può inviare gli agenti verso $l$ successori diversi ($2 \le l \le k$), permettendo una decomposizione degli obiettivi in quel punto.
• Gavoid: Un sottografo del gioco da cui il Disruptor può forzare il gioco a rimanere, evitando le "fork". All'interno di $G_{avoid}$, il gioco si comporta come un gioco a un solo giocatore (poiché tutti gli agenti devono seguire la stessa traiettoria).

Strategia di Analisi:
Gli autori utilizzano una caratterizzazione ricorsiva: il Coverer vince se può raggiungere una "fork" da cui gli obiettivi possono essere decomposti, oppure se vince nel sottografo $G_{avoid}$ trattando tutti gli agenti come un'unica entità.

3. Risultati Principali e Complessità Computazionale

Il paper fornisce un'analisi completa della complessità dei problemi di copertura e sovversione, sia nel caso generale che in casi parametrizzati (fissando il numero di agenti $k$ o il numero di obiettivi $|\beta|$).

A. Proprietà Teoriche

• Indeterminazione: I giochi di copertura non sono determinati. Esistono casi (anche con solo 2 agenti e 3 obiettivi) in cui né il Coverer né il Disruptor hanno una strategia vincente.
• Impossibilità di Decomposizione A Priori: Non è sempre possibile assegnare un sottoinsieme fisso di obiettivi a ciascun agente all'inizio del gioco; la strategia vincente può richiedere di adattare l'assegnazione in base alle mosse del Disruptor.

B. Complessità nel Caso Generale

La Tabella 1 del paper riassume i risultati di complessità (tutti ottimali/tight):

• Nota: Il problema di copertura è PSPACE-completo, più difficile dei giochi standard a due giocatori con obiettivi multipli (che sono spesso in PTIME o NP). Il problema di sovversione è nella classe $\Sigma_2^P$ (più facile di PSPACE), il che riflette il fatto che il Disruptor deve solo trovare una strategia che fallisca la copertura, mentre il Coverer deve garantire la copertura contro tutte le strategie.

C. Complessità Parametrizzata

Gli autori analizzano la complessità fissando parametri specifici, simulando scenari reali dove il grafo $G$ è grande ma il numero di agenti o obiettivi è piccolo.

1. Numero di Agenti Fisso ($k$):

   • Copertura: Diventa NP-completo (per Büchi e co-Büchi). La profondità della ricorsione nell'algoritmo diventa costante.
   • Sovversione (Büchi): Diventa NP-completo.
   • Sovversione (co-Büchi): Rimane $\Sigma_2^P$-completo. Questo è un risultato sorprendente: fissare il numero di agenti non riduce la complessità per gli obiettivi co-Büchi, a causa della difficoltà intrinseca di trovare insiemi massimali di obiettivi soddisfattibili in questo contesto.

2. Numero di Obiettivi Fisso ($|\beta|$):

   • Copertura e Sovversione: Entrambi diventano PTIME-completi (risolvibili in tempo polinomiale). Fissare il numero di obiettivi elimina la nondeterministica legata alla partizione degli obiettivi, rendendo il problema trattabile.

4. Contributi Chiave

1. Nuovo Framework: Introduzione dei "Coverage Games" come estensione naturale della sintesi e della pianificazione multi-agente in ambienti ostili.
2. Caratterizzazione delle Strategie: Definizione formale della decomponibilità degli obiettivi e introduzione del concetto di "fork" come strumento per analizzare le strategie vincenti.
3. Analisi di Complessità Completa: Mappatura precisa della complessità computazionale, mostrando come la combinazione di agenti multipli e obiettivi multipli in un setting competitivo cambi drasticamente la classe di complessità rispetto ai giochi standard.
4. Risultati Sorprendenti: La dimostrazione che fissare il numero di agenti non semplifica il problema di sovversione per obiettivi co-Büchi (rimane $\Sigma_2^P$), a differenza del caso Büchi.

5. Significato e Applicazioni

Il lavoro ha implicazioni significative in diversi domini:

• Sorveglianza Multi-Robot: Garantire che ogni zona critica sia pattugliata infinitamente spesso da almeno un robot, anche in presenza di ostacoli dinamici o avversari.
• Sicurezza Informatica: Assicurare che ogni vettore di attacco potenziale sia mitigato da almeno uno dei meccanismi di difesa, contro un hacker avversario.
• Sistemi Multi-Threaded: Garantire che ogni risorsa critica sia acceduta infinitamente spesso da almeno un processo, in tutti gli ambienti possibili.
• Gestione del Traffico: Assicurare che almeno un percorso rimanga libero da congestioni, considerando il comportamento degli altri veicoli come un ambiente ostile.

In sintesi, il paper fornisce le fondamenta teoriche per progettare sistemi multi-agente robusti in ambienti incerti, evidenziando che la coordinazione dinamica degli obiettivi è essenziale e computazionalmente impegnativa, ma analizzabile attraverso gli strumenti sviluppati dagli autori.