Riepilogo Tecnico: Pianificazione Disaccoppiata per Obiettivi Multipli $\omega$-Regolari

Enunciato del Problema

Il documento affronta il problema della generazione di percorsi su un grafo diretto finito che soddisfino una collezione di obiettivi $\omega$-regolari ($\phi_1, \dots, \phi_N$). Gli approcci tradizionali risolvono questo problema calcolando un'unica politica monolitica per la congiunzione di tutti gli obiettivi. Questo lavoro propone un framework disaccoppiato in cui $N$ agenti indipendenti sono assegnati a obiettivi individuali. Ogni agente $i$ seleziona una politica locale $\pi_i$ per soddisfare $\phi_i$ senza conoscere gli obiettivi o le politiche degli altri agenti. Uno schedulatore $\sigma$, ignaro della struttura del grafo e degli obiettivi specifici, compone dinamicamente queste politiche selezionando quale agente determina il prossimo vertice a ogni passo temporale.

La sfida principale è determinare in quali condizioni una composizione di politiche locali indipendenti, guidata da uno schedulatore, soddisfi quasi certamente la congiunzione di tutti gli obiettivi ($\bigwedge \phi_i$), assumendo che esista un tale percorso. Il framework mira a massimizzare la modularità (gli agenti progettano le politiche indipendentemente) garantendo al contempo la correttezza.

Metodologia

Il Framework Disaccoppiato

Il sistema è costituito da:

1. Agenti: $N$ agenti, ciascuno responsabile di un obiettivo $\phi_i$.
2. Politiche: Gli agenti selezionano politiche da classi specifiche in base alla loro conoscenza del processo di schedulazione:
   • Consapevoli del percorso: Politiche tradizionali che dipendono solo dalla cronologia del percorso.
   • Consapevoli della schedulazione: Politiche che sanno se sono state schedulate nei passi precedenti.
   • Consapevoli della cronologia completa: Politiche che sanno esattamente quale agente è stato schedulato a ogni passo precedente.
3. Schedulatore: Uno schedulatore stocastico $\sigma$ che seleziona un agente a ogni passo. Il documento sostiene che gli schedulatori deterministici (anche quelli estremamente equi) sono insufficienti per una composizione universale, rendendo necessari schedulatori stocastici con proprietà di equità probabilistica.

Decomposizione degli Obiettivi

Gli autori decompongono gli obiettivi $\omega$-regolari in componenti di sicurezza e vivacità ($\phi = \phi_{safe} \cap \phi_{live}$).

• Sicurezza: Richiede l'evitamento di stati non sicuri. Il documento dimostra che la sicurezza non può essere garantita sotto schedulazione stocastica senza comunicazione. Introducono un protocollo di composizione schermata in cui gli agenti scambiano insiemi di azioni sicure (politiche massimamente permissive) a ogni passo. L'agente schedulato deve scegliere un'azione dall'intersezione degli insiemi sicuri di tutti gli agenti. Sotto l'ipotesi di chiusura reciproca di sicurezza (ogni prefisso di un percorso che soddisfa i vincoli di sicurezza individuali può essere esteso per soddisfare tutti), questo protocollo garantisce la sicurezza.
• Vivacità: Richiede di visitare stati buoni infinite volte o eventualmente. Una volta imposta la sicurezza (ristrizzando il grafo al sottografo sicuro), l'attenzione si sposta sul soddisfacimento degli obiettivi di vivacità.

Convenzioni

Poiché politiche non coordinate possono fallire anche per obiettivi semplici (ad esempio, obiettivi di Büchi in grafi fortemente connessi), il documento introduce le convenzioni. Una convenzione è una mappatura dalle classi di obiettivi a restrizioni sui tipi di politica (ad esempio, limiti di memoria, consapevolezza della schedulazione) concordate a priori, prima che il grafo specifico o gli obiettivi siano rivelati. Se tutti gli agenti aderiscono alla convenzione, la composizione è garantita per soddisfare tutti gli obiettivi quasi certamente.

Contributi e Risultati Chiave

1. Impossibilità di Schedulatori Deterministici Universali e Stocastici Non Coordinati

• Schedulatori Deterministici: Il documento dimostra che nessun schedulatore deterministico è universale. Anche con equità estrema (ogni agente schedulato infinite volte), esistono grafi e politiche in cui la composizione non riesce a soddisfare gli obiettivi (Esempio 1, Teorema 1).
• Schedulatori Stocastici Non Coordinati: Per gli obiettivi di Büchi, anche gli schedulatori stocastici falliscono se gli agenti utilizzano politiche arbitrarie. Gli autori costruiscono uno scenario in cui gli agenti utilizzano politiche con "tempi di attesa" che crescono esponenzialmente (Esempio 2, Teorema 3). Uno schedulatore stocastico non può superare la probabilità che gli agenti si perdano le finestre critiche reciproche, portando a un fallimento nel soddisfare la congiunzione quasi certamente. Questo si estende agli obiettivi di raggiungibilità (Corollario 1).

2. Sicurezza tramite Composizione Schermata

Il documento stabilisce che la sicurezza richiede comunicazione. Propongono un protocollo in cui gli agenti trasmettono i loro insiemi di successori sicuri. L'agente schedulato seleziona un'azione dall'intersezione di questi insiemi. Il Teorema 2 dimostra che se gli obiettivi sono reciprocamente chiusi per la sicurezza, questa composizione schermata garantisce che la componente di sicurezza sia soddisfatta quasi certamente, riducendo il problema alla vivacità su un sottografo sicuro.

3. Convenzioni per Obiettivi di Vivacità

Il documento caratterizza convenzioni minimamente restrittive per le principali sottoclassi di obiettivi $\omega$-regolari:

• Obiettivi di Büchi:

  • Convenzione: Gli agenti utilizzano politiche a memoria finita (nello specifico, politiche con tempi di impatto attesi uniformemente limitati per l'insieme target).
  • Risultato: Il Teorema 4 mostra che se tutti gli agenti utilizzano tali politiche, uno schedulatore stocastico le compone per soddisfare tutti gli obiettivi di Büchi quasi certamente. Non è richiesta alcuna coordinazione in esecuzione o conoscenza degli altri agenti.

• Obiettivi di Co-Büchi:

  • Sfida: Le semplici politiche a memoria finita sono insufficienti (Teorema 5). Gli agenti devono eventualmente convergere verso un ciclo comune.
  • Convenzione: Gli agenti utilizzano politiche consapevoli della schedulazione che mantengono una "ipotesi" di un percorso a forma di laccio (un percorso verso un ciclo buono).
  • Meccanismo: Se un agente non è schedulato e osserva una transizione in conflitto con la sua ipotesi corrente, scarta l'ipotesi e campiona un nuovo percorso a forma di laccio.
  • Risultato: Il Teorema 6 dimostra che questo protocollo porta a un consenso su un percorso a forma di laccio comune quasi certamente, soddisfacendo tutti gli obiettivi di Co-Büchi.

• Obiettivi di Parità:

  • Sfida: Gli obiettivi di parità sono più complessi; un singolo ciclo semplice potrebbe non essere sufficiente (Lemma 1).
  • Convenzione: Gli agenti utilizzano politiche consapevoli della cronologia completa. Ogni agente mantiene una tupla di politiche interne senza memoria, ipotizzando la politica di ogni altro agente (incluso se stesso).
  • Meccanismo: Se un agente osserva una transizione in conflitto con la sua ipotesi sulla politica di un altro agente, seleziona casualmente una nuova tupla di politiche interne.
  • Risultato: Il Teorema 7 dimostra che questo processo converge a uno stato di consenso in cui tutti gli agenti concordano su un insieme di politiche che soddisfano gli obiettivi di parità quasi certamente.

Significato e Affermazioni

Il documento afferma di stabilire le fondamenta di un framework di progettazione modulare senza precedenti per il processo decisionale $\omega$-regolare. Il suo significato risiede in:

1. Modularità e Robustezza: Permette la separazione delle preoccupazioni nella progettazione delle politiche. Le politiche possono essere progettate, aggiunte, rimosse o modificate indipendentemente senza ricalcolare l'intero sistema, a condizione che gli agenti aderiscano alle convenzioni concordate.
2. Esecuzione Leggera: Gli schedulatori sono semplici e stocastici, adatti a dispositivi con capacità di elaborazione limitate (ad esempio, robot, droni).
3. Limiti Teorici: Caratterizza rigorosamente il compromesso tra la complessità della classe di obiettivi e il livello richiesto di coordinamento (consapevolezza dello schedulatore) tra gli agenti.
   • Büchi: Richiede solo politiche consapevoli del percorso.
   • Co-Büchi: Richiede conoscenza dello stato di schedulazione (consapevoli della schedulazione).
   • Parità: Richiede la conoscenza di quale agente è stato schedulato (consapevoli della cronologia completa).
4. Sicurezza vs. Vivacità: Chiarisce che mentre la vivacità può essere ottenuta attraverso una convergenza probabilistica tramite convenzioni, la sicurezza richiede fondamentalmente un protocollo di comunicazione (composizione schermata) per garantire la correttezza deterministica su ogni percorso.

Gli autori notano che, sebbene dimostrino l'esistenza di tali convenzioni e schedulatori, il tempo di convergenza dei protocolli proposti potrebbe essere esponenziale, e il miglioramento di questo aspetto rimane un argomento per lavori futuri. Distinguono inoltre il loro approccio dalla "schedulazione basata su aste" (che è incompleta per obiettivi multipli) e dai "modelli di strategia" (che comportano un elevato onere computazionale), posizionando il loro metodo come un'alternativa solida, completa e modulare per grafi fortemente connessi.