PDF de programación - Inteligencia artificial, lógicamente

Inteligencia artificial, lógicamente

Málaga, Septiembre 2002

Inteligencia artificial,

lógicamente

José A. Alonso Jiménez

http://www.cs.us.es/∼jalonso

Dpto. de Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.1

Definición de problemas de estados
x Elementos que describen un problema:
u Estado inicial.
u Operadores.
u Estados finales.
x Suposiciones subyacentes:
u Agente único.
u Conocimiento completo.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.2

Ejemplo de PES: problema de las jarras
x Enunciado:
u Se tienen dos jarras, una de 4 litros de capacidad y otra de 3.
u Ninguna de ellas tiene marcas de medición.
u Se tiene una bomba que permite llenar las jarras de agua.
u Averiguar cómo se puede lograr tener exactamente 2 litros de agua en la jarra de
x Representación de estados: (x y) con x en {0,1,2,3,4} e y en {0,1,2,3}.
x Número de estados: 20.

4 litros de capacidad.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.3

Planteamiento del problema de las jarras
x Estado inicial: (0 0).
x Estados finales: (2 y).
x Operadores:
u Llenar la jarra de 4 litros con la bomba.
u Llenar la jarra de 3 litros con la bomba.
u Vaciar la jarra de 4 litros en el suelo.
u Vaciar la jarra de 3 litros en el suelo.
u Llenar la jarra de 4 litros con la jarra de 3 litros.
u Llenar la jarra de 3 litros con la jarra de 4 litros.
u Vaciar la jarra de 3 litros en la jarra de 4 litros.
u Vaciar la jarra de 4 litros en la jarra de 3 litros.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.4

Implementación del problema de las jarras
x Representación de estados

(defun crea-estado (x y)

(list x y))

(defun contenido-jarra-4 (estado)

(first estado))

(defun contenido-jarra-3 (estado)

(second estado))

x Estado inicial

(defparameter *estado-inicial*

(crea-estado 0 0))

x Estados finales

(defun es-estado-final (estado)

(= 2 (contenido-jarra-4 estado)))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.5

Implementación del problema de las jarras
x Operadores

(defparameter *operadores*

’(llenar-jarra-4
llenar-jarra-3
vaciar-jarra-4
vaciar-jarra-3
llenar-jarra-4-con-jarra-3
llenar-jarra-3-con-jarra-4
vaciar-jarra-3-en-jarra-4
vaciar-jarra-4-en-jarra-3))

(defun llenar-jarra-4 (estado)

(when (< (contenido-jarra-4 estado) 4)

(crea-estado 4

(contenido-jarra-3 estado))))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.6

Implementación del problema de las jarras

(defun vaciar-jarra-4 (estado)

(when (> (contenido-jarra-4 estado) 0)

(crea-estado 0

(contenido-jarra-3 estado))))

(defun llenar-jarra-4-con-jarra-3 (estado)

(let ((x (contenido-jarra-3 estado))

(y (contenido-jarra-4 estado)))

(when (and (> x 0)
(< y 4)
(> (+ y x) 4))

(crea-estado 4 (- x (- 4 y))))))

(defun vaciar-jarra-3-en-jarra-4 (estado)

(let ((x (contenido-jarra-3 estado))

(y (contenido-jarra-4 estado)))

(when (and (> x 0)

(<= (+ y x) 4))

(crea-estado (+ x y) 0))))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.7

:
d
a
d
i
d
n
u
f
o
r
p

n
e

a
d
e
u
q
s
ú
b

e
d

o
f
a
r
G

x

n
ó
i
c
u

l
o
s

e
d

a
d
e
u
q
s
ú
B

8
.

e
t
n
e
m
a
c
i
g
ó
l

,
l
a
i
c
fi
i
t
r
a

a
i
c
n
e
g
i
l
e
t
n
I

a
I
c
C

o
s
n
o
l
A

.

A
.
J

(0 0)1(4 3)(1 0)(0 1)(4 1)(2 3)(1 3)(4 0)2(0 3)346785)
)
3

0
(

)
3

)
)
3

)
)
3

)
)
3

)
)
3

)
)
3

)
)
3

0
(

1
(

0
(

0
(

0
(

0
(

0
(

)
0

)
3

)
3

)
0

)
1

)
1

)
3

)
)
0

0
(
(

4
(
(

4
(
(

1
(
(

1
(
(

0
(
(

4
(
(

2
(
(

)
)
3

)
)
3

0
(

1
(

)
0

)
3

4
(
(

4
(
(

)
)
0

)
)
1

)
)
1

)
)
3

1
(
(

0
(
(

4
(
(

2
(
(

)
(

)
0

)
0

)
3

)
3

)
0

)
1

)
1

)
3

0
(

4
(

4
(

1
(

1
(

0
(

4
(

2
(

1

2

3

4

5

6

7

8

s
o
t
r
e
i
b
A

s
e
r
o
s
e
c
u
S

l
a
u
t
c
A

o
d
o
N

:
d
a
d
i
d
n
u
f
o
r
p

n
e

a
d
e
u
q
s
ú
b

e
d

a
l
b
a
T

)
)
0

0
(

)
0

4
(

)
3

1
(

)
0

1
(

)
1

0
(

)
1

4
(

)
3

2
(
(

:
n
ó
i
c
u

l
o
s

a
l

e
d

s
o
d
a
t
s
E

x

x

n
ó
i
c
u

l
o
s

e
d

a
d
e
u
q
s
ú
B

9
.

e
t
n
e
m
a
c
i
g
ó
l

,
l
a
i
c
fi
i
t
r
a

a
i
c
n
e
g
i
l
e
t
n
I

a
I
c
C

o
s
n
o
l
A

.

A
.
J

Procedimiento de búsqueda en profundidad

1. Crear las siguientes variables locales

1.1. ABIERTOS (para almacenar los nodos generados aún no analizados)

con valor la lista formada por el nodo inicial (es decir, el nodo
cuyo estado es el estado inicial y cuyo camino es la lista vacía);

1.2. CERRADOS (para almacenar los nodos analizados) con valor la

lista vacía;

1.3. ACTUAL (para almacenar el nodo actual) con valor la lista vacía.
1.4. NUEVOS-SUCESORES (para almacenar la lista de los sucesores del

nodo actual) con valor la lista vacía.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.10

Procedimiento de búsqueda en profundidad

2. Mientras que ABIERTOS no esté vacía,

2.1 Hacer ACTUAL el primer nodo de ABIERTOS
2.2 Hacer ABIERTOS el resto de ABIERTOS
2.3 Poner el nodo ACTUAL en CERRADOS.
2.4 Si el nodo ACTUAL es un final,

2.4.1 devolver el nodo ACTUAL y terminar.
2.4.2 en caso contrario, hacer

2.4.2.1 NUEVOS-SUCESORES la lista de sucesores del nodo

ACTUAL que no están en ABIERTOS ni en CERRADOS y

2.4.2.2 ABIERTOS la lista obtenida añadiendo los

NUEVOS-SUCESORES al principio de ABIERTOS.

3. Si ABIERTOS está vacía, devolver NIL.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.11

Implementación de la búsqueda en profundidad

(defun busqueda-en-profundidad ()

(let ((abiertos (list (crea-nodo :estado *estado-inicial*

;1.1

:camino nil)))

(cerrados nil)
(actual nil)
(nuevos-sucesores nil))

(loop until (null abiertos) do

(setf actual (first abiertos))
(setf abiertos (rest abiertos))
(setf cerrados (cons actual cerrados))
(cond ((es-estado-final (estado actual))

(return actual))

(t (setf nuevos-sucesores

;1.2
;1.3
;1.4
;2
;2.1
;2.2
;2.3
;2.4
;2.4.1
;2.4.2.1

(nuevos-sucesores actual abiertos cerrados))

(setf abiertos

;2.4.2.2

(append nuevos-sucesores abiertos)))))))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.12

Soluciones de los problemas en profundidad
x Problema de las jarras:

> clisp
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
...
Copyright (c) Bruno Haible, Sam Steingold 1999-2002
> (load "p-jarras-1.lsp")
T
> (load "b-profundidad.lsp")
T
> (busqueda-en-profundidad)
#S(NODO :ESTADO (2 3)

:CAMINO (LLENAR-JARRA-3-CON-JARRA-4

LLENAR-JARRA-4
VACIAR-JARRA-4-EN-JARRA-3
VACIAR-JARRA-3
LLENAR-JARRA-3-CON-JARRA-4
LLENAR-JARRA-4))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.13

Soluciones de los problemas en profundidad

> (trace es-estado-final)
(ES-ESTADO-FINAL)
> (busqueda-en-profundidad)
1. Trace: (ES-ESTADO-FINAL ’(0 0))
1. Trace: (ES-ESTADO-FINAL ’(4 0))
1. Trace: (ES-ESTADO-FINAL ’(4 3))
1. Trace: (ES-ESTADO-FINAL ’(1 3))
1. Trace: (ES-ESTADO-FINAL ’(1 0))
1. Trace: (ES-ESTADO-FINAL ’(0 1))
1. Trace: (ES-ESTADO-FINAL ’(4 1))
1. Trace: (ES-ESTADO-FINAL ’(2 3))
#S(NODO :ESTADO (2 3)

:CAMINO (LLENAR-JARRA-3-CON-JARRA-4 LLENAR-JARRA-4
VACIAR-JARRA-4-EN-JARRA-3 VACIAR-JARRA-3
LLENAR-JARRA-3-CON-JARRA-4 LLENAR-JARRA-4))

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.14

a
c
i
t
s
í
r
u
e
h

a
1

:
r
o
j
e
m

l
e

o
r
e
m

i
r
p

r
o
p

e
l
z
z
u
p
–
8

5
1
.

e
t
n
e
m
a
c
i
g
ó
l

,
l
a
i
c
fi
i
t
r
a

a
i
c
n
e
g
i
l
e
t
n
I

a
I
c
C

o
s
n
o
l
A

.

A
.
J

175283164 H = 425283164 7H = 57528314 6H = 372831645 H = 55283476 1H = 37523146H = 3 87283165 4H = 4353476 821H = 35246H = 48371 53147682 H = 27521463 8H = 447534 6128H = 0345H = 21278 6753612 84H = 1567a
c
i
t
s
í
r
u
e
h

a
2

:
r
o
j
e
m

-
l
e
-
o
r
e
m

i
r
p

r
o
p

e
l
z
z
u
p
–
8

6
1
.

e
t
n
e
m
a
c
i
g
ó
l

,
l
a
i
c
fi
i
t
r
a

a
i
c
n
e
g
i
l
e
t
n
I

a
I
c
C

o
s
n
o
l
A

.

A
.
J

127523146H = 3 875283164 H = 55283164 7H = 67528314 6H = 472831645 H = 65283476 1H = 57283165 4H = 5353147682 H = 27521463 8H = 47534 6128H = 0345H = 21278 6753612 84H = 1654Problemas de espacio de estados y lógica
x Relación histórica:
u 1957: Newell, Shaw y Simon: “General Problem Solver”.
u 1956: Newell y Simon: lógico teórico.
x Relación conceptual:
u Estado inicial: teorema a demostrar.
u Operadores: reglas de inferencia.
u Estados finales: axiomas.
x Relación instrumental:
u Lisp y lambda cálculo.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.17

Resolución SLD: Problema
x Base de conocimiento de animales:
u Regla 1: Si un animal es ungulado y tiene rayas negras, entonces es una cebra.
u Regla 2: Si un animal rumia y es mamífero, entonces es ungulado.
u Regla 3: Si un animal es mamífero y tiene pezuñas, entonces es ungulado.
u Hecho 1: El animal tiene es mamífero.
u Hecho 2: El animal tiene pezuñas.
u Hecho 3: El animal tiene rayas negras.
x Objetivo:
u Demostrar a partir de la base de conocimientos que el animal es una cebra.

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.18

Resolución SLD: Representación
x Representación lógica de la base de conocimiento:

es_cebra
es_ungulado :- rumia, es_mamífero.
es_ungulado :- es_mamífero, tiene_pezuñas.
es_mamífero.
tiene_pezuñas.
tiene_rayas_negras.

:- es_ungulado, tiene_rayas_negras. % Regla 1
% Regla 2
% Regla 3
% Hecho 1
% Hecho 2
% Hecho 3

x Sesión:

> pl
Welcome to SWI-Prolog (Version 5.0.3)
Copyright (c) 1990-2002 University of Amsterdam.
?- [animales].
Yes
?- es_cebra.
Yes

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.19

Resolución SLD: Arbol de resolución

J.A. Alonso

CcIa

Inteligencia artificial, lógicamente

.20

:− es_cebra.es_mamifero,:− rumia, tiene_rayas_negras.:− es_mamifero, tiene_pezuñas, tiene_rayas_negras. tiene_rayas_negras.:− es_ungulado,:− tiene_pezuñas, tiene_rayas_negras.:−.R1R3R2H1H2:− tiene_rayas_negras.H3FalloExitoResolución con unificación
x Programa lógico suma

suma(0,X,X).
suma(s(X),Y,s(Z)) :- suma(X,Y,Z).

x Sesión

% R1
% R2

?- suma(s(0),s(s(0)),X).
X = s(s(s(0)))
Yes
?- suma(X,Y,s(s(0))).
X = 0
Y = s(