ierl 2.1 josé ignacio aguillo mendi isbc curso 2001-02 [email protected]...
TRANSCRIPT
Situación de partida …
• El sistema experto basado en reglas y encadenamiento progresivo propuesto en el libro de Winston, con sus virtudes y defectos.
• Otras cosas irrelevantes para las modificaciones realizadas…
Primeras ideas …
• Añadir la posibilidad de insertar más de un hecho en las poscondiciones de las reglas.
• Añadir la posibilidad de ejecutar código LISP en las poscondiciones de las reglas.
Pensando un poco más …
• Añadir la posibilidad de ejecutar código LISP en las poscondiciones de las reglas.
La ejecución de código LISP en la poscondición permite la definición de funciones para asertar hechos
=>en la poscondición podremos
ejecutar una sola instrucción LISP (uso de progn para más).
Estructura anterior de una regla
(<nombre><afirmación antecedente 1><afirmación antecedente 2>…<afirmación antecedente n><afirmación consecuente>)
Nueva estructura de una regla
(<nombre><afirmación antecedente 1><afirmación antecedente 2>…<afirmación antecedente n><instrucción LISP>)
Ejemplo de regla
(mover-bloque-sobre-bloque (objetivo (? objeto-1) esta-encima-del (? objeto-2)) (bloque (? objeto-1)) (bloque (? objeto-2)) (estado nada esta-encima-del (? objeto-1)) (estado (? objeto-1) esta-encima-del (? objeto-3)) (estado nada esta-encima-del (? objeto-2)) (progn (retract! '(objetivo (? objeto-1) esta-encima-del (? objeto-2))) (retract! '(estado (? objeto-1) esta-encima-del (? objeto-3))) (retract! '(estado nada esta-encima-del (? objeto-2))) (assert! '(estado (? objeto-1) esta-encima-del (? objeto-2))) (assert! '(estado nada esta-encima-del (? objeto-3))) (format t "~&~a movido encima del ~a.~%" '(? objeto-1) '(? objeto-2))))
• Observar también la utilización de las funciones assert! (para asertar hechos) y retract! (para retirarlos de la memoria de trabajo).
Cambios en el código …
• En lugar de intentar recordar la afirmación del consecuente, se evalúa el propio consecuente ya que es código LISP.
… (let ((primera-regla (prim-reg-ag *agenda*) (resultado (FC-particulariza-variables (consecuente-de-la-regla regla) (ligaduras-regla-ag primera-regla)))) (eval resultado) …
Más ideas …
• Implementar variables de patrón de tipo lista como
($ <nombre>).• Introduce mayor complejidad,
debido a la posibilidad de más de una correspondencia entre un mismo patrón y dato.
Variable de patrón de tipo lista …• Esto obliga a que la función que
realiza la correspondencia de un patrón (antecedente) con un dato (hecho) pueda devolver o bien una lista de ligaduras (si no hay variable lista), o bien una lista de listas de ligaduras (si hay alguna variable de lista en el patrón).
Variable de patrón de tipo lista (2) …• Por supuesto, podremos tener
predicados sobre las variables de tipo lista, del mismo modo que lo teníamos con las variables normales.
($ x longitud-tres)
• También podremos utilizar variables de tipo lista anónimas.
($ _)
Ejemplos …
> (corresponde '(($ x)($ y)($ z)) '(hola a b c adios))(((z (hola a b c adios)) (y nil) (x nil)) ((z (a b c adios))
(y (hola)) (x nil)) ((z (b c adios)) (y (hola a)) (x nil)) ((z (c adios)) (y (hola a b)) (x nil)) ((z (adios)) (y (hola
a b c)) (x nil)) ((z nil) (y (hola a b c adios)) (x nil)) ((z (a b c adios)) (y nil) (x (hola))) ((z (b c adios)) (y
(a)) (x (hola))) ((z (c adios)) (y (a b)) (x (hola))) ((z (adios)) (y (a b c)) (x (hola))) ...)
Inconvenientes …
• La aparición de variables de tipo lista en los antecedentes provocan una explosión combinatoria de posibles valores para dichas variables.
• Los distintos valores se obtienen con la función genera-posibilidades.
La función genera-posibilidades• Toma como argumento una lista y
devuelve una lista con todos los posibles valores que puede tomar una variable de tipo lista y el resto de la propia lista.
> (genera-posibilidades '(a b c))((nil a b c) ((a) b c) ((a b) c) ((a b c)))
• Esto se realiza cada vez que se encuentra en el patrón una variable de tipo lista => si el dato es muy largo, mayor número de posibilidades, aunque quizá sólo una buena => muy lento.
Más ideas …
• Ante la ausencia de un control sobre el disparo de las reglas, se plantea la creación de una agenda que mantenga las reglas sensibilizadas, tanto disparadas como no disparadas.
La agenda
• Implementación de la agenda como una lista, donde cada elemento está formado por el nombre de la regla sensibilizada, los hechos que la sensibilizan, las ligaduras que dan lugar a esos hechos y un valor que indica si la regla ya ha sido disparada o no. Por tanto, se va a considerar la refracción.
La agenda (2)
• La agenda se ordenará según una estrategia de control (MEA), pudiendo ser implementada cualquier otra con relativa facilidad y teniendo en cuenta que las reglas ya disparadas siempre estarán al final de la agenda.
La agenda (3)
• La operación de retirar un hecho de la memoria de trabajo (retract!) trae consigo no sólo eliminarlo de la memoria de trabajo, sino también retirar de la agenda aquellas reglas, disparadas o no, que tengan ese hecho como uno de los que la sensibilizan.
Algoritmo principal
(defun encadenamiento-progresivo () (prueba-reglas) (do () ((agenda-vacia?) 'HECHO) (ordena-reglas) (dispara-primera-regla) (prueba-reglas)))
Ligar variables con hechos
• Ligar variables con hechos es muy importante, ya que nos evita tener que escribir, en muchas ocasiones, hechos completos. Si la longitud del hecho es considerable, se apreciará la validez de esta característica.
Ligar variables con hechos (2)
• Podemos ligar variables con hechos en las precondiciones de una regla de la siguiente forma:
((? <nombre>) <- <hecho>)
• Podemos utilizarlo, por ejemplo, para retirar hechos:
(retract! '(? <nombre>))
Otras contribuciones
• Otras funciones realizadas de utilidad para un posible usuario del sistema son:• ver-afirmaciones: muestra los hechos de la memoria de trabajo en
un momento determinado.• clear: borra los hechos de memoria de trabajo y vacía la agenda.• watch: permite ver hechos y/o reglas conforme se van asertando,
retirando o disparando.• unwatch: desactiva la funcionalidad aportada por la función watch.• prueba-reglas: introduce en la agenda las instancias de reglas
sensibilizadas.
Otras contribuciones (2)
• ordena-reglas: ordena las instancias de reglas en la agenda según un criterio especificado, dicho criterio puede ser cambiado por el usuario con relativa facilidad.
• dispara-primera-regla: dispara la primera regla de la agenda.• ver-agenda: permite ver la situación de la agenda en un momento
determinado.
Ejemplos: el mundo de bloques sin variables $(defun ejemplo-7 () (clear) (recuerda-afirmacion '(bloque A)) (recuerda-afirmacion '(bloque B)) (recuerda-afirmacion '(bloque C)) (recuerda-afirmacion '(bloque D)) (recuerda-afirmacion '(bloque E)) (recuerda-afirmacion '(bloque F)) (recuerda-afirmacion '(estado nada esta-encima-del A)) (recuerda-afirmacion '(estado A esta-encima-del B)) (recuerda-afirmacion '(estado B esta-encima-del C)) (recuerda-afirmacion '(estado C esta-encima-del suelo)) (recuerda-afirmacion '(estado nada esta-encima-del D)) (recuerda-afirmacion '(estado D esta-encima-del E)) (recuerda-afirmacion '(estado E esta-encima-del F)) (recuerda-afirmacion '(estado F esta-encima-del suelo)) (recuerda-afirmacion '(objetivo C esta-encima-del E))
A
B
C
D
E
F
Ejemplos: el mundo de bloques sin variables $ (2) (recuerda-regla '(mover-bloque-sobre-bloque ((? objetivo)<-(objetivo (? objeto-1) esta-encima-del (? objeto-2))) (bloque (? objeto-1)) (bloque (? objeto-2)) (estado nada esta-encima-del (? objeto-1)) ((? pila-1)<-(estado (? objeto-1) esta-encima-del (? objeto-3))) ((? pila-2)<-(estado nada esta-encima-del (? objeto-2)))
(progn (retract! '(? objetivo)) (retract! '(? pila-1)) (retract! '(? pila-2)) (assert! '(estado (? objeto-1) esta-encima-del (? objeto-2))) (assert! '(estado nada esta-encima-del (? objeto-3))) (format t "~&~a movido encima del ~a.~%" '(? objeto-1) '(? objeto-2)))))
Ejemplos: el mundo de bloques sin variables $ (3) (recuerda-regla '(mover-bloque-al-suelo ((? objetivo)<-(objetivo (? objeto-1) esta-encima-del suelo)) (bloque (? objeto-1)) (estado nada esta-encima-del (? objeto-1)) ((? pila)<-(estado (? objeto-1) esta-encima-del (? objeto-2)))
(progn (retract! '(? objetivo)) (retract! '(? pila)) (assert! '(estado (? objeto-1) esta-encima-del suelo)) (assert! '(estado nada esta-encima-del (? objeto-2))) (format t "~&~a movido encima del suelo.~%" '(? objeto-1)))))
Ejemplos: el mundo de bloques sin variables $ (4) (recuerda-regla '(libera-bloque-movible (objetivo (? objeto-1) esta-encima-del (? _)) (bloque (? objeto-1)) (estado (? objeto-2) esta-encima-del (? objeto-1)) (bloque (? objeto-2)) (assert! '(objetivo (? objeto-2) esta-encima-del suelo)))) (recuerda-regla '(libera-bloque-soporte (objetivo (? _) esta-encima-del (? objeto-1)) (bloque (? objeto-1)) (estado (? objeto-2) esta-encima-del (? objeto-1)) (bloque (? objeto-2)) (assert! '(objetivo (? objeto-2) esta-encima-del suelo)))))
Ejemplos: el mundo de bloques sin variables $ (5)> (ejemplo-7)…
> (watch 'afirmaciones)
…> (encadenamiento-progresivo)
=> (objetivo d esta-encima-del suelo)<= (objetivo d esta-encima-del suelo)<= (estado d esta-encima-del e)=> (estado d esta-encima-del suelo)=> (estado nada esta-encima-del e)d movido encima del suelo.
Ejemplos: el mundo de bloques sin variables $ (6)=> (objetivo b esta-encima-del suelo)=> (objetivo a esta-encima-del suelo)<= (objetivo a esta-encima-del suelo)<= (estado a esta-encima-del b)=> (estado a esta-encima-del suelo)=> (estado nada esta-encima-del b)a movido encima del suelo.<= (objetivo b esta-encima-del suelo)<= (estado b esta-encima-del c)=> (estado b esta-encima-del suelo)=> (estado nada esta-encima-del c)b movido encima del suelo.<= (objetivo c esta-encima-del e)<= (estado c esta-encima-del suelo)<= (estado nada esta-encima-del e)=> (estado c esta-encima-del e)=> (estado nada esta-encima-del suelo)c movido encima del e.hecho
Ejemplos: el mundo de bloques con variables $
(defun ejemplo-8 () (clear) (recuerda-afirmacion '(pila A B C)) (recuerda-afirmacion '(pila D E F)) (recuerda-afirmacion '(objetivo C esta-encima-del E))
A
B
C
D
E
F
Ejemplos: el mundo de bloques con variables $ (2)(recuerda-regla '(mover-bloque-sobre-bloque ((? objetivo)<-(objetivo (? bloque-1) esta-encima-del (? bloque-2))) ((? pila-1)<-(pila (? bloque-1) ($ resto-1))) ((? pila-2)<-(pila (? bloque-2) ($ resto-2))) (progn (retract! '(? objetivo)) (retract! '(? pila-1)) (retract! '(? pila-2)) (assert! '(pila ($ resto-1))) (assert! '(pila (? bloque-1) (? bloque-2) ($ resto-2))) (format t "~&~a movido encima del ~a.~%" '(? bloque-1) '(? bloque-2)))))
Ejemplos: el mundo de bloques con variables $ (3)(recuerda-regla '(mover-bloque-al-suelo ((? objetivo)<-(objetivo (? bloque-1) esta-encima-del suelo)) ((? pila)<-(pila (? bloque-1) ($ resto))) (progn (retract! '(? objetivo)) (retract! '(? pila)) (assert! '(pila (? bloque-1))) (assert! '(pila ($ resto))) (format t "~&~a movido encima del suelo.~%" '(? bloque-1)))))
Ejemplos: el mundo de bloques con variables $ (4)
(recuerda-regla
'(libera-bloque-movible (objetivo (? bloque) esta-encima-del (? _)) (pila (? cima) ($ _) (? bloque) ($ _)) (assert! '(objetivo (? cima) esta-encima-del suelo)))) (recuerda-regla '(libera-bloque-soporte (objetivo (? _) esta-encima-del (? bloque)) (pila (? cima) ($ _) (? bloque) ($ _)) (assert! '(objetivo (? cima) esta-encima-del suelo)))))
Ejemplos: el mundo de bloques con variables $ (5)> (ejemplo-8)…> (watch 'afirmaciones)…> (encadenamiento-progresivo)=> (objetivo d esta-encima-del suelo)<= (objetivo d esta-encima-del suelo)<= (pila d e f)=> (pila d)=> (pila e f)d movido encima del suelo.
Ejemplos: el mundo de bloques con variables $ (6)=> (objetivo a esta-encima-del suelo)<= (objetivo a esta-encima-del suelo)<= (pila a b c)=> (pila a)=> (pila b c)a movido encima del suelo.=> (objetivo b esta-encima-del suelo)<= (objetivo b esta-encima-del suelo)<= (pila b c)=> (pila b)=> (pila c)b movido encima del suelo.<= (objetivo c esta-encima-del e)<= (pila c)<= (pila e f)=> (pila)=> (pila c e f)c movido encima del e.hecho
Para saber más …
Temas 24, 25, 26 y 27 del libro “LISP” 3ª edición de
Patrick Henry Winston&
Berthold Klaus Paul Horn
