Download Sistemas de Producción

Sistemas de Producción
Daniel Borrajo, Carlos Linares
{daniel.borrajo,carlos.linares}@uc3m.es
Departamento de Inteligencia Artificial
Noviembre 2004
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Sistemas de Producción
En los primeros pasos de la IA, se cuestionó el tratamiento que daban los
algoritmos tradicionales a los problemas.
• Flujo de control fijo
• Secuencialidad
• No adecuado en entornos cambiantes
Solución: los datos dirigen las operaciones
Octubre, 2004
I
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Componentes de un SP
Base de hechos o memoria de trabajo (BH o WM): conocimiento sobre el
dominio en un determinado momento
Base de reglas (BR): conjunto de reglas (producciones)
SI A ENTONCES B
A: condiciones de aplicación
B: acciones sobre la BH o mundo externo
Estrategia de control, intérprete de reglas, o motor de inferencias (EC o MI):
responsable de encadenar los ciclos de funcionamiento.
• Fase de decisión: selección de reglas
• Fase de acción: ejecución de reglas
Una regla se activa cuando sus precondiciones son ciertas en el estado actual
de la BH o cuando la regla concluye algo que se busca establecer
Octubre, 2004
II
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Funcionamiento de un SP
Tipos de sistemas
• Sistemas dirigidos por el antecedente. Modus Ponens
• Sistemas dirigidos por el consecuente. Modus Tollens
Fases
Fase de decisión
• Etapa de restricción (opcional)
• Etapa de equiparación o filtrado. RETE
• Etapa de resolución del conjunto conflicto
Fase de acción
Caracterı́sticas de la estrategia
• Lo más general posible
• Lo más eficiente posible (heurı́sticas): implı́citas o explı́citas
• Causar movimiento
• Ser sistemática
Octubre, 2004
III
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Ejemplo: 8 puzzle. Base de hechos
1
2
3
?
5 6
4
7
8
2
3
1
5 6
4
7
8
listas: (V11,V12,V13,. . . ,V33)
lógica de predicados: casilla(X,Y,Valor)
marcos:
Casilla
es-un:
Octubre, 2004
Atributo
Posibles valores/Valor
x
número [1..3]
y
número [1..3]
valor
número [0..8]
IV
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
8-puzzle. Base de hechos inicial
1
2
3
5 6
4
7
?
8
2
3
1
5 6
4
7
8
listas: (1,2,3,0,5,6,4,7,8)
lógica de predicados: casilla(1,1,1),casilla(1,2,2),. . . ,casilla(3,3,8)
marcos:
Octubre, 2004
casilla11
casilla12
instancia-de: Casilla
instancia-de: Casilla
Atributo
Posibles valores/Valor
Atributo
Posibles valores/Valor
x
1
x
1
y
1
y
2
valor
1
valor
2
V
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
8-puzzle. Base de hechos final o metas
1
2
3
5 6
4
7
?
8
2
3
1
5 6
4
7
8
listas: (2,0,3,1,5,6,4,7,8) ó (2,X,Y,1,5,Z,4,7,8)
lógica de predicados: casilla(1,1,2),casilla(1,2,0),. . . ,casilla(3,3,8)
marcos:
Octubre, 2004
casilla11
casilla12
instancia-de: Casilla
instancia-de: Casilla
Atributo
Posibles valores/Valor
Atributo
Posibles valores/Valor
x
1
x
1
y
1
y
2
valor
2
valor
0
VI
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
8-puzzle. Base de reglas
listas
Si (0,X1,X2,X3,X4,X5,X6,X7,X8)
Entonces (X1,0,X2,X3,X4,X5,X6,X7,X8)
Si (0,X1,X2,X3,X4,X5,X6,X7,X8)
Entonces (X3,X1,X2,0,X4,X5,X6,X7,X8)
...
Problema: implica definir todas las posibles combinaciones de posición del
vacı́o (0) y sus posibles movimientos
Octubre, 2004
VII
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
8-puzzle. Lógica de predicados
Si casilla(X,Y,0),casilla(X1,Y,Z),X=X1+1
Entonces casilla(X1,Y,0),casilla(X,Y,Z),∼casilla(X,Y,0),∼casilla(X1,Y,Z)
Si casilla(X,Y,0),casilla(X1,Y,Z),X=X1-1
Entonces casilla(X1,Y,0),casilla(X,Y,Z),∼casilla(X,Y,0),∼casilla(X1,Y,Z)
Si casilla(X,Y,0),casilla(X,Y1,Z),Y=Y1+1
Entonces casilla(X,Y1,0),casilla(X,Y,Z),∼casilla(X,Y,0),∼casilla(X,Y1,Z)
Si casilla(X,Y,0),casilla(X,Y1,Z),Y=Y1-1
Entonces casilla(X,Y1,0),casilla(X,Y,Z),∼casilla(X,Y,0),∼casilla(X,Y1,Z)
Realmente en
PROLOG
difı́cil de realizar dado que requiere razonamiento no
monótono
Octubre, 2004
VIII
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
8-puzzle. Marcos
Si ?casilla ← (casilla (x ?x) (y ?y) (valor 0))
Derecha
?casilla1 ← (casilla (x ?x1) (y ?y) (valor ?v))
(test ?x=?x1+1)
Entonces modifica(?casilla,valor,?v),modifica(?casilla1,valor,0)
Si ?casilla ← (casilla (x ?x) (y ?y) (valor 0))
Izquierda
?casilla1 ← (casilla (x ?x1) (y ?y) (valor ?v))
(test ?x=?x1-1)
Entonces modifica(?casilla,valor,?v),modifica(?casilla1,valor,0)
Si ?casilla ← (casilla (x ?x) (y ?y) (valor 0))
Abajo
?casilla1 ← (casilla (x ?x) (y ?y1) (valor ?v))
(test ?y=?y1+1)
Entonces modifica(?casilla,valor,?v),modifica(?casilla1,valor,0)
Si ?casilla ← (casilla (x ?x) (y ?y) (valor 0))
Arriba
?casilla1 ← (casilla (x ?x) (y ?y1) (valor ?v))
(test ?y=?y1-1)
Entonces modifica(?casilla,valor,?v),modifica(?casilla1,valor,0)
Octubre, 2004
IX
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Equiparación
Primera aproximación: en cada ciclo se calcula el CC y se resuelve
Problema: lentitud
Solución: algoritmo
RETE
(algoritmo de redundancia temporal)
• a partir de las reglas se crea inicialmente un grafo (red RETE)
• se propaga el contenido de la base de hechos inicial a través de la red
• cada vez que se produce un cambio en la base de hechos (normalmente, a
través del consecuente de una regla), se propagan los cambios
• en cada ciclo, en los nodos terminales de la red se dispondrá del CC
Idea clave: similitud estructural
Octubre, 2004
X
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Encadenamiento hacia adelante
BH inicial: (casilla (x 1) (y 1) (valor 1))
(casilla (x 1) (y 2) (valor 2))
...
(casilla (x 3) (y 3) (valor 8))
Equiparación:
(Arriba, ?x=1, ?y=2, ?y1=1, ?v=1, ?casilla=casilla-1-2, ?casilla1=casilla-1-1)
(Abajo, ?x=1, ?y=2, ?y1=3, ?v=4, ?casilla=casilla-1-2, ?casilla1=casilla-1-3)
(Derecha, ?x=1, ?y=2, ?x1=2, ?v=5, ?casilla=casilla-1-2, ?casilla1=casilla-2-1)
Resolución del CC (por ejemplo, primera regla):
(Arriba, ?x=1, ?y=2, ?y1=1, ?v=1, ?casilla=casilla-1-2, ?casilla1=casilla-1-1)
Ejecución: (- (casilla (x 1) (y 1) (valor 1)))
(+ (casilla (x 1) (y 1) (valor 0)))
(- (casilla (x 1) (y 2) (valor 0)))
(+ (casilla (x 1) (y 2) (valor 1)))
Equiparación . . .
Octubre, 2004
XI
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Encadenamiento hacia atrás (à la PROLOG)
Metas: (casilla (x 1) (y 1) (valor 2))
(casilla (x 1) (y 2) (valor 0))
...
(casilla (x 3) (y 3) (valor 8))
Reducción: selección meta (por ejemplo, la primera)
(casilla (x 1) (y 1) (valor 2))
Equiparación:
(Abajo, ?v=2, ?casilla=casilla-1-1, ?casilla1=casilla-1-2)
(Derecha, ?v=2, ?casilla=casilla-1-1, ?casilla1=casilla-2-1)
Resolución del CC (por ejemplo, primera regla):
(Abajo, ?v=2, ?casilla=casilla-1-1, ?casilla1=casilla-1-2)
Ejecución:
introducir las condiciones de la regla instanciada en conjunto de metas
Reducción: . . .
Octubre, 2004
XII
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Comparativa de tipos de encadenamiento
Inconvenientes de encadenamiento hacia adelante
• No focalización hacia las metas
• Es necesario tener inicialmente todos los datos en la BH
Ventajas de encadenamiento hacia atrás
• Limita el número de equiparaciones
• Disminuye el árbol de búsqueda
Factores de elección
• Número de estados iniciales y metas
• Factor de ramificación
• Justificación del funcionamiento
Octubre, 2004
XIII
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Estrategias de resolución
Primera regla
Más conocimiento
Más prioridad
Más especı́fica
Más general
Referente al elemento más nuevo
No aplicada antes
Más veces aplicada
Aleatoriamente
Explorar todas
Metarreglas
Mezcla de estrategias
Octubre, 2004
XIV
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Ventajas e inconvenientes
Ventajas
• Modularidad, lo que facilita incrementalidad
• Carácter declarativo
• Uniformidad
• Naturalidad
• Flexibilidad
• Aprendizaje automático
• Modelización del comportamiento animal y humano
Inconvenientes
• Ineficiencia
• Opacidad
• Dificultad de representación de los algoritmos
Octubre, 2004
XV
Departamento de Inteligencia Artificial
Sistemas de Producción
Daniel Borrajo, Carlos Linares
Dominios Apropiados
Tareas: transición entre estados
Conocimiento difuso
Conjuntos de acciones independientes
Conocimiento separable de la forma de usarse
Octubre, 2004
XVI
Departamento de Inteligencia Artificial