On Sample-Efficient Generalized Planning via Learned Transition Models

Questo lavoro propone un approccio di pianificazione generalizzata basato sull'apprendimento esplicito di modelli di transizione neurali che prevedono gli stati successivi, dimostrando che tale metodo supera i pianificatori basati su Transformer nella generalizzazione fuori distribuzione e nell'efficienza dei campioni, richiedendo meno dati e modelli più piccoli.

L'essenziale

🧠 Il Problema: Imparare a guidare senza mappa

Immagina di dover insegnare a un robot come risolvere un puzzle (come spostare dei blocchi o organizzare una consegna) in qualsiasi situazione, non solo in quella specifica che ha visto durante l'allenamento.

Fino a poco tempo fa, i ricercatori hanno provato ad addestrare questi robot (chiamati "planner") facendogli memorizzare liste di azioni. È come se dicessimo al robot: "Quando vedi la situazione A, fai il movimento X; quando vedi la situazione B, fai il movimento Y".

• Il problema: Se il robot si trova in una situazione leggermente diversa da quelle che ha visto (ad esempio, c'è un blocco in più o una stanza in più), va in tilt. Si perde, fa errori e finisce per "allucinare" (creare piani che non funzionano). È come se un guidatore avesse imparato a memoria le svolte di una strada specifica, ma non sapesse come funziona la guida in generale: appena cambia il traffico, non sa più cosa fare.

💡 La Soluzione: Insegnare la "Fisica" del mondo

Invece di insegnare al robot la lista delle mosse, gli autori di questo studio hanno deciso di insegnargli la fisica del mondo.

Hanno creato un modello che impara a rispondere alla domanda: "Se faccio questa azione, come cambia il mondo?".

• Invece di dire "Fai X", il modello dice "Se fai X, il blocco si sposterà qui e la mano diventerà libera".
• Questo è come insegnare a un bambino non solo a fare i passi di una danza, ma a capire la gravità e l'equilibrio. Una volta che capisce le regole, può ballare in qualsiasi stanza, anche se è più grande o ha più persone.

🛠️ Come funziona il loro "Super-Robot"

Il metodo proposto si basa su tre idee chiave, che possiamo paragonare a un processo di apprendimento molto intelligente:

1. La Mappa Universale (Rappresentazione Invariante):
   Immagina di dover descrivere una stanza. Se dici "Il tavolo è al posto 1, la sedia al posto 2", non funziona se la stanza è più grande.
   Gli autori usano un trucco matematico (chiamato Weisfeiler-Leman) che trasforma la stanza in un disegno astratto. Invece di contare i mobili, il robot guarda le relazioni: "Il tavolo è sopra la sedia". Questo disegno è sempre della stessa grandezza, che la stanza abbia 5 mobili o 500. È come se il robot vedesse la "struttura" della realtà, non i dettagli specifici.

2. Il Predittore di Cambiamenti (Modello di Transizione):
   Il robot non indovina la mossa successiva. Indovina come cambierà la situazione.

   • Analogia: È come un meteorologo. Non ti dice "pioverà alle 14:00" (azione), ma ti dice "le nuvole si sposteranno verso nord e la temperatura scenderà" (stato futuro).
   • Per essere ancora più efficienti, il modello impara solo le differenze (i "delta"). Se la maggior parte delle cose nella stanza rimane uguale, il modello impara solo cosa cambia. È come dire: "Il mondo è quasi uguale, tranne che per quel blocco che si è spostato". Questo rende l'apprendimento velocissimo e richiede pochissimi esempi.

3. Il Controllore Simbolico (Verifica):
   Una volta che il modello "immagina" il futuro, un piccolo controllore logico verifica: "Ehi, questa è una mossa possibile secondo le regole del gioco?". Se il modello immagina qualcosa di impossibile, il controllore lo corregge immediatamente. È come avere un allenatore che ti dice: "Quella mossa è bella, ma non è legale nel regolamento".

📊 I Risultati: Piccolo ma Potente

I risultati sono sorprendenti:

• Efficienza: Il loro modello è minuscolo (come un'app per smartphone) rispetto ai giganti attuali (come i modelli Transformer che sono grandi come intere biblioteche).
• Risparmio: Hanno bisogno di migliaia di volte meno dati per imparare.
• Generalizzazione: Funziona bene anche quando il problema diventa molto più grande di quelli usati per l'allenamento (ad esempio, passare da 4 blocchi a 20 blocchi). I vecchi modelli fallivano completamente in questi casi, mentre il loro continua a funzionare.

🎯 In Sintesi

Questo studio ci dice che per insegnare a un'intelligenza artificiale a risolvere problemi complessi in modo flessibile, non serve un cervello enorme che memorizza milioni di esempi. Serve invece un modello intelligente che capisca come funziona il mondo (le regole di causa-effetto) e che possa adattarsi a scenari nuovi.

È il passaggio dal memorizzare la ricetta a capire la chimica della cucina: così potrai cucinare qualsiasi piatto, anche con ingredienti che non hai mai usato prima.

Sommario tecnico

1. Il Problema

Il Pianificazione Generalizzata (Generalized Planning - GP) mira a costruire strategie di soluzione che siano valide per intere famiglie di problemi di pianificazione che condividono lo stesso modello di dominio, formalizzato da una funzione di transizione $\gamma: S \times A \rightarrow S$.

Il lavoro identifica due limiti principali negli approcci recenti basati su Transformer (come PlanGPT e Plansformer):

• Approccio "Action-Centric": Questi modelli predicono direttamente le sequenze di azioni ($p(\pi | \Pi)$) senza modellare esplicitamente l'evoluzione dello stato del mondo.
• Scarsa Efficienza e Drift: Richiedono dataset enormi e modelli di grandi dimensioni. Inoltre, soffrono di "drift di stato" (state drift) in scenari a lungo orizzonte o fuori distribuzione (OOD), poiché non hanno una rappresentazione esplicita di come lo stato cambia dopo ogni azione.

L'obiettivo di questo lavoro è dimostrare che è possibile ottenere una generalizzazione robusta e size-invariant (indipendente dal numero di oggetti) con modelli molto più piccoli e dati di training limitati, cambiando il paradigma di apprendimento.

2. Metodologia

Gli autori propongono un approccio State-Centric (centrato sullo stato) che riformula la pianificazione generalizzata come un problema di apprendimento di un modello di transizione.

A. Rappresentazione dello Stato Size-Invariant

Per gestire domini con un numero variabile di oggetti, il sistema non utilizza vettori a dimensione fissa basati su slot (che falliscono se il numero di oggetti supera quello di training), ma utilizza Embedding di Grafi Weisfeiler-Leman (WL).

• Lo stato e l'obiettivo vengono mappati in un grafo relazionale.
• Attraverso iterazioni di raffinamento dei colori (WL), si ottiene un vettore di embedding $\phi(s, g)$ a dimensione fissa $D$, che dipende solo dal dominio e non dal numero di oggetti $|O|$.
• Questa rappresentazione è invariante per permutazione e dimensione.

B. Apprendimento del Modello di Transizione

Invece di prevedere l'azione successiva, il modello apprende una funzione neurale $f_\theta$ che predice la transizione di stato nello spazio degli embedding.

• Formulazione Residuale: Dato che le transizioni STRIPS sono sparse (la maggior parte dei predicati rimane invariata), il modello predice un vettore di differenza (delta) $\Delta_t$ piuttosto che lo stato intero.
  $$\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$$
• Vengono testati due tipi di modelli:
  1. Parametrico: Una rete LSTM a due livelli (per catturare dipendenze temporali).
  2. Non Parametrico: XGBoost (regressore basato su alberi decisionali), che si è rivelato molto efficace per la previsione dei delta.

C. Decodifica Neuro-Simbolica

Al momento dell'inferenza, il sistema non esegue direttamente l'output neurale, ma utilizza un processo di verifica simbolica:

1. Il modello neurale predice l'embedding target $\hat{\phi}(s_{t+1})$.
2. Il sistema enumera tutti i successori simbolici validi $Succ(s_t)$ generati dagli operatori del dominio.
3. Viene selezionato il successore simbolico il cui embedding è più vicino (in termini di distanza euclidea o coseno) alla predizione neurale.
4. L'azione corrispondente a questo successo viene eseguita.
   Questo garantisce che ogni passo del piano sia simbolicamente valido, correggendo eventuali errori di previsione del modello neurale.

3. Contributi Chiave

1. Formulazione State-Centric: Una nuova formulazione della pianificazione generalizzata basata sulla previsione dello stato successore condizionato all'obiettivo, invece che sulla previsione diretta delle azioni.
2. Valutazione Sistematica delle Rappresentazioni: Dimostrazione empirica che le rappresentazioni relazionali invarianti per dimensione (WL) sono essenziali per la generalizzazione OOD, mentre le codifiche a slot fissi (FSF) falliscono.
3. Efficienza del Campionamento e dei Modelli: Dimostrazione che modelli compatti (LSTM con ~1M parametri o XGBoost con ~115k nodi) addestrati su piccoli dataset (senza augmentation dei dati) superano o eguagliano i Transformer di grandi dimensioni (25-220M parametri) in termini di successo nella pianificazione fuori distribuzione.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su quattro domini benchmark IPC: Blocksworld, Gripper, Logistics, VisitAll.

• Generalizzazione Estensiva (Extrapolation):
  • Gli approcci basati su Transformer (Plansformer, PlanGPT, SymT) hanno ottenuto un successo del 0% nella generalizzazione estensiva (problemi con più oggetti rispetto al training) in quasi tutti i domini.
  • I modelli State-Centric (specialmente WL-XGBoost con previsione residuale) hanno ottenuto risultati significativi:
    • Blocksworld: 45% di successo (vs 13% di SymT).
    • VisitAll: 87% di successo (vs 64% di SymT).
• Efficienza: I modelli proposti sono ordini di grandezza più piccoli e richiedono meno dati di training rispetto alle controparti basate su Transformer.
• Limiti: Il modello ha faticato nel dominio Logistics, che presenta accoppiamenti causali gerarchici complessi e dipendenze a lungo raggio, dove la previsione di transizione a un solo passo non è sufficiente. Anche il pianificatore simbolico classico (Fast Downward) ha mostrato degrado in questo dominio sotto vincoli di tempo.
• Impatto della Previsione Residuale: L'uso della previsione del delta ($\Delta_t$) ha migliorato drasticamente le prestazioni nei domini sparsi (es. da 8% a 87% in VisitAll per XGBoost).

5. Significato e Implicazioni

Questo lavoro sfida la convinzione corrente secondo cui la pianificazione generalizzata richiede modelli linguistici di grandi dimensioni (LLM) e enormi quantità di dati.

• Bias Induttivo vs. Scala: Dimostra che un bias induttivo appropriato (apprendimento esplicito della fisica del dominio tramite modelli di transizione e rappresentazioni relazionali invarianti) è più efficace della semplice scala architetturale o dell'aumento dei dati.
• Robustezza: L'interfaccia neuro-simbolica garantisce la correttezza logica dei piani, mitigando il problema del "drift di stato" tipico dei modelli autoregressivi.
• Futuro: Suggerisce che per domini complessi con dipendenze gerarchiche, è necessario estendere il framework verso transizioni astratte o multi-step, mantenendo la verifica simbolica.

In sintesi, il paper propone un ritorno alla modellazione esplicita delle dinamiche del mondo, combinata con rappresentazioni geometriche avanzate (WL), per ottenere una pianificazione generalizzata efficiente, robusta e scalabile.