Representación Basada en reglas
6.1 Objetivo de la práctica
En las prácticas anteriores se plantearon
los problemas de búsqueda como un sistema de producción que
consistente en:
Al igual que en la anterior práctica, para aprender a programar en CLIPS es muy interesante estudiar programas que han creado otras personas. Tras una breve introducción a CLIPS, se presenta la implementación de un problema clásico de búsqueda. En concreto se implementa el problema de las garrafas simplificado.
El programa es completado en tres etapas que permiten ir asimilando las características de un lenguaje basado en reglas como CLIPS. Esta introducción a CLIPS a través del ejemplo de las garrafas está inspirado en el curso "Knowledge Based Engineering" de Edward S. Blurock disponible en http://info.risc.uni-linz.ac.at/people/blurock/courses/expert/expert.html.
El índice de la práctica es el siguiente:
CLIPS soporta tres tipos de paradigmas de programación: basado en reglas, orientado a objeto, y procedural. El lenguaje de programación procedural es sintácticamente muy parecido a LISP. El lenguaje orientado a objeto, denominado COOL (Clips Object Oriented Languaje), es muy parecido a CLOS (Common Lisp Object System), aunque en realidad incorpora características de otros lenguajes como SmallTalk. En ésta práctica nos centraremos en el lenguaje basado en reglas de CLIPS.
Las componentes básicos al representar el conocimiento en un sistema basado en reglas como CLIPS son:
Memoria de trabajo: Contiene los datos que representan el estado, y sobre los cuales se van a hacer inferencias (aplicación de operadores).
Memoria de producción: Conjunto de reglas (operadores) que se expresan mediante sentencias de la forma: IF precondición - THEN acción
El motor de inferencia ejecuta este ciclo repetidamente
hasta que no haya reglas en el conjunto conflicto o se detenga el sistema
explícitamente (predeterminando el número de ciclos que se
van a ejecutar, o mediante una instrucción de parada en la parte
acción de una regla).
6.3 Representación de hechos
La memoria de trabajo contiene una lista de hechos,
que son los datos con los cuales se puede razonar. Los datos de la memoria
de trabajo definen el estado del proceso de razonamiento. Cada hecho consta
de un nombre de relación seguido de cero o más atributos
con sus valores asociados. Por ejemplo para representar la información
de una persona:
La especificación del tipo de atributos puede ser ?VARIABLE, SYMBOL, STRING, LEXEME, INTEGER, FLOAT, o NUMBER. VARIABLE? indica que el atributo puede contener cualquier tipo de dato; LEXEME que el dato puede ser SYMBOL o STRING; y NUMBER que el dato puede ser INTEGER o FLOAT?.
Se puede restringir los valores permitidos en un atributo mediante allowed-symbols, allowed-strings, allowed-lexemes, allowed-integers, allowed-floats, allowed-numbers, y allowed-values. También es posible especificar un rango numérico mediante los valores mínimo y máximo mediante (range <mínimo> <máximo>), y la cardinalidad indicando el mínimo y máximo número de valores mediante (cardinality <mínimo> <máximo>) (?VARIABLE indica que no hay máximo o mínimo).
Si no se especifica el valor por defecto, se asume (default ?DERIVE), que especifica que como valor del atributo se derivará uno que cumpla con las restricciones impuestas. En el ejemplo de plantilla que se expone a continuación, si no se especifica otra cosa el atributo estado civil será soltero (el primero de la lista de valores permitidos).
Default también puede ir seguido de cualquier expresión cuyo valor será utilizado como valor por defecto; o seguido de ?NONE para indicar que no existe valor por defecto y que no se derivará ningún valor.
El estado de la memoria de trabajo puede ser alterado añadiendo nuevos hechos, y eliminando o modificando hechos de la lista. La instrucción (fatcs) visualiza la lista de hechos, y las siguientes instrucciones permiten modificar el estado de la memoria de trabajo:
La memoria de producción está constituida por reglas. Las reglas representan el conocimiento sobre la resolución de problemas de un dominio específico incluyendo reglas físicas, conocimiento heurístico o reglas de experiencia.
Por ejemplo, consideremos los hechos y reglas que necesitariamos para monitorizar y responder a posibles emergencias en un edificio. Informalmente podemos expresar el conocimiento mediante reglas de la siguiente forma:
SI la emergencia es incencio
ENTONCES la respuesta es activar
los extintores de incendios.
Para convertir esta representación informal del conocimiento en reglas se deben definir primero los tipos de hechos a los que se refiere la regla. Una emergencia puede ser descrita mediante la siguiente plantilla:
La parte condición de una regla, también denominada precondición, antecedente, o parte izquierda de la regla (Left-hand side, LHS), consta cero o más elementos condicionales (EC). El elemento más simple de EC es un simple patrón. Cada patrón consiste en una o más restricciones sobre el valor de alguno de los atributos de una hecho. En la regla emergencia-incendio, el patrón es (emergencia (tipo incendio)). La restricción sobre el atributo tipo indica que esta regla sólo será satisfecha por hechos creados con la plantilla emergencia que contengan el símbolo incendio en el atributo tipo.
CLIPS intenta encajar (reconocer) los patrones de las reglas con todos los hechos en la memoria de trabajo. Si todos los patrones de la regla reconocen hechos de la memoria de trabajo, la regla está activa y es puesta en la agenda. La agenda contiene la lista de reglas activadas. Es importante notar que una misma regla puede estar activada por combinaciones diferentes de hechos, por lo que puede aparecer varias veces en la agenda. A cada posible activación de una regla se la denomina instancia de la regla.
Sin una regla no tiene precondición se considera que tiene el patrón (initial-fact) implícitamente, de forma que toda regla sin precondiciones será activada al ejecutarse la instrucción (reset).
6.4.2 Reconocimiento de patrones
Hasta ahora hemos visto patrones muy simples. Como en otros lenguajes, CLIPS tiene variables para almacenar valores. Por convenio, todo identificador de una variable es precedido por el carácter ?, como por ejemplo ?color, ?nombre, ?valor.
Un primer uso de las variables es ligar una variable a un valor en la parte izquierda de una regla y usar el valor posteriormente en la parte derecha. Por ejemplo:
De paso, observa el uso de la función printout para escribir mensajes por la pantalla. crlf produce un salto de línea. La instrucción (run) ejecuta las reglas instanciadas.
El segundo uso de las variables consiste en utilizar la misma variable en múltiples lugares en la parte izquierda de una regla. La primera aparición de la variable liga un valor a dicha variable, y este valor es retenido para el resto de apariciones en la regla. De esta forma podemos definir relaciones entre los patrones de la parte izquierda de una regla, y definir restricciones adicionales.
Siguiendo con el ejemplo anterior, podemos asertar un hecho que indique que color de ojos buscar:
CLIPS permite especificar patrones más sofisticados, así como funciones para manipular hechos en las reglas. Cabe destacar las siguientes posibilidades:
Ligar un hecho a una variable
La modificación, eliminación y duplicación de un hecho son operaciones frecuentes. El operador "<-" permite ligar un hecho a una variable. Un hecho ligado a una variable puede ser manipulado mediante las funciones modify, retract y duplicate. Por ejemplo:
Algunas veces es útil comprobar la existencia de un valor en un atributo sin necesidad de ligar el valor a ninguna variable. Para ello utilizaremos el símbolo "?", que puede ser visto como un comodín que reconoce cualquier valor. Por ejemplo:
Podemos representar patrones que reconozcan hechos que no tengan un determinado valor en un atributo, o que tengan alguno de los valores que se especifican. Los operadores operador ~, | y & cumplen este propósito. Por ejemplo
El operador & se utiliza en realidad en combinación con los anteriores para ligar valor a una variable. Por ejemplo
Un elemento condicional puede evaluar una expresión, en lugar de representar un patrón que debe ser reconocido. Por ejemplo, para comprobar que la variable ?edad es mayor que 18 se puede representar mediante (test (> ?edad 18)).
Función bind
Si queremos ligar un valor a una variable para utilizarlo en varios sitios sin tener que recalcular el valor podemos hacerlo con la función bind. Por ejemplo:
(bind ?suma (+ ?a ?b))
Combinación de elementos condicionales con And, Or, y Not
Para que una regla este activada todos los elementos condicionales de la precondición deben reconocer hechos de la memoria de trabajo. Por lo tanto, hasta ahora todas la reglas vistas tienen un and implícito entre los elementos condicionales. CLIPS ofrece la posibilidad de representar and y or explícitos, así como la posibilidad de indicar mediante not que una regla será activada si no existe ningún hecho reconocido por un patrón.
En el siguiente ejemplo, en lugar de tener dos reglas que tienen la misma acción, se puede representar mediante una única regla que se activará si existe una emergencia de tipo inundación o si se han activado los aspersores del sistema de extinción de incendios.
Las reglas que están activadas son incluidas en la agenda. En principio todas las reglas de la agenda serán ejecutadas, pero la ejecución de una regla puede desactivar reglas de la agenda al modificar hechos de la memoria de trabajo. Además, si hacemos la comparación con un problema de búsqueda, los nodos a expandir son las reglas en la agenda. Desde este punto de vista, la ejecución de una regla da lugar a nuevas ramas (nuevas instancias de reglas en la agenda).
Por todo lo dicho anteriormente será importante el orden en el que se ejecuten las reglas de la agenda. Los criterios de ordenación de la agenda constituyen la estrategia de control.
CLIPS ofrece varias estrategias para ordenar la agenda:
6.6 Utilidades CLIPS
Las siguientes instrucciones te serán de utilidad:
Para comprender como se representa un problema de búsqueda en un sistema basado en reglas como CLIPS, vamos a tratar el problema de las garrafas simplificado. El problemas consiste en llenar una garrafa de 3 litros con sólo dos operaciones, añadir un litro y añadir 2 litros. Utilizando la estrategia por defecto de CLIPS para ordenar la agenda, que es en profundidad, se presenta distintas etapas del desarrollo hasta llegar a un programa completo que realiza la búsqueda en anchura.
La plantilla utilizada para representar cada uno de los posibles estados de la garrafa es:
(deftemplate
estado
(slot garrafa
(type INTEGER)
(default 0)))
Para definir el estado inicial utilizaremos la siguiente regla:
;
El estado inicial
(defrule
Estado-Inicial
?inicial
<- (initial-fact)
=>
(printout
t "El estado inicial es la garrafa vacia"
crlf)
(assert
(estado (garrafa 0))))
Las reglas que
representan los operadores son:
;----------------------------------------------------------------
;
Regla para agnadir un litro a la garrafa
(defrule
Agnade-Un-Litro
?estado <- (estado
(garrafa ?cantidad))
=>
(printout t "Agnadiendo 1 litro a " ?cantidad " quedando "
(+ 1 ?cantidad) " litros" crlf)
(modify ?estado (garrafa (+ ?cantidad 1))))
;----------------------------------------------------------------
;
Regla para agnadir dos litros a la garrafa
(defrule
Agnade-Dos-Litros
?estado <- (estado
(garrafa ?cantidad))
=>
(printout t "Agnadiendo 2 litros a " ?cantidad " quedando "
(+ 2 ?cantidad) " litros" crlf)
(modify ?estado (garrafa (+ ?cantidad 2))))
La regla para detectar el estado final es:
;----------------------------------------------------------------
;
Regla para detectar tarea realizada (Es decir la garrafa tiene 3 litros).
(defrule
Hecho
?estado <- (estado
(garrafa 3))
=>
(printout t "Hecho - La garrafa tiene tres litros." crlf))
El fichero garrafa1.clp contiene las reglas anteriores. Para ejecutar el programa carga el fichero con la instrucción (load "garrafa1.clp"). A continuación ejecuta (reset) para que se creen los hechos definidos con deffacts, o bien se active la regla encargada de definir el estado inicial. La instrucción (run) puede ir seguida por el número de ciclos de inferencia que se quieren ejecutar. El resultado de la ejecución del programa es el siguiente:
Encontrarás la solución a los problemas planteados anteriormente en el fichero garrafa2.clp. En este segundo programa se implementa la búsqueda en anchura.
Primero se asigna mayor prioridad a la regla Hecho, de forma que cuando ésta esté instanciada se coloque la primera en la agenda. Con esto conseguimos que el programa nos avise de que se ha alcanzado el objetivo. Pero como sigue habiendo reglas instanciadas no terminará la ejecución. Para solucionarlo se elimina el hecho estado de la memoria de trabajo:
;----------------------------------------------------------------
;
Regla para detectar objetivo, es decir garrafa con 3 litros.
;
Tiene la prioridad alta para que si es activada se ejecute.
;
(defrule
Hecho
(declare (salience 1000))
?estado <- (estado
(garrafa 3))
=>
(printout t "Hecho - La garrafa tiene tres litros." crlf)
(retract ?estado))
Todavía no tenemos resuelto el problema. Si no hay ningún criterio para decidir entre dos instancias de reglas distintas se coloca antes en la agenda la que esta declarada primero. La regla Agnade-Dos-Litros no ha sido ejecutada en ningún momento. Si hubiesemos declarado esta regla antes que la regla Agnade-Un-Litro se hubiera ejecutado siempre la regla Agnade-Dos-Litros.
En este caso no habríamos encontrado la solución y el programa no se detendría nunca. Con este programa no se hace la búsqueda de forma adecuada ya que sólo tenemos un estado para expandir en cada paso, sólo podemos explorar una rama del árbol de búsquedas, y además no guardamos la historia de las acciones realizadas.
Podemos implementar la búsqueda en anchura manteniendo un hecho (profundidad ?) que indique el nivel de profundidad alcanzado en la búsqueda. De esta forma podemos expandir los hechos de la profundidad en curso para crear los del siguiente nivel. Todos los hechos del nivel en curso se expanden antes que los hechos del siguiente nivel. Esto es llevado a cabo por la regla actualiza-profundidad, la cual (debido a su baja prioridad) será llamada después de que todos los estados de un nivel han sido tratados. La regla incrementa el nivel de profundidad modificando el valor del hecho (profundidad ?). De esta forma se activan las reglas para expandir los nodos del siguiente nivel de profundidad.
La plantilla estado debe considerar el nivel de profundidad del nodo representado:
(deftemplate estado
(slot garrafa
(type INTEGER)
(default 0))
(slot profundidad ; Profundidad del nodo en el arbol
(type INTEGER)
(default 0)
(range 0 ?VARIABLE)))
La regla que define el estado inicial crea el hecho profundidad, que inicialmente es cero, y el nodo inicial:
(defrule
Estado-Inicial
?inicial <- (initial-fact)
=>
(printout t "El estado inicial es la garrafa vacia" crlf)
(assert (profundidad 0))
(assert (estado (garrafa 0) (profundidad 0))))
Las reglas que definen los operadores se modifican de forma que se expandan los nodos del nivel de profundidad en curso antes de considerar los del siguiente nivel:
(defrule
Agnade-Un-Litro
(declare (salience 500))
?estado <- (estado (garrafa ?cantidad)
(profundidad ?profundidad))
(profundidad ?nivel)
(test (= ?profundidad ?nivel))
=>
(printout t "Agnadiendo 1 litro a " ?cantidad " para llegar a "
(+ 1 ?cantidad) " litros" crlf)
(assert (estado (garrafa (+ ?cantidad 1))
(profundidad (+ ?profundidad 1)))))
Para completar la estrategia de búsqueda en anchura se utiliza la regla actualiza-profundidad, que actualizará el nivel de profundidad cuando no queden más nodos que expandir del nivel en curso:
;----------------------------------------------------------------
;
Regla para actualizar la profundidad
;
Llamada solo si se han expandido todos los nodos de un nivel
;
(Por lo tanto prioridad mas baja)
;
(defrule
actualiza-profundidad
(declare (salience 100))
?profundidad <- (profundidad ?nivel)
=>
(retract ?profundidad)
(assert (profundidad (+ 1 ?nivel))))
Inicializa el sistema ejecutando (clear). A continuación carga el fichero garrafa2.clp, y comprueba su funcionamiento ejecutando paso a paso el programa y visualizando la agenda y la memoria de trabajo.
Para finalizar vamos a mejorar el programa de forma que escriba el camino de la solución encontrada. El programa encontrará todas las soluciones hasta el nivel de profundidad indicado por el hecho (maxima-profundidad ?). Se finalizará la ejecución si no quedan más nodos por expandir, o se sobrepasa el nivel de profundidad indicado. El programa garrafa3.clp realiza las tareas anteriores. En el programa se redefine la plantilla del estado, de forma que se guarda en un atributo el padre del nodo, y en el atributo operacion se registra la operación realizada para alcanzar el nodo desde su nodo padre. Observa que el hecho profundidad tiene dos valores, el primero registra la profundidad en curso, y el segundo el número de nodos expandidos hasta el nivel en curso.
Fíjate en la regla FIN, que detecta el fin de la búsqueda si no hay nuevos nodos que expandir, y en la regla Incrementa-cuenta-nodos, que actualiza la cuenta de nodos cada vez que es creado un nodo nuevo:
;*******************************
;*
PLANTILLAS *
;*******************************
;----------------------------------------------------------------
;
la cantidad de agua en la garrafa
;
(deftemplate
estado
(slot garrafa
(type INTEGER)
(default 0))
(slot profundidad
; Profundidad del nodo en el arbol
(type INTEGER)
(default 0)
(range 0 ?VARIABLE))
(slot nodo
(type INTEGER)
(default 0)) ;
Numero de nodo en el arbol
(slot padre
; Nodo padre
(type FACT-ADDRESS SYMBOL)
(allowed-symbols no-padre))
(slot operacion
; Descripcion del movimiento
(type STRING)))
;******************************
;*
ESTADO INICIAL *
;******************************
;----------------------------------------------------------------
;
El estado inicial
(defrule
Estado-Inicial
?inicial <- (initial-fact)
=>
(printout t "El estado inicial es la garrafa vacia" crlf)
(assert (profundidad 0 0)) ;0
profundidad 0 nodos
(assert (estado (garrafa 0) (profundidad 0) (padre no-padre)
(operacion "No moviento")))
(assert (maxima-profundidad 6))
(assert (nodos 1)))
;******************************
;*
OPERADORES *
;******************************
;----------------------------------------------------------------
;
Regla para agnadir un litro a la garrafa
(defrule
Agnade-Un-Litro
(declare
(salience 500))
?estado
<- (estado
(garrafa ?cantidad)
(profundidad ?profundidad))
(profundidad
?nivel ?)
(test
(= ?profundidad ?nivel))
(test
(< ?cantidad 3))
=>
(assert
(estado (garrafa (+ ?cantidad 1))
(profundidad (+ ?profundidad 1))
(padre ?estado)
(operacion "Agnade un litro"))))
;----------------------------------------------------------------
;
Regla para agnadir dos litros a la garrafa
;
(defrule
Agnade-Dos-Litros
(declare
(salience 500))
?estado
<- (estado
(garrafa ?cantidad)
(profundidad ?profundidad))
(profundidad
?nivel ?)
(test
(= ?profundidad ?nivel))
(test(<
?cantidad 3))
=>
(assert
(estado (garrafa (+ ?cantidad 2))
(profundidad (+ ?profundidad 1))
(padre ?estado)
(operacion "Agnade dos litros"))))
;******************************
;*
BUSQUEDA EN PROFUNDIDAD *
;******************************
;----------------------------------------------------------------
;
Regla para Increntar la cuenta de nodos
;
LLevamos la cuenta de nodos en profundidad y en nodos, de forma
;
que si no se crean nuevos nodos al aplicar los operadores
;
a los nodos del nivel de profundidad en curso pararemos la
;
busqueda
(defrule
Incrementa-cuenta-nodos
(declare (salience 1100))
?estado <- (estado (nodo ?estadoNodo))
?nodos <- (nodos ?cuentaNodos)
(test (= ?estadoNodo 0))
=>
(assert (nodos (+ 1 ?cuentaNodos)))
(modify ?estado (nodo ?cuentaNodos))
(retract ?nodos))
;----------------------------------------------------------------
;
Regla para actualizar la profundidad
;
Llamada solo si se han expandido todos los nodos de un nivel
;
(Por lo tanto prioridad mas baja)
;
(defrule
actualiza-profundidad
(declare
(salience 100))
?profundidad
<- (profundidad ?nivel ?numNodosViejo)
(nodos
?nodos)
(test
(> ?nodos ?numNodosViejo))
=>
(retract
?profundidad)
(assert
(profundidad (+ 1 ?nivel) ?nodos)))
;******************************
;*
ESTADO FINAL *
;******************************
;----------------------------------------------------------------
;
Regla para detectar tarea realizada, es decir la garrafa tiene
;
3 litros. Tiene la prioridad mas alta para que cuando sea
;
reconocida sea la que se ejecute.
;
(defrule
Hecho
(declare
(salience 1000))
?estado
<- (estado
(garrafa 3))
=>
(assert
(completa ?estado))
(assert
(lista "Hecho")))
;**************************************
;*
FIN BUSQUEDA E IMPRESION SOLUCION *
;**************************************
;----------------------------------------------------------------
;
Regla para construir el camino una vez encontrada una solucion
;
(defrule
Completa
(declare (salience 2000))
?estado <- (estado (padre ?padre) (operacion ?movimiento))
?completa <- (completa ?estado)
?lista-vieja <- (lista $?resto)
=>
(assert (lista ?movimiento ?resto))
(assert (completa ?padre))
(retract ?completa)
(retract ?lista-vieja))
;----------------------------------------------------------------
;
Regla para imprimir la solucion
;
(defrule
Camino-Completado
(declare (salience 2000))
?completa <- (completa no-padre)
?lista-vieja <- (lista ?primero $?movimientos ?ultimo)
=>
(printout t "Solucion:" crlf ?movimientos crlf)
(retract ?completa ?lista-vieja))
;----------------------------------------------------------------
;
Regla para acabar cuando se alcanze cierto nivel de profundidad
;
(defrule
alcanza-maxima-profundidad
(declare (salience 1000))
(profundidad ?nivel)
(maxima-profundidad =(+ 1 ?nivel))
=>
(printout t crlf "Sobrepasado el nivel de profundidad ", ?nivel "." crlf)
(halt))
;----------------------------------------------------------------
;
Regla para acabar cuando no se agnaden mas nodos
;
(defrule
FIN
(declare (salience 100))
?profundidad <- (profundidad ?nivel ?numNodosViejos)
(nodos ?numNodos)
(test (= ?numNodos ?numNodosViejos))
=>
(printout t "Un total de " (- ?numNodos 1) " nodos en el arbol"
crlf)
(retract ?profundidad)
(halt))
6.8 Tarea