2.7 MACRO-Operadores

Los operadores usados en planificación generalmente tienen:

• Pre-condiciones: determinan cuándo (en qué estados) puede aplicarse.
• Acciones: cambian el estado actual en un nuevo estado.

La solución de un problema implica una búsqueda de operadores.

Meta = encontrar una secuencia de operadores que mapea el estado inicial a alguno de los estados finales.

En muchos casos, algunas de las secuencias de operadores se repiten en problemas diferentes.

Idea principal: juntar estas secuencias de operadores en macro operadores, ``chunks'', etc.

Considerar a los macros como operadores primarios para aumentar la velocidad de solución en problemas similares.

Si se llega a una solución (o sub-meta), guardar la secuencia de operadores que se utilizaron como un nuevo ``macro''-operador.

Los macros:

• Reducen la profundidad del árbol de búsqueda al considerar secuencias largas de operadores como una sola.
• Aumentan el branching factor.

Strips guardaba planes generalizados en tablas triangulares.

Para generalizar un plan (y por lo tanto para que sirva en nuevas situaciones), STRIPS transforma las constantes en variables y para cada operador del plan, re-evalúa sus precondiciones (para asegurarse de no sobre-generalizar).

El uso de macros es común en la vida diaria (e.g., ir del trabajo a casa).

Korf le dió impulso a los macros ('85, '87) resolviendo problemas de manera eficiente (8-puzzle y 15-puzzle y el cubo de Rubik).

Korf construye tablas de macros.

En el 8-puzzle, las 181,440 posiciones posibles, se pueden resolver sin búsqueda usando una tabla de 35 macros.

La tabla de macro operadores para el 8-puzzle se muestra en la tabla 2.16. Cada operador es una secuencia de movimientos: up (U), down (D), left (L), right (R) de un cuadro. Para usarla se localiza el espacio (cuadro 0) y dependiendo de su posición se realizan los movimientos indicados en la columna de cuadro 0. Luego se sigue con el cuadro 1 y asi sucesivamente.

Estos macros llegan a la posición final mostrada en la figura 1.2.

Tabla 2.16: Tabla de macro operadores para el 8-puzzle.

Pos	Cuadros
	0	1	2	3
0
1	UL
2	U	RDLU
3	UR	DLURRDLU	DLUR
4	R	LDRURDLU	LDRU	RDLLURDRUL
5	DR	ULDRURDLDRUL	LURDLDRU	LDRULURDDLUR
6	D	URDLDRUL	ULDDRU	URDDLULDRRUL
7	DL	RULDDRUL	DRUULDRDLU	RULDRDLULDRRUL
8	L	DRUL	RULLDDRU	RDLULDRRUL

Pos	Cuadros
	4	5	6
5	LURD
6	ULDR	RDLLUURDLDRRUL
7	URDLULDR	ULDRURDLLURD	URDL
8	RULLDR	ULDRRULDLURD	RULD

En el cubo de Rubik ($4 * 10^{19}$) se usan 238 macros.

La descomposición de problemas en sub-metas juega un papel fundamental en la creación de macros.

• Permite la simplificación del problema.
• Ayuda a identificar la repetición de submetas.

Las submetas pueden ser:

• Independientes: solución óptima se obtiene al concatenar soluciones óptimas de submetas.
• Serializables: existe un cierto orden de las submetas que resuelven el problema sin violar una submeta resuelta con anterioridad.
• No serializables: se necesitan violar soluciones anteriores para resolver el problema.

Los macros pueden ayudar a resolver problemas no serializables.

El beneficio de los macros decae al incrementar su número (i.e., al resolver más problemas) y es necesario usar filtros de aplicabilidad.

Al aplicar los filtros hay que considerar que los macros no son unidades totalmente independientes.

Se deben de considerar cuándo y bajo qué condiciones crear/eliminar macros (relacionado con Case-based reasoning).

En general los macros aprendidos y su filtrado dependen de la función de evaluación (heurística) que se usa durante la búsqueda de la solución del problema.

En general:

• Una buena función de evaluación requiere de un filtro agresivo.
• Con una mala función de evaluación los macors son indispensables y el filtro puede ser más laxo.
• Con una muy buena función de evaluación los macros no sirven.

Se pueden utilizar en aprendizaje incremental.

Problemas: ciegan la vista del solucionador de problemas (sobretodo en ambientes dinámicos).