Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion

Modelos Cualitativos

Algoritmo

Eduardo Morales, Enrique Sucar INAOE

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

1 / 40

Contenido

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

´ 1 Introduccion

´ Simulacion Algoritmo

2 QSIM

´ 3 Simulacion 4 Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

2 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Conocimiento superficial vs. profundo. • Normalmente los SE tienen conocimiento superficial en

´ forma de reglas de produccion. • El conocimiento superficial representa conocimiento

que puede utilizarse en situaciones espec´ıficas, en donde las conclusiones se derivan directamente de las observaciones, e.g., IF el tanque esta vacio Then el coche no arranca

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

3 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Un sistema f´ısico puede describirse en terminos ´ de sus

componentes y conecciones. • La motivacion ´ es capturar conocimiento de sentido comun ´ de los expertos. • El conocimiento profundo se refiere a las estructuras

internas y causales de un sistema y considera las interacciones entre sus componentes.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

4 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

5 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Una forma de representar conocimiento profundo es

por medio de modelos cualitativos. • Normalmente se hace una simulacion ´ cualitativa. • Surgio´ al tratar de resolver problemas de ingenier´ıa y

´ grandes o dandose cuenta que simuladores mas mejores resolvedores de ecuaciones no resolverian totalmente el problema.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

6 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

Sistema F´ısico

Comportamiento Real

-

´ Simulacion Algoritmo

?

´ Ecuaciones Diferenciales

?

Restricciones Cualitativas

Eduardo Morales, Enrique Sucar (INAOE)

´ numerica ´ solucion o anal´ıtica

´ simulacion cualitativa

Modelos Cualitativos

?

fi : R ∗ → R

?

-

´ del Descripcion Comportamiento

7 / 40

´ Introduccion Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

Modelos Cualitativos y QSIM • Un modelo cualitativo consiste en un conjunto de

´ variables de estado (o parametros) del sistema y un conjunto de restricciones que relacionan las variables.

´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

8 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Restricciones CantA + CantB = Total PresA = M+ (CantA) PresB = M+ (CantB) PresA - PresB = ∆PAB flujoA−>B = M+ (∆PAB)

Valores Corresp. (0 0) (∞∞) (0 0) (∞∞) (−∞ − ∞) (0 0)(∞∞)

d CantB/dt = flujoA−>B d CantA/dt = - flujoA−>B

Variables CantA (0 AMax ∞) CantB (o BMax ∞) PresA (0 ∞) PresB (0 ∞) ∆PAB (-∞ 0 ∞) flujoA−>B (-∞ 0 ∞) Total (0 ∞)

´ inicial queremos predecir el Dada una descripcion comportamiento.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

9 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

10 / 40

´ Introduccion Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

11 / 40

´ Introduccion

Variables Cualitativas

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Operan sobre funciones razonables. Si [a, b] ⊆ R∗ , la ´ f : [a, b] → R∗ es una funcion ´ razonable sobre [a, b] funcion si: 1

f es continua es [a, b]

2

f es continuamente diferenciable en (a, b)

3

´ f tiene un numero finito de puntos de infleccion ´ (cr´ıticos) en cualquier intervalo cerrado

4

existen los l´ımites limt→a f 0 (t) = f 0 (a) y limt→b f 0 (t) = f 0 (b)

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

12 / 40

´ Introduccion Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Espacios Cualitativos - Valores Caracter´ısticos • El espacio cualitativo esta´ definido por un conjunto de

s´ımbolos totalmente ordenado (valores landmark (caracter´ısticos)) l1 < l2 < . . . < lk • Cada landmark es un nombre simbolico ´ de un valor

particular cuyo valor actual no se conoce. Por default: (−∞, 0, ∞) • Se debe de incluir un valor landmark por cada punto de

´ (i.e., f 0 (t) = 0), por lo que durante la infleccion ´ a veces es posible crear nuevos landmarks. simulacion

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

13 / 40

´ Introduccion Modelos Cualitativos

Restricciones Cualitativos

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Las restricciones representan versiones cualitativas de

´ operaciones matematicas comunes, tales como suma, ´ ´ y diferenciacion, ´ y permiten mapear multiplicacion directamente una gran cantidad de ecuaciones diferenciales.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

14 / 40

QSIM

QSIM

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

• QSIM es un sistema para simulacion ´ cualitativa

desarrollado por B. Kuipers y otros

´ Simulacion Algoritmo

• Dado un conjunto incompleto de estados de variables y

un conjunto de restricciones, QSIM determina todos los posibles estados que son consistentes con las restricciones. • El estado cualitativo de un variable es una lista con su

valor cualitativo (en o entre valores caracter´ısticos) y la derivada cualitativa: aumentando (inc), decreciendo (dec) o constante (std).

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

15 / 40

QSIM

Estado Cualitativo

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Defn: Sean l1 < . . . < lk los valores caracter´ısticos de f : [a, b] → R∗ , para cualquier t ∈ [a, b]. Un estado cualitativo de f en t, QS(f , t), en un par definido como:  lj if f (t) = lj ; un landmark qval = (lj , lj+1 ) if f (t) ∈ (lj , lj+1 )  if f 0 (t) > 0  inc std if f 0 (t) = 0 qdir =  dec if f 0 (t) < 0

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

16 / 40

QSIM

Estado Cualitativo

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• A pesar de que esta´ definido continuamente, la

´ se hace en puntos discretos. descripcion • Entre puntos distinguibles ti y ti+1 podemos definir un

valor cualitativo QS(f , ti , ti+1 ) para todo el tiempo entre ti y ti+1 . • Si un sistema, es un conjunto F = {f1 , . . . , fm } de

funciones fi : [a, b] → R∗ , el comportamiento cualitativo de un sistema se describe como una secuencia de estados de la forma:

QS(F , t0 ), QS(F , t0 , t1 ), QS(F , t1 ), . . . , QS(F , tn−1 , tn ), QS(F , tn )

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

17 / 40

QSIM Modelos Cualitativos

Restricciones Cualitativas

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• El estado cualitativo se expresa en terminos ´ de los

valores de las variables. Las relaciones entre las variables esta´ dado por las restricciones cualitativas: suma, mult, menos, deriv, M + , M − y constante. • Dada cualquier ODE (ecuaciones diferenciales

ordinarias), estan las podemos traducir a su equivalente QDE (ecuaciones diferenciales cualitativas), pero una QDE puede mapear a un numero infinito de ODE. ´

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

18 / 40

QSIM Modelos Cualitativos

Ejemplo

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion

d 2 u/dt − du/dt + arctanku = 0

Algoritmo

f1 = du/dt f2 = df1 /dt f3 = ku f4 = arctanf3 f2 − f1 + f4 = 0

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

deriv (u, f1 ) deriv (f1 , f2 ) mult(k , u, f3 ) M + (f3 , f4 ) suma(f2 , f4 , f1 )

19 / 40

QSIM Modelos Cualitativos

Valores Correspondientes

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Los valores correspondientes son tuplas de valores landmark que pueden tomar las variables en un tiempo determinado (e.g.,M + (x, y ), [(0, 0)]). [V ] = el signo de V   [+] if V > 0 [0] if V = 0 [V ]0 = signo(V )  [–] if V < 0 [V ]V0 = signo(V − V0 )

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

20 / 40

QSIM

Restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

SUMA: suma(x, y , z)[(x1 , y1 , z1 ), ...] (corresponding values) ˙ ] + [Y˙ ] = [Z˙ ] 1 [X suma [+] [0] [-] [+] [+] [+] [+]/[0]/[-] [0] [+] [0] [-] [−] [+]/[0]/[-] [-] [-] 2

[X ]xi + [Y]yi = [Z]zi

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

21 / 40

QSIM

Restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

MULT: mult(x, y, z)[(x1 , y1 , z1 ), ...]

´ Simulacion Algoritmo

1

2

[X ]0 [Y ]0 = [Z ]0 mult [+] [0] [-] [+] [+] [0] [-] [0] [0] [0] [0] [−] [-] [0] [+] [Y ]0 [X˙ ] + [X ]0 [Y˙ ] = [Z˙ ]

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

22 / 40

QSIM

Restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

MENOS: 1

[X ] = −[Y ]

2

[X ]xi = −[Y ]yi

3

Valores correspondientes: (0 0), (-∞, ∞), (∞, -∞)

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

23 / 40

QSIM

Restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion

´ M + : Monotonicamente creciente ˙ ˙ 1 [X ] = [ Y ]

Algoritmo

2

[X ]xi = [Y ]yi

´ M − : Monotonicamente decreciente ˙ ˙ 1 [X ] = −[Y ] 2

[X ]xi = −[Y ]yi

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

24 / 40

QSIM

Restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM

DERIV ˙ ] = [Y ]0 1 [X

´ Simulacion Algoritmo

CONSTANT ˙]=0 1 [X 2

[X ]a = 0

• Tambien ´ pueden existir para operaciones de muchas

variables. • Se pueden combinar los landmark con valores

´ informacion ´ cuantitativos para tener mas

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

25 / 40

QSIM

Manejo de restricciones

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Propagacion ´ de restricciones: Es eficiente, local,

pero no siempre exitosa • Propagar descripciones cualitativas entre variables a

traves de restricciones, e.g., si M + (x, y ) y [x]∗ = [+] => [y ]∗ = [+], si suma(x, y, z) y [x]0 = [+] y [z]0 = [−] => [y]0 = [−]. • Ejemplo, en el caso de tubo-U, dada la descripcion ´ inicial de Tanque A lleno y Tanque B vac´ıo (CantA = AMax y CantB = 0), podemos propagar para conocer los otros valores de las otras variables. • Satisfaccion ´ de restricciones: encuentra todas las

soluciones, pero es computacionalmente caro.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

26 / 40

´ Simulacion Modelos Cualitativos

´ Simulacion

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

27 / 40

´ Simulacion

´ Simulacion

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion

Tabla de transiciones de estados desde un punto:

QSIM ´ Simulacion Algoritmo

Trans-P P1 P2 P3 P4 P5 P6 P7

Eduardo Morales, Enrique Sucar (INAOE)

QS(f , ti ) < lj , std > < lj , std > < lj , std > < lj , inc > < (lj , lj+1 ), inc > < lj , dec > < (lj , lj+1 ), dec >

Modelos Cualitativos

⇒ QS(f , ti , ti+1 ) < lj , std > < (lj , lj+1 ), inc > < (lj−1 , lj ), dec > < (lj , lj+1 ), inc > < (lj , lj+1 ), inc > < (lj−1 , lj ), dec > < (lj , lj+1 ), dec >

28 / 40

´ Simulacion

´ Simulacion

Modelos Cualitativos Eduardo Morales, Enrique Sucar

Tabla de transiciones de estados desde un intervalo: ´ Introduccion QSIM ´ Simulacion Algoritmo

Trans-I I1 I2 I3 I4 I5 I6 I7 I8 I9

Eduardo Morales, Enrique Sucar (INAOE)

QS(f , ti , ti+1 ) < lj , std > < (lj , lj+1 ), inc > < (lj , lj+1 ), inc > < (lj , lj+1 ), inc > < (lj , lj+1 ), dec > < (lj , lj+1 ), dec > < (lj , lj+1 ), dec > < (lj , lj+1 ), inc > < (lj , lj+1 ), dec >

Modelos Cualitativos

⇒ QS(f , ti+1 ) < lj , std > < lj+1 , std > < lj+1 , inc > < (lj , lj+1 ), inc > < lj , std > < lj , dec > < (lj , lj+1 ), dec > < l ∗ , std > < l ∗ , std >

29 / 40

´ Simulacion Modelos Cualitativos

´ Simulacion

Eduardo Morales, Enrique Sucar

Entrada: 1 Un conjunto de {f1 , . . . , fm } de s´ımbolos representando funciones en el sistema 2 Un conjunto de restricciones aplicadas a los s´ımbolos funcionales: ADD(f , g, h), MULT (f , g, h), MINUS(f , g), DERIV (f , g), M + (f , g), M − (f , g). Cada una puede tener relacionada valores correspondientes ´ esta´ asociada con un conjunto ordenado 3 Cada funcion de s´ımbolos, representando valores caracter´ısticos ´ tiene por los menos el conjunto: (cada funcion {−∞, 0, +∞}) ´ puede tener asociada l´ımites superiores e 4 Cada funcion inferiores (valores caracter´ısticos donde las restricciones ya no aplican) 5 Un punto temporal inicial, t0 , y los valores cualitativos para cada de las fi en t0

´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

30 / 40

´ Simulacion

´ Simulacion

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

´ descripciones cualitativas para las Salida: una o mas ´ tiene: funciones dadas. Cada descripcion 1

2

3

Una secuencia {t0 , . . . , tn } de s´ımbolos, representando los puntos temporales ´ fi tiene un conjunto totalmente ordenado Cada funcion de valores caracter´ısitcos, posiblemente mayor que el original ´ tiene una descripcion ´ cualitativa en cada Cada funcion punto temporal o intervalo entre puntos temporales

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

31 / 40

Algoritmo

Algoritmo

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion

Coloca en ACTIVOS el estado inicial. REPEAT Until ACTIVOS = vac´ıo o Tiempo ≥ tiempo l´ımite. 1 2

Algoritmo

3

Selecciona un estado cualitativo de ACTIVOS ´ determina sus posibles transiciones Para cada funcion (usando la tabla) ´ genera un conjunto de tuples y Para cada restriccion, filtra de acuerdo a consistencia

4

Realiza filtrado de consistencia entre conjuntos de tuples (transiciones adyacentes deben de concordar con las transiciones de los parametros comunes)

5

Genera todas las intepretaciones globales ˜ Aplica filtros globales y anade los estados restantes a ACTIVOS

6

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

32 / 40

Algoritmo

Filtros

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

1

No cambio

2

Valores infinitos

3

Reconocer estado estable (quiescent)

4

Nuevos landmarks

5

Nuevos valores correspondientes en puntos temporales

6 7

Aparear estados e identificar ciclos ´ Propagar inconsistencias hacia atras

8

´ Regiones de transicion

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

33 / 40

Algoritmo

Ejemplo: Tiro vertical

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Restricciones: deriv (Y , V ), deriv (V , A), A(t) = g Estado Inicial: QS(A, t0 , t1 ) =< g, std > QS(V , t0 , t1 ) =< (0, ∞), dec > QS(Y , t0 , t1 ) =< (0, ∞), inc >

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

34 / 40

Algoritmo

Ejemplo: Tiro vertical

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

A V

Y

I1: < g, std > I5: < (0, ∞), dec > I6: < (0, ∞), dec > I7: < (0, ∞), dec > I9: < (0, ∞), dec > I4: < (0, ∞), inc > I8: < (0, ∞), inc >

Eduardo Morales, Enrique Sucar (INAOE)

=>< g, std > =>< 0, std > =>< 0, dec > =>< (0, ∞), dec > =>< L∗ , std > =>< (0, ∞), inc > =>< L∗ , std >

Modelos Cualitativos

35 / 40

Algoritmo Modelos Cualitativos

Ejemplo: Tiro vertical

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

deriv(Y,V) (I4,I5) c (I4,I6) c (I4,I7) (I4,I9) w (I8,I5) w (I8,I6) (I8,I7) c (I8,I9) c

deriv(V,A) (I5,I1) c (I6,I1) (I7,I1) (I9,I1) c

Modelos Cualitativos

36 / 40

Algoritmo

Ejemplo: Tiro vertical

Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion

Y I4 I8

Algoritmo

V I7 I6

A I1 I1

QS(A, t1 ) =< g, std > QS(V , t1 ) =< 0, dec > QS(Y , t1 ) =< Ymax , std >

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

37 / 40

Algoritmo Modelos Cualitativos

Ejemplo: Tanque

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

38 / 40

Algoritmo Modelos Cualitativos

Modelos Cualitativos y QSIM

Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

• Se puede demostrar que QSIM garantiza incluir todos

los comportamientos que exhiben las ecuaciones diferenciales originales (sound), pero no garantiza incluir solo esas (no complete) y normalmente genera comportamientos que no representan realidades f´ısicas. • Uno de los problemas es ambiguedad en la derivada de ¨

expresiones complejas. Por ejemplo: z = xy, x = inc, y = dec, entonces z = inc, dec o std. • Las derivadas solo estan ´ restringidas por consideraciones de continuidad y no por valores caracter´ısticos.

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

39 / 40

Algoritmo Modelos Cualitativos Eduardo Morales, Enrique Sucar ´ Introduccion QSIM ´ Simulacion Algoritmo

Modelos Cualitativos y QSIM Posibles soluciones (Kuipers y Chiu ’87) • Ignorar la direccion ´ de cambio de una variable (Kuipers y Chiu ’87) • Restricciones de “curvatura” cuando la derivada de una

variable es cero para validar o refutar las curvaturas propuestas por QSIM (Kuipers y Chiu ’87) • Restricciones en las trayectorias de las variables en el

plano de la fase (NIC: Non-Intersection of phase-space Constraint) (Lee y Kuipers ’88, Struss ’88) • Incorporacion ´ de conocimiento cuantitativo • Abstracciones de comportamientos en uno solo • Derivadas de alto orden

Eduardo Morales, Enrique Sucar (INAOE)

Modelos Cualitativos

40 / 40