II. Razonamiento con conocimiento preciso

Tema 2 Sistemas Basados en Reglas Sistemas Basados en el Conocimiento Grado en Ingeniería Informática

–1–

Razonamiento con conocimiento preciso

Tema 2. Sistemas Basados en Reglas 1. Descripción 2. CLIPS 3. Ejemplos

Tema 3. Repaso de Lógica Tema 4. Web Semántica y Web de Datos

–2–

Referencias •

• • •

Inteligencia Artificial — Métodos y Técnicas. D. Borrajo, N. Juristo, V. Martínez-Orga, J. Pazos. Editorial Centro de estudios Ramón Areces. 1997 Sistemas expertos representación e inferencia problemas resueltos. A. Fernández. Dykinson (URJC). 2010 Problemas resueltos de inteligencia artificial aplicada: búsqueda y representación. Fernández, S.; González, J.; Mira, J. Addison-Wesley Iberoamericana. 1998. Ingeniería del Conocimiento. Aspectos Metodológicos. A. Alonso, B. Guijarro, A. Lozano, J. T. Palma, M. J. Tabeada. Pearson Prentice Hall. 2004

CLIPS: • Sistemas expertos: principios y programación (3ª ed.). J. Giarratano, G. Riley, G. Editorial. Thompson Ed. 2001. • CLIPS Reference Manual (CLIPS 6.1). http://clipsrules.sourceforge.net/ • JESS in Action: Rule-based systems in Java. Friedman-Hill, E. Manning. 2003. –3–

Sistemas Basados en Reglas DEFINICIÓN conjunto de sentencias en un LRC

mecanismo de inferencia automática



BASE DE HECHOS

MOTOR DE INFERENCIA

(Memoria de trabajo) Representa conocimientos sobre el problema:datos, hechos establecidos y metas a alcanzar

Razona con el conocimiento del problema y sobre su solución Determina cómo se aplican las reglas

BASE DE REGLAS Representa conocimientos sobre la solución del problema en forma de producciones

–4–

Base de Hechos • Hechos: – – – –

estructuras de datos: aserciones sobre objetos/situaciones etc. representamos hechos como listas de símbolos pueden concebirse como relaciones entre entidades ejemplo: (ladra perro), (on A B)

• Base de hechos (BH): – representa el modelo del mundo (o el problema en curso de solución) – cambia con el proceso de inferencia – Estado inicial: situación inicial – Estado final: situación final – Estado intermedio: situación actual o en curso de resolución – ejemplo BH: (bloque A) (bloque B) (on A B) (on B T) (clear A) –5–

Base de Hechos Partes de la BH: • permanente: hechos invariantes – describen características que siempre se dan en el problema – Ejemplo: (bloque A) (bloque B) (clear T)

• temporal: hechos variantes – cambian durante el proceso de la solución del problema – Ejemplo: (on A B) (on B T) (clear A)

Modificación de la BH: • añadir hechos a la BH • borrar hechos de la BH

–6–

Base de Reglas Regla: • Representa una parte del conocimiento sobre la solución del problema • Sintaxis: SI ENTONCES “Antecedente, LHS”

• Ejemplo Regla R1:

“Consecuente, RHS”

SI (hombre Socrates) ENTONCES añadir(mortal Socrates)

• Semántica: – Si todas las premisas se encuentran en la BH, se pueden ejecutar todas las acciones sobre la BH – Ej.: Si (hombre Socrates) se encuentra en la BH, se puede añadir (mortal Socrates) a la BH

Base de Reglas (BR): • conjunto de reglas: agrupa el conocimiento sobre la solución del problema • La BH describe el problema, la BR da información para resolverlo

–7–

Base de Reglas Reglas con variables: • premisas y acciones pueden contener constantes (p.e. A, ladra, on) o variables (p.e. ?x) • Ejemplos: – Regla R2: SI (hombre ?x) ENTONCES añadir(mortal ?x) – Regla R3: SI (padre ?x ?y) (padre ?y ?z) ENTONCES añadir(ancestro ?x ?z)

Semántica: • Una variable puede ligarse con cualquier constante de un hecho en la misma posición • Una variable ha de ligarse al mismo valor en toda la regla

Nótese: • sólo las reglas pueden contener variables, no los hechos • cualquier variable del consecuente ha de ligarse anteriormente en el antecedente –8–

Motor de inferencia • Mecanismo automático que permite contestar consultas a partir de una BC basada en reglas • Dos posibles estrategias de inferencia para BC basadas en reglas – Encadenamiento hacia delante (inglés: forward chaining) Soluciones intermedias

BH inicial

Consulta (BH final)

BR – Encadenamiento hacia atrás (inglés: backward chaining) Objetivo (Consulta)

Subobjetivos

BR

BH inicial –9–

Soluciones

Motor de Inferencia Mecanismo de encadenamiento hacia delante: • a partir de la BH1 se procura deducir una BHn en la que se cumple la consulta • “disparando” sucesivamente las reglas Ri de la BR • cada disparo de una regla caracteriza un ciclo de razonamiento CCk

BH1 R1 R2 ... Rm

CC1

BH2 Ri

... Rj

CC2 CC n-1

– 10 –

BHn-1

BHn Rk

Ciclo de Inferencia Paso 1: Detección de reglas aplicables (determinación del conjunto conflicto) Paso 2: Selección de una regla aplicable (resolución del conjunto conflicto) Paso 3: Aplicación de una regla y actualización de la BH (disparo de la regla)

– 11 –

Ciclo de Inferencia: Detección de reglas aplicables Equiparación: •

Selección del conjunto de reglas candidatas para dispararse, las que son compatibles con la BH (instancias de reglas aplicables o activadas)

BH (enfermedad Pepe pulmón) (enfermedad ?persona corazón) (enfermedad Juan corazón) (enfermedad María corazón) (enfermedad Juan corazón), ?persona=Juan (edad Pepe 18) (enfermedad María corazón), ?persona=María

Conjunto conflicto: •

todas las (instancias de) reglas que son aplicables en el presente ciclo

•

puede haber varias instancias de la misma regla en el conjunto conflicto – 12 –

Ciclo de Inferencia: Selección de una regla aplicable Estrategias de selección: • Establecer un orden de preferencia en la aplicación de las reglas • Preferencia basada en las reglas – – – –

prioridad explícita: asignar valores de prioridad a cada regla prioridad implícita: orden de de las reglas en la BR (Prolog) refracción: historia de una regla (la más/menos disparada) especificidad: preferir la reglas con más/menos condiciones

• Preferencia basada en las instancias de reglas – la más antigua en el conjunto conflicto (estrategia de amplitud) – la más nueva en el conjunto conflicto (estrategia de profundidad)

• Preferencia basada en objetos – selección de reglas que se aplican a los objetos más recientes – prioridad explícita: asignación de prioridades a los patrones más comunes de la BH

• Combinaciones de las diferentes preferencias – 13 –

Ciclo de Inferencia: Aplicación y actualización de la BH “Disparo” de la instancia de regla seleccionada: • Se ejecutan todas las acciones del consecuente de la (instancia de) regla • se modifica la BH actual dando lugar a una BH nueva al añadir y borrar elementos de la primera • La BH nueva se tomará como punto de partida en el siguiente ciclo de funcionamiento (por tanto es posible que algunas reglas han de eliminarse del antiguo del conjunto conflicto!)

Parada del mecanismo de inferencia: • cuando no hay más reglas aplicables en el conjunto conflicto • cuando el consecuente de una regla ejecuta un comando de parada (regla de terminación, puede codificar la consulta)

– 14 –

Ejemplo de inferencia hacia adelante en BC de reglas CONSULTA: ¿(perro Tucky)?

BASE DE HECHOS BH1 (animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky)

BASE DE REGLAS Regla R1: SI (animal ?A) (esqueleto ?A si) ENT añadir (vertebrado ?A)

Motor de inferencia Regla R2: SI (animal ?A) (esqueleto ?A no) ENT añadir (invertebrado ?A)

Ciclo1

R1,?A=Tucky R1,?A=Piolín

(animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky) (vertebrado Tucky)

Regla R3: SI (vertebrado ?A) (ladra ?A) ENT añadir (perro ?A) – 15 –

Ejemplo de inferencia hacia adelante en BC de reglas BASE DE HECHOS BH2

CONSULTA: ¿(perro Tucky)?

(animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky) (vertebrado Tucky)

BASE DE REGLAS Regla R1: SI (animal ?A) (esqueleto ?A si) ENT añadir (vertebrado ?A)

Motor de inferencia Ciclo2

Regla R2: SI (animal ?A) (esqueleto ?A no) ENT añadir (invertebrado ?A)

R1,?A=Tucky R1,?A=Piolín R3, ?A=Tucky

(animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky) (vertebrado Tucky) (vertebrado Piolín)

Regla R3: SI (vertebrado ?A) (ladra ?A) ENT añadir (perro ?A) – 16 –

Ejemplo de inferencia hacia adelante en BC de reglas BASE DE HECHOS BH3

CONSULTA: ¿(perro Tucky)?

(animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky) (vertebrado Tucky) (vertebrado Piolín)

BASE DE REGLAS Regla R1: SI (animal ?A) (esqueleto ?A si) ENT añadir (vertebrado ?A)

Motor de inferencia Ciclo3

Regla R2: SI (animal ?A) (esqueleto ?A no) ENT añadir (invertebrado ?A)

R1,?A=Tucky R1,?A=Piolín R3, ?A=Tucky

(animal Tucky) (animal Piolín) (esqueleto Piolín si) (esqueleto Tucky si) (ladra Tucky) (vertebrado Tucky) (vertebrado Piolín) (perro Tucky)

Regla R3: SI (vertebrado ?A) (ladra ?A) ENT añadir (perro ?A) – 17 –

BASE DE HECHOS BH4

Ciclo de Inferencia: Aspectos de Implementación Problema: • Ineficiencia del mecanismo de inferencia debido a la fase 1 (determinación del conjunto conflicto) • en cada ciclo se equiparan todas las reglas con todos los elementos de la MT para construir el nuevo conjunto conflicto Solución: Algoritmo de Redundancia Temporal (RETE) • se construye el conjunto conflicto de forma incremental Cambios en la MT

Red RETE

Cambios en el CC

• La red RETE se genera al principio de la ejecución del sistema de producción mediante un compilador.

– 18 –

RETE (Redundancia Temporal) • Red de nodos (RETE) • En cada ciclo de funcionamiento, las acciones modifican Memoria de Trabajo (inclusión o borrado) • En cada ciclo, no es necesario equiparar todas las reglas con todos los elementos de la MT • La red RETE se genera al principio mediante un compilador

– 19 –

RETE: Ejemplo

• Compartir partes comunes • Ej.:

¿es 1º una a?

– R7: SI (a b ?x) (c ?x d e ?y) ENT ... – R8: SI (a b ?x) (c ?x d f ?y) ENT ...

¿es 1º una c?

¿es 3º una d?

¿es 2º una b?

¿es 4º una e?

¿es 4º una f?

Nodo de unión si 3º izda = 2º dcha

Nodo de unión si 3º izda = 2º dcha

Informar de cambios en R7

Informar de cambios en R8

– 20 –

Diseño de BCs: Errores frecuentes Una regla NO es una estructura “if-then-else” SI condicion1 condicion2 ... ENTONCES acciones1 EN CASO CONTRARIO acciones2 ¿QUÉ HACER? • Identificar las condiciones que no se cumplen para la ejecución de las acciones2 • Crear dos reglas, una para cada bloque de acciones – 21 –

Diseño de BCs: Errores frecuentes No pueden aparecer OR en el consecuente de la regla SI condicion1 condicion2 ... ENTONCES acciones1 OR acciones2 ¿QUÉ HACER? • Crear dos reglas, una para cada bloque de acciones – para conservar la precedencia, p.e. establecer prioridades entre las reglas Ri: SI condicion1 condicion2... ENTONCES acciones1

Rj: SI condicion1 condicion2... ENTONCES acciones2 – 22 –

Diseño de BCs: Errores frecuentes En el consecuente de la regla NO hay elementos de decisión SI condicion1 , condicion2 ... ENTONCES acciones1 SI condicion4 ... ENTONCES acciones2 ¿QUÉ HACER? • Introducir señalizadores que provoquen la ejecución prioritaria de reglas con tales elementos • No olvidar borrar los señalizadores Ri: SI condicion1 , condicion2 ... ENTONCES acciones1 añadir S – 23 –

Rj: SI S, condicion4 ... ENTONCES acciones2 borrar S

Diseño de BCs: Errores frecuentes Desde una regla nunca se puede lanzar otra regla Ri: SI condicion1 condicion2 ... ENTONCES Rj

¿QUÉ HACER? • Introducir señalizadores que provoquen la ejecución de Rj • No olvidar borrar los señalizadores al ejecutar la regla Rj

– 24 –

Diseño de BCs: Errores frecuentes BR

Regla R1: SI (envio ?e ?origen ?destino) (dia-entrega ?e hoy) (coste ?e ?coste) ENTONCES añadir(coste ?e ?coste+10)

BH (envio E1 Madrid Barcelona)

Motor de inferencia

Ciclo1 ?e=E1 ?origen=Madrid ?destino=Barcelona ?coste=7

(dia-entrega E1 hoy) (coste E1 7)

BH (envio E1 Madrid Barcelona) ERROR: El coste del envío es único SOLUCIÓN: Modificar la regla – 25 –

(dia-entrega E1 hoy) (coste E1 7) (coste E1 17)

Diseño de BCs: Errores frecuentes BR

Regla R1: SI (envio ?e ?origen ?destino) (dia-entrega ?e hoy) (coste ?e ?coste) ENTONCES borrar (coste ?e ?coste) añadir (coste ?e ?coste+10)

BH (envio E1 Madrid Barcelona)

Motor de inferencia

Ciclo1 ?e=E1 ?origen=Madrid ?destino=Barcelona ?coste=7

(dia-entrega E1 hoy) (coste E1 7)

BH

PROBLEMA: Bucle infinito SOLUCIÓN: • Introducir señalizadores, • Utilizar nuevo hecho (coste-final) – 26 –

(envio E1 Madrid Barcelona) (dia-entrega E1 hoy) (coste E1 7) (coste E1 17)

Características de la Representación del Conocimiento • Ventajas – Representación próxima a la forma de proceder de los expertos – Sintaxis simple y homogénea – Permite seguimiento del proceso de deducción

• Inconvenientes – Conocimiento procedimental y heurístico • Dificultad para verificar la consistencia de la BC

– 27 –

Sistemas Basados en Reglas

Tema 2. Sistemas Basados en Reglas 1. Descripción 2. CLIPS 3. Ejemplos

...

– 28 –

Qué es CLIPS • CLIPS (C Language Integrated Production System): – herramienta para desarrollar sistemas inteligentes basadas en reglas – desarrollada en C/ANSI por Software Technology Branch, NASA/Lyndon B. Johnson Space Center desde 1986 – implementación eficiente del encadenamiento hacia delante

• Facilidades adicionales – – – –

diferentes estrategias de resolución de conflictos adición dinámica de reglas sistema de mantenimiento de verdad lenguaje orientado a objetos: COOL (Clips Object-Oriented Language)

• Extensiones: – – – –

fácilmente embebible en aplicaciones en C, FORTRAN, Java, ... disponible en diversas plataformas (MS-DOS/Windows, Unix) extensiones para Lógica Borrosa (FuzzyCLIPS) JESS: versión en Java que usa el sistema de objetos correspondiente – 29 –

Sistemas Basados en Reglas

Tema 2. Sistemas Basados en Reglas 1. Descripción 2. CLIPS 1. Base de Hechos 2. Base de Reglas 3. Motor de Inferencia 3. Ejemplos

…

– 30 –

CLIPS: Base de Hechos Terminología • La BH en CLIPS se llama memoria de trabajo (MT) • puede contener diferentes tipos de hechos

Hechos ordenados (“ordered facts”) • Patrones con uno o varios campos – la posición de la información en el hecho es relevante – información tipada: símbolos, integers, real, string, etc. – sintaxis acostumbrada

• Ejemplos: (hola) (alumnos Pepe Juan Luis) (nombre "Juan") (edad 14) (pi 3.1415) – 31 –

CLIPS: Base de Hechos Patrones no-ordenados (deftemplate) • Permiten definir la información en forma de clases de elementos y atributos de esas clases. • Permiten abstraer la estructura de un hecho asignando un nombre a cada campo – campos slot: pueden tener exactamente un valor – campos multislot: pueden tener varios valores (de varios tipos)

• Se permite una cadena de caracteres como comentario (opcional) • Ejemplo: (deftemplate clase "Informacion sobre clases" (slot grupo) (slot aula) (slot hora) (multislot alumnos) (multislot profesor)) – 32 –

CLIPS: Base de Hechos Hechos no-ordenados (“unordered facts”, “deftemplate facts”) • • • • •

hechos que “instancian” los patrones deftemplate el primer nombre del hecho no-ordenado referencia su deftemplate el orden de los campos no tiene importancia se pueden omitir slots del patrón deftemplate Ejemplo: (cliente (cliente (clase

(nombre Juan Pérez) (id 33435)) (id 33435) (nombre Juan Pérez)) (aula "III-002") (profesor Alberto Fernández) (alumnos))

– 33 –

CLIPS: Base de Hechos Hechos iniciales: • los hechos iniciales, se definen con la estructura deffacts – ejemplo1: (deffacts hechos-600 “información del 600” (modelo 600) (puertas 2) ) – ejemplo2: (deffacts OtrosHechos (cliente (nombre Juan Pérez) (id 33435)) (cliente (nombre Rosa Gómez) (id 33436)) )

• por defecto existe el hecho inicial (initial-fact) • los hechos iniciales se añadirán a la MT al hacer reset – 34 –

CLIPS: Base de Hechos Indices de hechos (etiquetas temporales, time-tags) • CLIPS genera para cada hecho un índice relativo al tiempo de su creación: – Al primer hecho creado le corresponde la etiqueta temporal 0 : f-0 (initial-fact) – Ejemplo: Si (ladra perro) es el segundo hecho añadido a la MT, su etiqueta temporal el f-1 – Nunca disminuye y nunca se reasigna. Para cada nuevo hecho que se cree o modifique se incrementa en uno

• Sirven para – Identificar de forma única y simplificada cada hecho – Saber el tiempo que lleva un hecho en la memoria de trabajo

– 35 –

CLIPS: Base de Hechos Ordenes básicas de manejo de la MT (facts) Lista los hechos de la MT (assert ) Añade (si no existe) un hecho a la MT (retract ) Elimina un hecho de la MT (modify *) Modifica un hecho (no ordenado) de la MT • (duplicate *) Como modify pero sin borrar el antiguo • (clear) Elimina todos los hechos y construcciones de la MT • (reset) Elimina todos los hechos de la MT, elimina las activaciones de la agenda y restaura las condiciones iniciales:

• • • •

Añade initial-fact – Añade el conocimiento inicial definido con deffacts – Añade las variables globales con su valor inicial – Fija como módulo principal el módulo MAIN –

– 36 –

CLIPS: Base de Hechos Ejemplo: CLIPS> (reset)

CLIPS> (retract 1)

CLIPS> (facts)

CLIPS> (assert (hola))

f-0 (initial fact)



For a total of 1 fact.

CLIPS> (facts)

CLIPS> (assert (hola))

f-0 (initial-fact)



f-2 hola

CLIPS> (facts)

For a total of 2 facts.

f-0 (initial-fact)

CLIPS> (clear)

f-1 hola

CLIPS> (facts)

For a total of 2 facts.

CLIPS>

– 37 –

Sistemas Basados en Reglas

Tema 2. Sistemas Basados en Reglas 1. Descripción 2. CLIPS 1. Base de Hechos 2. Base de Reglas 3. Motor de Inferencia 3. Ejemplos

…

– 38 –

CLIPS: Base de Reglas Sintaxis

Ejemplo

(defrule marca-del-600 (defrule "Marca del modelo 600" [] (modelo 600) [] => (premisa 1) (assert (marca-es SEAT)) (premisa 2) ) ... (premisa N) Semántica => • Si “se cumplen” todas las premisas (accion 1) • Se ejecutan todas las acciones (accion 2) ... (accion M) ) – 39 –

CLIPS: Base de Reglas

Elementos de las premisas • Patrones – existencia / ausencia de hechos en la BH – pueden instanciar variables a partir de hechos

• Restricciones – restricciones como premisas (tipo test) – restricciones de variables (conectivas)

– 40 –

CLIPS: Base de Reglas • Patrones: Constantes – equiparación con hechos concretos en la MT – Ejemplos: (defrule encontrar-dato (dato 1 azul rojo) =>)

(defrule encontrar-Roberto (persona (nombre Roberto) (edad 20)) =>)

– 41 –

CLIPS: Base de Reglas Equiparación de patrones constantes • Caso a: Hechos ordenados BR

MT

1 equiparación

(defrule R1 (A B) => (assert (C D)) f-1 f-2

(A B) (C D)

Conjunto Conflicto={R1(f-1)} La ejecución de la regla introduce en la MT a (CD)

• Caso b: hechos no ordenados BR

(defrule R1 (clase1 (nombre1 A)) => (assert (C D))

MT

f-1(clase1 (nombre1 A)) f-2(C D)

1 equiparación Conjunto Conflicto={R1(f-1)}

La ejecución de la regla introduce en la MT a (CD)

– 42 –

CLIPS: Base de Reglas • Patrones: Comodines – patrones genéricos que equiparan con diferentes hechos – se usan cuando no importa el valor de un campo •? : • $? :

Equipara con un campo Equipara con cero a n campos

• Ejemplos:

(defrule encontrar-dato (dato ? azul rojo $?)=>) (defrule encontrar-dato (dato $? amarillo $?)=>)

– 43 –

CLIPS: Base de Reglas • Equiparación con comodines – cada par hecho-comodín puede dar lugar a una instanciación – Ejemplo:

BR

(defrule R1 (A $? B) =>...

MT

f-1 f-2 f-3

3 equiparaciones de la misma regla Eq1: $?= Eq2: $?=3 Eq3: $?= C E B

(A B) (A 3 B) (A C E B B)

Conjunto Conflicto: {R1(f-1),R1(f-2),R1(f-3)}

– Un comodín repetido puede tener valores diferentes – 44 –

CLIPS: Base de Reglas • Patrones: Variables – patrones genéricos que equiparan con diferentes hechos – almacenan valores de campos para usarlos posteriormente • ?x : variable de valor único • $?x : variable multivalor (cero, uno o más valores) • Ejemplos: (defrule encontrar-dato (dato ?x ?y ?z)=>) (defrule encontrar-dato (dato ?x $?y ?z)=>)

– 45 –

CLIPS: Base de Reglas • Equiparación con variables – Una variable que aparece dos o más veces en la regla debe equipararse en todas las ocurrencias con el mismo valor

BR

(defrule R1 (animal ?x) (piel pelo ?x) => (assert (especie mamifero ?x))

MT

f-1 f-2 f-3 f-4 f-5

(animal Tucky) (piel pelo Dolly) (piel pelo Tucky) (animal Dolly) (animal Dumbo)

Eq1: ?x=Tucky : (animal Tucky) (piel pelo Tucky) Eq2: ?x=Dolly : (animal Dolly) (piel pelo Dolly) Dumbo no equipara por no tener (piel pelo Dumbo) en la MT Conjunto Conflicto = { R1(f-1,f-3), R1(f-4,f-2) } – 46 –

CLIPS: Base de Reglas Patrones: Ausencia de patrones • Sintaxis: (not ()) • la premisa se cumple, si no hay ningún hecho en la MT que equipara con • Ejemplo: (defrule volar (pajaro ?x) (not (avestruz ?x)) => (assert (vuela ?x)) )

• Hipótesis del mundo cerrado: – todo lo que no se encuentra en la MT es “falso”

– 47 –

CLIPS: Base de Reglas

• Equiparación basada en la ausencia de patrones – Ejemplo: (defrule R1 (A ?x) (not (B ?x)) => ) MT: (A C) (B D) (A B) (A A) (B A)

Eq1: ?x=C Eq2: ?x=B ?x=A no equipara porque en la MT está (B A)

– 48 –

CLIPS: Base de Reglas Patrones: Direcciones de hechos (referencia a la MT): • se pueden almacenar referencias a los hechos de la MT en variables • dichas referencias pueden ser usadas en las acciones de consecuente • Ejemplo (defrule matrimonio ?ref-soltero (retract ?ref-soltero) (assert (casado ?nombre)) )

– 49 –

Premisas de las Reglas CLIPS: Restricciones Restricciones de premisa: • premisa del tipo (test ()) • forma más general para comprobar el cumplimiento de una condición • Expresiones booleanas se construyen en notación prefija sobre: – Funciones de comparación • Numérica: =, , , >=, = ?mes 1) () – 50 –

Premisas de las Reglas CLIPS: Restricciones Restricciones conectivas (connective constraints) : • limitan la posibilidad de equiparación de variables • restricciones conectivas con constantes: – Sintaxis: ?x&˜ – Semántica:?x equipara con cualquier valor menos – ejemplos (defrule no-rojo-ni-verde (color ?x&~rojo&~verde) =>)

(defrule no-rojo-ni-verde-test (color ?x) (test (neq ?x rojo verde)) =>)

(defrule datos-distintos (dato ?x ?y&~?x) =>)

(defrule datos-distintos-test (dato ?x ?y) (test (neq ?x ?y)) =>)

– 51 –

Premisas de las Reglas CLIPS: Restricciones Restricciones conectivas de resultado (return value constraints) • Sintaxis: ?x&=() • Semántica: – ?x equipara sólo con el valor que resulta de evaluar – puede ser de cualquier tipo (i.e. se aplica eq)

• Ejemplos: (defrule mas-una (dato ?x ?y&=(+ ?x 1)) =>)

(defrule mas-una-test (dato ?x ?y) (test (= ?y (+ ?x 1))) =>)

(defrule segundo-elemento (lista $?l) (valor ?x&=(nth$ 2 $?l)) =>)

(defrule segundo-elemento-test (lista $?l) (valor ?x) (test (eq ?x (nth$ 2 $?l))) =>)

– 52 –

Premisas de las Reglas CLIPS: Restricciones Restricciones conectivas de predicado (predicate constraints) • Sintaxis: ?x&:() • Semántica: – ?x equipara con cualquier valor si sólo si es true – también suele contener variables

• Ejemplos: (defrule valor-numerico (valor ?x&:(numberp ?x)) =>)

(defrule valor-numerico-test (valor ?x) (test (numberp ?x)) =>)

(defrule dos-o-mas (lista $?y&:(> (length$ ?y) 2)) =>)

(defrule dos-o-mas-test (lista $?y) (test (> (length$ ?y) 2)) =>)

– 53 –

Acciones de las Reglas CLIPS • • • • •

Modificar MT: assert, retract, modify, duplicate Entrada/Salida: printout, read, readline, open, close Parada del proceso de inferencia: halt Asignar valores a variables (en el consecuente): bind Ejemplo: (defrule coste-del-envio (envio ?paquete ?origen ?destino) (dia-entrega ?paquete hoy) ?coste-inicial (retract ?coste-inicial) (bind ?suplemento (read)) (bind ?nuevo-precio (+ ?precio ?suplemento)) (assert (coste-final ?paquete ?nuevo-precio)) (printout t "Coste final es " ?nuevo-precio crlf) (halt)

) – 54 –

Funciones predefinidas en CLIPS Funciones de predicado

Funciones campos multislot Funciones matemáticas

• • • • • • • • • • • • •

• • • • • • • • • • • •

numberp floatp integerp lexmep stringp symbolp evenp oddp multifieldp eq neq =, , >, >=, ?x (+10 ?y)) (< ?x 100))) =>) – 59 –

CLIPS: Motor de inferencia Estrategias de resolución de conflictos (II): • LEX Strategy – Se ordenan los time-tag en orden decreciente y se comparan uno a uno, hasta encontrar uno mayor que otro – En caso de que no haya el mismo número de time-tag se añaden ceros al final – Si igual entonces se elige la más específica – Ejemplo: • Conjunto Conflicto= {R1(f-4), R2(f-2,f-4)} • Para R1: 4, 0 / para R2: 4, 2 / por tanto LEX elige R2

• MEA Strategy – parecido a LEX, pero mirando sólo el primer patrón que equipara en la regla (si es el mismo se usa LEX) – Ejemplo: R1

• Random Strategy – A cada activación se le asigna un número aleatorio para determinar su orden en la agenda. – 60 –

Sistemas Basados en Reglas

Tema 2. Sistemas Basados en Reglas 1. Descripción 2. CLIPS 3. Ejemplos

…

– 61 –

Diseño de BCs Proceso: • Definir el modelo: – conceptualizar el mundo: ¿qué es importante? – p.e.: bloques, mesas, posición vertical relativa de los bloques

• Definir la ontología: – Escoger vocabulario – p.e.: block1, clear, on, encima...

• Definir conocimiento del dominio: – Codificar el conocimiento general sobre el dominio – p.e.: (defrule R (on ?x ?y) => (assert (encima ?x ?y)))

• Definir conocimiento del caso: – Codificar una descripción del caso específico (p.e.: estado actual) – p.e.: (deffacts ((On A B) (On B T)))

• Hacer consultas – 62 –

Ejemplo: El mundo de los circuitos

• Construir una BC que permita contestar preguntas acerca del comportamiento del siguiente circuito

1 2

xor1

xor2

3

1

and2

or1

and1

Circuito C – 63 –

2

El mundo de los circuitos • Definir el modelo: – características relevantes • circuitos, puertas binarias, tipos de puertas binarias (and, or, xor), terminales de puertas/circuitos, conexiones entre terminales, señales, señales en las terminales, ...

– características irrelevantes • rutas de las líneas, posición de las puertas, tamaño de las puertas etc.

• Definir la ontología: – Puertas: patrón no ordenado puerta • Identificación puerta: slot id-puerta • Tipo de puertas: slot tipo • Terminales: slots id-entrada-1, id-entrada-2, id-salida

– Circuito: patrón circuito • Identificación circuito: slot id-circuito • Terminales: multislots id-entradas, id-salidas

– Conexiones entre terminales: patrón ordenado conexión/4 – Señales: valores booleanos TRUE y FALSE – Señales en las terminales: patrón no ordenado estado-terminal – 64 –

Declaración parcial de la Ontología • Declaración de la estructura de patrones no-ordenados: (deftemplate puerta "Puertas logicas binarias" (slot id-puerta) (slot tipo (allowed-symbols (slot id-entrada-1 (default (slot id-entrada-2 (default (slot id-salida-1 (default

AND OR XOR)) e1)) e2)) s1)) )

(deftemplate circuito "Circuito con multiples entradas y salidas" (slot id-circuito) (multislot id-entradas) (multislot id-salidas ) ) (deftemplate estado-terminal "Senyal en terminales de una puerta o circuito" (slot id-elemento) (slot id-terminal) (slot senyal (allowed-symbols TRUE FALSE)) ) – 65 –

Conocimiento del dominio • Regla para modelar el comportamiento de una puerta AND: (defrule logica-AND (puerta (id-puerta ?p) (tipo AND) (id-entrada-1 ?e1) (id-entrada-2 ?e2) (id-salida-1 ?s1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e1) (senyal ?senyal-e1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e2) (senyal ?senyal-e2) ) => (assert (estado-terminal (id-elemento ?p) (id-terminal ?s1) (senyal (and ?senyal-e1 ?senyal-e2)) ) ) ) – 66 –

Conocimiento del dominio • Regla para modelar el comportamiento de una puerta OR: (defrule logica-OR (puerta (id-puerta ?p) (tipo OR) (id-entrada-1 ?e1) (id-entrada-2 ?e2) (id-salida-1 ?s1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e1) (senyal ?senyal-e1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e2) (senyal ?senyal-e2) ) => (assert (estado-terminal (id-elemento ?p) (id-terminal ?s1) (senyal (or ?senyal-e1 ?senyal-e2)) ) ) ) – 67 –

Conocimiento del dominio • Regla para modelar el comportamiento de una puerta XOR: (defrule logica-XOR (puerta (id-puerta ?p) (tipo XOR) (id-entrada-1 ?e1) (id-entrada-2 ?e2) (id-salida-1 ?s1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e1) (senyal ?senyal-e1) ) (estado-terminal (id-elemento ?p) (id-terminal ?e2) (senyal ?senyal-e2) ) => (assert (estado-terminal (id-elemento ?p) (id-terminal ?s1) (senyal (not (eq ?senyal-e1 ?senyal-e2))) ) ) ) – 68 –

Conocimiento del dominio • Regla para propagar señales por conexiones: (defrule logica-conexion "Si dos terminales estan conectados, entonces tienen la misma senyal" (estado-terminal (id-elemento ?elemento-A) (id-terminal ?terminal-A) (senyal ?senyal)) (conexion ?elemento-A ?terminal-A ?elemento-B ?terminal-B) => (assert (estado-terminal (id-elemento ?elemento-B) (id-terminal ?terminal-B) (senyal ?senyal)))) – 69 –

Conocimiento del caso • Hechos iniciales para definir los elementos de un circuito concreto: (deffacts lista-de-elementos (circuito (id-circuito C) (id-entradas e1 e2 e3) (id-salidas s1 s2) ) (puerta (id-puerta X1) (tipo XOR)) (puerta (id-puerta X2) (tipo XOR)) (puerta (id-puerta A1) (tipo AND)) (puerta (id-puerta A2) (tipo AND)) (puerta (id-puerta O1) (tipo OR )) )

– 70 –

Conocimiento del caso • Hechos iniciales para definir las conexiones concretas entre elementos: (deffacts lista-de-conexiones (conexion C e1 X1 e1) (conexion C e1 A1 e1) (conexion C e2 X1 e2) (conexion C e2 A1 e2) (conexion C e3 A2 e1) (conexion C e3 X2 e2) (conexion X1 s1 X2 e1) (conexion X1 s1 A2 e2) (conexion A1 s1 O1 e2) (conexion A2 s1 O1 e1) (conexion X2 s1 C s1) (conexion O1 s1 C s2) )

• Regla para completar conexiones: (defrule conexion "La conexion es conmutativa" (conexion ?p1 ?t1 ?p2 ?t2) => (assert (conexion ?p2 ?t2 ?p1 ?t1)) ) – 71 –

Conocimiento del caso • Regla para leer las señales iniciales en las entradas: (defrule leer-entradas (circuito (id-circuito ?c) (id-entradas $? ?t $?)) => (printout t "Circuito: " ?c " Entrada: " ?t " Senyal: " ) (bind ?senyal (read)) (assert (estado-terminal (id-elemento ?c) (id-terminal ?t) (senyal ?senyal)) ) )

– 72 –

Conocimiento del caso

• Regla para escribir las señales deducidas en las salidas: (defrule imprimir-salidas (estado-terminal (id-elemento ?c) (id-terminal ?t) (senyal ?senyal)) (circuito (id-circuito ?c) (id-salidas $? ?t $?)) => (printout t "Circuito: " ?c " Salida: " ?t " Senyal: " ?senyal crlf) )

– 73 –

Realizar Consultas

• Preguntar por las salidas que producen ciertas entradas: – Consulta a la BC CLIPS> (reset) CLIPS> (run) Circuito: C Entrada: e1 Circuito: C Entrada: e2 Circuito: C Entrada: e3

Senyal: TRUE Senyal: TRUE Senyal: FALSE

– Respuesta: Circuito: C Circuito: C

Senyal: FALSE Senyal: TRUE

Salida: 11 Entrada: e2

– 74 –

Ejercicio Suponga que se ha cargado la anterior Base de Conocimiento en CLIPS, y que se ha configurado para que aplique la estrategia breadth (amplitud). Suponga también que todos los hechos sobre conexiones se encuentran ya en la MT, y que se han leído ya los señales en los terminales de entradas, dando lugar a estos hechos (estado-terminal (estado-terminal (estado-terminal (estado-terminal (estado-terminal (estado-terminal

(id-elemento (id-elemento (id-elemento (id-elemento (id-elemento (id-elemento

A2) X2) X1) A1) X1) A1)

(id-terminal (id-terminal (id-terminal (id-terminal (id-terminal (id-terminal

e1) e2) e2) e2) e1) e1)

(senyal (senyal (senyal (senyal (senyal (senyal

TRUE) TRUE) FALSE) FALSE) TRUE) TRUE)

Simule algunos ciclos de razonamiento de CLIPS. ¿Qué se escribiría en en pantalla? ¿Cuál es la funcionalidad del circuito C? – 75 –

Modelar acciones Para modelar la función expandir: • un estado se caracteriza por un hecho en la memoria de trabajo • reglas modelan acciones: – el antecedente representa las precondiciones – el consecuente modela el resultado de la acción

• al disparar todas las reglas activadas por un estado, se obtienen los estados sucesores Implementación 1 (destructiva): • la regla borra el estado que la activaba, y sólo deja el estado actual en la memoria • Problema: – no queda traza de los estados visitados – al no mantener los estados hermanos en la MT, no se puede dar marcha atrás

– 76 –

Modelar acciones Implementación 2: • se mantienen todos los estados en la memoria (“árbol de búsqueda”) • las reglas aplicables en cada momento se encuentran en la agenda (conjunto conflicto) • completo con estrategia “breadth” (amplitud) Ejemplo: • dos jarras, con una capacidad de 3 litros (llamada Tres), y 4 litros (llamada Cuatro). • inicialmente Tres y Cuatro están vacías, y se intenta que haya 2l de agua en Cuatro • cualquiera de ellas puede llenarse con el agua de un grifo G. • el contenido tanto de Tres como de Cuatro puede vaciarse en una pila P. • es posible echar todo el agua de una jarra a la otra., pero no se dispone de dispositivos de medición adicionales.

– 77 –

Modelar acciones • Llenar jarras del grifo (defrule llenar-cuatro-del-grifo ?nodo (assert (situacion (padre ?nodo) (litros-en-cuatro 4) (litros-en-tres ?tres))) ) (defrule llenar-tres-del-grifo ?nodo (duplicate ?nodo (padre ?nodo) (litros-en-tres 3)) )

– 78 –

Modelar acciones • Vaciar jarras en la pila (defrule vaciar-cuatro-en-pila ?nodo ?cuatro 0)) => (duplicate ?nodo (padre ?nodo) (litros-en-cuatro 0)) )

(defrule vaciar-tres-en-pila ?nodo ?tres 0)) => (duplicate ?nodo (padre ?nodo) (litros-en-tres 0)) )

– 79 –

Modelar acciones • Llenar una jarra de la otra

(defrule llenar-cuatro-desde-tres ?nodo (+ ?cuatro ?tres) 4)) (test (< ?cuatro 4)) => (assert (situacion (padre ?nodo) (litros-en-cuatro 4) (litros-en-tres (- ?tres (- 4 ?cuatro))))) )

– 80 –

Modelar acciones • Llenar una jarra de la otra

(defrule llenar-tres-desde-cuatro ?nodo (+ ?cuatro ?tres) 3)) (test (< ?tres 3)) => (bind ?nuevo-cuatro (- ?cuatro (- 3 ?tres))) (assert (situacion (padre ?nodo) (litros-en-cuatro ?nuevo-cuatro) (litros-en-tres 3))) )

– 81 –

Modelar acciones • Vaciar una jarra en la otra: (defrule vaciar-tres-en-cuatro ?nodo (assert (situacion (padre ?nodo) (litros-en-cuatro (+ ?tres ?cuatro)) (litros-en-tres 0)) ) ) (defrule vaciar-cuatro-en-tres ?nodo (assert (situacion (padre ?nodo) (litros-en-cuatro 0) (litros-en-tres (+ ?tres ?cuatro)) ) ) ) – 82 –

Ejercicio

Representación de acciones con reglas: Aunque el número de estados para el problema de las jarras el relativamente pequeño, existen muchos ciclos, por lo que se genera un árbol de búsqueda bastante grande – ¿Cómo se podrían modificar las reglas para evitar ciclos simples? – ¿Cómo se podrían modificar las reglas para evitar todos los ciclos?

– 83 –

Modelar cambio ¿Cómo representar acciones en el mundo de los bloques ?

C A B

B C A

C A B

A B C

Problema: • estados parcialmente caracterizados – sólo algunas propiedades del estado son relevantes – no se puede definir de antemano un deftemplate para estados

• Solución: – hechos ordenados: asignar un nombre a cada estado, y añadirlo como argumento a cada propiedad – p.e.: (on C A S0), (on A T S0), (on B T S0), (clear C S0), (clear B S0),(clear T S0) – 84 –

Modelar cambio: Axiomas de efecto Reglas de efecto: • describir qué propiedades son relevantes para una acción – el antecedente describe las precondiciones para que se pueda realizar la acción – el consecuente describe las nuevas propiedades (las que no se cumplen en el estado actual S1, pero sí en el estado resultante S2) (defrule efecto-move (clear ?x ?s1) (clear ?z&~?x ?s1) (on ?x ?y&~?z ?s1) => (bind ?s2 (gensym*)) (assert (on ?x ?z ?s2)) (assert (clear ?y ?s2)) (assert (clear T ?s2)) (assert (move ?s1 ?s2 ?x ?y ?z)) ) – 85 –

Modelar cambio: Axiomas de marco Reglas de marco: • Problema: – las acciones sólo cambian algunas propiedades – la mayoría de las propiedades no es afectada por una acción – de momento no se puede deducir que después de poner C de A sobre T en el estado s0, se cumple (on A T S1)

• Solución: – describir qué propiedades no cambian con una acción

• Reglas de marco: – reglas que indican qué propiedades no cambian – aquí: una reglas de marco para cada par propiedad/acción

– 86 –

Modelar cambio: Axiomas de marco

• Regla de marco para clear: (defrule marco-move-1 (move ?s1 ?s2 ?x ?y ?z) (clear ?u&~?z ?s1) => (assert (clear ?u ?s2)) )

• Regla de marco para on: (defrule marco-move-2 (move ?s1 ?s2 ?u ?v ?z) (on ?x&~?u ?y ?s1) => (assert (on ?x ?y ?s2)) )

– 87 –

Ejemplo de ejecución (Breadth): ciclo 0

• Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

C A B

• Agenda: 0 efecto-move: f-4,f-5,f-3

– 88 –

“move(C,A,T)”

Ejemplo de ejecución: ciclo 1

Se ejecuta la regla efecto: “cambios producidos por move(C,A,T) ” • Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

f-6 f-7 f-8 f-9

(on C T gen1) (clear A gen1) (clear T gen1) (move S0 gen1 C A T)

• Agenda: 0 marco-move-1: f-9,f-4 0 marco-move-2: f-9,f-1 0 marco-move-2: f-9,f-2

– 89 –

“clear(C) persiste en gen1” “on(B,T) persiste en gen1” “on(A,B) persiste en gen1”

Ejemplo de ejecución: ciclo 2

Se ejecuta la regla marco: “clear(C) persiste después de move(C,A,T) ” • Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

f-6 (on C T gen1) f-7 (clear A gen1) f-8 (clear T gen1) f-9 (move S0 gen1 C A T) f-10 (clear C gen1)

• Agenda: 0 marco-move-2: f-9,f-1 0 marco-move-2: f-9,f-2 0 efecto-move: f-10,f-7,f-6

– 90 –

“on(B,T) persiste en gen1” “on(A,B) persiste en gen1” “move(C,T,A) en gen1”

Ejemplo de ejecución: ciclo 3

Se ejecuta la regla efecto: “on(B,T) persiste después de move(C,A,T) ” • Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

f-6 (on C T gen1) f-7 (clear A gen1) f-8 (clear T gen1) f-9 (move S0 gen1 C A T) f-10 (clear C gen1) f-11 (on B T gen1)

• Agenda: 0 marco-move-2: f-9,f-2 0 efecto-move: f-10,f-7,f-6

– 91 –

“on(A,B) persiste en gen1” “move(C,T,A) en gen1”

Ejemplo de ejecución: ciclo 4

Se ejecuta la regla efecto: “on(A,B) persiste después de move(C,A,T)” • Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

f-6 (on C T gen1) f-7 (clear A gen1) f-8 (clear T gen1) f-9 (move S0 gen1 C A T) f-10 (clear C gen1) f-11 (on B T gen1) f-12 (on A B gen1)

• Agenda: 0 efecto-move: f-10,f-7,f-6 0 efecto-move: f-7,f-10,f-12 0 efecto-move: f-7,f-8,f-12

... – 92 –

“move(C,T,A) en gen1” “move(A,B,C) en gen1” “move(A,B,T) en gen1”

Ejemplo de ejecución: ciclo 5

Se ejecuta la regla efecto: “cambios producidos por move(C,T,A)” • Memoria de Trabajo f-0 f-1 f-2 f-3 f-4 f-5

(initial-fact) (on B T S0) (on A B S0) (on C A S0) (clear C S0) (clear T S0)

f-6 (on C T gen1) f-13 (on C A gen2) f-7 (clear A gen1) f-14 (clear T gen2) f-8 (clear T gen1) f-15 (move gen1 gen2 f-9 (move S0 gen1 C A T) C T A) f-10 (clear C gen1) f-11 (on B T gen1) f-12 (on A B gen1)

• Agenda: 0 0 0 0 0 0

efecto-move: f-7,f-10,f-12 efecto-move: f-7,f-8,f-12 marco-move-1: f-15,f-8 marco-move-1: f-15,f-10 marco-move-2: f-15,f-11 marco-move-2: f-15,f-12 – 93 –

“move(A,B,C) en gen1” “move(A,B,T) en gen1” “clear(T) persiste en gen1” “clear(C) persiste en gen1” “on(B,T) persiste en gen1” “on(A,B) persiste en gen1”

...