1

4.8 Sistemas Basados en Reglas Los modelos basados en reglas constituyen uno de los paradigmas más populares para la modelización del comportamiento y el control de sistemas complejos, donde es necesaria una representación de conocimiento simbólica, cualitativa, basada en relaciones, etc.. Básicamente, cualquier sistema basado en reglas está compuesto por un conjunto de reglas que definen acciones o conclusiones si se cumplen determinadas condiciones, y un mecanismo de control de inferencia que determina la manera y orden de ejecución de las reglas. Los sistemas basados en reglas son probablemente la herramienta más general y más popular de la Inteligencia Artificial. En el caso de sistemas de supervisión pueden aplicarse a la monitorización y evaluación de situaciones, detección y diagnóstico de fallos y comportamientos no deseados, control jerarquizado, razonamiento sobre el estado y las características del sistema, apoyo a decisiones, etc., En esta sección se presentan los conceptos básicos de los sistemas basados en reglas

Introducción elemental a los sistemas basado en reglas

Un sistema basado en reglas está compuesto, en principio, por dos partes principales: un conjunto de reglas que definen su base de reglas (la parte básica de la base de conocimiento) y el mecanismo apropiado de interpretación de las reglas llamado motor de inferencia. Las reglas definen las variantes del comportamiento mientras que el mecanismo de control de inferencia se encarga de la selección y ejecución de las mismas. En su forma mas popular, el formato de reglas se define como

si < antecedente > entonces < consecuente >

considerandola una inferencia, razonamiento o regla de producción; en la práctica semejante regla es similar o equivalente a la implicación lógica y también es llamada regla si-entonces. El <antecedente> también puede ser llamado condiciones previas, parte condicional, condiciones, etc., mientras que el <consecuente> también puede ser nombrado conclusión, hipótesis, acción, etc., dependiendo a veces del contexto y del significado específico. Si se define una regla: si <antecedente> entonces <consecuente>, entonces <antecedente> = LHS(regla) (parte izquierda), mientras <consecuente> = RHS(rule) (parte derecha). El significado básico de cualquier regla de este tipo es que si las condiciones definidas por el <antecedente> se satisfacen, entonces las conclusiones o acción definidos por el <consecuente> se cumplen o pueden ejecutarse. En ciertos trabajos, el formato básico está a veces extendido, por ejemplo:

si <antecedente> entonces <consequent_1> de lo contario <consequent_2>

En este caso si el <antecedente> es verdad el <consequente_1> se cumple o se realiza (si es una acción), pero si el <antecedente> no es satisfecho, entonces se cumple o se realiza el <consequente_2>.

Son posibles muchas otras extensiones del formato básico. Por ejemplo, aparte de especificar el nombre y la numeración de las reglas, es posible definir lo siguientes elementos adicionales de definición:

Recursos: son los recursos necesarios para ejecutar la acción descrita por una regla. Por ejemplo, en el caso de ejecución de reglas en paralelo, algunas pueden requerir un uso exclusivo de ciertos recursos (pueden bloquear su uso por parte de otras reglas). Esta información puede ser necesaria para el mecanismo de control de inferencia para resolver algunos conflictos potenciales.

Condiciones excluyentes: esta parte proporciona información sobre cuando no puede usarse la certidumbre de la regla. Respecto al hecho que se especifican condiciones previas explícitamente, esto puede introducir cierta información redundante. Sin embargo, en ciertos casos puede ser útil para desestimar algunas o la mayoría de las reglas de una manera simple y eficaz, ya que encontrar que una regla es a veces inaplicable puede ser mucho más rápido. Éste sería el caso de reglas raramente usadas, el uso de las cuales puede ser excluido por una simple condición, un solo hecho.

Retractar-anular resultados: en el caso de sistemas que se modifican dinámicamente puede ser necesario incluir estos cambios directamente en la memoria del sistema; esta parte especifica qué hechos no son verdad después de la aplicación de determinadas reglas y deben retractarse de la base de conocimiento,

Afirmar-agregar resultados: como la anterior, después de la aplicación de una regla, nuevos hechos pueden volverse verdaderos; esta parte de la regla especifica qué hechos deben afirmarse en la base de conocimiento después de la aplicación exitosa de la misma,

Acciones: en el caso que las reglas de control, esta parte especifica las acciones u operaciones que deben ser realizadas.

Informes: en sistemas de monitorización y supervisión con operadores humanos puede ser útil especificar una parte adicional que contenga mensajes para éstos. La información dada, enviada a la consola o a un archivo, puede estar parametrizada, conteniendo algún conocimiento o incluso los parámetros actuales del proceso.

regla(s) siguiente(s): en ciertos casos, después de la aplicación de alguna regla puede ocurrir que la próxima regla (o reglas) candidata(s) a ser aplicada(s) sea muy probable (o incluso seguro). Así, puede ser razonable especificar esta regla (estas reglas) explícitamente, para permitir al mecanismo de control del razonamiento cambiar el orden de examen de las reglas. Esta especificación puede acelerar la ejecución de las reglas significativamente, y así mejorar el rendimiento total del sistema.

Son posibles muchas otras modificaciones y extensiones; sin embargo estas no cambian el concepto básico de las reglas si-entonces, sino que constituyen algún mecanismo auxiliar conveniente en aplicaciones prácticas.

Mecanismo básico de ejecución de reglas

En el esquema presentado de reglas de producción la parte de las condiciones previas se especifica mediante una fórmula lógica, expresión de representación de conocimiento atributiva, expresión cualitativa o incluso formulación lingüística. Sin tener en cuenta el lenguaje, las condiciones previas especifican todas las condiciones necesarias para que la regla se aplique. Simultáneamente, especifican todos los estados en los que la regla de producción es aplicable. Cualquiera de los componentes de la regla puede contener parámetros, variables para "ajustar" la regla al estado actual y propósitos. Los valores de las variables pueden encontrarse mediante un mecanismo de emparejamiento durante el proceso de comprobar si la regla puede aplicarse, o pueden ser dadas por un mecanismo de control superior, por ejemplo un objetivo definido por el usuario.

Desde punto de vista lógico pueden considerarse todas las variables en una regla como universalmente cuantificadas, como en el caso de cláusulas en Prolog. Sin embargo, las variables denotan parámetros a ser instanciados antes de la aplicación de la regla. Esto significa, de hecho, que cualquier regla con variables denota un conjunto de (o un esquema general de) reglas aplicables. Los valores precisos pueden ser seleccionados por el usuario y entonces se demuestran las condiciones previas, o - y éste es el enfoque más frecuente - se encuentran los valores de las variables para los que las condiciones previas se cumplen durante el proceso de demostracion de éstas, como un efecto secundario del procedimiento de emparejamiento.

Asumamos que una regla dada tiene la forma básica, si <antecedente> entonces <consecuente>, donde el <antecedente> es equivalente a una fórmula simple. Supongamos que el estado actual de la base de conocimiento se describe mediante fórmulas lógicas simples, proporcionando una conjunción de todos los hechos actualmente verdaderos. Sea h la fórmula (o acción) que define el <consecuente>. Todos los componentes pueden ser parametrizados mediante ciertas variables. El algoritmo básico de ejecución de la regla es:

Chequear si las condiciones previas de la regla se satisfacen; en ese caso buscar los valores apropiados de los parámetros de la regla. Desde el punto de vista lógico este chequeo es equivalente a encontrar una substitución tal que Æ , las condiciones previas provienen lógicamente (emparejamiento generalizado) del estado actual de la base de conocimiento. Si es posible, proceder, en caso negativo la regla no puede aplicarse.

Llegar a la conclusión (o aplicar la acción de control apropiada). La substitución define los valores de los parámetros (si es el caso).

Devolver el control al mecanismo de control de inferencia (motor de inferencia).

En el caso de que la regla tenga una estructura extendida, las extensiones específicas deben interpretarse de la manera apropiada, si embargo, estas extensiones son bastante directas. El único problema práctico es aplicar de forma consistente la substitución encontrada () en cualquier fase. La generación de la substitución puede ser realizada por cualquier procedimiento de emparejamiento de formas; los más directos pueden ser los basados en un esquema de unificación lógico.

Inferencia en sistemas basado en reglas

La inferencia en sistemas basados en reglas esta basada en la lógica. Básicamente, el esquema de las reglas es similar a la implicación en sintaxis y en semántica. La aplicación de cualquier regla, siendo el paso básico de cualquier paradigma de razonamiento, es así análoga al modus ponens. El chequeo de satisfacción de la condición previa es un caso específico de emparejamiento de formas; de hecho también es un emparejamiento de términos o de condiciones previas. Como la aplicación de una sola regla ya se ha descrito en la subsección anterior, aquí nos centraremos en los problemas que involucran aspectos más avanzados de la inferencia basada en reglas. En primer lugar el llamado problema de resolución de conflictos.

Consideremos un sistema dinámico compuesto de n reglas. El problema de resolución de conflictos puede declararse como: dado un conjunto de n reglas, si dos o más reglas son potencialmente aplicables, seleccionar una sola regla para ser aplicada en el estado actual del sistema bajo control/supervisión. El problema de la resolución de conflictos no existe en sistemas deterministicos, para los que sólo una regla puede aplicarse en cualquier estado. El problema ocurre si para algún estado puede aplicarse más de una la regla; en la mayoría de sistemas se selecciona una sola regla con respecto a algún criterio auxiliar, diferente del consistente en que satisfagan las condiciones previas. Dependiendo de la complejidad de la estructura del mecanismo de control de inferencia son posibles dos formulaciones, una básica y otra avanzado.

La formulación básica es como sigue. Considérese un sistema de control basado en reglas compuesto de n reglas. Supongamos que las reglas están linealmente ordenadas según un índice. El problema de la resolución de conflictos consiste ahora en seleccionar exactamente una regla aplicable en el estado actual. La regla seleccionada debe aplicarse y el proceso repetirse desde el principio.

Las estrategias básicas para atacar el problema anterior pueden variar dependiendo de la especificación del sistema y de la aplicación. Hay, sin embargo, dos posibilidades básicas:

puede seleccionarse primero una regla apropiada para lograr el objetivo deseado y luego puede intentarse satisfacer sus condiciones; este enfoque se aplica principalmente en sistemas de planificación,

pueden probarse secuencialmente las reglas mediante la satisfacción de sus condiciones previas, y la primera cuyas condiciones previas sean satisfechas (y destinada a la tarea específica de interés, sobre todo si se especifican requisitos adicionales) se selecciona y se ejecuta.

Principalmente en control y supervisión se aplica el segundo enfoque. Con respecto a la organización del intérprete de reglas pueden distinguirse tres estrategias básicas de atacar el problema:

las reglas se ordenan linealmente y la satisfacción de sus condiciones previas se prueba secuencialmente en un lazo cerrada; después de la regla i, se prueba la regla número i+1 y posiblemente se ejecuta, y después de la regla n se prueba la regla 1 (ejecución lineal),

se asume una jerarquía entre las reglas; las reglas se prueban secuencialmente según su jerarquía hasta que se encuentra una cuyas condiciones previas se satisfacen - entonces la regla se ejecuta y el proceso se reanuda en la regla 1 (ejecución jerárquica),

se preselecciona un subconjunto del conjunto inicial de reglas y se ordena de nuevo según algunas de prioridades (dependiendo de contexto); las reglas se inspeccionan entonces con respecto a cualquiera de los dos esquemas anteriores.

Por supuesto, los enfoques anteriores pueden modificarse y extenderse con el uso de mecanismos de control de razonamiento auxiliares, herramientas de preselección de reglas, etc., Por ejemplo, un mecanismo útil lo constituye una modificación que consiste en la utilización de un mecanismo para el cambio jerárquico de valores dependiendo del contexto mediante el uso de una pila de memoria.

La forma avanzada de declaración del problema de resolución de conflictos incluye la selección del conjunto de conflictos y la selección y ejecución de regla/reglas posiblemente pasando el control a otros mecanismos. De nuevo, consideremos un sistema compuestos de n reglas, . La formulación avanzada de la tarea de resolución de conflictos consiste en seleccionar reglas que satisfagan las condiciones y, si hay dos o más reglas, seleccionar una de ellas que satisfaga algún criterio auxiliar. Este enfoque consiste en dos fases: (1) eliminación inicial de las reglas que no pueden aplicarse, y (2) selección de la mejor regla, o probablemente la mas apropiada para realizar la tarea del control en curso. Para el caso avanzado, pueden establecerse varias clasificaciones de estrategias de resolución de conflictos:

Estáticas vs. Dinámicas; las estrategias estáticas están basadas en criterios constante en el tiempo, mientras que las dinámicas pueden tener en cuenta el contexto, tiempo, el número de repeticiones(exitosas) de una regla, etc.,

Sintácticas vs. Semánticas; las primeras se basan en "la forma" de las condiciones previas de la regla, mientras que las segundas pueden tener en cuenta el contexto actual, el objetivo deseado, y evaluar criterios especificados por el usuario,

Directas vs. Indirectas; las directas se basan en la comparación simple de reglas y la assignación de "factores de orden", prioridades, mientras que las estrategias indirectas pueden llevarse a cabo mediante sistemas basados en conocimiento auxiliar, meta-reglas y esquemas complejos de inferencia,

Basadas en criterios simples preespecifcados vs. Modificables, adaptables, y basadas en mecanismos de aprendizaje.

Dependiendo del problema, de su especificación y de los recursos disponibles pueden aplicarse varias estrategias; no puede darseningún criterio general. Las combinaciones de varias estrategias también pueden ser útiles.

Algunas estrategias para la resolución de conflictos

En esta sección se perfilan brevemente algunas estrategias seleccionadas para la resolución de conflictos. Una buena visión global de algunos de los enfoques más populares para sistemas de control puede encontrarse en la literatura sobre problema; a continuación se listan estrategias:

Ordenamiento de reglas (la regla que aparece antes tiene la prioridad más alta),

Ordenamiento de datos (la regla cuyas condiciones tengan asignada la prioridad más alta tiene la prioridad más alta),

Ordenamiento de tamaño (la regla con la lista más larga de condiciones restrictivas tiene la prioridad más alta),

Ordenamiento de especificidad (se ordenan las reglas cuyas condiciones provienen de otras reglas),

Limitación del contexto (consiste en poder activar o desactivar grupos de reglas en cualquier momento para reducir la ocurrencia de conflictos).

Los dos primeros enfoques se dirigen hacia estrategias de clasificación directas, estáticas. El tercero y el cuarto se refieren a casos específicos de clasificación de posibilidades principalmente mediante mecanismos de evaluación de prioridades basados en sintaxis. Sólo el quinto se refiere a la semántica del proceso, pero se usa para reducir el número de reglas en conflicto y no para seleccionar una única regla.

Por ejemplo, en el sistema de programación basado en reglas OPS5 [Brownston et al, 1985] pueden usarse dos estrategias más complejas, LEX y MEA. A grandes rasgos, estas estrategias se llevan a cabo en cuatro pasos consecutivos: refracción (anulando todas las instanciaciones ejecutadas previamente), clasificación parcial basada en reciente actualidad (se consideran etiquetas de tiempo correspondientes a los elementos de memoria de trabajo usados), clasificación parcial basada en especificidad (se consideran primero las reglas con mayor número de pruebas), y, finalmente, la selección arbitraria. La estrategia de la MEA considera más importante la actualidad de la primera condición de las reglas. Estrategias de este tipo pueden ser útiles para la programación basada en reglas pero pueden ser poco satisfactorias o incluso inadmisibles para el control de sistemas dinámicos. Por ejemplo, la estrategia de refracción puede eliminar alguna instanciación ejecutada previamente, mientras que la repetición de exactamente la misma regla puede ser necesaria para lograr cierto objetivo a través de movimientos similares.

Inferencia hacia delante vs. inferencia hacia atrás

Dos direcciones básicas de inferencia son teóricamente posibles: el encadenamiento hacia adelante, o inferencia dirigida por datos, y el encadenamiento hacia atrás, o inferencia dirigida por los objetivos. Dependiendo del problema particular, sus características y el tipo de reglas aplicadas el usuario puede seleccionar a veces la dirección del razonamiento teniendo en cuenta el objetivo de inferencia.

La inferencia del encadenamiento hacia delante puede aplicarse prácticamente en todos los casos. Es útil si hay relativamente pocos hechos iniciales, deben producirse nuevos hechos, el objetivo se especifica poco o no se especifica en absoluto, etc. El encadenamiento hacia delante normalmente produce hechos bien definidos.

El encadenamiento hacia atrás es un poco más complicado; no puede aplicarse en cualquier sistema. Si las reglas tienen más variables en las condiciones previas que en las conclusiones, probablemente se generaran hechos no totalmente especificados. Aún más, la estrategia es un poco más compleja, ya que es necesario que se cumplan todos los hechos en cualquier fase para demostrar un objetivo. Este tipo de inferencia es sin embargo más eficaz cuando el objetivo esta bien definido y hay muchos hechos de entrada. Esta estrategia también se usa en ciertos sistemas, como Prolog.

También pueden aplicarse combinaciones de los dos modos. La estrategia más típica es combinar una estrategia hacia delante y la aplicación el encadenamiento hacia atrás en algunas fases si deben detallarse algunos objetivos.

Modelos de intérpretes de reglas Aun en el caso de intérpretes simples que seleccionan y ejecutan una sola regla simultáneamente, hay varias posibilidades de organizar el trabajo. Asúmase una sucesión lineal de reglas se especifica de la forma

. Los esquemas de interpretación pueden proceder como sigue:

Ejecución lineal con la selección consecutiva de todas las reglas ejecutables que se ejecutan sucesivamente; así después de encontrar y ejecutar una sola regla, se examinan y se ejecutan las próximas reglas sucesivamente. Sólo después de alcanzar la última regla el sistema vuelve al principio. En Prolog este esquema correspondería al formato de lazo repeat-find-execute-fail. En las listas de decisión este modo de trabajo corresponde a una organización lineal de la lista. Este tipo de interpretación se realiza normalmente en tablas de decisión.

Interpretación jerárquica desde el principio a la primera regla ejecutable (con condiciones previas satisfechas); entonces el sistema vuelve inmediatamente al principio y repite el ciclo. En Prolog esto correspondería a run-find-execute-run. Este tipo de interpretación es similar al proporcionado en listas de decisión jerárquicas.

Interpretación lineal con cambio de reglas. Interpretación lineal desde el principio a la primera regla ejecutable (con condiciones previas satisfechas); entonces el sistema salta a la reglas indicadas por la regla recientemente ejecutada. Este tipo de esquema equivale a intercambiar las reglas dentro de la base de reglas. Hay también varias posibilidades de interpretación posterior: las nuevas reglas pueden dirigir el sistema a otras reglas o después de ejecutarlas el sistema puede saltar hacia atrás o al lugar de donde salió o al principio. Puede no haber ninguna opción de retorno, y el sistema puede seguir una interpretación lineal después de ejecutar (o no) la regla a la que saltó.

Examen lineal con contexto cambiante; el examen lineal puede combinarse con contexto cambiante, es decir, después de que alguna regla se ejecute, la situación del sistema se evalúa, se determina el contexto (situación cualitativa) y un mecanismo de decisión cambiar a un conjunto diferente de reglas destinadas a este contexto.

A continuación se presentan esquemáticamente los tipos anteriores de intérpretes.

Aplicaciones genéricas de reglas de inferencia

Permítanos presentar tres problemas básicos que pueden enfocarse mediante el uso de los sistemas de reglas de inferencia presentados anteriormente. Los problemas se refieren al modelado del comportamiento de un sistema (en otras palabras, simulación del comportamiento), control directo de un sistema (o meta-control), y generación de planes (síntesis de control). Los problemas pueden formularse a grandes rasgos como sigue:

Simulación: Consideremos un sistema dinámico relacional. Se da un conjunto fijo finito de reglas T de producción que definen las transformaciones para el modelado de todos los cambios de estado posibles. Dado un estado inicial , encontrar el posible comportamiento del sistema para un número limitado de fases de transformación. En el caso de simulación puede interesar obtener cualquier posible comportamiento (para cualquier sucesión admisible de reglas de transformación y parámetros), o sólo algunas de las posibles trayectorias que se generan con un poco de información adicional que involucra qué reglas y qué parámetros deben ser considerados en cualquier fase. Este tipo de acercamiento es llamado simulación basada en conocimiento y si se aplica un formalismo cualitativo simulación cualitativa.

Control: Supongamos que se observa un sistema dinámico relacional en instantes discretos de tiempo. En cualquier instante, la fórmula de estado del sistema es conocida, así como el objetivo de control (si se especifica explícitamente). En la práctica, la fórmula que define el objetivo actual puede ser una parte de la fórmula de estado. La tarea es construir un sistema del control basado en conocimiento, diseñar un conjunto fijo de reglas T para ser aplicado al estado actual en un instante determinado y asegurar el comportamiento deseado del sistema controlado. El conjunto de reglas debe llevarse a cabo de forma que por lo menos para cualquier estado sea aplicable una acción (incluso la acción no-hacer-nada, si es necesario). Si en cierto estado son aplicables más de dos acciones, o una acción es aplicable de maneras diferentes (para parámetros diferentes dados por ), también debe proporcionarse un mecanismo de control de razonamiento para la resolución de conflictos. Este tipo de sistema basado en reglas puede usarse para el control directo (control directo basado en reglas, control reactivo) o puede aplicarse en un meta-nivel de control, por ejemplo para la selección de parámetros y consignas, selección del algoritmo de control, ajuste del modelo o del objetivo, etc. La aplicación a la monitorización de procesos, reconocimiento de situaciones, y supervisión (incluso detección de fallos, diagnostico y soporte a decisiones) puede localizarse dentro de este tipo de aplicaciones.

Planificacion: Como en el caso de simulación, consideremos un sistema dinámico relacional. Se da un conjunto fijo finito de reglas T de producción para modelar todas las posibles transformaciones de estado (de hecho son reglas de transformación de estado). Dado un estado inicial y un objetivo deseado , buscar una sucesión de acciones (junto a sus parámetros) que transformen el estado inicial en otro que satisfaga las condiciones declaradas en el objetivo; el estado del objetivo puede definirse de una manera más general, pueden especificarse sólo algunos requisitos explícitamente y así puede existir más de un estado que satisface las condiciones del objetivo.

Aunque aquí se traten principalmente los problemas de monitorización, control y supervisión basados en conocimiento, el propio formalismo y ciertos resultados se aplican directamente a los casos de simulación y planificación. Es más, el formalismo presentado puede aplicarse en otros problemas resueltos mediante enfoques de ingeniería del conocimiento, como diagnóstico automatizado, apoyo de decisiones, diseño asistido por ordenador y otros.