Riepilogo Tecnico: Imparare a Cercare e Cercare per Imparare per la Generalizzazione nella Pianificazione

Enunciato del Problema

La generalizzazione combinatoria rimane una sfida centrale nell'Apprendimento per Rinforzo Profondo (DRL), dove le politiche o le funzioni di valore devono generalizzare a scenari fuori distribuzione definiti da una struttura comune del problema. La pianificazione classica offre un banco di prova ideale per questo problema perché la struttura relazionale sottostante (predicati e schemi d'azione) è fissa ed esplicita, mentre le istanze variano per numero di oggetti, stati iniziali e obiettivi.

Tuttavia, gli approcci DRL standard faticano nei domini di pianificazione con ricompense sparse. La ricerca in tempo reale (transizioni stato-a-stato iterative), tipica degli algoritmi RL come LRTA* o RTDP, è inefficace per trovare piani in questi contesti. Al contrario, i pianificatori classici utilizzano la ricerca best-first (ad es. A*, WA*) ma si affidano a euristiche costruite a mano. Sebbene lavori recenti abbiano tentato di apprendere politiche o euristiche generali, i metodi esistenti spesso si basano sulla ricerca in tempo reale, sull'apprendimento supervisionato da dimostrazioni esperte o sul ridenominamento a posteriori (hindsight relabeling), fallendo nel stabilire un ciclo di auto-miglioramento in cui ricerca e apprendimento si rafforzino reciprocamente per raggiungere una generalizzazione zero-shot attraverso dimensioni del problema variabili.

Metodologia: Ricerca Generalizzata per la Pianificazione (GSP)

Gli autori propongono GSP, un framework di auto-miglioramento che combina la ricerca best-first con il Q-learning per apprendere funzioni azione-valore generali ($Q_\theta$).

Ciclo Principale

1. Apprendimento Guidato dalla Ricerca: Invece della ricerca in tempo reale, GSP utilizza Weighted A (WA)** per risolvere le istanze di addestramento. La ricerca è guidata dai valori $Q_\theta(s, a)$ appresi correntemente.
2. Generazione dei Dati: Mentre WA* espande i nodi, genera un buffer di replay di transizioni. Crucialmente, la ricerca fornisce segnali di supervisione che il RL standard non possiede:
   • Percorsi Obiettivo: Quando un obiettivo viene raggiunto, l'algoritmo risale all'indietro per assegnare valori reali di ritorno all'obiettivo alle coppie sul percorso della soluzione.
   • Punti Morti: Se uno stato è un punto morto (nessuna azione applicabile), alla coppia genitore viene assegnato un ritorno di penalità fisso.
   • Limiti Inferiori: La ricerca fornisce un limite inferiore sul ritorno ottimale per qualsiasi coppia stato-azione incontrata su un percorso di soluzione.
3. Aggiornamento del Q-Learning: La rete $Q_\theta$ viene aggiornata utilizzando questi target derivati dalla ricerca. Per le coppie del percorso obiettivo, il target è $\max(R, \hat{y})$, dove $R$ è il limite inferiore derivato dalla ricerca e $\hat{y}$ è il target standard di bootstrap. Questo impedisce che le stime di valore scendano al di sotto di quanto la ricerca ha già dimostrato raggiungibile.
4. Selezione delle Istanze: Per ottimizzare l'efficienza dell'apprendimento, il framework mantiene tre pool di istanze (non risolte, risolte e soddisfatte) e campiona da essi con pesi che crescono esponenzialmente, dando priorità alle istanze che forniscono gli aggiornamenti più informativi (ad es. quelle con soluzioni subottimali).

Rappresentazione: GNN Relazionali

Per garantire la generalizzazione attraverso diversi numeri di oggetti e obiettivi, $Q_\theta$ è rappresentata da una Rete Neurale a Grafo Relazionale (R-GNN).

• Input: Uno stato $s$ e un obiettivo $g$ sono codificati come un insieme di atomi ground. Le azioni applicabili sono rappresentate esplicitamente introducendo "oggetti azione" e atomi ausiliari, permettendo alla rete di valutare scelte d'azione specifiche nel contesto dello stato.
• Architettura: La rete utilizza il passaggio di messaggi sulla struttura relazionale. MLP specifici per i predicati generano messaggi basati sui ruoli degli argomenti, che vengono aggregati tramite funzioni invarianti per permutazione.
• Output: Un MLP di lettura condiviso combina l'embedding dell'oggetto azione specifico con un riepilogo raggruppato dello stato e dell'obiettivo per produrre il valore Q. Questa architettura garantisce che il modello apprenda un principio di punteggio comune per le azioni grounded piuttosto che predittori separati per ogni schema.

Contributi Chiave

1. Ciclo di Apprendimento-Ricerca di Auto-Miglioramento: Il documento introduce un framework in cui la ricerca best-first (WA*) genera dati di addestramento di alta qualità (inclusi limiti inferiori e segnali di punti morti) per aggiornare un'euristica appresa, che a sua volta guida ricerche future più efficienti.
2. Generalizzazione Zero-Shot: Le funzioni Q apprese funzionano come politiche generali capaci di risolvere istanze con significativamente più oggetti e obiettivi diversi rispetto a quelli visti durante l'addestramento, senza richiedere ricerca al momento del test in molti casi.
3. Framework Unificato: L'approccio si applica uniformemente a domini diversificati, dagli benchmark della 2023 International Planning Competition (IPC) a puzzle combinatori (Sokoban, The Witness) e al dominio PushWorld, utilizzando una singola architettura e un singolo set di iperparametri.
4. Superiorità rispetto alla Ricerca in Tempo Reale: Il lavoro dimostra che sostituire la ricerca in tempo reale con la ricerca best-first nel ciclo di apprendimento è critico per il successo nei domini di pianificazione con ricompense sparse e alto fattore di diramazione.

Risultati Sperimentali

Gli autori hanno valutato GSP su tre categorie di benchmark:

• Track di Apprendimento IPC 2023:

  • Esecuzione Greed ($GSP_\pi$): Ha raggiunto una copertura del 100% su Blocksworld, Miconic e Spanner, superando baseline come Lifted HER, LAMA e politiche in stile AlphaZero.
  • Guidato dalla Ricerca ($GSP_{WA^*}$): Ha mostrato risultati misti; sebbene abbia migliorato la copertura su puzzle come Sokoban (da 14% a 32%), ha talvolta ridotto la copertura su domini con fattori di diramazione massicci (ad es. Blocksworld) dove l'euristica appresa, sebbene buona per il ranking locale, mancava di calibrazione globale.
  • Scalabilità: Le euristiche addestrate su istanze di Blocksworld con <30 blocchi hanno risolto con successo istanze con 488 blocchi senza ricerca.

• Puzzle Combinatori (Sokoban, The Witness, 24-Puzzle):

  • Su Sokoban, $GSP_{WA^*}$ ha risolto il 100% delle istanze con una media di 207 espansioni, superando significativamente WA* con euristiche standard (3298 espansioni) e DeepCubeA (1050 espansioni).
  • Su The Witness, il metodo ha risolto tutte le istanze, dimostrando il valore dell'addestramento su stati di punto morto.
  • Su 24-Puzzle, il metodo non è riuscito a trovare soluzioni durante l'addestramento, evidenziando che l'approccio richiede la capacità di trovare almeno una soluzione per avviare l'apprendimento, il che è difficile in puzzle fissi estremamente difficili senza euristiche iniziali informate.

• PushWorld:

  • Addestrato sul Livello 0, il modello ha generalizzato al Livello 1. $GSP_{WA^*}$ ha risolto 48/63 istanze del Livello 1 con piani più brevi e circa 30 volte meno espansioni rispetto al pianificatore classico LAMA.
  • Come politica greed, ha superato significativamente le baseline RL senza modello (DQN, PPO).

Significato e Affermazioni

Il documento afferma che la ricerca best-first è un meccanismo di esplorazione superiore per l'apprendimento per rinforzo generalizzato quando il modello di transizione è noto, in particolare nei domini con ricompense sparse dove la ricerca in tempo reale fallisce nel scoprire traiettorie informative.

Il significato principale risiede nella dimostrazione di un ciclo di auto-rafforzamento: la ricerca fornisce i target di addestramento (limiti inferiori, punti morti) che permettono all'euristica di migliorare, e l'euristica migliorata rende le ricerche successive più efficienti. Ciò permette al sistema di apprendere politiche generali in grado di risolvere problemi di dimensioni e complessità arbitrarie senza ricerca, o euristiche altamente efficienti che guidano la ricerca verso soluzioni ottimali.

Gli autori notano modestamente le limitazioni: la funzione Q appresa spesso agisce come un forte meccanismo di ranking locale delle azioni ma può mancare di calibrazione globale su tutto il fronte di ricerca, il che può portare a prestazioni subottimali in WA* su domini con fattori di diramazione estremamente grandi. Suggeriscono che il lavoro futuro potrebbe concentrarsi sul miglioramento della generalizzazione del valore tra gli stati e sulla combinazione della ricerca best-first con i punti di forza complementari della ricerca in tempo reale e del ridenominamento a posteriori delle esperienze.