Problema De Las Jarras

´
Inteligencia artificial, logicamente

´
Malaga, Septiembre 2002

Inteligencia artificial,
l´gicamente
o

Jos´ A. Alonso Jim´nez
e
e
http://www.cs.us.es/∼jalonso

Dpto. de Ciencias de la Computaci´n e Inteligencia Artificial
o

Universidad de Sevilla

J.A. Alonso

Cc Ia

Inteligencia artificial, l´gicamente
o

.1

Definici´n de problemas de estados
o
x

Elementosque describen un problema:
u
u

Operadores.

u
x

Estado inicial.
Estados finales.

Suposiciones subyacentes:
u

Agente unico.
´

u

Conocimiento completo.

J.A. Alonso

Cc Ia

Inteligencia artificial, l´gicamente
o

.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 ellastiene marcas de medici´n.
o

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
o
4 litros de capacidad.

x

Representaci´n de estados: (x y) con x en {0,1,2,3,4} e y en {0,1,2,3}.
o

x

N´ mero de estados: 20.
u

J.A. Alonso

Cc Ia

Inteligencia artificial, l´gicamente
o

.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

Llenarla 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

Cc Ia

Inteligencia artificial, l´gicamente
o

.4

Implementaci´n del problema de las jarras
o
x

Representaci´n de estados
o
(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

Cc Ia

Inteligencia artificial, l´gicamente
o

.5

Implementaci´n del problema de las jarras
o
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

Cc Ia

Inteligencia artificial, l´gicamente
o

.6

Implementaci´n del problemade las jarras
o
(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)
( 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-3LLENAR-JARRA-3-CON-JARRA-4
LLENAR-JARRA-4))

J.A. Alonso

Cc Ia

Inteligencia artificial, l´gicamente
o

.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:...