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

Technical Summary: XDiffuser – Extrinsic Graph Guidance for Long-Horizon Diffusion Planning

Problem Statement
The paper addresses the challenge of offline long-horizon motion planning for robots operating in continuous state spaces, given only a dataset of short-horizon, potentially suboptimal trajectories. While diffusion-based planners (e.g., Diffuser) offer a promising "planning-as-inference" approach by sampling coherent trajectories, they struggle when the target long-horizon distribution was never observed during training.

Existing compositional diffusion methods attempt to solve this by stitching overlapping short segments. However, the authors argue that relying solely on local consistency (ensuring adjacent segments overlap) is insufficient to guarantee global coherence over long chains. As the horizon grows, the inference process becomes brittle; locally plausible segments may be mutually incompatible, leading to failures in task completion or constraint satisfaction. Furthermore, recent approaches that perform intrinsic search (searching inside the denoising loop) improve coherence but incur prohibitive computational costs, scaling poorly with horizon length and search depth.

Methodology: XDiffuser
The authors propose XDiffuser (eXtrinsic search-guided Diffuser), which decouples global coordination from local trajectory generation. Instead of searching during denoising, XDiffuser performs extrinsic search outside the diffusion process to guide a pretrained compositional diffusion model. The method consists of three main stages:

1. Connectivity Graph Construction:

   • A sparse, undirected graph $G = (V, E)$ is constructed over the offline dataset.
   • Vertices are sampled states from the dataset.
   • Edges are determined using a learned Temporal Distance Representation (TDR), where Euclidean distance in the latent TDR space reflects temporal proximity.
   • This graph serves as a lightweight "connectivity oracle," capturing coarse reachability without guaranteeing smooth dynamics.

2. Extrinsic Graph Search (Planning):

   • At test time, a task-specific graph algorithm (e.g., Dijkstra for goal-reaching, priority-based planners for multi-agent, or MILP solvers for inspection) is executed on $G$.
   • This produces a high-level plan: a sequence of temporal waypoints $W = \{(w_m, \hat{t}_m)\}$.
   • The path is downsampled to create a sparse scaffold, and the timing is temporally dilated to align with the diffusion model's chunking capabilities.

3. Waypoint-Guided Compositional Diffusion:

   • A pretrained short-horizon diffusion model generates the continuous trajectory.
   • The graph-derived waypoints act as a soft energy term (guidance) rather than hard constraints.
   • A triangular guidance window $\lambda_m(t)$ is defined around each waypoint's nominal time. The diffusion score is augmented by the gradient of a waypoint cost function $E_W(\tau)$, which penalizes deviations from the waypoints.
   • This biases the denoising process toward trajectories that are locally plausible (per the diffusion prior) and globally consistent (per the graph plan).

Key Contributions

• Extrinsic vs. Intrinsic Search: The paper argues that extrinsic search (outside denoising) is a more effective mode of exploration for long-horizon planning than intrinsic search. It offloads the burden of exploration to classical, efficient graph algorithms, avoiding the repeated, expensive evaluations of the diffusion model required by intrinsic methods.
• Modularity and Scalability: By separating the search layer from the generative layer, XDiffuser supports adaptive horizon selection (inferred from the graph path duration) and allows for the integration of different planning algorithms at test time without retraining the diffusion model.
• Generalization to Unseen Tasks: The framework enables a single pretrained diffusion model to solve complex, unseen combinatorial tasks (e.g., multi-agent coordination, Traveling Salesperson-style inspection) simply by changing the high-level graph objective.

Experimental Results
The authors evaluate XDiffuser on the OGBench suite and a custom bridge inspection simulation:

• Long-Horizon Goal Reaching: On the AntMaze Explore Large dataset (low-quality, random-walk data), XDiffuser achieves a 98.5% success rate, significantly outperforming the base compositional diffusion (CD) baseline (27%) and other search-augmented baselines like CDGS and C-MCTD. The gains are most pronounced in low-quality data regimes where local stitching fails.
• Multi-Agent Path Finding (MAPF): In a zero-shot multi-agent setting (2–4 agents) using a single-agent trained model, XDiffuser (with a priority planner) achieves 58.3% success with 4 agents, compared to 13.3% for Prioritized CDGS. It also demonstrates superior efficiency, taking seconds to plan versus minutes for intrinsic search methods.
• Inspection Planning: For drone inspection of a bridge with up to 128 points of interest (POIs), the MILP-guided XDiffuser achieves >95% coverage, whereas the intrinsic-search baseline (IP-CDGS) plateaus below 50% coverage, highlighting the inability of local search to solve global combinatorial constraints.

Significance and Claims
The paper claims that the fundamental limitation of pure planning-as-inference is that local consistency alone cannot guarantee globally coherent behavior when the long-horizon distribution is unseen. XDiffuser addresses this by leveraging the strengths of both paradigms:

1. Graph Search provides the necessary global structure and combinatorial reasoning.
2. Diffusion provides the smooth, dynamically feasible trajectory synthesis.

The authors emphasize that this decomposition is efficient (avoiding exponential scaling of denoiser calls) and flexible, enabling the reuse of a single generative model across diverse, complex planning tasks that were not explicitly part of the training distribution. The work suggests that for long-horizon tasks, especially with imperfect data, a "Plan First, Diffuse Later" strategy is superior to attempting to learn global coherence purely through iterative denoising.