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

Resumen Técnico: La toma de decisiones descentralizada para sistemas de estados finitos sobre alfabetos finitos es indecidible

1. Formulación del Problema

Este artículo investiga la decidibilidad fundamental de la toma de decisiones descentralizada para sistemas de transición de estados finitos (Sistemas de Eventos Discretos o DES) bajo estrictas restricciones de comunicación. El problema se enmarca dentro de una arquitectura de observación descentralizada general que involucra:

• Una Planta: Un autómata de estados finitos determinista $G = (Q, \Sigma, f, q_0)$.
• Agentes Locales: Dos agentes observan la planta a través de conjuntos de eventos disjuntos $\Sigma_{o,1}$ y $\Sigma_{o,2}$ mediante proyecciones naturales $P_1$ y $P_2$.
• Comunicación: Cada agente genera un símbolo de decisión local de un alfabeto finito $\Delta$ basándose únicamente en su historial de observación.
• Centro de Fusión: Un centro de fusión sin memoria aplica una regla fija $F: \Delta \times \Delta \to \{0, 1\}$ al par de decisiones locales para producir una decisión binaria global.

La cuestión central, denominada el Problema de Observación Descentralizada con Alfabetos Finitos, es determinar si existen mapas de decisión local $S_i: P_i(L(G)) \to \Delta$ tales que el centro de fusión pueda reconstruir exactamente un lenguaje de especificación regular $K \subseteq L(G)$. Específicamente, para todo $s \in L(G)$, debe cumplirse la condición $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$.

2. Metodología

Los autores establecen la indecidibilidad de este problema mediante una reducción del problema de las palabras de Thue, un problema clásico de indecidibilidad en la teoría de lenguajes formales relativo a la equivalencia de dos palabras bajo un conjunto finito de reglas de reescritura bidireccionales.

Estrategia de Construcción:
Dada una instancia del problema de las palabras de Thue $(\Gamma, R, \alpha, \beta)$, los autores construyen una instancia específica de observación descentralizada $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ con las siguientes propiedades:

• Arquitectura Restringida: El alfabeto de comunicación es binario ($\Delta = \{0, 1\}$) y la regla de fusión es fija como el operador OR exclusivo (XOR) ($a \oplus b = 1 \iff a \neq b$).
• Estructura de la Planta: El autómata $G$ se construye con tres ramas distintas:
  1. Rama de Identidad: Genera cadenas que codifican palabras arbitrarias $w \in \Gamma^*$ como secuencias emparejadas. Esta rama obliga a los dos agentes a asignar valores de decisión idénticos a la misma palabra subyacente $w$ (ya que la salida debe ser 0 para las cadenas no marcadas, y $x \oplus y = 0 \implies x=y$). Esto permite la definición de una función de valoración global $C(w)$.
  2. Ramas de Reescritura: Para cada regla de reescritura $(\ell_j, r_j) \in R$, la planta genera cadenas donde el Agente 1 observa un contexto que contiene $\ell_j$ y el Agente 2 observa el mismo contexto que contiene $r_j$. Dado que estas cadenas no están marcadas, la regla de fusión XOR fuerza $C(\dots \ell_j \dots) = C(\dots r_j \dots)$. Esto impone que la valoración $C$ sea invariante bajo los pasos de reescritura de Thue.
  3. Rama Marcada: Genera una cadena marcada única que codifica las palabras específicas $\alpha$ y $\beta$ observadas por los Agentes 1 y 2, respectivamente. Para que la salida de la fusión sea 1 (indicando la pertenencia a $K$), los agentes deben asignar valores diferentes: $C(\alpha) \neq C(\beta)$.

Reducción Lógica:
La existencia de mapas de decisión local válidos implica la existencia de una valoración $C$ que es constante en las clases de equivalencia de Thue (debido a las ramas de reescritura) pero que distingue $\alpha$ y $\beta$ (debido a la rama marcada). Tal valoración existe si y solo si $\alpha \not\equiv_R \beta$. Dado que el problema de las palabras de Thue es indecidible, determinar la existencia de tales mapas también es indecidible.

3. Contribuciones Clave y Resultados

• Indecidibilidad bajo XOR: El artículo demuestra que el problema de la observación descentralizada es indecidible incluso cuando el alfabeto de decisión es binario y la regla de fusión es fija como XOR. Esto se mantiene para una arquitectura de información altamente restringida (dos agentes, alfabeto finito, fusión sin memoria).
• Papel de la Monotonía: Los resultados resaltan que la decidibilidad de las arquitecturas existentes (por ejemplo, reglas de conjunción AND o disyunción OR) depende fundamentalmente de la naturaleza monótona y de preservación del orden de dichas reglas de fusión. La regla XOR es intrínsecamente no monótona, rompiendo las propiedades estructurales que permiten la síntesis constructiva y la decidibilidad en entornos clásicos.
• Extensión al Control y Diagnóstico: Los autores demuestran que el problema de la observación descentralizada puede reducirse a:
  • Control Supervisado Descentralizado: Determinar la existencia de supervisores locales para imponer una especificación.
  • Diagnóstico de Fallos Descentralizado: Determinar la existencia de diagnósticos locales para detectar fallos con retardo acotado y sin falsas alarmas.
  • Pronóstico de Fallos Descentralizado: Determinar la existencia de prognosticadores locales para predecir fallos antes de su ocurrencia.
    Consecuentemente, todos estos problemas resultan ser indecidibles bajo alfabetos de decisión binarios y la regla de fusión XOR.

4. Significado y Reivindicaciones

El artículo afirma revelar una limitación fundamental en las arquitecturas de toma de decisiones descentralizadas. Mientras que la literatura previa se ha centrado en enriquecer los alfabetos de decisión o diseñar reglas de fusión sofisticadas para mejorar la capacidad de expresión, este trabajo muestra que la elección de la regla de fusión puede alterar fundamentalmente la decidibilidad del problema de síntesis mismo.

Los autores enfatizan que su resultado es estrictamente más fuerte que los resultados de indecidibilidad previos (por ejemplo, aquellos que involucran alfabetos de comunicación infinitos) porque la indecidibilidad persiste incluso cuando el alfabeto de comunicación es finito (binario) y la regla de fusión es fija. La fuente intrínseca de la indecidibilidad se identifica como la estructura de información descentralizada inducida por las observaciones independientes interactuando con reglas de fusión no monótonas, en lugar del tamaño del alfabeto de comunicación.

El artículo concluye modestamente, señalando que, aunque el problema general es indecidible, las aplicaciones prácticas con memoria acotada en los agentes locales podrían hacer que el problema de síntesis sea decidible mediante enumeración exhaustiva, sugiriendo una dirección para la investigación futura en técnicas de síntesis acotada.