Decentralized Decision-Making for Finite-State Systems over Finite Alphabets is Undecidable

Sintesi Tecnica: Il processo di decisione decentralizzata per sistemi a stati finiti su alfabeti finiti è indecidibile

1. Formulazione del Problema

Questo articolo investiga la decidibilità fondamentale del processo decisionale decentralizzato per sistemi di transizione a stati finiti (Sistemi a Eventi Discreti o DES) sotto rigidi vincoli di comunicazione. Il problema è inquadrato in un'architettura di osservazione decentralizzata generale che coinvolge:

• Un Pianta (Plant): Un automa a stati finiti deterministico $G = (Q, \Sigma, f, q_0)$.
• Agenti Locali: Due agenti osservano la pianta attraverso insiemi di eventi disgiunti $\Sigma_{o,1}$ e $\Sigma_{o,2}$ tramite proiezioni naturali $P_1$ e $P_2$.
• Comunicazione: Ogni agente genera un simbolo decisionale locale da un alfabeto finito $\Delta$ basandosi esclusivamente sulla propria storia di osservazione.
• Centro di Fusione: Un centro di fusione privo di memoria applica una regola fissa $F: \Delta \times \Delta \to \{0, 1\}$ alla coppia di decisioni locali per produrre una decisione globale binaria.

La questione centrale, denominata Problema dell'Osservazione Decentralizzata con Alfabeto Finito, consiste nel determinare se esistano mappe decisionali locali $S_i: P_i(L(G)) \to \Delta$ tali che il centro di fusione possa ricostruire esattamente un linguaggio di specifica regolare $K \subseteq L(G)$. Nello specifico, per ogni $s \in L(G)$, deve essere soddisfatta la condizione $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$.

2. Metodologia

Gli autori stabiliscono l'indecidibilità di questo problema attraverso una riduzione dal problema della parola di Thue, un classico problema indecidibile della teoria del linguaggio formale riguardante l'equivalenza di due parole sotto un insieme finito di regole di riscrittura bidirezionali.

Strategia di Costruzione:
Data un'istanza del problema della parola di Thue $(\Gamma, R, \alpha, \beta)$, gli autori costruiscono un'istanza specifica di osservazione decentralizzata $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ con le seguenti proprietà:

• Architettura Restrittiva: L'alfabeto di comunicazione è binario ($\Delta = \{0, 1\}$) e la regola di fusione è fissata all'operatore OR esclusivo (XOR) ($a \oplus b = 1 \iff a \neq b$).
• Struttura della Pianta: L'automa $G$ è costruito con tre rami distinti:
  1. Ramo di Identità: Genera stringhe che codificano parole arbitrarie $w \in \Gamma^*$ come sequenze accoppiate. Questo ramo costringe i due agenti ad assegnare valori decisionali identici alla stessa parola sottostante $w$ (poiché l'output deve essere 0 per le stringhe non marcate, e $x \oplus y = 0 \implies x=y$). Ciò permette la definizione di una funzione di valutazione globale $C(w)$.
  2. Rami di Riscrittura: Per ogni regola di riscrittura $(\ell_j, r_j) \in R$, la pianta genera stringhe in cui l'Agente 1 osserva un contesto contenente $\ell_j$ e l'Agione 2 osserva lo stesso contesto contenente $r_j$. Poiché queste stringhe non sono marcate, la regola di fusione XOR impone che $C(\dots \ell_j \dots) = C(\dots r_j \dots)$. Ciò impone che la valutazione $C$ sia invariante rispetto ai passi di riscrittura di Thue.
  3. Ramo Marcato: Genera una stringa marcata unica che codifica le parole specifiche $\alpha$ e $\beta$ osservate rispettivamente dagli Agenti 1 e 2. Affinché l'output della fusione sia 1 (indicando l'appartenenza a $K$), gli agenti devono assegnare valori differenti: $C(\alpha) \neq C(\beta)$.

Riduzione Logica:
L'esistenza di mappe decisionali locali valide implica l'esistenza di una valutazione $C$ che è costante sulle classi di equivalenza di Thue (a causa dei rami di riscrittura) ma distingue $\alpha$ e $\beta$ (a causa del ramo marcato). Tale valutazione esiste se e solo se $\alpha \not\equiv_R \beta$. Poiché il problema della parola di Thue è indecidibile, anche determinare l'esistenza di tali mappe è indecidibile.

3. Contributi Chiave e Risultati

• Indecidibilità sotto XOR: Il documento dimostra che il problema dell'osservazione decentralizzata è indecidibile anche quando l'alfabeto decisionale è binario e la regola di fusione è fissata a XOR. Ciò è valido per un'architettura informativa altamente ristretta (due agenti, alfabeto finito, fusione senza memoria).
• Ruolo della Monotonicità: I risultati evidenziano che la decidibilità delle architetture esistenti (ad esempio, regole di fusione congiuntive AND o disgiuntive OR) si basa fondamentalmente sulla natura monotona e preservante l'ordine di tali regole di fusione. La regola XOR è intrinsecamente non monotona, rompendo le proprietà strutturali che permettono la sintesi costruttiva e la decidibilità nei contesti classici.
• Estensione al Controllo e alla Diagnosi: Gli autori dimostrano che il problema dell'osservazione decentralizzata può essere ridotto a:
  • Controllo Supervisonato Decentralizzato: Determinare l'esistenza di supervisori locali per imporre una specifica.
  • Diagnosi dei Guasti Decentralizzata: Determinare l'esistenza di diagnosi locali per rilevare guasti con ritardo limitato e senza falsi allarmi.
  • Prognosi dei Guasti Decentralizzata: Determinare l'esistenza di prognostici locali per prevedere i guasti prima che si verifichino.
    Di conseguenza, tutti questi problemi risultano indecidibili sotto alfabeti decisionali binari e la regola di fusione XOR.

4. Significato e Rivendicazioni

Il documento sostiene di rivelare un limite fondamentale nelle architetture di processo decisionale decentralizzato. Mentre la letteratura precedente si è concentrata sull'arricchimento degli alfabeti decisionali o sulla progettazione di regole di fusione sofisticate per potenziare la capacità espressiva, questo lavoro mostra che la scelta della regola di fusione può alterare fondamentalmente la decidibilità stessa del problema della sintesi.

Gli autori sottolineano che il loro risultato è strettamente più forte dei precedenti risultati di indecidibilità (ad esempio, quelli che coinvolgono alfabeti di comunicazione infiniti) perché l'indecidibilità persiste anche quando l'alfabeto di comunicazione è finito (binario) e la regola di fusione è fissa. La fonte intrinseca dell'indecidibilità è identificata nella struttura informativa decentralizzata indotta dalle osservazioni indipendenti che interagiscono con regole di fusione non monotone, piuttosto che nella dimensione dell'alfabeto di comunicazione.

L'articolo conclude con modestia, osservando che, sebbene il problema generale sia indecidibile, le applicazioni pratiche con memoria limitata agli agenti locali potrebbero rendere il problema della sintesi decidibile tramite enumerazione esaustiva, suggerendo una direzione per la ricerca futura sulle tecniche di sintesi limitata.