PDF de programación - Unidad IV - Introducción a sistemas basados en el conocimiento - Inteligencia Computacional

Inteligencia Computacional

Introducción a sistemas basados en el conocimiento.

Unidad IV

Docente:

Dra. Georgina Stegmayer

[email protected]

Inteligencia Computacional – Unidad IV

El juego del Wumpus

(Russell & Norvig, Artificial Intelligence a Modern Approach, 2010, cap. 9)

Cueva

Cueva

Cueva

Un cazador explora un mundo formado por habitaciones.
En alguna habitación reside Wumpus
Algunas habitaciones poseen cuevas mortales.
En alguna habitación del ambiente hay una barra de oro que puede ser tomada por el

cazador.

Inteligencia Computacional – Unidad IV

El juego del Wumpus

Objetivo:
Encontrar el ORO
sin entrar en una celda con Wumpus vivo
o con caverna

Conocimiento del problema/juego:
1. En la celda que contiene el Wumpus y en las adyacentes se percibe un mal olor
2. En la celda directamente adyacente a un pozo se percibe una brisa
3. En la celda en donde hay oro se percibe un resplandor
4. Cuando el Wumpus es destruido, emite un gemido que se percibe en todos lados
5. Cuando el cazador choca contra una pared percibe un golpe
6. El cazador muere si entra en una celda con el Wumpus o un pozo. Si el Wumpus está

muerto, la celda es segura pero hay mal olor.

Inteligencia Computacional – Unidad IV

El juego del Wumpus

Información que se recibe del juego (percepciones) :
olor, brisa, resplandor, golpe y gemido
(lista de 5 valores)
Por ejemplo:

(1, 1, 1, 0, 0)

Acciones para el cazador:
Avanzar,
Girar-Derecha (90°) ,
Girar-Izquierda (90°),
Levantar (un objeto que esté en la misma celda),
Lanzar-Flecha (el cazador tiene una sola flecha) y
Depositar.

Inteligencia Computacional – Unidad IV

El juego del Wumpus

EXPERIMENTEMOS CON EL DOMINIO DE WUMPUS

(0 , 0 , 0 , 0 , 0)

OK

OK

OK

Inteligencia Computacional – Unidad IV

El juego del Wumpus

EXPERIMENTEMOS CON EL DOMINIO DE WUMPUS

(0 , 0 , 0 , 0 , 0)

(0, 1, 0, 0, 0)

OK

OK

OK

Inteligencia Computacional – Unidad IV

El juego del Wumpus

Inteligencia Computacional – Unidad IV

El juego del Wumpus

(1 , 0 , 0, 0, 0)

O

Inteligencia Computacional – Unidad IV

El juego del Wumpus

O

Inteligencia Computacional – Unidad IV

El juego del Wumpus

O

O

Inteligencia Computacional – Unidad IV

El juego del Wumpus

(0, 0, 0, 0, 0)

O

Inteligencia Computacional – Unidad IV

El juego del Wumpus

(0, 0, 0, 0, 0)

(1, 0, 1, 0, 0)

O

O R

O

Inteligencia Computacional – Unidad IV

El juego del Wumpus

(0, 0, 0, 0, 0)

(1, 0, 1, 0, 0)

O

O R

O

FIN

Inteligencia Computacional – Unidad IV

Lógica

lógicas son

información y/o

Las
conocimiento de una forma que sea tratable por computadoras.

lenguajes formales para representar

Inteligencia Computacional – Unidad IV

Lógica

lógicas son

información y/o

Las
conocimiento de una forma que sea tratable por computadoras.

lenguajes formales para representar

Lenguaje

Qué existe en el Mundo

Qué estados asume el

conocimiento

Lógica Proposicional

Hechos

V / F

Inteligencia Computacional – Unidad IV

Lógica

lógicas son

información y/o

Las
conocimiento de una forma que sea tratable por computadoras.

lenguajes formales para representar

Lenguaje

Qué existe en el Mundo

Qué estados asume el

conocimiento

Lógica Proposicional

Hechos

V / F

Lógica de predicados
de 1er. orden

Hechos/objetos, relaciones

V / F

Inteligencia Computacional – Unidad IV

Lógica

lógicas son

información y/o

Las
conocimiento de una forma que sea tratable por computadoras.

lenguajes formales para representar

Lenguaje

Qué existe en el Mundo

Qué estados asume el

conocimiento

Lógica Proposicional

Hechos

V / F

Lógica de predicados
de 1er. orden

Lógica Temporal

Hechos/objetos, relaciones

V / F

Hechos/objetos, relaciones,
tiempo

V / F

Lógica difusa

Grado de verdad

Grado de certeza 0 …1

Inteligencia Computacional – Unidad IV

Lógica - reglas de inferencia

Olor(1,1) => W(2,1) ˅ W(1,2)

Olor(1,1)

W(2,1) ˅W(1,2)

Inteligencia Computacional – Unidad IV

Lógica - reglas de inferencia

Modus Tollens
α => β, ¬β
¬α

Olor(1,1) => W(2,1)

¬W(2,1)

¬Olor(1,1)

Inteligencia Computacional – Unidad IV

Lógica - reglas de inferencia

Cueva(1,1) ˄ ¬Cueva(3,1)

Cueva(1,1)

Inteligencia Computacional – Unidad IV

Lógica - reglas de inferencia

W(2,1) ˅ W(1,2)

¬W(1,2)

W(2,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

La percepción actual es

(1, 1, 1, 0, 0)

4

3

2

1

1 2 3 4

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

La percepción actual es

(1, 1, 1, 0, 0)

Brisa(3,2)
Olor(3,2)

Resplandor(3,2)

4

3

2

1

1 2 3 4

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

4

3

2

1

1 2 3 4

La percepción actual es

(1, 1, 1, 0, 0)

Brisa(3,2)
Olor(3,2)

Resplandor(3,2)

Además, ya sabemos que:

Olor(1,1)

Brisa(1,1)
Olor(2,1)
Brisa(2,1)
Olor(1,2)
Brisa(2,1)
Cueva(1,3)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

Sabemos estas reglas del juego:

Regla 1: Olor(1,1)   W(1,1)  W(1,2)  W(2,1)

Regla 2: Olor(1,2)   W(1,2)  W(2,2)  W(1,3) 
W(1,1)

Regla 3: Olor(2,1)  W(1,1)  W(2,2)  W(3,2)

Dadas estas afirmaciones, veremos cómo se puede inferir que:


W(3,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con las afirmaciones: Regla 1 y  Olor(1,1), obtenemos

Regla 1: Olor(1,1)   W(1,1)  W(1,2)  W(2,1)

Obtenemos las siguientes afirmaciones

 W(1,1) W(1,2) W(2,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con las afirmaciones: Regla 2 y  Olor(1,2), obtenemos

 W(1,2) W(2,2) W(1,3)  W(1,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con las afirmaciones: Regla 3 y Olor(2,1) obtenemos



W(1,1)  W(2,2)  W(3,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

W(1,1)  W(2,2)  W(3,1)





Aplicando Resolución entre (W(1,1)  W(2,2)  W(3,1) ) y ( ¬ W(1,1)),
obtenemos



W(2,2)  W(3,1)

Inteligencia Computacional – Unidad IV

Lógica e inferencia

Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con las afirmaciones: Regla 3 y Olor(2,1) obtenemos

W(1,1)  W(2,2)  W(3,1)

Aplicando Resolución entre (W(1,1)  W(2,2)  W(3,1) ) y ( ¬ W(1,1)),
obtenemos



W(2,2)  W(3,1)

Aplicando Resolución entre (W(2,2)  W(3,1)) y (¬W(2,2)), obtenemos

W(3,1)

Inteligencia Computacional – Unidad IV

Lógica de predicados de 1er orden

Ejemplo

R1: O1,1   W1,1  W1,2  W2,1
R2: O1,2   W1,2  W2,2  W1,3  W1,1

Reglas:

∀x,y Olor(x) Adyacente(x,y) Wumpus(x) Wumpus(y)

Inteligencia Computacional – Unidad IV

Lógica de predicados de 1er orden

Ejemplo

R1: O1,1   W1,1  W1,2  W2,1
R2: O1,2   W1,2  W2,2  W1,3  W1,1

R3: O2,1  W1,1  W2,2  W3,1

Reglas:

∀x,y Olor(x) Adyacente(x,y) Wumpus(x) Wumpus(y)

∀x Olor(x)  y ∃ Adyacente(x,y) Wumpus(y)

Inteligencia Computacional – Unidad IV

Lógica de predicados de 1er orden

Ejemplo

Reglas:

∀x,y Olor(x) Adyacente(x,y) Wumpus(x) Wumpus(y)

∀x Olor(x)  y ∃ Adyacente(x,y) Wumpus(y)

∀x Brisa(x)

⇒ ∃
y Adyacente(x,y) Pozo(y)

∧

∀x Pozo(x)

⇒ ∀
[ y Adyacente(x,y)

⇒
Brisa(y)]

Inteligencia Computacional – Unidad IV

Lógica de 1er orden e inferencia
Ejemplo: el juego del Wumpus

Hechos:
Olor(1,1) Brisa(1,1) Olor(2,1) Brisa(1,2) Olor(1,2) Brisa(2,1)
Pozo(1,3) Brisa(3,2) Olor(3,2) Resplandor(3,2)
Adyacente([1,1],[1,2]), Adyacente([1,1],[2,1]) …

Reglas:

R1: x,y ∀ Olor(x) Adyacente(x,y) Wumpus(x) Wumpus(y)

R2: x ∀ Olor(x)  y ∃ Adyacente(x,y) Wumpus(y)

R3: x Brisa(x)

∀

⇒∃
y Adyacente(x,y) HayPozo(y)

∧

R4: x Pozo(x)

∀

⇒ ∀
[ y Adyacente(x,y)

⇒
Brisa(y)]

Inteligencia Computacional – Unidad IV

Lógica de 1er orden e inferencia
Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con R1 y Olor(1,1) y Adyacente([1,1],[1,2]) y Adyacente([1,1],[2,1])

∀x,y Olor(x) Adyacente(x,y) Wumpus(x) Wumpus(y)

Inteligencia Computacional – Unidad IV

Lógica de 1er orden e inferencia
Ejemplo: el juego del Wumpus

Aplicando Modus Ponens con R1 y Olor(1,1) y Adyacente([1,1],[1,2]) y Adyacente([1,1],[2,1])

Inferimos:

Wumpus(1,1) Wumpus(1,2)Wumpus(2,1)

Inteligencia Computacional – Unidad IV

Sistemas Expertos

(o de producción con encadenamiento hacia adelante)

M.I

B.C

M.P

M.T.

M.I: Máquina de inferencia
BC: Base de conocimiento
MP: Memoria de producciones
MT: Memoria de trabajo.

Inteligencia Computacional – Unidad IV

Sistemas Expertos

(o de producción con encadenamiento hacia adelante)

 Se comienza desde las sentencias atómicas (hechos) de la memoria de
trabajo y se infiere añadiendo las sentencias atómicas nuevas hasta que
no se puedan realizar más inferencias o hasta que el objetivo haya sido
agregado.

 Cada inferencia es la aplicación de Modus Ponens

 Utiliza solamente cláusulas positivas: disyunción de literales de los

cuales sólo uno es positivo.

Inteligencia Computacional – Unidad IV

Sistemas Expertos

(o de producción con encadenamiento hacia adelante)

Inteligencia Computacional – Unidad IV

Sistemas Expertos

(o de producción con encadenamiento hacia adelante)

 Memoria de Producciones (MP):

está constituidas por reglas del tipo:

IF

<cond 1>
<cond 2>
...
<cond n>
<acc 1>
...
<acc n>

THEN

lado izquierdo - antecedentes

lado derecho - consecuentes

Inteligencia Computacional – Unidad IV

Sistemas Expertos

(o de producción con encadenamiento hacia adelante)