Embodied Task Planning via Graph-Informed Action Generation with Large Language Model

Resumen Técnico: GiG (Graph-in-Graph)

1. El Problema

La planificación de tareas para agentes encarnados (robots o agentes de software que interactúan con un entorno físico o simulado) enfrenta desafíos fundamentales cuando se utilizan Grandes Modelos de Lenguaje (LLMs), especialmente en tareas de largo horizonte (secuencias de pasos extensas).

• Limitaciones de los Planificadores Estándar: Los enfoques actuales como ReAct o Tree-of-Thoughts suelen fallar en mantener la coherencia de la estrategia a lo largo del tiempo debido a las limitaciones de la ventana de contexto. Esto provoca "deriva contextual" (el modelo olvida el objetivo principal) o alucinaciones de transiciones que violan las restricciones del entorno.
• Ineficiencia de las Estructuras Árbol: Los métodos basados en árboles de descomposición (como ReCAP) imponen una serialización artificial de tareas concurrentes. Por ejemplo, si una tarea requiere esperar (ej. "hervir agua"), un árbol bloquea la ejecución de otras tareas paralelas (ej. "poner un bol en la mesa") hasta que el nodo actual se complete, generando tiempos de inactividad innecesarios.
• Falta de Memoria Estructurada: Los LLMs carecen de una memoria que capture las relaciones espaciales y topológicas dinámicas del entorno, lo que dificulta la recuperación de patrones de éxito pasados para guiar decisiones futuras.

2. Metodología: El Marco GiG

Los autores proponen GiG (Graph-in-Graph), un marco de planificación que estructura la memoria del agente utilizando una arquitectura de dos niveles de grafos, combinada con un módulo de "búsqueda prospectiva" (lookahead).

A. Arquitectura de Memoria Graph-in-Graph:

1. Grafo de Escena (Grafo Interno):
   • En cada paso $t$, las observaciones del entorno se transforman en un grafo de escena ($SG_t$).
   • Los nodos representan entidades (objetos, robot) y las aristas representan relaciones espaciales (ej. "sobre", "dentro de").
   • Un Red Neuronal de Grafos (GNN), específicamente una Graph Attention Network (GAT), codifica este grafo en un embedding denso ($z_t$) que captura la topología local y las dependencias espaciales, en lugar de solo estadísticas globales.
2. Grafo de Transición de Estados (Grafo Externo):
   • Los embeddings de los grafos de escena se organizan en un grafo de transición global ($OG$) que rastrea la trayectoria de exploración del agente.
   • Este grafo permite detectar bucles (revisitar estados estructuralmente idénticos) y facilita la recuperación de experiencias pasadas.
   • A diferencia de los árboles, este grafo permite la instanciación dinámica de sub-objetivos, permitiendo al agente intercalar tareas (ej. realizar una acción mientras otra está en espera), rompiendo las restricciones de bloqueo de los métodos basados en árboles.

B. Módulo de Búsqueda Prospectiva Acotada (Bounded Lookahead - BL):

• Para evitar que el LLM "alucine" el futuro, GiG integra un módulo que proyecta simbólicamente las consecuencias inmediatas de las acciones candidatas.
• Utiliza una función de transición $T$ (basada en lógica PDDL o modelos del mundo aprendidos) para simular el estado siguiente $s'$ para cada acción válida $a$.
• Esta información de transición "aterrizada" (grounded) se inyecta en el contexto del LLM, transformando la generación de acciones de una predicción imaginativa a una selección discriminativa basada en realidades observables.

C. Recuperación de Experiencia:

• El sistema utiliza los embeddings del GNN para buscar en un banco de memoria experiencias pasadas exitosas que sean estructuralmente similares al estado actual.
• Si se encuentra una similitud (distancia euclidiana por debajo de un umbral $\tau$), se recupera la secuencia de acciones exitosa asociada y se proporciona al LLM como un ejemplo "one-shot" en el prompt, guiando la toma de decisiones.

3. Contribuciones Clave

1. Arquitectura Graph-in-Graph: Introducción de una memoria de doble nivel que combina grafos de escena (topología espacial) y grafos de transición (historia de exploración), permitiendo una recuperación de experiencia basada en la estructura y no solo en el texto.
2. Codificación con GNN: Uso de una GNN ligera para generar representaciones estructurales del entorno, lo que permite una localización precisa de estados y una recuperación eficiente de patrones de éxito.
3. Módulo Bounded Lookahead (BL): Integración de lógica de transición simbólica para validar las consecuencias inmediatas de las acciones antes de que el LLM las ejecute, reduciendo errores de planificación.
4. Eficiencia Computacional: El enfoque evita el crecimiento lineal del historial de contexto (común en ReAct/ReCAP), manteniendo el contexto acotado y reduciendo drásticamente el costo computacional en tareas de largo horizonte.

4. Resultados Experimentales

El marco GiG se evaluó en tres benchmarks de planificación encarnada: Robotouille (Síncrono y Asíncrono) y ALFWorld, utilizando diversos modelos LLM (Qwen3, DeepSeek-R1, Gemini).

• Rendimiento Superior:
  • Robotouille Síncrono: GiG superó a los baselines de última generación (ReCAP, ReAct), logrando mejoras de Pass@1 de hasta un 22% (con Qwen3-235B).
  • Robotouille Asíncrono: En tareas que requieren gestión de concurrencia y esperas, GiG mejoró la tasa de éxito en un 37% respecto al mejor baseline.
  • ALFWorld: Logró un rendimiento casi perfecto (97% en Qwen3 y DeepSeek), superando a ReCAP, demostrando una fuerte capacidad de generalización en entornos parcialmente observables.
• Eficiencia de Pasos: Aunque GiG a veces utiliza más pasos en intentos exitosos (debido a la exploración robusta en tareas difíciles), es significativamente más eficiente en el promedio global (incluyendo fallos) porque evita bucles infinitos y exploraciones estériles.
• Escalabilidad y Costo:
  • El análisis de costos (FLOPs) muestra que GiG es órdenes de magnitud más eficiente que ReAct y ReCAP en tareas de largo horizonte, ya que no acumula historiales de texto extensos.
  • La latencia de construcción del grafo es insignificante (<150 ms) comparada con la decodificación del LLM.
• Transferencia a Modelos Pequeños: La memoria de experiencia actúa como un "plugin" efectivo, mejorando significativamente el rendimiento de modelos más pequeños (ej. Qwen3-30B) al permitirles reutilizar trayectorias exitosas aprendidas por modelos más grandes.

5. Significado e Impacto

Este trabajo demuestra que la representación estructurada de la memoria es crucial para la razonamiento encarnado robusto. Al pasar de una memoria basada en texto plano (historial de conversación) a una memoria basada en grafos estructurales, GiG resuelve problemas críticos de:

• Coherencia a largo plazo: Manteniendo el rastro de objetivos complejos sin perderse en el contexto.
• Concurrencia: Permitiendo la planificación paralela y la gestión de recursos de manera más natural que las estructuras de árbol.
• Eficiencia: Reduciendo drásticamente el costo computacional y la necesidad de ventanas de contexto masivas.

GiG establece un nuevo paradigma para la integración de LLMs en agentes robóticos, donde la combinación de razonamiento simbólico (grafos, lógica de transición) y capacidades semánticas (LLM) permite una ejecución de tareas más fiable y escalable en entornos dinámicos.