Resumen Técnico: Aprendizaje de Modelos de Acción Levantados a partir de Huellas con Información Mínima

Declaración del Problema

Trabajos recientes han demostrado que los modelos STRIPS levantados pueden aprenderse eficientemente únicamente a partir de huellas de acción (algoritmo SIFT), y que los modelos STRIPS+ (que permiten argumentos de acción implícitos) pueden aprenderse a partir de huellas de estado-acción totalmente observables (algoritmo SYNTH). Sin embargo, estos enfoques enfrentan limitaciones prácticas:

1. SIFT requiere huellas de acción STRIPS completas donde los argumentos son explícitos, lo que a menudo incluye parámetros innecesarios no requeridos para la selección de acciones (por ejemplo, en acertijos de baldosas deslizantes, la posición actual de una baldosa debe pasarse explícitamente incluso si la acción es "mover a la izquierda").
2. SYNTH asume la observabilidad total de todos los predicados de estado, lo cual es poco realista para agentes que operan en entornos parcialmente observables.

Este artículo aborda el problema de aprender dominios de acción STRIPS+ a partir de huellas donde tanto los argumentos de acción como la información de estado son parcialmente observables. Específicamente, los autores investigan las condiciones bajo las cuales puede aprenderse un dominio equivalente cuando las huellas portan información mínima: algunos argumentos de acción se omiten, y los predicados de estado son totalmente no observables, totalmente observables o solo localmente observables (observables únicamente para objetos relevantes para el estado actual).

Metodología

La solución propuesta, SYNTH+, es un algoritmo unificado que extiende y combina las capacidades de SIFT y SYNTH. Opera sobre huellas extendidas (secuencias de acciones y observaciones parciales de estado) y se basa en dos mecanismos centrales:

1. Características de Mutua Exclusión (Extensión de SIFT)

Para manejar argumentos de acción faltantes sin observabilidad de estado, los autores introducen características de mutua exclusión (mutex).

• Concepto: Una característica de mutua exclusión $f = \langle k, A, D \rangle$ representa un predicado de aridad $k$ donde el $k$-ésimo argumento está determinado implícitamente por los primeros $k-1$ argumentos.
• Mecanismo: A diferencia de las características estándar donde los patrones de adición y eliminación tienen la misma aridad, las características de mutua exclusión permiten que los patrones de eliminación tengan aridad $k-1$. Esto captura la restricción de que una acción (por ejemplo, soltar()) elimina un predicado (por ejemplo, sosteniendo(o)) basándose en el objeto que se sostiene actualmente, sin nombrar explícitamente ese objeto en la huella de acción.
• Consistencia: Una característica de mutua exclusión es consistente si, a través del grafo de huellas, cada átomo ground $f(o)$ recibe un único valor de verdad, y para cualquier par de átomos verdaderos $f(o)$ y $f(o')$ en el mismo estado, si los últimos argumentos difieren ($o_k \neq o'_k$), entonces al menos un argumento precedente también debe diferir ($o_i \neq o'_i$ para algún $i < k$).

2. Síntesis de Consultas e Integración (Extensión de SYNTH)

SYNTH+ integra la "invención" de predicados (vía SIFT) con la inferencia de argumentos implícitos (vía SYNTH) en un bucle iterativo:

1. Entrada: Un grafo etiquetado de huellas extendidas y un conjunto de predicados totalmente observables $P_\omega$.
2. Iteración:
   • Paso SIFT+: Utiliza patrones de acción sobre argumentos explícitos y argumentos implícitos actualmente conocidos para inventar nuevas características de mutua exclusión y características simples. Estas características representan nuevos predicados y sus efectos.
   • Paso SYNTH: Utiliza los predicados recién inventados (y cualquier predicado observable) para definir consultas (subconsultas $Q_i$) que vinculan variables implícitas ($z_i$) a objetos únicos en el estado.
   • Actualización: El grafo se actualiza con los nuevos argumentos implícitos y sus consultas definitorias.
3. Terminación: El proceso continúa hasta alcanzar un punto fijo o exceder un límite de profundidad máximo ($d_{max}$).

3. Observabilidad Local

El marco se extiende a LOCAL SYNTH+, que maneja la observabilidad local. En este escenario, un predicado es observable solo para objetos "locales" (aquellos que aparecen como argumentos en la acción actual). El algoritmo modifica el procedimiento de prueba de consistencia (TEST*) para asumir que los átomos no locales son falsos al probar precondiciones, asegurando que las partes no observadas del estado no invaliden el aprendizaje de argumentos implícitos.

Contribuciones Clave

1. Algoritmo SYNTH+: Un algoritmo general para aprender dominios STRIPS+ a partir de huellas con observabilidad parcial tanto de acciones como de estados. Unifica la invención de predicados de SIFT con la resolución de argumentos implícitos de SYNTH.
2. Características de Mutua Exclusión: Un formalismo novedoso que permite el aprendizaje de predicados donde el último argumento depende funcionalmente de los demás, permitiendo la recuperación de argumentos de acción omitidos sin observación total del estado.
3. Resultados de Completitud: Se establecen condiciones teóricas para cuando los algoritmos son completos:
   • SIFT+ (Sin observabilidad de estado): Requiere que el dominio STRIPS+ oculto esté bien formado, sea fuertemente conexo y acíclico en su grafo de dependencias (donde los nodos son predicados y variables implícitas).
   • SYNTH+ (Observabilidad parcial de estado): Requiere que el grafo de dependencias restringido a predicados no observables sea acíclico.
   • LOCAL SYNTH+: Probado completo bajo observabilidad local para predicados clave (predicados en precondiciones que involucran solo argumentos implícitos) si son totalmente observables, y otros predicados son localmente observables.
4. Generalización: El trabajo demuestra que SIFT y SYNTH son casos especiales de SYNTH+ (donde $P_\omega = \emptyset$ y $P_\omega = P$, respectivamente).

Resultados Experimentales

Los autores evaluaron SIFT+ y SYNTH+ en una suite de dominios de planificación estándar (por ejemplo, Bloques, Entrega, Cuadrícula, Sokoban, Logística) utilizando huellas extendidas generadas a partir de modelos STRIPS+ ocultos.

• Rendimiento de SIFT+: Aprendió con éxito dominios correctos (tasa de verificación del 100%) únicamente a partir de huellas de acción en todos los dominios probados, recuperando un promedio del 55% de los argumentos de acción que fueron omitidos de las huellas.
• Rendimiento de SYNTH+: Aprendió dominios correctos utilizando significativamente menos predicados observables que SYNTH.
  • En Entrega, SYNTH+ aprendió el dominio observando solo la posición del agente (at(x)) y la adyacencia estática, mientras que SYNTH requería todos los predicados fluente.
  • En Sokoban y Logística, SYNTH+ aprendió dominios con solo predicados estáticos observados, un escenario donde ni SYNTH ni SIFT+ pudieron tener éxito.
• Eficiencia: Los algoritmos se ejecutaron eficientemente (de segundos a minutos) en hardware estándar, escalando a dominios con miles de pasos de huella.

Significado y Afirmaciones

El artículo afirma que SYNTH+ proporciona una alternativa práctica y levantada al aprendizaje por refuerzo basado en modelos al permitir el aprendizaje de modelos dinámicos a partir de huellas "naturales". Estas huellas requieren información mínima:

• No necesitan listar cada argumento requerido por una codificación STRIPS formal (por ejemplo, la posición actual de un bloque siendo desapilado).
• No requieren observabilidad total del estado; la observabilidad parcial o local de predicados específicos es suficiente.

Los autores enfatizan que su enfoque cierra la brecha entre el aprendizaje teórico de modelos (que a menudo asume observabilidad total) y la aplicación práctica (donde los agentes tienen percepción limitada). Al caracterizar las condiciones exactas (aclicidad de los grafos de dependencias) bajo las cuales el aprendizaje es posible, el trabajo establece un alcance riguroso para el aprendizaje de modelos de acción levantados en entornos parcialmente observables. Los resultados sugieren que los dominios complejos pueden reconstruirse a partir de huellas que transmiten solo la información necesaria para seleccionar acciones, en lugar de la descripción completa del estado.