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

Resumo Técnico: A Tomada de Decisão Descentralizada para Sistemas de Estados Finitos sobre Alfabetos Finitos é Indecidível

1. Formulação do Problema

Este artigo investiga a decidibilidade fundamental da tomada de decisão descentralizada para sistemas de transição de estados finitos (Sistemas de Eventos Discretos ou DES) sob restrições estritas de comunicação. O problema é formulado dentro de uma arquitetura de observação descentralizada geral envolvendo:

• Uma Planta: Um autômato de estados finitos determinístico $G = (Q, \Sigma, f, q_0)$.
• Agentes Locais: Dois agentes observam a planta através de conjuntos de eventos disjuntos $\Sigma_{o,1}$ e $\Sigma_{o,2}$ via projeções naturais $P_1$ e $P_2$.
• Comunicação: Cada agente gera um símbolo de decisão local de um alfabeto finito $\Delta$ baseado exclusivamente em seu histórico de observação.
• Centro de Fusão: Um centro de fusão sem memória aplica uma regra fixa $F: \Delta \times \Delta \to \{0, 1\}$ ao par de decisões locais para produzir uma decisão global binária.

A questão central, denominada Problema de Observação Descentralizada com Alfabeto Finito, é determinar se existem mapas de decisão local $S_i: P_i(L(G)) \to \Delta$ tais que o centro de fusão possa reconstruir exatamente uma linguagem de especificação regular $K \subseteq L(G)$. Especificamente, para todo $s \in L(G)$, a condição $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ deve ser satisfeita.

2. Metodologia

Os autores estabelecem a indecidibilidade deste problema através de uma redução do problema da palavra de Thue, um problema clássico de indecidibilidade na teoria das linguagens formais referente à equivalência de duas palavras sob um conjunto finito de regras de reescrita bidirecionais.

Estratégia de Construção:
Dada uma instância do problema da palavra de Thue $(\Gamma, R, \alpha, \beta)$, os autores constroem uma instância específica de observação descentralizada $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ com as seguintes propriedades:

• Arquitetura Restrita: O alfabeto de comunicação é binário ($\Delta = \{0, 1\}$), e a regra de fusão é fixa para o operador OU exclusivo (XOR) ($a \oplus b = 1 \iff a \neq b$).
• Estrutura da Planta: O autômato $G$ é construído com três ramos distintos:
  1. Ramo de Identidade: Gera cadeias que codificam palavras arbitrárias $w \in \Gamma^*$ como sequências pareadas. Este ramo força os dois agentes a atribuírem valores de decisão idênticos para a mesma palavra subjacente $w$ (já que a saída deve ser 0 para strings não marcadas, e $x \oplus y = 0 \implies x=y$). Isso permite a definição de uma função de valoração global $C(w)$.
  2. Ramos de Reescrita: Para cada regra de reescrita $(\ell_j, r_j) \in R$, a planta gera cadeias onde o Agente 1 observa um contexto contendo $\ell_j$ e o Agente 2 observa o mesmo contexto contendo $r_j$. Como estas cadeias não são marcadas, a regra de fusão XOR força $C(\dots \ell_j \dots) = C(\dots r_j \dots)$. Isso impõe que a valoração $C$ seja invariante sob passos de reescrita de Thue.
  3. Ramo Marcado: Gera uma única cadeia marcada codificando as palavras específicas $\alpha$ e $\beta$ observadas pelos Agentes 1 e 2, respectivamente. Para que a saída da fusão seja 1 (indicando pertinência em $K$), os agentes devem atribuir valores diferentes: $C(\alpha) \neq C(\beta)$.

Redução Lógica:
A existência de mapas de decisão local válidos implica a existência de uma valoração $C$ que é constante nas classes de equivalência de Thue (devido aos ramos de reescrita) mas distingue $\alpha$ e $\beta$ (devido ao ramo marcado). Tal valoração existe se, e somente se, $\alpha \not\equiv_R \beta$. Como o problema da palavra de Thue é indecidível, determinar a existência de tais mapas também é indecidível.

3. Contribuições Principais e Resultados

• Indecidibilidade sob XOR: O artigo prova que o problema da observação descentralizada é indecidível mesmo quando o alfabeto de decisão é binário e a regra de fusão é fixa para XOR. Isso ocorre para uma arquitetura de informação altamente restrita (dois agentes, alfabeto finito, fusão sem memória).
• Papel da Monotonicidade: Os resultados destacam que a decidibilidade de arquiteturas existentes (ex: regras de conjunção AND ou disjunção OR) baseia-se fundamentalmente na natureza monotônica e de preservação de ordem dessas regras de fusão. A regra XOR é inerentemente não-monotônica, quebrando as propriedades estruturais que permitem a síntese construtiva e a decidibilidade em contextos clássicos.
• Extensão para Controle e Diagnóstico: Os autores demonstram que o problema da observação descentralizada pode ser reduzido a:
  • Controle Supervisório Descentralizado: Determinar a existência de supervisores locais para impor uma especificação.
  • Diagnóstico de Falhas Descentralizado: Determinar a existência de diagnosticadores locais para detectar falhas com atraso limitado e sem alarmes falsos.
  • Prognóstico de Falhas Descentralizado: Determinar a existência de prognosticadores locais para prever falhas antes de sua ocorrência.
    Consequentemente, todos esses problemas são mostrados como indecidíveis sob alfabetos de decisão binários e a regra de fusão XOR.

4. Significância e Alegações

O artigo afirma revelar uma limitação fundamental nas arquiteturas de tomada de decisão descentralizada. Enquanto a literatura anterior focou em enriquecer os alfabetos de decisão ou projetar regras de fusão sofisticadas para aumentar o poder de expressão, este trabalho mostra que a escolha da regra de fusão pode alterar fundamentalmente a própria decidibilidade do problema de síntese.

Os autores enfatizam que seu resultado é estritamente mais forte do que resultados de indecidibilidade anteriores (ex: aqueles envolvendo alfabetos de comunicação infinitos) porque a indecidibilidade persiste mesmo quando o alfabeto de comunicação é finito (binário) e a regra de fusão é fixa. A fonte intrínseca da indecidibilidade é identificada como a estrutura de informação descentralizada induzida por observações independentes interagindo com regras de fusão não-monotônicas, e não pelo tamanho do alfabeto de comunicação.

O artigo conclui modestamente, observando que, embora o problema geral seja indecidível, aplicações práticas com memória limitada nos agentes locais podem tornar o problema de síntese decidível via enumeração exaustiva, sugerindo um caminho para pesquisas futuras em técnicas de síntese com limites (bounded-synthesis).