Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning

Riepilogo Tecnico: XDiffuser – Guida Esterna su Grafo per la Pianificazione Diffusiva a Orizzonte Lungo

Enunciato del Problema
Il documento affronta la sfida della pianificazione del movimento offline a orizzonte lungo per robot che operano in spazi di stato continui, disponendo solo di un dataset di traiettorie a orizzonte breve, potenzialmente subottimali. Sebbene i pianificatori basati sulla diffusione (ad esempio, Diffuser) offrano un approccio promettente di "pianificazione come inferenza" campionando traiettorie coerenti, incontrano difficoltà quando la distribuzione target a orizzonte lungo non è mai stata osservata durante l'addestramento.

I metodi di diffusione compositiva esistenti tentano di risolvere questo problema assemblando segmenti brevi sovrapposti. Tuttavia, gli autori sostengono che fare affidamento esclusivamente sulla coerenza locale (assicurando che i segmenti adiacenti si sovrappongano) è insufficiente a garantire la coerenza globale su catene lunghe. All'aumentare dell'orizzonte, il processo di inferenza diventa fragile; segmenti localmente plausibili possono risultare mutualmente incompatibili, portando a fallimenti nel completamento del compito o nel rispetto dei vincoli. Inoltre, gli approcci recenti che eseguono una ricerca intrinseca (ricerca all'interno del ciclo di denoising) migliorano la coerenza ma comportano costi computazionali proibitivi, scalando male con la lunghezza dell'orizzonte e la profondità della ricerca.

Metodologia: XDiffuser
Gli autori propongono XDiffuser (Diffuser guidato da ricerca estrinseca), che disaccoppia il coordinamento globale dalla generazione locale della traiettoria. Invece di cercare durante il denoising, XDiffuser esegue una ricerca estrinseca al di fuori del processo di diffusione per guidare un modello di diffusione compositiva preaddestrato. Il metodo consta di tre fasi principali:

1. Costruzione del Grafo di Connettività:

   • Viene costruito un grafo non orientato e sparso $G = (V, E)$ sul dataset offline.
   • I vertici sono stati campionati dal dataset.
   • Gli archi sono determinati utilizzando una Rappresentazione della Distanza Temporale (TDR) appresa, dove la distanza euclidea nello spazio latente TDR riflette la vicinanza temporale.
   • Questo grafo funge da "oracolo di connettività" leggero, catturando la raggiungibilità approssimativa senza garantire dinamiche fluide.

2. Ricerca su Grafo Esterna (Pianificazione):

   • Al momento del test, viene eseguito su $G$ un algoritmo di grafo specifico per il compito (ad esempio, Dijkstra per il raggiungimento dell'obiettivo, pianificatori basati su priorità per sistemi multi-agente, o risolutori MILP per l'ispezione).
   • Ciò produce un piano di alto livello: una sequenza di waypoint temporali $W = \{(w_m, \hat{t}_m)\}$.
   • Il percorso viene sottocampionato per creare un'impalcatura sparsa, e la tempistica viene dilatata temporalmente per allinearsi alle capacità di suddivisione in blocchi del modello di diffusione.

3. Diffusione Compositiva Guidata da Waypoint:

   • Un modello di diffusione a orizzonte breve preaddestrato genera la traiettoria continua.
   • I waypoint derivati dal grafo agiscono come un termine di energia morbido (guida) piuttosto che come vincoli rigidi.
   • Viene definito una finestra di guida triangolare $\lambda_m(t)$ attorno al tempo nominale di ciascun waypoint. Il punteggio di diffusione è aumentato dal gradiente di una funzione di costo dei waypoint $E_W(\tau)$, che penalizza le deviazioni dai waypoint.
   • Ciò spinge il processo di denoising verso traiettorie che sono localmente plausibili (secondo il prior di diffusione) e globalmente coerenti (secondo il piano del grafo).

Contributi Chiave

• Ricerca Estrinseca vs Intrinseca: Il documento sostiene che la ricerca estrinseca (fuori dal denoising) è una modalità di esplorazione più efficace per la pianificazione a orizzonte lungo rispetto alla ricerca intrinseca. Scarica l'onere dell'esplorazione su algoritmi di grafo classici ed efficienti, evitando le valutazioni ripetute e costose del modello di diffusione richieste dai metodi intrinseci.
• Modularità e Scalabilità: Separando il livello di ricerca dal livello generativo, XDiffuser supporta la selezione adattiva dell'orizzonte (inferita dalla durata del percorso del grafo) e permette l'integrazione di diversi algoritmi di pianificazione al momento del test senza riaddestrare il modello di diffusione.
• Generalizzazione a Compiti Non Visti: Il framework permette a un singolo modello di diffusione preaddestrato di risolvere compiti combinatori complessi e non visti (ad esempio, coordinamento multi-agente, ispezione di tipo Traveling Salesperson) semplicemente modificando l'obiettivo del grafo di alto livello.

Risultati Sperimentali
Gli autori valutano XDiffuser sulla suite OGBench e su una simulazione personalizzata di ispezione di ponti:

• Raggiungimento dell'Obiettivo a Orizzonte Lungo: Sul dataset AntMaze Explore Large (dati casuali di bassa qualità), XDiffuser ottiene un tasso di successo del 98,5%, superando significativamente la linea di base della diffusione compositiva (CD) di base (27%) e altre linee di base potenziate dalla ricerca come CDGS e C-MCTD. I guadagni sono più pronunciati nei regimi di dati di bassa qualità dove l'assemblaggio locale fallisce.
• Ricerca di Percorsi Multi-Agente (MAPF): In un setting multi-agente zero-shot (2–4 agenti) utilizzando un modello addestrato su un singolo agente, XDiffuser (con un pianificatore a priorità) ottiene un successo del 58,3% con 4 agenti, rispetto al 13,3% di Prioritized CDGS. Dimostra anche un'efficienza superiore, richiedendo secondi per pianificare contro i minuti dei metodi di ricerca intrinseca.
• Pianificazione dell'Ispezione: Per l'ispezione di un ponte da parte di droni con fino a 128 punti di interesse (POI), XDiffuser guidato da MILP raggiunge una copertura >95%, mentre la linea di base con ricerca intrinseca (IP-CDGS) si stabilizza sotto il 50% di copertura, evidenziando l'incapacità della ricerca locale di risolvere vincoli combinatori globali.

Significato e Affermazioni
Il documento afferma che il limite fondamentale della pura pianificazione come inferenza è che la sola coerenza locale non può garantire un comportamento globalmente coerente quando la distribuzione a orizzonte lungo non è stata vista. XDiffuser affronta questo problema sfruttando i punti di forza di entrambi i paradigmi:

1. La Ricerca su Grafo fornisce la struttura globale necessaria e il ragionamento combinatorio.
2. La Diffusione fornisce la sintesi di traiettorie fluide e dinamicamente fattibili.

Gli autori sottolineano che questa decomposizione è efficiente (evitando la scalabilità esponenziale delle chiamate al denoiser) e flessibile, permettendo il riutilizzo di un singolo modello generativo su compiti di pianificazione diversi e complessi che non facevano parte esplicitamente della distribuzione di addestramento. Il lavoro suggerisce che per compiti a orizzonte lungo, specialmente con dati imperfetti, una strategia "Pianifica Prima, Diffondi Dopo" è superiore al tentativo di apprendere la coerenza globale puramente attraverso il denoising iterativo.