PDF de programación - Tema 10: Aplicaciones de SBC en CLIPS

Inteligencia Artificial 2

Curso 2000–2001

Tema 10: Aplicaciones de SBC

en CLIPS

José A. Alonso Jiménez
Miguel A. Gutiérrez Naranjo
Francisco J. Martín Mateos

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

Universidad de Sevilla

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.1

Aplicaciones de SBC en CLIPS
x Búsqueda
u Búsqueda ciega
u Búsqueda con heurística
u Búsqueda con coste y heurística
x Sistemas de control
x Árboles de decisión
x Bibliografía:
u Giarratano, J.C. y Riley, G. “Expert Systems Princi-

ples and Programming (2nd ed.)” (PWS Pub. Co.,
1994)
* Cap. 12.3: “Decision Trees”
* Cap. 12.5: “A Monitoring Problem”

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.2

a
d
e
u
q
s
ú
b

e
d

s
a
m
e
l

b
o
r
p

s
o
l

e
d

l
a
r
e
n
e
g

a
m
e
u
q
s
E

3
.
0
1

S
P
I
L
C
n
e
C
B
S

e
d

s
e
n
o
i
c
a
c
i
l

p
A

a
I
c
C

1
0
–
0
0
0
2

2
A
I

nodonodo− Aplicar operadores− Inicializar datos(− Heurística y coste)MAIN− Reconocer e imprimir la soluciónSOLUCIONRESTRICCIONES prohibidos y repetidos− Eliminar estadosBúsqueda ciega
x Enunciado
u La situación inicial es

u La situación final es

u Los movimientos permitidos consisten en desplazar

una ficha al hueco saltando, como máximo, sobre otras
dos.

x Módulo MAIN

(defmodule MAIN

(export deftemplate nodo))

(deftemplate MAIN::nodo

(multislot estado)
(multislot camino))

(deffacts MAIN::nodo-inicial

(nodo (estado B B B H V V V)

(camino "B B B H V V V")))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.4

BBBVVV BBBVVVBúsqueda ciega

(defrule MAIN::movimiento-izquierda

(nodo (estado $?x

H
$?y&:(<= (length $?y) 2)
?ficha
$?z)

(camino $?movimientos))

=>
(bind $?nuevo-estado

(create$ $?x ?ficha $?y H $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado)))))

(defrule MAIN::movimiento-derecha

(nodo (estado $?x

?ficha
$?y&:(<= (length $?y) 2)
H
$?z)

(camino $?movimientos))

=>
(bind $?nuevo-estado

(create$ $?x H $?y ?ficha $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado)))))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.5

Búsqueda ciega
x Módulo RESTRICCIONES

(defmodule RESTRICCIONES

(import MAIN deftemplate nodo))

(defrule RESTRICCIONES::repeticion-de-nodo

(declare (auto-focus TRUE))
(nodo (estado $?actual)

(camino $?movimientos))

?nodo <- (nodo (estado $?actual)

(camino $?movimientos ? $?))

=>
(retract ?nodo))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.6

Búsqueda ciega
x Módulo SOLUCION

(defmodule SOLUCION

(import MAIN deftemplate nodo))

(defrule SOLUCION::reconoce-solucion

(declare (auto-focus TRUE))
?nodo <- (nodo (estado V V V H B B B)

(camino $?estados))

=>
(retract ?nodo)
(assert (solucion $?estados)))

(defrule SOLUCION::escribe-solucion

(solucion $?estados)
=>
(bind ?longitud (length $?estados))
(printout t "La solucion, de longitud " ?longitud

" es " crlf)

(loop-for-count (?i 1 ?longitud)

(bind ?estado (nth ?i $?estados))
(printout t ?estado crlf))

(retract *))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.7

Búsqueda ciega
x Sesión con estadística

CLIPS> (load "fichas-1.clp")
+%$**+*+**
TRUE
CLIPS> (watch statistics)
CLIPS> (reset)
CLIPS> (run)
La solucion, de longitud 83 es:
B B B H V V V
H B B B V V V
B H B B V V V
B B H B V V V
B B V B H V V
.............
V B V V H B B
V H V V B B B
H V V V B B B
V V H V B B B
V V V H B B B
238 rules fired
6.898550724637682 rules per second.
43 mean number of facts (84 maximum).
1 mean number of instances (1 maximum).
103 mean number of activations (205 maximum).

Run time is 34.50 seconds.

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.8

Búsqueda con heurística
x Heurística:
u Definición: La heurística de un estado es la suma de

piezas blancas situadas a la izquierda de cada una de
las piezas verdes.

u Ejemplo: La heurística del siguiente estado es 1+2+2

= 5.

x Módulo MAIN

(defmodule MAIN

(export deftemplate nodo))

(deftemplate MAIN::nodo

(multislot estado)
(multislot camino)
(slot heuristica)
(slot clase (default abierto)))

(defglobal MAIN

?*estado-inicial* = (create$ B B B H V V V))

(defrule MAIN::inicial

=>
(assert (nodo (estado ?*estado-inicial*)

(camino (implode$ ?*estado-inicial*))
(heuristica

(heuristica ?*estado-inicial*))

(clase cerrado))))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.9

BVBBVVBúsqueda con heurística

(deffunction MAIN::heuristica ($?estado)

(bind ?resultado 0)
(bind ?verdes 3)
(loop-for-count (?i 1 7)

(bind ?ficha (nth ?i $?estado))
(if (eq ?ficha B)

then (bind ?resultado

(+ ?resultado ?verdes))

else (if (eq ?ficha V)

then (bind ?verdes

(- ?verdes 1)))))

?resultado)

(defrule MAIN::movimiento-izquierda

(nodo (estado $?x H

$?y&:(<= (length $?y) 2)
?ficha $?z)

(camino $?movimientos)
(clase cerrado))

=>
(bind $?nuevo-estado

(create$ $?x ?ficha $?y H $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado))

(heuristica

(heuristica $?nuevo-estado)))))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.10

Búsqueda con heurística

(defrule MAIN::movimiento-derecha

(nodo (estado $?x ?ficha

$?y&:(<= (length $?y) 2)
H $?z)

(camino $?movimientos)
(clase cerrado))

=>
(bind $?nuevo-estado

(create$ $?x H $?y ?ficha $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado))

(heuristica

(heuristica $?nuevo-estado)))))

(defrule MAIN::pasa-el-mejor-a-cerrado

(declare (salience -10))
?nodo <- (nodo (clase abierto)

(not (nodo (clase abierto)

(heuristica ?h1))

(heuristica ?h2&:(< ?h2 ?h1))))

=>
(modify ?nodo (clase cerrado)))

x Módulo RESTRICCIONES: Ningún cambio
x Módulo SOLUCION: Ningún cambio

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.11

Búsqueda con heurística
x Sesión con estadística

CLIPS> (watch statistics)
CLIPS> (reset)
CLIPS> (run)
La solucion, de longitud 15 es:
B B B H V V V
B B B V V V H
B B B V V H V
B B H V V B V
B B V V H B V
B H V V B B V
B V V H B B V
B V V V B B H
B V V V B H B
B V V V H B B
B V V H V B B
H V V B V B B
V V H B V B B
V V V B H B B
V V V H B B B
93 rules fired
50.7272727270043 rules per second.
26 mean number of facts (49 maximum).
1 mean number of instances (1 maximum).
5 mean number of activations (12 maximum).

Run time is 1.83 seconds.

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.12

Búsqueda con heurística y coste
x Coste de un nodo = número de movimientos
x Módulo MAIN

(defmodule MAIN

(export deftemplate nodo))

(deftemplate MAIN::nodo

(multislot estado)
(multislot camino)
(slot heuristica)
(slot coste)
(slot clase (default abierto)))

(defglobal MAIN

?*estado-inicial* = (create$ B B B H V V V))

(deffunction MAIN::heuristica ($?estado)

(bind ?resultado 0)
(bind ?verdes 3)
(loop-for-count (?i 1 7)

(bind ?ficha (nth ?i $?estado))
(if (eq ?ficha B)

then (bind ?resultado

(+ ?resultado ?verdes))

else (if (eq ?ficha V)

then (bind ?verdes

(- ?verdes 1)))))

?resultado)

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.13

Búsqueda con heurística y coste

(defrule MAIN::inicial

=>
(assert (nodo (estado ?*estado-inicial*)

(camino (implode$ ?*estado-inicial*))
(heuristica

(heuristica ?*estado-inicial*))

(coste 0)
(clase cerrado))))

(defrule MAIN::movimiento-izquierda

(nodo (estado $?x H

$?y&:(<= (length $?y) 2)
?ficha $?z)

(camino $?movimientos)
(coste ?coste)
(clase cerrado))

=>
(bind $?nuevo-estado

(create$ $?x ?ficha $?y H $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado))

(coste (+ ?coste 1))
(heuristica

(heuristica $?nuevo-estado)))))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.14

Búsqueda con heurística y coste

(defrule MAIN::movimiento-derecha

(nodo (estado $?x ?ficha

$?y&:(<= (length $?y) 2)
H $?z)

(camino $?movimientos)
(coste ?coste)
(clase cerrado))

=>
(bind $?nuevo-estado

(create$ $?x H $?y ?ficha $?z))
(assert (nodo (estado $?nuevo-estado)

(camino $?movimientos

(implode$ $?nuevo-estado))

(coste (+ ?coste 1))
(heuristica

(heuristica $?nuevo-estado)))))

(defrule MAIN::pasa-el-mejor-a-cerrado

(declare (salience -10))
?nodo <- (nodo (clase abierto)

(heuristica ?h1)
(coste ?c1))

(not (nodo (clase abierto)

(heuristica ?h2&:(< ?h2 ?h1))))

(not (nodo (clase abierto) (heuristica ?h1)

(coste ?c2&:(< ?c2 ?c1))))

=>
(modify ?nodo (clase cerrado)))

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.15

Búsqueda con heurística y coste
x Módulo RESTRICCIONES

(defmodule RESTRICCIONES

(import MAIN deftemplate nodo))

(defrule RESTRICCIONES::repeticion-de-nodo

(declare (auto-focus TRUE))
(nodo (estado $?actual)
(coste ?coste-1))

?nodo <- (nodo (estado $?actual)

(coste ?coste-2&:(> ?coste-2 ?coste-1)))

=>
(retract ?nodo))

x Módulo SOLUCION: Ningún cambio

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.16

Búsqueda con heurística y coste
x Sesión con estadística

CLIPS> (load "fichas-3.clp")
+%:!****+*+**
TRUE
CLIPS> (watch statistics)
CLIPS> (reset)
CLIPS> (run)
La solucion, de longitud 13 es:
B B B H V V V
B B B V V H V
B B H V V B V
B B V V H B V
B H V V B B V
B V V H B B V
H V V B B B V
V V H B B B V
V V B H B B V
V V B V B B H
V V B V B H B
V V H V B B B
V V V H B B B
120 rules fired
184.6153846170378 rules per second.
25 mean number of facts (47 maximum).
1 mean number of instances (1 maximum).
5 mean number of activations (11 maximum).

Run time is 0.65 seconds.

IA2 2000–01

CcIa

Aplicaciones de SBC en CLIPS

10.17

a
c
i
t
s
í
r
u
e
h
(

)
a
c
i
t
s
í
r
u
e
h
(

3

n
ó
i
c
u
l
o
S

2

n
ó
i
c
u

l
o
S

1

n
ó
i
c
u
l
o
S

)
e
t
s
o
c

y

3
1

5
6
.
0

0
2
1

7
4

5
2

1
1

5

5
1

3
8
.
1

3
9

9
4

6
2

2
1

5

3
8

0
5
.
4
3

8
3
2

4
8

3
4

5
0
2

3
0
1

s
e
n
o
i
c
a
v
i
t
c
a

e
d

o
m
i
x
á
m
o
r
e
m
ú
N

s
e
n
o
i
c
a
v
i
t
c
a

e
d

o
i
d
e
m
o
r
e
m
ú
N

s
o
h
c
e
h

e
d

o
m
i
x
á
m
o
r
e
m
ú
N

s
o
h
c
e
h

e
d

o
i
d
e
m
o
r
e
m