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

1. Il Problema

L'articolo affronta le sfide fondamentali nella pianificazione di compiti per agenti incarnati (embodied agents) che utilizzano i Large Language Models (LLM). Sebbene gli LLM dimostrino eccellenti capacità di ragionamento zero-shot, il loro utilizzo come agenti fisici o simulati in compiti a lungo raggio (long-horizon) presenta limiti critici:

• Coerenza Strategica: Gli agenti faticano a mantenere una strategia coerente su orizzonti temporali estesi a causa delle limitazioni della finestra di contesto.
• Allucinazioni: Gli LLM tendono a generare transizioni di stato che violano i vincoli dell'ambiente o a "allucinare" passaggi impossibili.
• Limiti delle Strutture ad Albero: I metodi esistenti (come ReCAP) utilizzano spesso decomposizioni gerarchiche basate su alberi. Tuttavia, gli alberi impongono una serializzazione artificiale dei compiti: se un sotto-obiettivo richiede un'attesa passiva (es. "bollire l'acqua"), l'albero blocca l'esecuzione di altri compiti paralleli (es. "preparare la ciotola"), costringendo l'agente a tempi morti inutili.
• Deriva del Contesto: L'accumulo lineare della storia delle interazioni porta a una perdita del focus sugli obiettivi principali.

2. Metodologia: Il Framework GiG

Gli autori propongono GiG (Graph-in-Graph), un nuovo framework di pianificazione che struttura la memoria dell'agente utilizzando un'architettura a due livelli basata su grafi.

A. Architettura della Memoria "Graph-in-Graph"

Il sistema utilizza due grafi nidificati per rappresentare lo stato e la memoria:

1. Grafo della Scena (Inner Graph - SG): Rappresenta lo stato istantaneo dell'ambiente al passo $t$. I nodi sono entità (oggetti, robot) e gli archi sono le relazioni spaziali (es. "formaggio sopra il tavolo").
   • Un Graph Neural Network (GNN), specificamente una Graph Attention Network (GAT), codifica questo grafo in un embedding vettoriale denso ($z_t$) che cattura la topologia strutturale e le proprietà semantiche, non solo le statistiche globali.
2. Grafo di Transizione di Stato (Outer Graph - OG): Rappresenta la traiettoria di esplorazione dell'agente nel tempo.
   • I nodi di questo grafo sono gli embedding $z_t$ dei grafi della scena.
   • Gli archi rappresentano le transizioni effettuate tramite azioni.
   • Questo grafo funge da memoria episodica, permettendo di rilevare cicli (loop) e recuperare pattern di successo passati.

B. Generazione di Azioni Informata dal Grafo

Il framework integra tre componenti chiave per guidare l'agente:

1. Recupero di Esperienze Strutturali: Utilizzando gli embedding del GNN, il sistema cerca nel "banco di memoria" (costituito da traiettorie di successo passate) stati strutturalmente simili alla situazione corrente. Questo permette un trasferimento di competenze tra compiti diversi basandosi sulla topologia dell'ambiente piuttosto che sulla semplice similarità testuale.
2. Modulo di Lookahead Limitato (Bounded Lookahead - BL): Per mitigare le allucinazioni, il sistema simula proattivamente le conseguenze immediate delle azioni candidate utilizzando una funzione di transizione simbolica (es. logica PDDL). L'agente riceve una "visione fondata" (grounded view) dei possibili stati successivi, trasformando la scelta dell'azione da una previsione immaginativa a una selezione discriminativa basata su realtà osservabili.
3. Rilevamento dei Loop (Loop Detection): Il sistema confronta l'embedding corrente con la storia recente nel grafo esterno. Se viene rilevato uno stato strutturalmente identico (loop), l'agente viene avvisato per evitare esplorazioni infinite.

3. Contributi Chiave

• Architettura di Memoria Ibrida: Introduzione di una struttura Graph-in-Graph che combina la descrizione topologica locale (scena) con la memoria di transizione globale, superando i limiti delle strutture ad albero nella gestione di compiti paralleli e asincroni.
• Codifica Strutturale tramite GNN: Uso di un GNN leggero per trasformare osservazioni non strutturate in embedding che preservano le relazioni spaziali, facilitando un recupero di memoria preciso e robusto.
• Lookahead Fondato: Integrazione di una simulazione simbolica a 1 passo per fornire all'LLM vincoli di transizione espliciti, riducendo drasticamente le azioni invalide.
• Efficienza Computazionale: A differenza dei metodi che accumulano intere storie di conversazione, GiG mantiene il contesto stretto aggregando lo stato in grafi, riducendo il costo computazionale e il rischio di deriva del contesto.

4. Risultati Sperimentali

Il framework è stato valutato su tre benchmark di pianificazione incarnata: Robotouille (Sincrono e Asincrono) e ALFWorld.

• Robotouille Sincrono: GiG ha superato i baselines (ReCAP, ReAct, CoT) con guadagni di Pass@1 fino al 22% (con Qwen3-235B). Ha dimostrato una maggiore robustezza nei compiti difficili, completando con successo task dove i baselines fallivano.
• Robotouille Asincrono: In scenari con ritardi e necessità di parallelismo (es. attendere mentre si fanno altre cose), GiG ha ottenuto miglioramenti fino al 37% rispetto ai baselines. La capacità di istanziare dinamicamente nuovi sotto-obiettivi durante le attese ha eliminato i tempi morti tipici delle decomposizioni ad albero.
• ALFWorld: In un ambiente parzialmente osservabile, GiG ha raggiunto quasi il 97% di successo con modelli avanzati, superando ReCAP.
• Efficienza e Scalabilità:
  • Costo Computazionale: L'analisi dei FLOPs mostra che GiG richiede ordini di grandezza meno risorse computazionali rispetto a ReAct e ReCAP nei compiti a lungo raggio, poiché non elabora intere finestre di contesto storiche.
  • Modelli Piccoli: L'uso della memoria di esperienza (GiG+Exp) ha permesso a modelli più piccoli (es. Qwen3-30B) di recuperare prestazioni significativamente, colmando il divario con modelli più grandi.

5. Significato e Impatto

Il lavoro di GiG rappresenta un passo avanti significativo nell'intersezione tra LLM e robotica/incarnazione:

1. Superamento dei Limiti degli Alberi: Dimostra che le strutture a grafo sono superiori agli alberi per la pianificazione in ambienti dinamici e paralleli, permettendo un'interleaving (intreccio) naturale dei compiti.
2. Memoria Strutturata vs. Testuale: Sposta il paradigma dal recupero di frammenti di testo al recupero di pattern strutturali dell'ambiente, rendendo l'agente più capace di generalizzare in scenari nuovi ma topologicamente simili.
3. Riduzione delle Allucinazioni: L'integrazione di un modulo di lookahead simbolico fornisce un ancoraggio alla realtà fisica, riducendo la dipendenza dalla capacità puramente generativa dell'LLM.
4. Efficienza Operativa: La riduzione del costo computazionale e della latenza rende fattibile l'implementazione di agenti pianificatori complessi su dispositivi con risorse limitate o in scenari real-time.

In sintesi, GiG offre un approccio robusto ed efficiente per la pianificazione a lungo raggio, combinando la flessibilità semantica degli LLM con la rigidezza logica e strutturale dei grafi e della simulazione simbolica.