4.11 Grafos y grafos causales   Los diversos tipos de grafos son herramientas populares para la representación de conocimiento en Inteligencia Artificial. Una noción básica de grafo es la siguiente. Consideremos un conjunto de nodos, N, que representan entidades; éstas pueden ser eventos, declaraciones, síntomas, variables o incluso más complejas como estructuras, teorías, etc., Entre los nodos pueden tener lugar varios tipos de relación; en la formulación básica podemos considerar simplemente un tipo, por ejemplo causalidad, dependencia física, etc. Las relaciones entre los nodos se representan mediante arcos (uniones), dirigidos (un solo sentido) o no (simétricos). La relación, denotada R, es un subconjunto del producto Cartesiano . El grafo se define así como el par , .

Dependiendo de la aplicación particular, varias modificaciones de la definición básica son posibles. Generalmente, pueden admitirse varios tipos diferentes de nodos y varios tipos diferentes de uniones entre ellos. Algunas uniones pueden tomar formas funcionales más complejas, pudiendo unir varios nodos de entrada y varios nodos de salida. Son posibles varias interpretaciones de los nodos y de las uniones.

Esta sección esta dedicada a la presentación de una selección básica de modelos basados en grafos, con especial atención a aquellos modelos que incorporan grafos causales. Existen diversas aproximaciones basadas en la noción intuitiva de causalidad y en la representación gráfica de dependencias causales entre síntomas (eventos, variables, nodos). Algunas de estas representaciones más típicas se esbozan a continuación. En el Capítulo 7 se presentará un modelo más general basado en grafos causales lógicos.

Arboles de fallos

  Una de las primeras utilizaciones o de grafos causales consistió en el análisis de seguridad y fiabilidad mediante los llamados arboles de fallos [Barlow and Lambert, 1975]. El análisis mediante árboles de fallos (FTA) ha sido reconocido e industrialmente aceptado durante mucho tiempo para tratar con la complejidad de los sistemas analizando su seguridad y fiabilidad. El origen de los FTA se remonta a las primeras en aplicaciones en la industria aerospacial. Esta técnica extensamente aplicable puede usarse en diversidad de campos, incluso sistemas complejos y heterogéneos, como plantas nucleares. Principalmente se aplica al análisis de seguridad, pero también puede usarse en el diagnóstico para predecir las causas probables en caso de averías del sistema, y como tal puede ser de interés en supervisión para la predicción y apoyo a la toma de decisiones.

Un árbol de fallos consiste en nodos que representan eventos en y puertas logicas, normalmente AND y OR, para representar las relaciones entre eventos. Típicamente, pueden distinguirse cuatro tipos de eventos:
 

  • de fallo, representados con rectángulos  , se refieren tanto a fallos como a eventos normales. Son salidas de puertas lógicas (básicamente OR y AND),
  • básicos, representados con círculos O , se refieren a fallos inherentes a algún elemento del sistema (primarios o generales),
  • subdesarrollados, representados con diamantes à , se refieren a otros fallos distintos a los primarios,
  • de cambio, representados con Ù encima de ë û , se refieren a algunos eventos esperados que ocurran que nunca ocurren en condiciones normales debido al diseño.
    •


    Los eventos se conectan mediante flechas de unión; un nodo OR representa la disyunción de condiciones que causan una salida, mientras un nodo AND representa la conjunción de condiciones que causan la salida. Un ejemplo simple de árbol de fallos se presenta en la siguiente figura.
     


    Otro ejemplo de árbol de fallos puede encontrarse en [Barlow and Lambert, 1975], donde se describen su construcción y su uso En [Isermann, 1994] pueden encontrarse ejemplos mas complejos, incluyendo razonamiento difuso para la evaluación de los fallos.

    El modelo de árbol de [Barlow and Lambert, 1975] puede usarse de varias maneras para analizar la seguridad de sistemas. Las posibles aproximaciones incluyen simulación de fallos, análisis de propagación de fallos, asignación probabilística de seguridad e inferencia de diagnóstico. A continuación se presenta un algoritmo útil para la identificación de posibles causas de funcionamiento defectuoso observadas del sistema. El procedimiento se llama minimum cut set algorithm.

    Un cut set es un conjunto de eventos básicos tal que la ocurrencia simultánea de estos eventos causa el evento superior. Un cut set es mínimo si ningún subconjunto puede causar el evento superior. Para un solo evento superior puede haber varios cut set mínimos diferentes. Una lista de todos los cut set mínimos - si es posible - puede ser útil para analizar la seguridad, identificando posibles o potenciales causas de fallo y - posiblemente - rediseñando el sistema para lograr nivel apropiado de seguridad.

    El principio básico del algoritmo consiste en el análisis hacia atrás de las causas potenciales de un evento seleccionado. A destacar que, en el caso de puertas OR hay varias causas alternativas, mientras en caso de puertas AND hay una sola causa pero compuesta de varios eventos simultáneos. Así, un nodo OR siempre aumenta el número de posibles cut set construido durante el análisis, mientras que un nodo AND aumenta el tamaño (número de elementos) de los mismos. El algoritmo funciona de arriba a abajo de modo recursivo. Cuando únicamente quedan eventos primarios, el algoritmo se detiene; entonces los cut set mínimos para el árbol son los conjuntos más recientes. El esquema principal del algoritmo puede expresarse con las siguiente reglas:
     

  • empezar por el nodo de la cima, y proceder hacia abajo de forma recursiva; la solución temporal es una lista de cut set (causas conjuntas) alternativos, inicialmente vacía,
  • para cualquier nodo OR, construir una lista de causas alternativas correspondientes a los nodos de entrada,
  • para cualquier nodo AND, construir una sola lista de causas que contenga todos los nodos de entrada,
  • en cualquier fase, reemplazar por lo menos un nodo no-terminal por una construcción apropiada según las reglas anteriores,
  • si un nodo OR aparece bajo un nodo AND, reducir la solución resultante a una lista de cut set creando un cut set separado para cada nodo de entrada de este nodo OR,
  • si todos los nodos corresponden a una causa primaria, detener: borrar los cut set no mínimos.
    •


    Finalmente, los cut set generados son los únicos mínimos. El algoritmo desarrolla sistemáticamente todos los cut set potenciales. Desde un punto de vista lógico, la idea de este algoritmo puede explicarse como un desarrollo de una fórmula DNF mínima que implique el nodo de la cima.

    Grafos dirigidos simples

      Los grafos dirigidos simples representan relaciones mutuas entre fallos y residuos. La construcción básica es un grafo de dos niveles, donde el nivel superior consiste en posibles fallos  y el nivel inferior en posibles residuos (observaciones)  Los fallos apuntan a residuos que (normalmente) son observados si el fallo ocurre. Este tipo de grafos simples se discute en \cite{Frank:94} y \cite{Frank:95}. Una representación esquemática se da en el cuadro siguiente.
    Un grafo como el anterior puede ser representado de forma equivalente por un conjunto de reglas de la forma:

    Si fallo = entonces residuo =,


     


    donde el número de reglas es igual al número de uniones en el grafo. La representación puede ser directa (caso clásico) o difusa, como en [Frank, 1996] y [Frank and Köppen-Seliger, 1995]. Mas adelante se presentan dos formalismos particulares que usan este paradigma.

    Para casos prácticos de aplicación, sin embargo, la interpretación del grafo mediante reglas de inferencia es normalmente ascendente en la dirección de causalidad. Esto significa que las reglas diagnóstico toman la forma:
     


    Si residuo = entonces fallo =es posible


     


    La ocurrencia de un residuo es la indicación específica de un fallo. Además, pueden interpretarse combinaciones de residuos, y pueden aplicarse reglas de inferencia difusa.

    Relaciones de diagnóstico y grafo bipartido de Kö nig

      Siguiendo las consideraciones anteriores, bajo una formulación básica clásica del problema de diagnóstico, se basa en el uso de relaciones de diagnóstico. A pesar de algunos cambios en los símbolos usados en la descripción, el formalismo esta basado en [Koscielny, 1994] y [Koscielny, 1995].
    En este caso se utiliza un conjunto finito y discreto de posibles fallos, . Los elementos de D también se llaman fallos elementales o diagnósticos elementales. Éstos denotan hallazgos finales elementales en el proceso de diagnóstico, tales que su asunción trae consigo el mal comportamiento observado. Desde el punto de vista funcional, cubren fallos en componentes, decisiones de control u operación y eventos externos. También pueden ser considerados como síntomas de entrada si se considera una interpretación causal.
    Además, se especifica un conjunto finito de manifestaciones, . Las manifestaciones se usan para descubrir la ocurrencia de los fallos y empezar el procedimiento diagnóstico; también son llamadas pruebas de diagnóstico o fallos observables. Si se tiene en cuenta una interpretación causal, también pueden ser considerados como síntomas de rendimiento.

    Los elementos de D y M pueden interpretarse como síntomas o eventos; o desde el punto de vista lógico también como proposiciones lógicas. En el modelo básico se supone que pueden tomar sólo dos valores, 0 si el síntoma no ocurre y 1 si se observa como verdadero.

    La relación de diagnóstico es el modelo central usado para el aislamiento de fallos; es de la forma . El significado de  es que el fallo elemental  es la causa de la manifestación , si  ocurre entonces es observada.

    La relación de diagnóstico  puede representarse en forma de matriz de diagnóstico (binaria) o en forma de grafo bipartido de Kö nig [Koscielny, 1994] y [Koscielny, 1995]; el grafo también se denota también como . Un ejemplo de grafo es el siguiente.

    El procedimiento de diagnóstico consiste en el aislamiento de los fallos. Para los valores conocidos de manifestaciones deben encontrarse todos los subconjuntos (mínimos) del conjunto de diagnósticos elementales, tales que asumir que ocurran constituya una explicación satisfactoria de la configuración de manifestaciones observada. Así, un diagnóstico es cualquier conjunto mínimo  tal que , donde  es la forma de manifestación observada que debe ser explicada mediante un diagnóstico. Por ejemplo, si la forma de manifestación observada se define como , entonces los diagnósticos mínimos son ,  y . Asumiendo un solo fallo, el único diagnóstico es .

    El algoritmo diagnóstico constituye una simple pero especifica inferencia abductiva. Puede realizarse de muchas maneras, incluyendo la evaluación sistemática de todos los subconjuntos de D; en este caso sería razonable empezar por subconjuntos de un solo elemento de D y detener el análisis para cualquier subconjunto que cause más manifestaciones que las observadas; por supuesto, para una solución generada que cause exactamente las manifestaciones observadas ningún conjunto superior debe ser analizado.

    Un algoritmo más eficaz puede ser el análisis abductivo del conjunto de manifestaciones observadas. Las siguientes reglas resumen la idea principal:
     

  • Seleccionar una sola manifestación observada como verdadera y examinar sucesivamente el conjunto de manifestaciones,
  • Para cualquiera la manifestación seleccionada construir una lista de causas primarias alternativas; excluir aquellas que serían causas de manifestaciones no observadas,
  • Si se selecciona una nueva manifestación y sus posibles causas son , y  son los diagnósticos temporales actuales, actualizar la lista creando nuevos diagnósticos temporales  y eliminar diagnósticos repetidos y no mínimos.
  • Si el conjunto de manifestaciones inexploradas está vacío, detener; la lista final proporciona todas las soluciones mínimas.
    •


    Este algoritmo es similar al algoritmo del mínimo cut-set presentado anteriormente. De hecho, considerando las manifestaciones como conectadas por puertas AND (todas deben explicarse), y el conjunto de diagnósticos elementales conectado a una manifestación como entradas de una puerta OR, la operación más difícil consiste en reducir el diagnóstico temporal a su forma canónica (de tipo DNF). Una diferencia visible es que admite sólo un nivel de conexiones (ningún nodo intermedio) y la eliminación de ciertos diagnósticos potenciales incoherentes con la observación que ciertas manifestaciones son falsas.

    Modelo Set Covering

      Otro modelo similar es el basado en set covering, inicialmente propuesto en [Reggia et al, 1983], donde el problema de diagnóstico se asume como especificado mediante un conjunto de hallazgos anormales, manifestaciones cuya presencia debe ser explicada mediante otro conjunto de desórdenes, o diagnósticos elementales. Consideremos que M denota el conjunto (potencial) de todas las posibles manifestaciones y D es el conjunto de desórdenes elementales potenciales. Normalmente se supone que . Además, la relación causal entre desórdenes y manifestaciones se expresa mediante alguna relación , donde  significa que  puede causar . Debe decirse que en este caso la relación es un no-determinística, la presencia de  no implica necesariamente que se observe . En otras palabras, la causalidad es débil o del tipo puede.

    Dados estos dos conjuntos y la relación causal, pueden definirse los siguientes conjuntos:
     

    y


    para cualquier  y . El primer conjunto, , denota todas las posibles manifestaciones causadas por desordenes específicos, mientras el segundo, , denota todo los desórdenes alternativos que pueden causar manifestaciones específicas. Finalmente, para un conjunto de manifestaciones observadas dado  tal que , Un problema de diagnóstico se especifica mediante la cuádrupla .

    Ahora se pueden buscar todas las posibles explicaciones. Obviamente, es conveniente considerar sólo las mínimas, tales que ningún subconjunto de ellas sea una explicación del conjunto completo de manifestaciones observadas. Así, dado un problema de diagnóstico, una explicación es un conjunto , tal que  ( D´ cubre o explica totalmente ), y tal que no existe ninguna otra explicación  que satisfaga la condición anterior (D´ es mínimo con respecto a la inclusión). La definición presentada es ligeramente más general que la de [Reggia et al, 1983]; en el articulo original la solución preferida es la mínima con respecto al número de elementos.

    Este tipo de modelo es bastante similar al anterior, basado en relaciones de diagnóstico. La diferencia principal consiste en que admite causalidad débil. Como resultado, puede esperarse un mayor número de diagnósticos potenciales, puesto que los diagnósticos potenciales no se limitan a los que ''encajan exactamente'' con las manifestaciones observadas.

    A destacar también que la solución - en el caso general - no es necesariamente única; varios conjuntos, incomparables con respecto a la inclusión, pueden formar explicaciones mínimas. Consideremos el problema de generación de diagnósticos como un caso específico de inferencia abductiva. Para cualquier manifestación  debe buscarse una lista disyuntiva de posibles causas. Examinando las manifestaciones sucesivamente observadas se generan varios conjuntos. Cada vez que se genera un nuevo conjunto, éste debe combinarse con la solución temporal exactamente como en el modelo anterior. Las soluciones no-mínimas se eliminan totalmente. Cualquier conjunto final de causas iniciales explica totalmente las manifestaciones observadas, y es mínimo. Puede, sin embargo, contener causas primarias que sean causas potenciales de otras manifestaciones que no se observan en el estado actual del sistema.

    Signed directed graphs - SDG

      Este tipo de grafos causales fue establecido para modelar procesos continuos. La idea básica de esta técnica consiste en rastrear los funcionamientos defectuosos observados hacia atrás (origen). Para habilitar este proceso es necesario representar las posibles formas y tipos de propagación de la información. El modelo propuesto toma la de signed directed graph (SDG) y fue propuesto por Kramer y Palowitch; una presentación basada en el articulo original puede encontrarse en [Tzafestas, 1989].

    Un SDG consiste en nodos que representan variables de estado, condiciones de alarma, fuentes de fallos o valores medidos, y ramas (bordes) representando la influencia entre los nodos. La influencia puede ser positiva (' + ') o negativa (' - '). Un nodo puede influir sobre varios de los otros nodos. Cualquier nodo puede ser influenciado por ninguno, uno o varios nodos. También puede especificarse información auxiliar; incluyendo retardos, la intensidad de la influencia, probabilidades, etc.

    La representación es muy simple pero muy intuitiva, y para la supervision y el diagnostico puede resultar satisfactoria en muchos casos. Sin embargo para asegurar un buen funcionamiento, deben aceptarse varias limitaciones:
     

  • el diagnóstico correcto sólo puede obtenerse si cada variable está como maximo en una transición entre los estados cualitativos durante la propagación del fallo; de hecho, se analiza un estado pseudoestacionario, donde las variables cambian de un valor normal al anormal a lo largo del camino de la propagación,
  • se asume que solo un fallo, que influye en un solo nodo raíz, es la fuente de toda las perturbaciones observadas,
  • la ocurrencia del fallo no cambia otros caminos causales en el grafo.
    •


    El grafo causal puede usarse tanto para el modelado de fallos (simulación de propagación fallos) como para el diagnóstico (buscando causas iniciales de los funcionamientos defectuosos observados). De hecho, estas dos actividades son aproximadamente duales (o inversas) . Es necesario asumir fallos en un solo nodo para posibilitar la generación de árboles dirigidos que muestren la propagación del fallo. Normalmente pueden generarse varios árboles desde un solo nodo. Cualquiera de estos árboles constituye una interpretación de propagación del fallo. Normalmente, solo uno de los árboles (o una parte de él) muestra los caminos reales de propagación del fallo, los otros se refieren a posibles interpretaciones que representan posibles comportamientos potenciales. La propagación de fallos involucra la construcción de todo este árbol que representa la posible propagación del fallo. La tarea de diagnóstico consiste en identificar todos los nodos de raíz provistos de valores cualitativos (medidos) de las variables del sistema. La opción típica para estos valores consiste de grande (+1), normal (0) pequeño (-1). Consideremos un grafo simple presentado en la siguiente figura.
     
     



     






    Consideremos que el fallo entra en la red en el nodo A que cambia su valor de normal (0) a alto (+1). Si consideramos que los nodos B y E no son medidos, puede simplificarse el grafo inicial mediante node-lumping a la forma presentada a continuación,; este procedimiento ' elimina ' todas las variables no medidas, asi como las que no tienen ningún interés (excepto como nodos de raíz potenciales, que no es el caso). De hecho, estos nodos no proporcionan nueva información comprobable. Además, se ha eliminado la unión de  a A, puesto que se asume que las perturbaciones positivas son suficientemente importantes para predominar sobre la realimentación negativa. El grafo simplificado resultante se presenta a continuación.
     


    Destaquemos que este grafo todavía contiene una realimentación negativa. Consideremos ahora los posibles caminos de propagación del fallo. Primero, puede propagarse de A a y después a . Simultáneamente, puede propagarse de A a y, a través del lazo cerrado, a . Debido a la asunción de una sola transición de estado, C no puede volver al valor normal por la realimentación. Semejantemente, en esta interpretación no pueden cambiarse a pequeño a normal a través de influencia negativo de . Esta interpretación es muestra a continuación.

    Otra posibilidad consiste en propagación de la fallo desde A a  a través de ,  y . En este camino existe una influencia negativa.
    En el desarrollo de interpretaciones, se trazan caminos hacia abajo desde el nodo raíz hasta los demás, guardando la consistencia con las suposiciones (ninguna variable puede cambiar dos veces o más), y teniendo en cuenta la dirección y el signo de las uniones. Los lazos de realimentación son normalmente eliminados asumiendo que no pueden compensar totalmente la perturbación. Sin embargo, en ciertos casos esto no puede ser verdad; entonces, las interpretaciones que tienen en cuenta el efecto de la realimentación negativa posiblemente cancelan la perturbación en la variable controlada.

    Los árboles de interpretación definen posibles modelos en estado estacionario como ocurrencias de fallos. El fallo, observado como perturbación del valor de la variable, sólo puede propagarse en el árbol hacia abajo, desde nodo de la raíz, según los signos de las uniones. Puede detenerse en algunas variables antes de alcanzar las hojas, sin embargo, debido a la asunción que no puede haber un hueco en el camino de propagación del fallo, si cierta variable en un camino seleccionado es perturbada, entonces todas las variables anteriores también deben ser igualmente influenciadas. Para las dos interpretaciones presentadas, los modelos de propagación de fallo son los de las tablas.
    0 0 0 0
    1 0 0 0
    1 1 0 0
    0 0 1  0
    0 0 1 1
    1 0 1 0
    1 1 1 0
    1 0 1 1
    1 1  1 1
    y
    0 0 0 0
    1 0 0 0
    1 1 0 0
    1 1 -1  0
    1 1 -1 -1
    Los modelos presentados pueden usarse directamente para el diagnóstico. Su uso básico consiste en emparejar alguno de los modelos con las observaciones actuales. Este tipo de aproximación es equivalente a los llamados diccionarios de fallos. Sin embargo, para tablas grandes puede resultar inoportuno guardar todos los datos. Así, una tabla como la anterior puede convertirse en reglas pseudo expertas donde una sola regla puede cubrir varios modelos (o incluso la tabla entera). Un método para convertir tablas en reglas se perfila en [Tzafestas, 1989]. Esta técnica puede resumirse en simular todas los posibles caminos de propagación de fallos (para todas las fuentes potenciales) para generar conjuntos de modelos que cubran los comportamientos posibles, y así crear el diccionario de fallos. Entonces, en base a esa generación de conocimiento de reglas expertas que cubren los casos incluidos en los diccionarios. Una técnica de este tipo, sin embargo, consume tiempo y es computacionalmente costosa. Además, algunos de los modelos nunca pueden ocurrir en la práctica y el conocimiento generado es inútil.

    Sin embargo, tener en cuenta las suposiciones y las interpretaciones generadas en un trazado simple del grafo puede ser un método de diagnóstico eficaz. A saber, descubriendo una variable perturbada (o un conjunto) es necesario remontar atrás hasta la última variable perturbada, que a su vez es la fuente del mal funcionamiento. Además, en la búsqueda directa pueden identificarse fuentes múltiples de errores. De hecho, la estructura del grafo inicial (después del node lumping y la eliminación de lazos cerrados) puede usarse para la construcción de un grafo AND/OR/NOT causal lógico (en práctica no se usará ninguna conexión AND); En Capítulo 7 se presentará una aproximación general basada en estos grafos.