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

Resumo Técnico: XDiffuser – Orientação por Gráfico Externo para Planejamento de Difusão de Longo Horizonte

Declaração do Problema
O artigo aborda o desafio do planejamento de movimento offline de longo horizonte para robôs operando em espaços de estado contínuos, dado apenas um conjunto de dados de trajetórias de curto horizonte, potencialmente subótimas. Embora planejadores baseados em difusão (por exemplo, Diffuser) ofereçam uma abordagem promissora de "planejamento como inferência" ao amostrar trajetórias coerentes, eles enfrentam dificuldades quando a distribuição de longo horizonte alvo nunca foi observada durante o treinamento.

Métodos de difusão composicional existentes tentam resolver isso costurando segmentos curtos sobrepostos. No entanto, os autores argumentam que confiar exclusivamente na consistência local (garantindo que segmentos adjacentes se sobreponham) é insuficiente para garantir coerência global em cadeias longas. À medida que o horizonte cresce, o processo de inferência torna-se frágil; segmentos localmente plausíveis podem ser mutuamente incompatíveis, levando a falhas na conclusão da tarefa ou na satisfação de restrições. Além disso, abordagens recentes que realizam busca intrínseca (buscando dentro do loop de remoção de ruído) melhoram a coerência, mas incorrem em custos computacionais proibitivos, escalando mal com o comprimento do horizonte e a profundidade da busca.

Metodologia: XDiffuser
Os autores propõem o XDiffuser (Diffuser guiado por busca Extrínseca), que desacopla a coordenação global da geração de trajetória local. Em vez de buscar durante a remoção de ruído, o XDiffuser realiza busca extrínseca fora do processo de difusão para guiar um modelo de difusão composicional pré-treinado. O método consiste em três etapas principais:

1. Construção do Gráfico de Conectividade:

   • Um grafo não direcionado e esparsos $G = (V, E)$ é construído sobre o conjunto de dados offline.
   • Os vértices são estados amostrados do conjunto de dados.
   • As arestas são determinadas usando uma Representação de Distância Temporal (TDR) aprendida, onde a distância euclidiana no espaço latente da TDR reflete a proximidade temporal.
   • Este gráfico serve como um "oráculo de conectividade" leve, capturando alcançabilidade grosseira sem garantir dinâmicas suaves.

2. Busca por Gráfico Extrínseco (Planejamento):

   • No momento do teste, um algoritmo de gráfico específico da tarefa (por exemplo, Dijkstra para alcance de objetivo, planejadores baseados em prioridade para múltiplos agentes, ou solucionadores MILP para inspeção) é executado em $G$.
   • Isso produz um plano de alto nível: uma sequência de pontos de passagem temporais $W = \{(w_m, \hat{t}_m)\}$.
   • O caminho é subamostrado para criar uma estrutura de suporte esparsa, e o tempo é dilatado temporalmente para alinhar com as capacidades de fragmentação do modelo de difusão.

3. Difusão Composicional Guiada por Pontos de Passagem:

   • Um modelo de difusão de curto horizonte pré-treinado gera a trajetória contínua.
   • Os pontos de passagem derivados do gráfico atuam como um termo de energia suave (orientação) em vez de restrições rígidas.
   • Uma janela de orientação triangular $\lambda_m(t)$ é definida ao redor do tempo nominal de cada ponto de passagem. A pontuação de difusão é aumentada pelo gradiente de uma função de custo de ponto de passagem $E_W(\tau)$, que penaliza desvios dos pontos de passagem.
   • Isso viés o processo de remoção de ruído em direção a trajetórias que são localmente plausíveis (segundo o prior de difusão) e globalmente consistentes (segundo o plano do gráfico).

Principais Contribuições

• Busca Extrínseca vs. Intrínseca: O artigo argumenta que a busca extrínseca (fora da remoção de ruído) é um modo de exploração mais eficaz para planejamento de longo horizonte do que a busca intrínseca. Ela transfere o fardo da exploração para algoritmos de gráfico clássicos e eficientes, evitando as avaliações repetidas e caras do modelo de difusão exigidas pelos métodos intrínsecos.
• Modularidade e Escalabilidade: Ao separar a camada de busca da camada generativa, o XDiffuser suporta seleção adaptativa de horizonte (inferida a partir da duração do caminho do gráfico) e permite a integração de diferentes algoritmos de planejamento no momento do teste sem re-treinar o modelo de difusão.
• Generalização para Tarefas Não Vistas: O framework permite que um único modelo de difusão pré-treinado resolva tarefas combinatórias complexas e não vistas (por exemplo, coordenação de múltiplos agentes, inspeção estilo Problema do Caixeiro Viajante) simplesmente alterando o objetivo de alto nível do gráfico.

Resultados Experimentais
Os autores avaliam o XDiffuser na suíte OGBench e em uma simulação personalizada de inspeção de ponte:

• Alcance de Objetivo de Longo Horizonte: No conjunto de dados AntMaze Explore Large (dados de baixa qualidade, passeio aleatório), o XDiffuser alcança uma taxa de sucesso de 98,5%, superando significativamente a linha de base de difusão composicional (CD) base (27%) e outras linhas de base aumentadas por busca como CDGS e C-MCTD. Os ganhos são mais pronunciados em regimes de dados de baixa qualidade onde a costura local falha.
• Encontrar Caminhos para Múltiplos Agentes (MAPF): Em um cenário de múltiplos agentes zero-shot (2–4 agentes) usando um modelo treinado para um único agente, o XDiffuser (com um planejador de prioridade) alcança 58,3% de sucesso com 4 agentes, comparado a 13,3% para o Prioritized CDGS. Ele também demonstra eficiência superior, levando segundos para planejar versus minutos para métodos de busca intrínseca.
• Planejamento de Inspeção: Para inspeção de ponte por drones com até 128 pontos de interesse (POIs), o XDiffuser guiado por MILP alcança >95% de cobertura, enquanto a linha de base de busca intrínseca (IP-CDGS) estagna abaixo de 50% de cobertura, destacando a incapacidade da busca local de resolver restrições combinatórias globais.

Significado e Alegações
O artigo alega que a limitação fundamental do planejamento puro como inferência é que a consistência local sozinha não pode garantir comportamento globalmente coerente quando a distribuição de longo horizonte é não vista. O XDiffuser aborda isso aproveitando as forças de ambos os paradigmas:

1. Busca por Gráfico fornece a estrutura global necessária e o raciocínio combinatório.
2. Difusão fornece a síntese de trajetória suave e dinamicamente viável.

Os autores enfatizam que essa decomposição é eficiente (evitando a escala exponencial de chamadas ao removedor de ruído) e flexível, permitindo a reutilização de um único modelo generativo em diversas tarefas de planejamento complexas que não faziam parte explicitamente da distribuição de treinamento. O trabalho sugere que, para tarefas de longo horizonte, especialmente com dados imperfeitos, uma estratégia "Planeje Primeiro, Difunda Depois" é superior a tentar aprender coerência global puramente através de remoção de ruído iterativa.