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

Resumen Técnico: XDiffuser – Guía de Grafos Externa para Planificación de Difusión de Largo Alcance

Enunciado del Problema
El artículo aborda el desafío de la planificación de movimiento de largo alcance fuera de línea para robots que operan en espacios de estado continuos, dado únicamente un conjunto de datos de trayectorias de corto alcance, potencialmente subóptimas. Si bien los planificadores basados en difusión (por ejemplo, Diffuser) ofrecen un enfoque prometedor de "planificación como inferencia" mediante el muestreo de trayectorias coherentes, tienen dificultades cuando la distribución objetivo de largo alcance nunca fue observada durante el entrenamiento.

Los métodos de difusión composicional existentes intentan resolver esto uniendo segmentos cortos superpuestos. Sin embargo, los autores argumentan que confiar únicamente en la consistencia local (asegurando que los segmentos adyacentes se superpongan) es insuficiente para garantizar la coherencia global en cadenas largas. A medida que aumenta el horizonte, el proceso de inferencia se vuelve frágil; los segmentos localmente plausibles pueden ser mutuamente incompatibles, lo que lleva a fallos en la finalización de la tarea o en el cumplimiento de restricciones. Además, los enfoques recientes que realizan una búsqueda intrínseca (buscando dentro del bucle de eliminación de ruido) mejoran la coherencia pero incurren en costos computacionales prohibitivos, escalando mal con la longitud del horizonte y la profundidad de la búsqueda.

Metodología: XDiffuser
Los autores proponen XDiffuser (Diffuser guiado por búsqueda extrínseca), que desacopla la coordinación global de la generación de trayectorias locales. En lugar de buscar durante la eliminación de ruido, XDiffuser realiza una búsqueda extrínseca fuera del proceso de difusión para guiar un modelo de difusión composicional preentrenado. El método consta de tres etapas principales:

1. Construcción del Grafo de Conectividad:

   • Se construye un grafo no dirigido y disperso $G = (V, E)$ sobre el conjunto de datos fuera de línea.
   • Los vértices son estados muestreados del conjunto de datos.
   • Las aristas se determinan utilizando una Representación de Distancia Temporal (TDR) aprendida, donde la distancia euclidiana en el espacio latente TDR refleja la proximidad temporal.
   • Este grafo sirve como un "oráculo de conectividad" ligero, capturando la alcanzabilidad gruesa sin garantizar dinámicas suaves.

2. Búsqueda en Grafo Externa (Planificación):

   • En el momento de prueba, se ejecuta un algoritmo de grafo específico de la tarea (por ejemplo, Dijkstra para alcanzar objetivos, planificadores basados en prioridades para múltiples agentes, o solucionadores MILP para inspección) sobre $G$.
   • Esto produce un plan de alto nivel: una secuencia de puntos de paso temporales $W = \{(w_m, \hat{t}_m)\}$.
   • La ruta se submuestrea para crear un andamio disperso, y la temporización se dilata temporalmente para alinearse con las capacidades de fragmentación del modelo de difusión.

3. Difusión Composicional Guiada por Puntos de Paso:

   • Un modelo de difusión de corto alcance preentrenado genera la trayectoria continua.
   • Los puntos de paso derivados del grafo actúan como un término de energía suave (guía) en lugar de restricciones duras.
   • Se define una ventana de guía triangular $\lambda_m(t)$ alrededor del tiempo nominal de cada punto de paso. La puntuación de difusión se aumenta mediante el gradiente de una función de costo de punto de paso $E_W(\tau)$, que penaliza las desviaciones de los puntos de paso.
   • Esto sesga el proceso de eliminación de ruido hacia trayectorias que son localmente plausibles (según el prior de difusión) y globalmente consistentes (según el plan del grafo).

Contribuciones Clave

• Búsqueda Externa vs. Intrínseca: El artículo argumenta que la búsqueda extrínseca (fuera de la eliminación de ruido) es un modo de exploración más efectivo para la planificación de largo alcance que la búsqueda intrínseca. Descarga la carga de la exploración a algoritmos de grafos clásicos y eficientes, evitando las evaluaciones repetidas y costosas del modelo de difusión requeridas por los métodos intrínsecos.
• Modularidad y Escalabilidad: Al separar la capa de búsqueda de la capa generativa, XDiffuser soporta la selección adaptativa del horizonte (inferida de la duración del camino del grafo) y permite la integración de diferentes algoritmos de planificación en el momento de prueba sin reentrenar el modelo de difusión.
• Generalización a Tareas No Vistas: El marco permite que un único modelo de difusión preentrenado resuelva tareas combinatorias complejas y no vistas (por ejemplo, coordinación de múltiples agentes, inspección estilo Viajante de Comercio) simplemente cambiando el objetivo de alto nivel del grafo.

Resultados Experimentales
Los autores evalúan XDiffuser en la suite OGBench y una simulación personalizada de inspección de puentes:

• Alcanzamiento de Objetivos de Largo Alcance: En el conjunto de datos AntMaze Explore Large (datos de caminata aleatoria de baja calidad), XDiffuser logra una tasa de éxito del 98.5%, superando significativamente la línea base de difusión composicional (CD) base (27%) y otras líneas base aumentadas con búsqueda como CDGS y C-MCTD. Las ganancias son más pronunciadas en regímenes de datos de baja calidad donde la unión local falla.
• Búsqueda de Ruta para Múltiples Agentes (MAPF): En un entorno de múltiples agentes sin entrenamiento previo (2–4 agentes) utilizando un modelo entrenado para un solo agente, XDiffuser (con un planificador de prioridades) logra un 58.3% de éxito con 4 agentes, en comparación con el 13.3% de Prioritized CDGS. También demuestra una eficiencia superior, tomando segundos para planificar frente a minutos para los métodos de búsqueda intrínseca.
• Planificación de Inspección: Para la inspección de un puente por drones con hasta 128 puntos de interés (POI), XDiffuser guiado por MILP logra una cobertura >95%, mientras que la línea base de búsqueda intrínseca (IP-CDGS) se estanca por debajo del 50% de cobertura, destacando la incapacidad de la búsqueda local para resolver restricciones combinatorias globales.

Significado y Afirmaciones
El artículo afirma que la limitación fundamental de la planificación pura como inferencia es que la consistencia local por sí sola no puede garantizar un comportamiento globalmente coherente cuando la distribución de largo alcance no ha sido vista. XDiffuser aborda esto aprovechando las fortalezas de ambos paradigmas:

1. La Búsqueda en Grafo proporciona la estructura global necesaria y el razonamiento combinatorio.
2. La Difusión proporciona la síntesis de trayectorias suaves y dinámicamente factibles.

Los autores enfatizan que esta descomposición es eficiente (evitando el escalado exponencial de las llamadas al eliminador de ruido) y flexible, permitiendo la reutilización de un único modelo generativo en diversas tareas de planificación complejas que no formaban parte explícitamente de la distribución de entrenamiento. El trabajo sugiere que para tareas de largo alcance, especialmente con datos imperfectos, una estrategia de "Planificar Primero, Difundir Después" es superior a intentar aprender la coherencia global puramente a través de la eliminación de ruido iterativa.