Implementación
Reglas
Implementación de motores de inferencia
dirigidos por patrones II
Departamento de Informática e Ingeniería de Sistemas
C.P.S. Universidad de Zaragoza
Copyright © 1998 José Angel Bañares
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
Última revisión: Nov. 2004
03/10/2015
1
Implementación
Reglas
 Índice
 Bibliografía
 7. Diseño de un sistema de
encadenamiento de reglas hacia
adelante con mecanismo de contexto
para establecer suposiciones.
 K.D. Forbus and J.de Kleer. “Building
Problem Solvers”. The MIT Press,
1993.
 8. Implementación de un JTMS
 9. Integración del JTMS con un motor
de inferencia.
 10. Ejemplo, búsqueda dirigida por
dependencias.
 11. Comparación
experimentales
de
resultados
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
2
Implementación
Reglas
7. Un PDIS con mecanismo de
manejo de contextos
 Aserciones: se almacenan en la base de datos
 Denominaremos aserción la estructura de datos asociada a la aserción para
registrar si se cree o no en la afirmación y por qué.
(Tiene-Valor (ganancia ?amperios) ?beta)
 Denominaremos forma a la lista registrada en la base de datos (BdD).
 Interfaz:
 assert!: Inserta una forma en la BdD
 fetch: Recupera una aserción de la BdD
 NO hay mecanismo para borrar aserciones
o Nuestro diseño hasta aquí no tiene una forma adecuada de eliminar las
consecuencias de una creencia, por lo que no podemos manejar adecuadamente
el borrado.
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
3
Implementación
Reglas
Reglas
 (rule <trigger> . <body>)
 Trigger: Un patrón que especifica la clase de aserciones a las que la regla
pretende responder
 body: Código lisp evaluado en el entorno formado al unificar el patrón con
una aserción particular.
(rule (foo ?x) (format t “foo(~A) ha sido asertado.” ?x))
 Una regla con varias premisas se escribiría anidando varias reglas más
simples:
(rule (sobre ?x mesa)
(rule (sobre ?y ?x)
(rule (sobre ? z ?y) (assert! ‘(Torre-3 ,?x ,?y ,?z)))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
4
Implementación
Reglas
reglas anidadas
 Cuando una regla contiene en su body otra regla, es decir formas que
comienzan con rule, el resultado de la ejecución de la primera es la creación
de una nueva regla que se añade a la base de reglas y se trata como
cualquier otra.
o El trigger y el body de esta nueva regla tiene como entorno de ligaduras las
introducidas por los triggers de las reglas que la contenían:
(sobre D MESA)
(sobre E D)
(sobre F E)
(rule (sobre ?x mesa) ; reconoce (sobre D MESA)
(rule (sobre ?y ?x)
(rule (sobre ?z ?y) (asser! ‘(Torre-3 ,?x ,?y ,?z)))))
Se inserta la regla -->
(rule(sobre ?y D) ; reconoce (sobre E D)
(rule (sobre ?z D)(asser! ‘(Torre-3 D E ,?z))))
Se inserta la regla -->
(rule (sobre ?z E) ; Reconoce (sobre F E)
(asser! ‘(Torre-3 D E F))))
Se inserta la aserción --> (Torre-3 D E F)
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
5
Implementación
Reglas
Duración de las reglas
 Las reglas creadas por anidación o sus progenitoras permanecen en la
Base de reglas siempre
(sobre
(sobre
(sobre
(sobre
D
E
F
G
MESA)
D)
E)
E)
La regla más interna vuelve a dispararse
(rule (sobre ?z E) ; Reconoce (sobre G E)
(asser! ‘(Torre-3 D E F))))
Se inserta la aserción --> (Torre-3 D E G)
o Beneficio de la permanencia de las reglas: El PDIS es independiente del orden de
ejecución de las reglas
o Inconveniente: Es más fácil generar explosiones combinatorias y más difícil de
mantener la eficiencia.
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
6
Implementación
Reglas
7.1 Diseño de TRE (Tiny Rule Engine)
 Organización de los cómputos
 Cuando una aserción es añadida se debe chequear cada regla que podría reconocerla
 Cuando se añade una regla, se debe chequear cada aserción que podría ser
reconocida
o En ambos casos el body y su entorno se apilan para una ejecución eventual
Aserciones y reglas
suministradas por el usuario
BdD
Aserciones
Nuevas
aserciones
derivadas
BdD
Reglas
Nuevas
reglas
instanciadas
Cola
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
7
Implementación
Reglas
Elecciones de diseño
 Elecciones obvias
 Aserciones: Implementadas como una lista
 Pattern matching: Implementa el algoritmo de unificación
 Elecciones no tan obvias
 Bases de datos: ¿Cómo almacenar las reglas y las aserciones?
 Reglas: ¿Cómo las representamos para que se ejecuten en el entorno
adecuado?
 Cola de reglas: ¿Qué debería ir exactamente a la cola y como servimos las
instancias?
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
8
Implementación
Reglas
Diseño de la BdD
 Class Indexing:
 Se parte las reglas y las aserciones en dbclasses que corresponden a los
elementos que podrían reconocerse
o La clase de una aserción / trigger es el símbolo constante más a la izquierda
DBClass((implies foo bar)) = implies
DBClass(foo) = foo
DBClass(((grumbble mumble) bar)) = grumble
o Sólo una aserción y un trigger en la misma clase (dbclass) pueden reconocerse
o Si el símbolo más a la izquierda es una variable, tomaremos la dbclass del valor
de la variable. Consideraremos un error si no tiene valor.
 Si queremos saber todas las relaciones binarias entre A y B,
 patrón (A ?rel B)
relaciones (<1er arg> <Predicado> <2 arg>)
 NO se puede patrón (?rel A B)
relaciones (<Predicado> <1er arg> <2 arg>)
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
9
Implementación
Reglas
7.2 Diseño de un FTRE
(Faster Tiny rule Engine)
 Mejoras:
 Una sintaxis más “limpia” para escribir reglas
 Mecanismo de manejo de contextos
 1. Mejora de la sintaxis
 Sintaxis más sencilla de las reglas anidadas
(rule (demuestra ?q)
(rule (implica ? p ?q) (assert! ‘(demuestra ,?p))))
(rule ((demuestra ?q) ;
(implica ? p ?q))
(assert! ‘(demuestra ?p))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
10
Implementación
Reglas
7.2.1 Mejora de la sintaxis
 :VAR y TEST en los triggers
o :VAR el siguiente elemento del trigger es una variable a la que se da el valor del
patrón
o :TEST un predicado adicional sobre el patrón
(rule ((demuestra ?q) :test (not (fetch ?q))
(implica ? p ?q) :var ?imp)
(DEBUG-ND “~% BC-CE: Buscando ~A para usar ~A.”
?p ?imp)
(assert! ‘(demuestra ?p))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
11
Implementación
Reglas
7.2.1 Manejo de contextos
 Muchas formas de razonar conllevan hacer suposiciones
 Una pila permite tener un contexto local en el cual las variables pueden tomar
valores distintos durante un tiempo
1
2
3
(demuestra P)
(not Q)
(implica (not P) Q)
(implica (not Q) R)
(demuestra P)
(not Q)
(implica (not P) Q)
(implica (not Q) R)
(demuestra P)
(not Q)
(implica (not P) Q)
(implica (not Q) R)
(not P)
(not P)
Q
4
(demuestra P)
(not Q)
(implica (not P) Q)
(implica (not Q) R)
¡Contradicción!
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
12
Implementación
Reglas
Manejo de contextos
 ¿Cómo debemos organizar nuestras reglas y nuestro intérprete?
o 1. Distinguiremos entre reglas que hacen suposiciones de las que no las hacen.
 Las reglas que no hacen suposiciones deben ejecutarse antes para
asegurarnos de que las deducciones se hacen en el entorno lógico
menor.
o 2. Debemos organizar la base de datos para apilar y desapilar aseciones e
instancias.
 Implícitamente estamos llevando a cabo una búsqueda en profundidad
o Pondremos un límite en la profundidad alcanzada
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
13
Implementación
Reglas
7.3 Interfaz del FTRE
(defstruct (ftre (:PRINT-FUNCTION ftre-printer))
title
; String para impresión
(dbclass-table nil)
; symbols --> classes (BdD global)
(debugging nil)
; imprime info. extra si non-nil
(debugging-contexts nil)
(normal-queue nil)
; LIFO. Instancias que no hacen supos.
(asn-queue nil)
;
Instancias que hacen supos.
(depth 0)
; Profundidad en curso
(max-depth 5)
; Máxima profundidad de contextos
(local-data nil)
; Contextos mantenidos por
(local-rules nil)
;
see-in-context y try-in-context
(rule-counter 0)
; id unico para reglas
(rules-run 0))
; Estadísticas
(defun ftre-printer (ftre st ignore)
(format st "<FTRE: ~A>" (ftre-title ftre)))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
14
Implementación
Reglas
Interfaz FTRE
(defun create-ftre (title &key (debugging nil)
(debugging-contexts nil)
(max-depth 5))
(make-ftre :TITLE title
:DBCLASS-TABLE (make-hash-table :test #'eq)
:DEBUGGING debugging
:DEBUGGING-CONTEXTS debugging-contexts
:MAX-DEPTH max-depth))
; Invocar el motor de inferencia
(defun run (&optional (*TRE* *TRE*))
(format T "~%>>")
(do ((form (read) (read)))
((member form '(quit stop exit)) nil)
(format t "~%~A" (eval form))
(run-rules *tre*)
(format t "~%>>")))
; Muestra el contenido de afirmaciones y reglas
(defun show (&optional (stream *standard-output*))
;; Pass on the request to both modules of default TRE
(show-data stream)
(show-rules stream))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
15
Implementación
Reglas
Evaluando en un contexto
(defun try-in-context (assumption form &optional (*ftre* *ftre*)
&aux (depth 0))
(setq depth (ftre-depth *ftre*))
(when (> depth (ftre-max-depth *ftre*))
(debugging-contexts
"~% ~A(~D): Punting on trying ~A, too deep."
*ftre* (ftre-depth *ftre*) assumption)
(return-from TRY-IN-CONTEXT nil))
(let ((old-local-data (ftre-local-data *ftre*))
(old-local-rules (ftre-local-rules *ftre*))
(old-normal-queue (ftre-normal-queue *ftre*))
(old-asn-queue (ftre-asn-queue *ftre*))
(result nil))
(setf (ftre-normal-queue *ftre*) nil)
(setf (ftre-asn-queue *ftre*) nil)
(incf (ftre-depth *ftre*))
(push (ftre-depth *ftre*) (ftre-local-data *ftre*))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
16
Implementación
Reglas
Evaluando en un contexto
(debugging-contexts "~% ~A(~D): Trying ~A."
*ftre* (ftre-depth *ftre*) assumption)
(with-ftre *ftre*
(if assumption (assert! assumption))
(run-rules *ftre*)
(debugging-contexts "~% ~A(~D): Context ~A for ~A."
*ftre* (ftre-depth *ftre*) assumption form)
(debugging-contexts
"~%
~D facts and ~D rules in local context."
(- (length (ftre-local-data *ftre*))
(length old-local-data))
(- (length (ftre-local-rules *ftre*))
(length old-local-rules)))
(setq result (eval form))
(setf (ftre-local-data *ftre*) old-local-data)
(setf (ftre-local-rules *ftre*) old-local-rules)
(setf (ftre-normal-queue *ftre*) old-normal-queue)
(setf (ftre-asn-queue *ftre*) old-asn-queue)
(decf (ftre-depth *ftre*))
result)))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
17
Implementación
Reglas
7.4 Data base
(defstruct (dbclass (:PRINT-FUNCTION print-dbclass-struct))
name
;Un símbolo
ftre
;ftre al que pertenece
facts
;Hechos en la dbclass
rules)
;Reglas aplicables en esta dbclass
(defun show-data (&optional (stream *standard-output*)
&aux counter)
(setq counter 0)
(format stream "~%In global context: ")
(maphash #'(lambda (key dbclass)
(dolist (datum (dbclass-facts dbclass))
(incf counter)
(format stream "~%~A" datum)))
(ftre-dbclass-table *ftre*))
(format stream "~% ~D assertions in global context." counter)
(when (> (ftre-depth *ftre*) 0)
(format stream "~% In current context:")
(dolist (datum (reverse (ftre-local-data *ftre*)))
(unless (numberp datum) (incf counter))
(format stream "~% ~A." datum)))
counter)
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
18
Implementación
Reglas
Insertando datos
(defun assert! (fact &optional (*ftre* *ftre*))
(when (insert fact *ftre*) (try-rules fact *ftre*)))
(defun insert (fact ftre &aux dbclass)
(when (null fact) (error "~% Can't assert NIL."))
(setq dbclass (get-dbclass fact ftre))
(cond ((member fact (dbclass-facts dbclass)
:TEST #'equal) nil)
((= (ftre-depth ftre) 0)
(push fact (dbclass-facts dbclass)))
((member fact (ftre-local-data ftre)
:TEST #'equal) nil)
(t (push fact (ftre-local-data *ftre*)))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
19
Implementación
Reglas
get-dbclas
(defun get-dbclass (fact ftre &aux dbclass)
(cond ((null fact) (error "~% NIL can't be a dbclass."))
((listp fact) (get-dbclass (car fact) ftre))
((variable? fact)
(cond ((boundp fact)
(get-dbclass (symbol-value fact) ftre))
(t (error "~%Dbclass unbound: ~A" fact))))
((symbolp fact)
(cond ((gethash fact (ftre-dbclass-table ftre)))
(t (setq dbclass
(make-dbclass :NAME fact :FTRE ftre
:FACTS nil :RULES nil))
(setf (gethash
fact (ftre-dbclass-table ftre))
dbclass)
dbclass)))
(t (error "Bad dbclass type: ~A" fact))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
20
Implementación
Reglas
Recuperando datos
(defun fetch (pattern &optional (*ftre* *ftre*)
&aux bindings unifiers)
(dolist (candidate (get-candidates pattern *ftre*)
unifiers)
(setq bindings (unify pattern candidate))
(unless (eq bindings :FAIL)
(push (sublis bindings pattern) unifiers))))
(defun get-candidates (pattern ftre)
(append (ftre-local-data ftre)
(dbclass-facts (get-dbclass pattern ftre))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
21
Implementación
Reglas
7.5 Reglas
(defstruct (rule (:PRINT-FUNCTION ftre-rule-printer))
id
;"nombre" único
Dbclass
;Dbclass con la que está relacionado
matcher
;Procedimiento que realiza el matching
body
;procedure que ejecuta el body
assumption?)
;Establece suposición?
(defun run-rules (*ftre*)
(do ((form (dequeue *ftre*) (dequeue *ftre*))
(counter 0 (1+ counter)))
((null form)
(debugging-ftre "~% ~A(~A): ~A rules run."
*ftre* (ftre-depth *ftre*) counter))
(incf (ftre-rules-run *ftre*))
(with-ftre *ftre*
(apply (car form) (cdr form)))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
22
Implementación
Reglas
try-rules
(defun try-rules (fact ftre)
(dolist (rule (get-candidate-rules fact ftre))
(try-rule-on rule fact)))
(defun get-candidate-rules (fact ftre)
(append (ftre-local-rules ftre)
(dbclass-rules (get-dbclass fact ftre))))
(defun try-rule-on (rule fact)
(with-ftre (dbclass-ftre (rule-dbclass rule))
(multiple-value-bind (okay? bindings)
(funcall (rule-matcher rule) fact)
(when okay?
(enqueue *ftre* (cons (rule-body rule) bindings)
(rule-assumption? rule))))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
23
Implementación
Reglas
7.6 Ejemplo de las N-reinas
 Dado un tablero de NxN cuantas formas hay de colocar N reinas en el
tablero sin que se coman
Q
Q
Q
Q
Q
Buena solución
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
Q
Q
Q
Mala solución
LenguajeReglas.ppt
03/10/2015
24
Implementación
Reglas
Choice set
 Conceptualmente podemos ver el conjunto de localizaciones alternativas
como un conjunto de elecciones.
 La idea de los choice sets como método para organizar la búsqueda es
o Cada choice set representa un factor/aspecto que puede aparecer en la solución
o Dentro de cada choice set, las elecciones son mutuamente excluyentes y
exhaustivas
o Cada solución puede encontrarse por un conjunto de selecciones, una de cada
choice set.
(defun Chrono (choice-sets)
(if (null choice-sets)
(record-solution)
; Guarda el resultado
(dolist (choice (first choice-sets))
(while-assuming choice ; Hace una suposición, y la retira
; una vez ejecutado el cuerpo
(if (consistent?) ;Cheque la consistentcia
(Chrono (rest choice-sets)))))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
25
Implementación
Reglas
Representación
 (Queen ?I ?J) ; indica que la reina de la fila ?I está en la columna ?J
 Regla que detecta dos reinas en peligro y aserta contradicción:
(rule ((queen ?column1 ?row1)
(queen ?column2 ?row2)
:TEST (not (or (= ?column1 ?column2)
(queens-okay? ?column1 ?row1
?column2 ?row2))))
(rassert! Contradiction))
(defun queens-okay? (x1 y1 x2 y2)
; Detecta si dos reinas están en mutuo peligro
(not (or (= y1 y2) (= (abs (- x1 x2)) (abs (- y1 y2))))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
26
Implementación
Reglas
Crea el motor de inferencia
 Creación de un motor de inferencia e inicio de la búsqueda:
;;; Estadísticas de la búsqueda
(defvar *n-assumptions* 0) ;numero de suposiciones
(defvar *placements* nil) ;Sóluciones encontradas
;;; Crea el motor de inferencia e inicia la búsqueda
(defun n-queens (n &optional (debugging? nil))
(setup-queens-puzzle n debugging?)
(solve-queens-puzzle (make-queens-choice-sets n))
(length *placements*))
(defun setup-queens-puzzle (n debugging?)
(in-ftre
(create-ftre (format nil "~D queens" n)
:DEBUGGING debugging?
:MAX-DEPTH (+ n 1)))
(setq *placements* nil
*n-assumptions* 0)
(load-file *ftre-path* *fqueen-rule-file*)) ; Carga el fichero
; con la regla
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
27
Implementación
Reglas
Búsqueda
 Búsqueda
(defun make-queens-choice-sets (n)
(do ((column 1 (1+ column))
(column-queens nil nil)
(choice-sets nil))
((> column n) (nreverse choice-sets))
(dotimes (row n)
(push `(Queen ,column ,(1+ row)) column-queens))
(push (nreverse column-queens) choice-sets)))
;;; Búsqueda cronológica
(defun solve-queens-puzzle (choice-sets)
(cond ((fetch 'contradiction)
(return-from solve-queens-puzzle nil))
(choice-sets ;; Hace la siguiente elección
(dolist (choice (car choice-sets))
(incf *n-assumptions*)
(try-in-context choice
`(solve-queens-puzzle ',(cdr choice-sets)))))
(t
;; Guarda la solución en *placements*
(gather-queens-solution))))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
28
Implementación
Reglas
Utilidades
 Utilidades
(defun gather-queens-solution ()
(push (fetch '(Queen ?x ?y) *ftre*) *placements*))
(defun show-queens-solution (solution n &aux l m)
(setq solutions (length solution))
(dotimes (sol solutions)
(terpri)
(dotimes (l n)
(terpri)
(dotimes (m n)
(setf i (1+ l) j (1+ m))
(format t "~A"
(if (member `(queen ,i ,j) (nth sol solution)
:TEST #'equal) "Q" "-"))))))
(defun n-reinas (n)
(n-queens n)
(show-queens-solution *placements* n))
Implementación de un lenguaje basado en reglas. José Angel Bañares. V-1998.
LenguajeReglas.ppt
03/10/2015
29
Descargar

Lenguajes basados en reglas y objetos