Trainingsfreier Diffusionsplaner TFDP setzt auf analytische lokale Scores für Multi-Agenten-Pfade

\tl_set:Ne\bracketeq

bracketeq \tl_set:Ne\boxeqboxeq

Abstract

Motion planning requires trajectories that are smooth, goal-directed, and collision-free in environments with complex geometric constraints. Recent diffusion-based planners have shown that trajectory generation can be cast as iterative denoising, which has opened the doors to learning-based approaches that can handle multi-modal trajectory distributions and refine entire trajectories. However, such planners require training on large collections of feasible trajectories, rendering them map-specific, and difficult to deploy when high-quality demonstrations are unavailable. This paper introduces a training-free diffusion-based motion planner that replaces learned global trajectory scores with analytical local scores derived from obstacle, smoothness, velocity, and inter-agent feasibility terms. The proposed idea relies on a key observation: the trajectory score can be approximated from local interactions between neighboring waypoints and nearby constraints. This structure exploitation yields a decomposed denoising procedure that retains the optimization structure of classical optimization methods while inheriting the iterative refinement behavior of diffusion models. Experiments on a large collection of complex environments on multi-agent planning tasks show that the proposed analytical score produces smooth and feasible trajectories within very limited computational costs, for example in generating feasible paths for 300 agents in environments with 100 obstacles in under 6 seconds, while avoiding the data requirements of learned diffusion planners.

1 Introduction

Motion planning is a fundamental problem in robotics and autonomous systems, where the goal is to compute trajectories that move a system from an initial state to a target state while avoiding collisions with obstacles (LaValle, 2006). In multi-agent settings, this problem becomes substantially more challenging: each robot must satisfy its own motion and safety constraints while also avoiding time-dependent collisions with other agents (Sharon et al., 2015; Ma et al., 2018). The spatio-temporal coupling and nonlinearity of these constraints make multi-agent path planning difficult to solve efficiently, especially as the number of agents and obstacles increases (Liang et al., 2025).

Sampling-based planners provide strong completeness properties under suitable assumptions and have been widely used for high-dimensional planning problems. However, they often produce paths in a coarse configuration space that require additional smoothing and can become inefficient in narrow passages or crawded spaces (Kuffner and LaValle, 2000; LaValle, 2006). Optimization-based planners instead formulate motion planning as continuous trajectory optimization, making it possible to incorporate obstacle avoidance, smoothness, and kinematic constraints directly into the objective or feasible set (Kalakrishnan et al., 2011; Mukadam et al., 2018b). However, these methods are often sensitive to initialization and can become expensive in multi-agent settings because collision constraints couple many agents across time. More recently, diffusion models have shown promising results for motion planning by casting trajectory generation as an iterative denoising process that refines noise into trajectories (Liang et al., 2026a; Shaoul et al., 2025). This perspective is attractive because diffusion models refine entire trajectories rather than committing to one waypoint at a time, and can represent multimodal distributions over possible plans (Carvalho et al., 2023). The key challenge, however, is that existing diffusion planners require learning a neural score model over high-dimensional trajectory distributions. This makes them expensive to train, dependent on large collections of feasible demonstrations, and often map- or distribution-specific. Moreover, learned diffusion planners may still fail to enforce safety constraints, a critical limitation for robotic planning (Liang et al., 2025). Projection-based refinement can improve constraint satisfaction, but it introduces additional computational cost (Liang et al., 2026a; Liang et al., 2025).

To address these challenges, this paper develops a training-free diffusion-based planner with fully analytical local scores. The key idea is based on the observation that trajectory refinement has a strong locality of influence (Pan et al., 2012). Although the exact score of a full trajectory distribution can be globally coupled, the update of an individual waypoint is dominated by local temporal and spatial interactions: neighboring waypoints determine smoothness and velocity consistency, nearby obstacles determine collision avoidance, and nearby agents at the same time determine inter-robot separation (Mukadam et al., 2018a; Zucker et al., 2013), as illustrated in Figure 1(b). Motivated by this structure, we introduce a decomposed local score formulation that constructs an analytical score surrogate directly from the planning constraints, rather than learning a neural approximation to the score of a high-dimensional distribution over complete trajectories. The resulting planner starts from a coarse trajectory initialization with fixed endpoints (Figure 1(a)) and repeatedly applies analytical denoising updates under a decreasing noise schedule (Figure 1(c)). Because each update depends only on local trajectory neighborhoods, nearby obstacles, and nearby agents, the method avoids dataset collection and neural-network training while remaining scalable to large multi-agent scenes. Contributions. The paper makes the following contributions: (1) It introduces a training-free diffusion planning framework that replaces learned global trajectory scores with analytical score surrogates derived from the structure of the motion planning problem. (2) It develops a decomposed local score formulation in which each waypoint is refined using smoothness, obstacle-avoidance, velocity-feasibility, and inter-agent collision-avoidance terms. (3) It demonstrates across multi-agent path planning benchmarks that the proposed planner achieves high feasibility and computational efficiency, obtaining high success on standard test configurations and scaling to scenes with 300 agents and 100 obstacles in just a few seconds.

2 Related Work

Multi-agent path planning has a long history in robotics, with early methods largely built around sampling-based and optimization-based approaches. Sampling-based planners, approximate the feasible configuration space by drawing samples and connecting them through local steering procedures (Kavraki et al., 1996; Kuffner and LaValle, 2000; LaValle, 2006). These can scale to high-dimensional spaces better than exhaustive search methods, however, they often produce piecewise or fragmented paths that require post-processing, and their performance can degrade in narrow passages or settings where continuous kinodynamic constraints must be enforced along the entire trajectory. A complementary line of work formulates motion planning as trajectory optimization problems (Augugliaro et al., 2012; Park et al., 2020; Mellinger et al., 2012). This gives these methods a direct mechanism for incorporating feasibility requirements, but the resulting optimization problems become increasingly difficult in multi-agent settings, where collision constraints couple agents across both space and time. To improve computational tractability, several optimization-based planners replace hard feasibility constraints with differentiable costs or penalty terms (Ratliff et al., 2009; Kalakrishnan et al., 2011; Mukadam et al., 2018b), but they are often sensitive to initialization and can struggle in environments with many obstacles or agents. In contrast, our method formulates planning as an iterative denoising process driven by analytical local scores, avoiding dense state-space exploration while also avoiding repeated global trajectory optimization. Score-based Generative Models for Motion Planning. Recent advancements in generative models offer have opened new avenues for solving motion planning problems by treating feasible trajectories as samples from a distribution and generating them through iterative denoising (Song et al., 2020). Diffusion planners are attractive because they refine whole trajectories at once and can represent multimodal plans in dense environments (Carvalho et al., 2023; Shaoul et al., 2025; Luo et al., 2024). However, they typically require learning a neural score over high-dimensional trajectory distributions, which depends on large collections of feasible demonstrations and does not guarantee constraint satisfaction. To improve feasibility, recent work has added gradient-based guidance during sampling, control barrier and Lyapunov functions, or projection-based refinement after denoising (Carvalho et al., 2023; Mizuta and Leung, 2024; Shaoul et al., 2025; Luo et al., 2024; Liang et al., 2026a; Liang et al., 2025; Christopher et al., 2024; Liang et al., 2026b). These Both retain learned generative models; TFDP constructs its refinement field directly from smoothness and feasibility factors.

The method proposed in this work, instead, replaces the learned global score with analytical local score components derived directly from smoothness, velocity, obstacle-avoidance, and collision constraints. This yields a training-free planner that preserves the iterative refinement behavior of diffusion models while making denoising updates fast and tied to the geometry of the environment.

3 Preliminaries

Multi-agent path planning. Multi-agent path planning involves computing collision-free trajectories for multiple agents navigating a shared environment from designated start positions to goal states. Let \mathcal{A}=\{a_{1},\dots,a_{N_{a}}\} be a set of N_{a} robots that move in a bounded, planar workspace \mathcal{W}\subset\mathbb{R}^{2} containing a set of static obstacles \mathcal{O}=\{o_{1},\dots,o_{N_{o}}\}. The free configuration space is defined as the set of all points in the workspace that are not occupied by obstacles: \mathcal{C}_{\mathrm{f}}:=\mathcal{W}\setminus\bigl(\bigcup_{o\in\mathcal{O}}o\bigr). Each robot a_{i} is modeled as a disk of radius r_{i}>0 and is characterized at discrete time steps h\in\{0,\ldots,H\} by a 2-D position \pi_{i}^{h}=(x_{i}^{h},y_{i}^{h})\in\mathcal{C}_{\mathrm{f}}. A trajectory for robot a_{i} is the sequence \bm{\pi}_{i}:=(\pi_{i}^{0},\pi_{i}^{1},\dots,\pi_{i}^{H}).

The goal of multi-agent path planning is to compute a set of trajectories \boldsymbol{\Pi}=\{\boldsymbol{\pi}_{1},\boldsymbol{\pi}_{2},\ldots,\boldsymbol{\pi}_{N_{a}}\} such that each robot starts at its designated start position and reaches its target position while avoiding collisions with obstacles and other agents. For every time index h we require

\displaystyle\pi_{i}^{h} \\ \displaystyle\in\mathcal{C}_{\mathrm{f}}, \\ \displaystyle\forall i, \\ \displaystyle\|\pi_{i}^{h}-\pi_{j}^{h}\|_{2} \\ \displaystyle\geq r_{i}+r_{j}, \\ \displaystyle\forall i<j, \\ \displaystyle\|\pi_{i}^{h+1}-\pi_{i}^{h}\|_{2} \\ \displaystyle\leq v_{\max}\,\Delta t, \\ \displaystyle\forall i,h<H,

where Eq. (1a) enforces obstacle avoidance, Eq. (1b) inter-robot separation, and Eq. (1c) a first-order kinematic bound with time step \Delta t and speed limit v_{\max}.

Diffusion models for motion planning. Score-based diffusion models define a forward noising process and a reverse sampling process (Song et al., 2020). In the forward process, samples from a data distribution are gradually perturbed with Gaussian noise. Let \pi denote a trajectory, and let p_{0}(\pi\mid\mathcal{O},s,g) denote the distribution of feasible trajectories conditioned on the obstacle set \mathcal{O}, start state s, and goal state g. At noise level \sigma, the forward process induces a noise-smoothed distribution p_{\sigma} by \pi_{\sigma}=\pi+\sigma\epsilon, with \epsilon\sim\mathcal{N}(0,I). The reverse process then generates samples by moving noisy trajectories back toward the feasible trajectory distribution. This reverse process is driven by the score function \nabla_{\pi}\log p_{\sigma}(\pi\mid\mathcal{O},s,g), which points in the direction of increasing probability under the noise-smoothed distribution. In learned diffusion planners, feasible trajectories are treated as data samples and used to train a neural network s_{\theta} to approximate this score function (Carvalho et al., 2023; Shaoul et al., 2025; Liang et al., 2025):

s_{\theta}(\pi;\mathcal{O},s,g).\approx\nabla_{\pi}\log p_{\sigma}(\pi\mid\mathcal{O},s,g)

At sampling time, the learned score is used in Langevin dynamics to iteratively refine an initial noisy trajectory, for example through updates of the form

\pi\leftarrow\pi+\epsilon s_{\theta}(\pi;\mathcal{O},s,g)+\sqrt{2\epsilon\tau}\,\xi,\qquad\xi\sim\mathcal{N}(0,I),

with a decreasing noise schedule, step size \epsilon (typically chosen proportional to \sigma^{2}), and optional temperature parameter \tau (Xu et al., 2018). Thus, the learned score determines the direction in which the full trajectory is refined at each denoising step.

Crucially, the score network s_{\theta} is a function of the entire noisy trajectory, since feasibility depends on global trajectory structure, obstacle geometry, and interactions among agents across time. Prior diffusion planners often add guidance terms during sampling to penalize obstacle penetration, inter-agent collisions, or trajectory roughness (Carvalho et al., 2023; Liang et al., 2025; Liang et al., 2026a). However, the underlying model still requires learning a global score over high-dimensional trajectory distributions, which is expensive and depends on access to feasible training trajectories. Next, the paper introduces a method that avoids learning such a global score model altogether.

4 Training-Free Diffusion-based Planning (TFDP)

This section presents Training-Free Diffusion-based Planning (TFDP), a method that performs iterative denoising without a learned score model. The key idea is to replace the unknown global score \nabla_{\pi}\log p_{\sigma}(\pi\mid\mathcal{O},s,g) of the data distribution with the score of an explicitly constructed surrogate target, whose factors are dictated by the locality of the planning problem itself.

4.1 A Surrogate Target Distribution over Trajectories

Rather than learning to approximate the data distribution of feasible trajectories, TFDP constructs a surrogate that exploits the spatio-temporal structure of the path planning problem. The surrogate is a product of four factors, colored in Figure 1(b), that encode smoothness, obstacle avoidance, inter-agent separation, and kinematic feasibility:

p(\pi)\;\propto\;{\color[rgb]{0.0313,0.3438,0.9727}\phi_{\mathrm{prior}}(\pi)}\,{\color[rgb]{0.9961,0.3555,0.0469}\chi_{\mathrm{obs}}(\pi)}\,{\color[rgb]{0.5,0.0977,0.7461}\chi_{\mathrm{agent}}(\pi)}\,{\color[rgb]{0.0234,0.5703,0.4375}\chi_{\mathrm{dyn}}(\pi)},

Specifically, the Gaussian factor

{\color[rgb]{0.0313,0.3438,0.9727}\phi_{\mathrm{prior}}(\pi)}\;=\;\exp\!\left(-\tfrac{\lambda_{\mathrm{sm}}}{2}\sum_{i}\sum_{h=1}^{H-1}\bigl\|\pi^{h+1}_{i}-2\pi^{h}_{i}+\pi^{h-1}_{i}\bigr\|^{2}\right),

penalizes sharp bends through a Gaussian finite-difference smoothness prior, derived from locality of motion and from the desire of producing smooth trajectories. The other three indicator factors are

\displaystyle{\color[rgb]{0.9961,0.3555,0.0469}\chi_{\mathrm{obs}}(\pi)} \\ \displaystyle=\prod_{i}\prod_{h=1}^{H}\mathbb{I}\!\left[\,\pi^{h}_{i}\in\mathcal{C}_{f}\,\right], \\ \displaystyle{\color[rgb]{0.5,0.0977,0.7461}\chi_{\mathrm{agent}}(\pi)} \\ \displaystyle=\prod_{i<j}\prod_{h=1}^{H}\mathbb{I}\!\left[\,\bigl\|\pi^{h}_{i}-\pi^{h}_{j}\bigr\|\geq r_{i}+r_{j}\,\right], \\ \displaystyle{\color[rgb]{0.0234,0.5703,0.4375}\chi_{\mathrm{dyn}}(\pi)} \\ \displaystyle=\prod_{i}\prod_{h=1}^{H-1}\mathbb{I}\!\left[\,\bigl\|\pi^{h+1}_{i}-\pi^{h}_{i}\bigr\|\leq v_{\max}\Delta t\,\right].

The three indicator factors are ordered to match the feasibility constraints: Eq. (5a) corresponds to obstacle avoidance in Eq. (1a), Eq. (5b) corresponds to inter-robot separation in Eq. (1b), and Eq. (5c) corresponds to the kinematic bound in Eq. (1c). The surrogate (3) deliberately discards information about which feasible trajectories are likely under demonstration data, retaining only which trajectories are feasible and smooth. This is the price paid for being training-free, but it is also a virtue: the surrogate is entirely determined by the problem geometry and the smoothness weight, so it can be evaluated without any learned component. The next step is to show how to compute its score in closed form.

Then, for each waypoint \pi_{i}^{h} of agent a, we approximate the full score at noise level \sigma by

\displaystyle\nabla_{\pi_{i}^{h}}\log p_{\sigma}(\pi\mid\mathcal{O})\;\approx{} \\ \displaystyle\color[rgb]{0.0313,0.3438,0.9727}{\displaystyle s_{\mathrm{prior}}(\pi_{i}^{h};\,\pi_{i}^{h-1},\pi_{i}^{h+1})}+{\color[rgb]{0.9961,0.3555,0.0469}s_{\mathrm{obs}}(\pi_{i}^{h};\,\mathcal{O})} \\ \displaystyle+{\color[rgb]{0.5,0.0977,0.7461}s_{\mathrm{agent}}(\pi_{i}^{h};\,\pi_{j\neq i}^{h})}+{\color[rgb]{0.0234,0.5703,0.4375}s_{\mathrm{dyn}}(\pi_{i}^{h};\,\pi_{i}^{h-1},\pi_{i}^{h+1})}.

The four terms define the local score (s_{\mathrm{local}} in Figure 1(b)) combining smoothness, agent-obstacle collision avoidance, agent-agent collision avoidance, and dynamic feasibility (i.e., velocity constraints). The approximation removes long-range score dependencies while preserving the terms that dominate local feasibility. Note this decomposition also makes the update interpretable as each waypoint is moved according to the direction described by each multi-agent path planning constraint. We describe the explicit form of the score components in Section 4.2.

The local score decomposition approximates the noisy trajectory score and does not imply exact conditional independence between distant waypoints. For Gaussian trajectory priors with local interactions, zeros in the precision matrix encode conditional independencies, and adding isotropic diffusion noise changes the precision structure. At small noise levels, indirect dependencies between distant variables are higher-order effects relative to the direct neighbor interactions. This motivates using short score windows in low-noise denoising regimes and considering larger windows at higher noise levels. We formalize this intuition next, by showing that the conditional independence structure of a multivariate Gaussian is approximately preserved under diffusion noise. This result is of independent interest and may be useful in other applications of diffusion models.

Theorem 1.

Let x\sim\mathcal{N}(0,\Sigma) be a multivariate normal distribution with covariance \Sigma\in\mathbb{R}^{n\times n} and precision matrix \Omega:=\Sigma^{-1}. Let \{x_{i}\}_{i=1}^{n} denote the components, and consider the associated Markov random field (MRF) where an edge (i,j) is present iff \Omega_{ij}\neq 0. Consider a diffusion process applied to x with noise level t, and let I(x_{i};x_{j}\mid x_{-\{i,j\}}) denote the mutual information between components x_{i} and x_{j}. Then the rate of increase of mutual information at small t is given by

\frac{\mathrm{d}}{\mathrm{d}t}I(x_{i};x_{j}\mid x_{-\{i,j\}})=t\frac{\left|\sum_{k}\Omega_{ik}\Omega_{kj}\right|^{2}}{\Omega_{ii}\Omega_{jj}}.

Consequently, the leading-order contribution to mutual information between x_{i} and x_{j} is governed by length-2 paths in the MRF. Variables separated by longer paths incur dependence only at higher orders in t, and are therefore negligible for sufficiently small t.

The detailed proof is shown in Appendix A.1. Theorem 1 shows that the local independence structures are approximately preserved. This is important for our proposed method because it motivates computing score updates from local trajectory neighborhoods at low noise levels.

4.2 Analytical Score Terms

Now, we provide explicit expressions for s_{{\color[rgb]{0.0313,0.3438,0.9727}\mathrm{prior}},{\color[rgb]{0.9961,0.3555,0.0469}\mathrm{obs}},{\color[rgb]{0.5,0.0977,0.7461}\mathrm{agent}},{\color[rgb]{0.0234,0.5703,0.4375}\mathrm{dyn}}}. We first introduce the constraint set:

\displaystyle\mathcal{C}_{\mathrm{obs}}(\pi_{i}^{h};\mathcal{O}):=\ \\ \displaystyle\mathcal{C}_{\mathrm{f}}, \\ \displaystyle\mathcal{C}_{\mathrm{agent}}(\pi_{i}^{h};\pi_{i\neq j}^{h}):=\ \\ \displaystyle\left\{y\in\mathcal{W}:\|y-\pi_{j}^{h}\|_{2}\geq r_{i}+r_{j},\ \forall j\neq i\right\}, \\ \displaystyle\mathcal{C}_{\mathrm{dyn}}(\pi_{i}^{h};\pi_{i}^{h+1},\pi_{i}^{h-1}):=\ \\ \displaystyle\left\{y\in\mathcal{W}:\|y-\pi_{i}^{h-1}\|_{2}\leq v_{\max}\Delta t,\ \|\pi_{i}^{h+1}-y\|_{2}\leq v_{\max}\Delta t\right\},

where y\in\mathcal{W} denotes a candidate position for the waypoint \pi_{i}^{h}. Using the smoothness factor defined in Equation (4), {\color[rgb]{0.0313,0.3438,0.9727}s_{\mathrm{prior}}}=\nabla\log{\color[rgb]{0.0313,0.3438,0.9727}\phi_{\mathrm{prior}}(\pi)}. For the constraint components, let:

\displaystyle{\color[rgb]{0.9961,0.3555,0.0469}\chi_{\mathrm{obs}}^{\sigma}(\pi_{i}^{h};\mathcal{O})} \\ \displaystyle=K_{\sigma}*\mathcal{C}_{\mathrm{obs}}(\pi_{i}^{h};\mathcal{O}) \\ \displaystyle{\color[rgb]{0.5,0.0977,0.7461}\chi_{\mathrm{agent}}^{\sigma}(\pi_{i}^{h};\pi_{i\neq j}^{h})} \\ \displaystyle=K_{\sigma}*\mathcal{C}_{\mathrm{agent}}(\pi_{i}^{h};\pi_{i\neq j}^{h}) \\ \displaystyle{\color[rgb]{0.0234,0.5703,0.4375}\chi_{\mathrm{dyn}}^{\sigma}(\pi_{i}^{h};\pi_{i}^{h+1},\pi_{i}^{h-1})} \\ \displaystyle=K_{\sigma}*\mathcal{C}_{\mathrm{dyn}}(\pi_{i}^{h};\pi_{i}^{h+1},\pi_{i}^{h-1})

be the constraint indicators convolved with Gaussians; i.e., a closed-form solution to the forward diffusion process of a uniform distribution over the corresponding feasible set, up to a constant. Then we use s_{{\color[rgb]{0.9961,0.3555,0.0469}\mathrm{obs}},{\color[rgb]{0.5,0.0977,0.7461}\mathrm{agent}},{\color[rgb]{0.0234,0.5703,0.4375}\mathrm{dyn}}}(\cdot)=\nabla\log\chi_{{\color[rgb]{0.9961,0.3555,0.0469}\mathrm{obs}},{\color[rgb]{0.5,0.0977,0.7461}\mathrm{agent}},{\color[rgb]{0.0234,0.5703,0.4375}\mathrm{dyn}}}^{\sigma}(\cdot), which pull the sample towards the feasible region with increasing strength as \sigma\to 0. Unlike guidance terms, the constraint terms \nabla\log{\color[rgb]{0.9961,0.3555,0.0469}\chi^{\sigma}_{\mathrm{obs}}} are explicitly tied to the probability that a noisy waypoint is feasible. Computing these terms directly requires a convolution integral. For a feasible set \mathcal{C}_{\mathrm{free}} of any arbitrary constraint,

\chi^{\sigma}_{\mathrm{constraint}}(\pi_{i}^{h})=\int_{\mathcal{C}_{\mathrm{free}}}\mathcal{N}(\pi_{i}^{h};x,\sigma^{2}I)\mathop{}\!\mathrm{d}x

We provide closed-form solutions for circular and rectangular feasible sets in Appendix A.2, A.3, and A.4, respectively, however, closed-form solutions are not available for general, non-convex sets, for which we propose a low-noise approximation that avoids computing the convolution integral directly.

Theorem 2 (Low-noise score approximation and projection).

Let p_{\sigma}(x) denote a Gaussian-smoothed density with noise scale \sigma>0, and let \Pi(x) denote the Euclidean projection of x onto a feasible set \mathcal{C}_{\mathrm{f}}. Then, in the limit as \sigma\to 0, the score function satisfies the first-order approximation

\sigma^{2}\nabla\log p_{\sigma}(x)\approx\bigl(\Pi(x)-x\bigr).

Thus, the score is proportional (up to a factor of \sigma^{2}) to the negative gradient of the squared distance to the feasible set. In particular, letting d(x,\mathcal{C}_{\mathrm{f}}) denote the Euclidean distance to \mathcal{C}_{\mathrm{f}}, we have

\nabla\left(\tfrac{1}{2}d(x,\mathcal{C}_{\mathrm{f}})^{2}\right)=x-\Pi(x),

which implies that the score direction aligns with the gradient of \frac{1}{2}d(x,\mathcal{C}_{\mathrm{f}})^{2} up to scaling.

See Appendix A.5 for the proof. Note that, due to the smoothing effect of the Gaussian convolution, the score function is nonzero even for points inside the feasible region, for small distances. Therefore, we also include a quadratically-scaled gradient such that the vertex of the parabola is at distance \sigma from the obstacle boundary. This motivates a general-purpose constraint satisfaction score function, constraining \pi_{i}^{h}\in\mathcal{C}\to\pi_{i}^{h}\in\mathcal{C}_{\mathrm{f}}\,\forall\,i,h:

\psi^{\sigma}(\pi_{i}^{h},\mathcal{C}_{f})=\nabla d(\pi_{i}^{h},\mathcal{C}_{f})\cdot\begin{cases}\,d(\pi_{i}^{h},\mathcal{C}_{f})+\dfrac{\sigma}{2}&\text{if }d(\pi_{i}^{h},\mathcal{C}_{f})>0,\\[8.0pt]
\,\nicefrac{{1}}{{2\sigma}}\!\left(d(\pi_{i}^{h},\mathcal{C}_{f})+\sigma\right)^{2}&\text{if }d(\pi_{i}^{h},\mathcal{C}_{f})\in(-\sigma,\,0],\\[8.0pt]
\,0&\text{otherwise.}\end{cases}

Where d(\pi_{i}^{h},\mathcal{C}_{\mathrm{f}}) is a signed distance function (being the negative distance to \mathcal{C}\setminus\mathcal{C}_{\mathrm{f}} if \pi_{i}^{h}\in\mathcal{C}_{\mathrm{f}}). We instantiate \psi^{\sigma} on two feasible sets derived from Eqs. (8b)–(8c): the static obstacle-free region \mathcal{C}_{f}^{\mathrm{obs}}(\pi_{i}^{h}):=\mathcal{C}_{\mathrm{obs}}(\pi_{i}^{h};\mathcal{O})=\mathcal{C}_{f}, and the agent-separation feasible region \mathcal{C}_{f}^{\mathrm{agent}}(\pi_{i}^{h};\,\pi_{j\neq i}^{h}):=\mathcal{C}_{\mathrm{agent}}(\pi_{i}^{h};\,\pi_{j\neq i}^{h}). The corresponding constraint score terms used in Eq. (6) are

\displaystyle\nabla\log{\color[rgb]{0.9961,0.3555,0.0469}\chi_{\mathrm{obs}}^{\sigma}(\pi_{i}^{h})} \\ \displaystyle=\tfrac{1}{\sigma^{2}}\,\psi^{\sigma}\!\left(\pi_{i}^{h},\,\mathcal{C}_{f}^{\mathrm{obs}}\right), \\ \displaystyle\nabla\log{\color[rgb]{0.5,0.0977,0.7461}\chi_{\mathrm{agent}}^{\sigma}(\pi_{i}^{h})} \\ \displaystyle=\tfrac{1}{\sigma^{2}}\,\psi^{\sigma}\!\left(\pi_{i}^{h},\,\mathcal{C}_{f}^{\mathrm{agent}}\right).

The complete procedure is summarized in Algorithm 1. An illustration of the true score function, our approximation, and the gradient given by SDF guidance is shown in Figure 2. Notice that the score pushes agents out of obstacles in proportion to their penetration depth. It also pushes agents apart only when their uncertainty neighborhoods overlap or approach collision. This gives a continuous analogue of conflict resolution in MAPF, but without constructing a discrete high-level search tree. We encode velocity constraints through a soft penalty:

U_{\mathrm{dyn}}(\pi)=\lambda_{\mathrm{vel}}\sum_{i}\sum_{h=0}^{H-1}\phi\left(\|\pi_{i}^{h}-\pi_{i}^{h+1}\|-v_{\max}\right),

where \phi(r)=\max\{0,r\}^{2} or a smooth approximation of the squared hinge. This discourages pairwise step displacements that exceed the velocity limit. We then set {\color[rgb]{0.0234,0.5703,0.4375}s_{\mathrm{dyn}}(\pi_{i}^{h})}=-\nabla_{\pi_{i}^{h}}U_{\mathrm{dyn}}(\pi).

5 Experiments

Settings. To evaluate the performance of various multi-agent path planning algorithms, we design two experimental settings targeting different aspects of the problem: 1. Feasibility, Efficiency, Quality: We adopt a recent multi-agent path planning benchmark (Liang et al., 2026a) which includes four representative map types: random maps with varying obstacle densities (basic and dense), and structured maps mimicking real-world environments (room and shelf layouts). For each map type, we consider three robot counts (6, 12, and 18), and evaluate across 25 instances with different configurations. Figure 3 illustrates the benchmark maps and representative 18-robot trajectories found by our method. 2. Scalability: To test scalability, we use a large-scale map containing over 100 heterogeneous obstacles. This setup is challenging and supports scenarios with up to 300 robots, largely beyond what existing diffusion methods handle.

Evaluation Metrics. Different algorithms are empirically evaluated based on Success rate, Running time, and Path Length. The Success rate indicates the proportion of test cases solved without collisions and within the time limit (900 seconds), Running time measures the computational efficiency required to generate a solution, Path Length evaluates the quality of generated trajectories. Competing Methods. Our proposed TFDP is compared against diffusion-based and classical baseline methods: (1) Multi-robot motion planning diffusion (MMD): A method that integrates diffusion models with a classical search-based MAPF algorithm to generate multi-agent trajectories under soft collision constraints (Shaoul et al., 2025). (2) Simultaneous multi-robot motion planning diffusion (SMD): It integrates diffusion models with constrained optimization to generate collision-free trajectories for multi-agent path planning (Liang et al., 2025). (3) Discrete-guided diffusion (DGD): This approach decomposes the original multi-agent path planning problem and leverages MAPF-derived spatiotemporal dependencies to guide diffusion models in generating trajectories that satisfy hard feasibility constraints. (Liang et al., 2026a). (4) Model Predictive Path Integral (MPPI): A classical sampling-based method whose updates admit a score-ascent interpretation (Xue et al., 2024). This connection motivates its use as a baseline: MPPI estimates update directions from sampled perturbations, while TFDP uses analytical approximations to local scores. For MMD, SMD, and DGD, we follow the hyperparameter settings reported in their original papers. For MPPI, we treat the MPPI \sigma the same as diffusion \sigma and use the our approach’s annealed energy landscapes as the optimization objective. For our method, we use 250 Langevin steps, with an exponential noise schedule decreasing from \sigma=0.1 to \sigma=0.0001, and an exponentially annealed temperature from \tau=0.3 to \tau=0.0001. We also exponentially decrease the weight of the kinetic-energy term from 0.5 to 0.001 during sampling. The step size is \eta=0.5.

5.1 Comparison across Methods

Table 1 presents the performance of TFDP and baseline methods across the four benchmark maps. The results show that TFDP consistently achieves a 100\% success rate in all but one configuration, matching or exceeding the success rates of the diffusion baselines. In particular, on Dense with 18 robots, TFDP achieves 96\% success, exceeding DGD’s 76\% and MMD’s 8\%. Compared with DGD, the strongest diffusion baseline in these experiments, TFDP matches success in 8 configurations and improves it in the remaining 4. MMD performs well on Basic but its success rate drops sharply on Dense, Room, and Shelf. SMD reaches 100\% success with 6 robots, but its computational cost limits evaluation to this setting. Appendix A.14 reports 95\% Wilson intervals for TFDP success and \pm 2 standard errors for runtime and path length (Table 21).

In terms of running time, TFDP is significantly faster than all other diffusion-based methods. Across the 12 configurations, TFDP requires 0.18–1.24 seconds, averaging 0.59 seconds, whereas DGD requires 12.2–324.8 seconds, averaging 88.23 seconds. The ratio of mean runtimes is approximately 150\times, with TFDP also achieving higher average success. The difference is especially pronounced on Shelf with 18 robots: TFDP requires 0.84 seconds, versus 324.8 seconds for DGD at 84\% success. MMD and SMD are also substantially slower and do not match TFDP’s combination of feasibility and scalability. MPPI remains slower under the same annealing schedule, even when run on a GPU. Running MPPI on the same CPU as TFDP is slower still, as reported in Appendix A.9 (Table 14).

Finally, TFDP matches or improves DGD’s path length in all 12 configurations and produces strictly shorter paths in 11. On Room and Shelf, these shorter paths accompany comparable feasibility and substantially lower runtime. MMD and SMD sometimes produce shorter paths, but path length must be interpreted jointly with success and evaluation coverage: MMD often fails on cluttered or structured maps, while SMD is evaluated only with 6 robots. TFDP also tends to produce shorter paths than MPPI; the latter’s noisier update is a possible explanation, although this mechanism is not isolated here. Representative 18-robot trajectories appear in Figure 3.

5.2 Ablation Studies and Scalability

To assess the contribution of the analytical scores, we replace them with CHOMP-style SDF penalty guidance while keeping TFDP’s denoising schedule (Zucker et al., 2013; Carvalho et al., 2023; Shaoul et al., 2025). We vary the Langevin step size \eta\in\{0.1,0.2,0.5\} and SDF scaling factor \alpha\in\{0.05,0.1\}. Note that, on Dense with 18 robots, TFDP reaches 96\% success versus 84\% for the best displayed SDF setting (see Table 2), thus supporting an advantage especially in obstacle-dense settings. Appendix A.6 reports a broader sweep of both methods with Wilson intervals while Figure 7 in Appendix A.16 compares their refinement processes.

Next, recall that the analytical scores are local in time, depending only on a short temporal neighborhood of each waypoint. This locality is important for scalability as it allows TFDP to refine each agent’s trajectory independently, without constructing a joint high-dimensional search space. We assess locality by training a neural score estimator with different temporal receptive fields. We notice that, at low noise levels, prediction error plateaus as the window includes more distant timesteps, thus supporting the use of short temporal neighborhoods for refinement. For example, at \sigma=0.05, increasing the window from 1 to 3 reduces mean squared error from 0.8679 to 0.3849, while extending it to 7 yields 0.2988. Appendix A.13 reports the full results. Note that we use this estimator used only to test locality; TFDP remains training-free. Next, we ablate the coarse planner used to initialize TFDP. We compare RRT initialization with Voronoi roadmaps, straight-line interpolation, and Brownian bridges between starts and goals. On Room and Shelf, straight-line and Brownian-bridge initialization achieves only 0–17\% success, versus 99–100\% for Voronoi and RRT. Thus, initialization is critical in these structured layouts, but the ones adopted are also extremely easy and cheap to compute. Appendix A.8 reports all four initializations for both TFDP and MPPI. Finally, we compare the default noise schedule with noiseless, deterministic annealed refinement. Removing noise matches or exceeds noisy success on the standard maps, whereas noise improves success point estimates by 5–7 percentage points in the crowded 8- and 12-agent Bottleneck and Standoff cases (Appendix A.10). Thus, among the tested settings, noise is most useful in the more constrained scenarios. It can also improve a weak initialization: with straight-line trajectories replacing RRT, suitable choices of temperature T and smoothing scale \sigma can improve success. Appendix A.11 reports this ablation on Basic and Dense, showing that the benefit depends on the sampling parameters.

Scalability. Next, we test TFDP on a large-scale map with 100 obstacles and up to 300 robots. The tested map is a 100\times 100 unit square with randomly placed obstacles of varying sizes. We generate random start and goal positions for each robot, ensuring that they are not in collision with obstacles or each other. Importantly, TFDP produces valid plans for such maps in 5.39 seconds, on average on an A100 GPU. None of the diffusion baselines tested were able to handle this scale, and MPPI fails to find feasible plans for more than 50 robots. Figure 6 in Appendix A.15 shows a generated plan. We furthertest two deadlock scenarios in which robots must pass through a wall opening only wide enough for one robot (see Appendix A.12, Figure 4). Here, TFDP achieves much higher success than MPPI across the tested robot counts, indicating an advantage when passage through a shared bottleneck requires coordination.

6 Conclusion

This paper presented a training-free analytical diffusion planner for path finding and multi-agent path planning. The method replaces learned full-trajectory scores with decomposed analytical scores derived from smoothness, obstacle, velocity, and inter-agent feasibility terms. The analysis and experiments show that local temporal neighborhoods capture most of the useful score information needed for denoising, enabling efficient trajectory refinement without demonstrations or map-specific training. Future work will extend the method to richer kinodynamic models, more challenging maze-like environments, and large-scale multi-agent benchmarks. Note that, although this is standard to test multi-agent planning on 2D environments, it is interesting to consider extensions to higher dimensions, which we believe will be a natural next step. We also assume a centralized planner and perfect plan executions, and so it is interesting to consider how approaches involving diffusion-like sampling processes could be extended to decentralized planning problems.

AI Use Statement

Generative AI assisted with the creation of Figure 1, its caption, and the associated manuscript edits. The figure is a schematic illustration of the method. The authors also used AI to proofread the manuscript and suggest edits for clarity and conciseness. The authors verified all AI-generated content for accuracy and appropriateness, and they take full responsibility for the final content of the paper.

Ethics statement

The research presented in this paper is focused on improving multi-agent path planning algorithms. The methods and experiments are designed to advance the state of the art in robotics and autonomous systems, with potential applications in areas such as warehouse automation, autonomous vehicles, and robotic swarms. The research is conducted with a commitment to transparency, reproducibility, and responsible use of technology.

Reproducibility statement

The paper describes the problem formulation, analytical score construction, planning algorithm, evaluation metrics, and sampling hyperparameters. The appendix provides supporting mathematical derivations, additional benchmark descriptions, hyperparameter sweeps, initialization and noise ablations, and confidence intervals for the reported results. The complete source code is available upon request and will be released publicly upon acceptance of the paper.

Acknowledgments

This research was supported by NSF grants 2334936, 2334448, NSF CAREER Award 2401285, and DARPA Contract No. #HR0011252E005. The authors acknowledge Research Computing at the University of Virginia for providing computational resources that have contributed to the results reported within this paper. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government.

References

1. Augugliaro et al. (2012) F. Augugliaro, A. P. Schoellig, and R. D’Andrea Generation of collision-free trajectories for a quadrocopter fleet: a sequential convex programming approach. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. , pp. 1917–1922.
2. Carvalho et al. (2023) J. Carvalho, A. T. Le, M. Baierl, D. Koert, and J. Peters Motion planning diffusion: learning and planning of robot motions with diffusion models. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1916–1923. External Links: Link
3. Christopher et al. (2024) J. K. Christopher, S. Baek, and F. Fioretto Constrained synthesis with projected diffusion models. In Advances in Neural Information Processing Systems, Vol. 37, pp. .
4. Kalakrishnan et al. (2011) M. Kalakrishnan, S. Chitta, E. Theodorou, P. Pastor, and S. Schaal STOMP: Stochastic trajectory optimization for motion planning. In 2011 IEEE International Conference on Robotics and Automation, pp. 4569–4574. Note: ISSN: 1050-4729 External Links: ISSN 1050-4729, Link, Document
5. Kavraki et al. (1996) L. E. Kavraki, P. Švestka, J. Latombe, and M. H. Overmars Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12 (4), pp. 566–580. External Links: Document
6. Kuffner and LaValle (2000) J. J. Kuffner and S. M. LaValle RRT-connect: an efficient approach to single-query path planning. In Proceedings 2000 IEEE International Conference on Robotics and Automation, Vol. 2, pp. 995–1001. External Links: Document
7. LaValle (2006) S. M. LaValle Planning Algorithms. Cambridge University Press (en). External Links: ISBN 978-1-139-45517-6
8. Liang et al. (2025) J. Liang, J. K. Christopher, S. Koenig, and F. Fioretto Simultaneous multi-robot motion planning with projected diffusion models. In Proceedings of the International Conference on Machine Learning, External Links: Link
9. Liang et al. (2026a) J. Liang, S. Koenig, and F. Fioretto Discrete-guided diffusion for scalable and safe multi-robot motion planning. In Proceedings of the AAAI Conference on Artificial Intelligence, External Links: Link
10. Liang et al. (2026b) J. Liang, S. Koenig, and F. Fioretto Simulation-informed diffusion for decentralized multi-robot motion planning. abs/2605.27697.
11. Luo et al. (2024) Y. Luo, C. Sun, J. B. Tenenbaum, and Y. Du Potential based diffusion motion planning. arXiv preprint arXiv:2407.06169.
12. Ma et al. (2018) H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig Searching with Consistent Prioritization for Multi-Agent Path Finding. arXiv. Note: arXiv:1812.06356 [cs] External Links: Link, Document
13. Mellinger et al. (2012) D. Mellinger, A. Kushleyev, and V. Kumar Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams. In 2012 IEEE International Conference on Robotics and Automation, Vol. , pp. 477–483.
14. Mizuta and Leung (2024) K. Mizuta and K. Leung CoBL-Diffusion: diffusion-based conditional robot planning in dynamic environments using control barrier and lyapunov functions. External Links: 2406.05309, Link
15. Mukadam et al. (2018a) M. Mukadam, J. Dong, X. Yan, F. Dellaert, and B. Boots Continuous-time gaussian process motion planning via probabilistic inference. The International Journal of Robotics Research 37 (11), pp. 1319–1340.
16. Mukadam et al. (2018b) M. Mukadam, J. Dong, X. Yan, F. Dellaert, and B. Boots Continuous-Time Gaussian Process Motion Planning via Probabilistic Inference. The International Journal of Robotics Research 37 (11), pp. 1319–1340. Note: arXiv:1707.07383 [cs] External Links: ISSN 0278-3649, 1741-3176, Link, Document
17. Pan et al. (2012) J. Pan, L. Zhang, D. Manocha, and U. Hill Collision-free and curvature-continuous path smoothing in cluttered environments. Robotics: science and systems VII 17, pp. 233.
18. Park et al. (2020) J. Park, J. Kim, I. Jang, and H. J. Kim Efficient multi-agent trajectory planning with feasibility guarantee using relative bernstein polynomial. In 2020 IEEE International Conference on Robotics and Automation (ICRA), Vol. , pp. 434–440.
19. Ratliff et al. (2009) N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa CHOMP: Gradient optimization techniques for efficient motion planning. In 2009 IEEE International Conference on Robotics and Automation, pp. 489–494. Note: ISSN: 1050-4729 External Links: ISSN 1050-4729, Link, Document
20. Shaoul et al. (2025) Y. Shaoul, I. Mishani, M. Likhachev, et al. Multi-robot motion planning with diffusion models. In Proceedings of the International Conference on Learning Representations, External Links: Link
21. Sharon et al. (2015) G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219, pp. 40–66. External Links: ISSN 0004-3702, Link, Document
22. Song et al. (2020) Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456.
23. Xu et al. (2018) P. Xu, J. Chen, D. Zou, and Q. Gu Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization. In Advances in Neural Information Processing Systems, Vol. 31. External Links: Link
24. Xue et al. (2024) H. Xue, C. Pan, Z. Yi, G. Qu, and G. Shi Full-order sampling-based mpc for torque-level locomotion control via diffusion-style annealing. External Links: 2409.15610, Link
25. Zucker et al. (2013) M. Zucker, N. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingensmith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa CHOMP: Covariant Hamiltonian optimization for motion planning. The International Journal of Robotics Research 32 (9-10), pp. 1164–1193 (EN). External Links: ISSN 0278-3649, Link, Document

Appendix A Technical appendices and supplementary material

A.1 Conditional Information Flow

We start with the definition of mutual information between a pair of random variables:

Particularly, for a bivariate normal distribution p(x_{i},x_{j})=\mathcal{N}(x_{i},x_{j};0,\Sigma),

I(x_{i};x_{j})=-\frac{1}{2}\log\left(1-\frac{\Sigma_{ij}^{2}}{\Sigma_{ii}\Sigma_{jj}}\right).

Noting that p(x_{i},x_{j}\mid x_{k\neq i,j}) has a precision matrix equal to a submatrix of the original for all x_{k\neq i,j}, we can read off the mutual information from the precision matrix of the overall distribution. The conditional mutual information, in terms of the precision matrix, is

I(x_{i};x_{j}\mid x_{-\{i,j\}})=-\frac{1}{2}\log\left(1-\frac{(\Sigma^{-1}_{ij})^{2}}{\Sigma^{-1}_{jj}\Sigma^{-1}_{ii}}\right).

If there is no connection between the two variables in the MRF (i.e., (\Sigma^{-1})_{ij}=0), the variables are independent conditioned on all other variables. Starting from a precision matrix \Sigma^{-1}, with nonzero entries representing adjacent random variables in an MRF, one can determine the covariance of the resulting distribution after a forward diffusion process as \Sigma_{t}=\Sigma+tI. In terms of the precision matrix, this is \Omega_{t}=(\Sigma+tI)^{-1}. For very small t, \Omega_{t}\approx\Omega-\Omega(tI)\Omega, and

\left.\frac{d}{dt}\Omega_{t}\right|_{t=0}=-\Omega^{2}

Thus, if we have a Gaussian distribution given by \Omega, the change after an infinitesimal amount of diffusion time is -\Omega^{2}. When \Omega is treated as an adjacency matrix, \Omega^{2} represents the adjacency after two “hops”. Thus, the net effect is that codependence between random variables spreads out across the MRF.

A.2 Analytical Score Function Derivation

For general energy landscapes \log p(x), we note that the “score” of the landscape convolved with \mathcal{N}(0,\sigma^{2}I) can be computed as the quotient of two integrals:

\nabla_{x}\log p_{\sigma}(x)=\frac{1}{\sigma^{2}}\frac{\int(\tilde{x}-x)\mathcal{N}(\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{\int\mathcal{N}(\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}

We then provide methods for computing these integrals for multi-agent pathfinding constraint types.

Circular exclusion constraints. These represent noncollision constraints between circular agents and circular obstacles or other agents. We assume the agent is positioned at (0,0)\in\mathbb{R}^{2}, with radius r:=r_{agent}, and that the obstacle is positioned at (x_{obs},0)\in\mathbb{R}^{2} with effective radius R:=r_{obstacle}+r_{agent}. The feasible region is \mathcal{C}=\{(x,y)\in\mathbb{R}^{2}\mid(x-x_{obs})^{2}+y^{2}>R^{2}\}. Because the agent is at (x,y)=(0,0), we may replace x\to 0 in 14.

Then let r_{1}=\min\,\{r>0\mid\exists x\in\delta\mathcal{C}:|x|^{2}=r\} and r_{2}=\max\,\{r>0\mid\exists x\in\delta\mathcal{C}:|x|^{2}=r\} (i.e., the minimum and maximum distances from the agent that are not wholly contained or wholly excluded from the object). Furthermore, let \theta_{\text{min}}(r)=\min\,\{\theta\in[-\pi,\pi]\mid(r\cos\theta,r\sin\theta)\in\mathcal{C}\}, \theta_{\text{max}}(r)=\max\,\{\theta\in[-\pi,\pi]\mid(r\cos\theta,r\sin\theta)\in\mathcal{C}\}. Since the coordinate system is such that the obstacle lies on the x axis, \theta_{min}(r)=-\theta_{max}(r). Then,

\displaystyle\int\tilde{x}\mathcal{N}(\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x} \\ \displaystyle=\int_{r_{1}}^{r_{2}}r^{2}\mathcal{N}(\tilde{x};0,\sigma^{2}I)\int_{-\pi}^{\pi}(\cos\theta\,\vec{e}_{1}+\sin\theta\,\vec{e}_{2})\,\mathbb{I}_{\mathcal{C}}(\tilde{x})\mathop{}\!\mathrm{d}\theta\mathop{}\!\mathrm{d}r \\ \displaystyle\propto\int_{r_{1}}^{r_{2}}r^{2}e^{-\frac{r^{2}}{2\sigma^{2}}}\int_{\theta_{\text{min}}(r)}^{\theta_{\text{max}}(r)}\cos\theta\,\vec{e}_{1}\mathop{}\!\mathrm{d}\theta\mathop{}\!\mathrm{d}r \\ \displaystyle=\int_{r_{1}}^{r_{2}}2r^{2}e^{-\frac{r^{2}}{2\sigma^{2}}}\sin\theta_{\max}(r)\,\vec{e}_{1}\mathop{}\!\mathrm{d}r

and,

\displaystyle\int\mathcal{N}(\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x} \\ \displaystyle\propto\int_{r_{1}}^{r_{2}}re^{-\frac{r^{2}}{2\sigma^{2}}}\int_{-\pi}^{\pi}\mathbb{I}_{\mathcal{C}}(\tilde{x})\mathop{}\!\mathrm{d}\theta\mathop{}\!\mathrm{d}r \\ \displaystyle=\int_{r_{1}}^{r_{2}}2re^{-\frac{r^{2}}{2\sigma^{2}}}\theta_{\max}(r)\mathop{}\!\mathrm{d}r

To compute \theta_{\max},

\displaystyle\begin{cases}x^{2}+y^{2}&=r^{2}\\
(x-x_{obs})^{2}+y^{2}&=R^{2}\end{cases} \\ \displaystyle\implies x^{2}+y^{2}-2x_{obs}x+x_{obs}^{2}=R^{2} \\ \displaystyle\implies-2x_{obs}x+x_{obs}^{2}=R^{2}-r^{2} \\ \displaystyle\implies x=-\frac{R^{2}-r^{2}-x_{obs}^{2}}{2x_{obs}} \\ \displaystyle\implies y=\sqrt{r^{2}-x^{2}}=r\sin\theta_{\max}

Then r\sin\theta_{\max} may be used directly in 15, and one can compute \theta_{\max}=\text{arctan2}(y,x) for 18.

A.3 Rectangular Feasible Region Score Function Derivation

Consider a 2D region \mathcal{C}=[x_{\min},x_{\max}]\times[y_{\min},y_{\max}]. A uniform distribution over this region has the probability density:

p(x,y)=\frac{\mathbb{I}_{\mathcal{C}}(x,y)}{(x_{\max}-x_{\min})(y_{\max}-y_{\min})}

To create a diffusion-based generative model of this region, we can convolve this region with the Gaussian \mathcal{N}(0,\sigma^{2}I). Let q=(x,y)\in\mathbb{R}^{2}. Then the distribution at noise level \sigma is given by:

p_{\sigma}(q)=\int\mathcal{N}(q;\tilde{q},\sigma^{2}I)p(\tilde{q})\mathop{}\!\mathrm{d}\tilde{q}

Because p(\tilde{q}) is proportional to the indicator function over the feasible set, p_{\sigma}(q) is proportional to an integral over the feasible region:

p_{\sigma}(q)\propto\int_{\mathcal{C}}\mathcal{N}(q;\tilde{q},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q}

This represents the overlap between a Gaussian distribution with mean q=(x,y) and standard deviation \sigma and the feasible region. Taking the score,

\nabla\log p_{\sigma}(q)=\frac{\nabla p_{\sigma}(q)}{p_{\sigma}(q)}

Since \mathcal{C} is rectangular, we can express the denominator in terms of the Gaussian CDF, \Phi(x)=\int_{-\infty}^{x}\mathcal{N}(\tilde{x};0,I)\mathop{}\!\mathrm{d}\tilde{x}.

\displaystyle\int_{x_{\min}}^{x_{\max}}\int_{y_{\min}}^{y_{\max}}\mathcal{N}(q;\tilde{q},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x} \\ \displaystyle=\left(\int_{x_{\min}}^{x_{\max}}\mathcal{N}(x;\tilde{x},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x}\right)\left(\int_{y_{\min}}^{y_{\max}}\mathcal{N}(y;\tilde{y},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{y}\right) \\ \displaystyle=\left(\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)\right)\left(\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)\right)

Similarly, the numerator can be computed through the following observation:

\int_{x_{\min}}^{x_{\max}}\mathcal{N}(x;\tilde{x},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x}=\int_{0}^{x_{\max}}\mathcal{N}(x;\tilde{x},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x}-\int_{0}^{x_{\min}}\mathcal{N}(x;\tilde{x},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x}

By the fundamental theorem of calculus,

\frac{\mathop{}\!\mathrm{d}}{\mathop{}\!\mathrm{d}x}\int_{x_{\min}}^{x_{\max}}\mathcal{N}(x;\tilde{x},\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{x}=\mathcal{N}(x;x_{\max},\sigma^{2}I)-\mathcal{N}(x;x_{\min},\sigma^{2}I)

Therefore,

\displaystyle\nabla p_{\sigma}(q) \\ \displaystyle=(\mathcal{N}(x;x_{\max},\sigma^{2}I)-\mathcal{N}(x;x_{\min},\sigma^{2}I))\left(\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)\right)\vec{e}_{x} \\ \displaystyle+\left(\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)\right)(\mathcal{N}(y;y_{\max},\sigma^{2}I)-\mathcal{N}(y;y_{\min},\sigma^{2}I))\vec{e}_{y}

Finally,

\nabla\log p_{\sigma}(q)=\frac{\mathcal{N}(x;x_{\max},\sigma^{2}I)-\mathcal{N}(x;x_{\min},\sigma^{2}I)}{\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)}\vec{e}_{x}+\frac{\mathcal{N}(y;y_{\max},\sigma^{2}I)-\mathcal{N}(y;y_{\min},\sigma^{2}I)}{\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)}\vec{e}_{y}

A.4 Rectangular Infeasible Region Score Function Derivation

To compute the score function for a rectangular infeasible region, we can reuse many of our prior results. Although technically, the resulting distribution is not normalizable, one can still plug in the equation and get a reasonable result. Let’s say now that \mathcal{C}=([x_{\min},x_{\max}]\times[y_{\min},y_{\max}])^{c}=:\mathcal{C}_{\text{inclusion}}^{c}, the complement of the feasible region used in the previous section (which we shall denote \mathcal{C}_{\text{inclusion}}). Then we adopt the perspective that p_{\sigma}(x) is proportional to the overlap between a Gaussian distribution of mean q=(x,y) and standard deviation \sigma and the feasible region. We get:

\displaystyle\nabla p_{\sigma}(q) \\ \displaystyle=\nabla\int_{\mathcal{C}}\mathcal{N}(\tilde{q};q,\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q} \\ \displaystyle=\nabla\left(\int\mathcal{N}(\tilde{q};q,\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q}-\int_{\mathcal{C}_{\text{inclusion}}}\mathcal{N}(\tilde{q};q,\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q}\right) \\ \displaystyle=\nabla\left(1-\int_{\mathcal{C}_{\text{inclusion}}}\mathcal{N}(\tilde{q};q,\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q}\right) \\ \displaystyle=-\nabla\int_{\mathcal{C}_{\text{inclusion}}}\mathcal{N}(\tilde{q};q,\sigma^{2}I)\mathop{}\!\mathrm{d}\tilde{q}

Therefore, we simply negate the numerator calculation from A.3. For the denominator, we can use a similar trick by subtracting the denominator calculation from the previous section from 1. The overall result is:

\displaystyle\nabla\log p_{\sigma}(q) \\ \displaystyle=\frac{-(\mathcal{N}(x;x_{\max},\sigma^{2}I)-\mathcal{N}(x;x_{\min},\sigma^{2}I))\left(\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)\right)}{1-\left(\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)\right)\left(\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)\right)}\vec{e}_{x} \\ \displaystyle+\frac{-(\mathcal{N}(y;y_{\max},\sigma^{2}I)-\mathcal{N}(y;y_{\min},\sigma^{2}I))\left(\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)\right)}{1-\left(\Phi\left(\frac{x_{\max}-x}{\sigma}\right)-\Phi\left(\frac{x_{\min}-x}{\sigma}\right)\right)\left(\Phi\left(\frac{y_{\max}-y}{\sigma}\right)-\Phi\left(\frac{y_{\min}-y}{\sigma}\right)\right)}\vec{e}_{y}

A.5 Connection to Projection-Based Methods

The Stein score for a distribution p_{\sigma}(x) is defined as \nabla_{x}\log p_{\sigma}(x). This may be extended to a more elucidating form:

\displaystyle\nabla_{x}\log p_{\sigma}(x) \\ \displaystyle=\frac{\nabla_{x}p_{\sigma}(x)}{p_{\sigma}(x)} \\ \displaystyle=\frac{\int\nabla_{x}\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{p_{\sigma}(x)} \\ \displaystyle=\frac{\int\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)\nabla_{x}\log\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{p_{\sigma}(x)} \\ \displaystyle=\frac{1}{\sigma^{2}}\frac{\int_{\mathbb{R}^{n}}(\tilde{x}-x)\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{p_{\sigma}(x)}

For linear inequality or box constraints, the necessary integrals may be computed analytically, and for other low-dimensional constraints, the integral may be computed numerically. Furthermore, we can note that happens for low-\sigma behavior. If we assume p(x)=p(x)=\frac{\mathbb{I}_{\mathcal{C}}(x)}{m(\mathcal{C})}, then:

\displaystyle\lim_{\sigma\to 0}\sigma^{2}\nabla_{x}\log p_{\sigma}(x) \\ \displaystyle=\lim_{\sigma\to 0}\frac{\int(\tilde{x}-x)\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{\int\mathcal{N}(x-\tilde{x};0,\sigma^{2}I)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}} \\ \displaystyle=\lim_{\sigma\to 0}\frac{\int(\tilde{x}-x)\exp\left(-\frac{(x-\tilde{x})^{2}}{2\sigma^{2}}\right)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}}{\int\exp\left(-\frac{(x-\tilde{x})^{2}}{2\sigma^{2}}\right)p(\tilde{x})\mathop{}\!\mathrm{d}\tilde{x}} \\ \displaystyle=\lim_{\sigma\to 0}\frac{\int_{\mathcal{C}}(\tilde{x}-x)\exp\left(-\frac{(x-\tilde{x})^{2}}{2\sigma^{2}}\right)\mathop{}\!\mathrm{d}\tilde{x}}{\int_{\mathcal{C}}\exp\left(-\frac{(x-\tilde{x})^{2}}{2\sigma^{2}}\right)\mathop{}\!\mathrm{d}\tilde{x}} \\ \displaystyle=\Pi_{\mathcal{C}}(x)-x

That is, at very low \sigma, taking a discrete-time Langevin step with size \sigma^{2} is precisely the projection operator:

\displaystyle x_{t+1} \\ \displaystyle=x_{t}+\sigma^{2}\nabla_{x}\log p_{\sigma}(x_{t})+2\sigma z \\ \displaystyle=x_{t}+(\Pi_{\mathcal{C}}(x_{t})-x_{t})+2\sigma z \\ \displaystyle=\Pi_{\mathcal{C}}(x_{t})+2\sigma z

Since \sigma\ll 1, the Brownian noise term is negligible.

A.6 Larger Hyperparameter Sweep

We vary the Langevin step size \eta for TFDP and CHOMP-style SDF guidance, with SDF scaling factors \alpha\in\{0.05,0.1,0.2,0.5\}. The reported Wilson confidence intervals use 10 trials of 30 maps each. Gray columns identify TFDP, and arrows indicate whether higher (\uparrow) or lower (\downarrow) values are better. Bold marks the best comparable central values, including ties; the captions specify the comparison groups.

TFDP, smaller steps. Table 3 tests whether small updates suffice for reliable refinement. Success remains at 0.01 for \eta\leq 0.02, while \eta=0.10 raises it to 0.94–0.97 with 6 robots. The same step size reaches only 0.31–0.68 with 18 robots. Thus, the smaller-step regime is particularly restrictive as the number of interacting robots increases.

TFDP, larger steps. Table 4 shows that larger updates substantially improve feasibility. At \eta=0.50, success is at least 0.95 in every setting. Increasing \eta further raises the Dense 18-robot point estimate from 0.95 to 0.97, but lowers Room from 0.99 to 0.94 at \eta=1.00. This supports \eta=0.50 as a broadly effective choice, without identifying a universal optimum.

SDF with \alpha=0.1, smaller steps. Table 5 shows the interaction between step size and robot count. At \eta=0.10, Room success decreases from 0.94 with 6 robots to 0.31 with 18, while Basic decreases from 0.97 to 0.68. Even the best step size in this panel leaves a substantial feasibility gap as coordination becomes more demanding.

SDF with \alpha=0.1, larger steps. Table 6 shows high success over several neighboring step sizes. Basic remains at 0.99 for all robot counts when \eta\geq 0.50, and Shelf remains between 0.98 and 0.99. Dense and Room retain greater sensitivity with 18 robots, indicating that a broad effective range on simpler cases does not imply uniform robustness across layouts.

SDF with \alpha=0.5, smaller steps. Table 7 tests the largest SDF scale in the small-step regime. The highest success in every row occurs at \eta=0.10, while \eta\leq 0.02 yields only 0.01. The remaining variation at \eta=0.10, from 0.31 on Room with 18 robots to 0.97 on Basic with 6, shows that the same update scale can yield very different planning outcomes.

SDF with \alpha=0.5, larger steps. Table 8 reports at least 0.95 success in every setting at \eta=0.50. Larger steps offer little improvement on Basic and Shelf, while Room with 18 robots declines to 0.94 at \eta=1.00. The table supports a moderate step size across these cases; small differences among the larger-step estimates should be read together with their uncertainty intervals.

A.7 Single-Agent Reduction (RRT-Connect)

Table 9 evaluates whether the multi-robot problem can be solved directly by applying RRT-Connect in the joint configuration space on Dense. Success falls from 0.83 with 4 robots to 0.07 with 10, while mean runtime rises from 2.97 to 21.98 seconds. Time on success conditions on solved instances and therefore does not reflect the cost of unsuccessful searches; mean runtime includes both outcomes. These results expose the practical scaling difficulty of joint-space search under the tested budget, despite its asymptotic completeness properties.

A.8 Coarse Planner Ablation

We compare straight-line interpolation, Brownian bridges with maximum variance \sigma^{2}=0.025^{2}, Voronoi roadmaps, and RRT. The tables report success (S, in %), runtime (T, seconds), and path length (P). Path length must be interpreted jointly with success, since short trajectories can remain infeasible.

TFDP with simple initializations. Table 10 tests refinement from straight lines and Brownian bridges. Straight lines achieve 89–98\% success on Basic, but both initializers reach only 0–17\% on Room and Shelf. Brownian perturbations do not consistently improve feasibility and reduce Dense success with 18 robots from 68\% to 45\%. Thus, local trajectory variation alone does not resolve the routing difficulty of structured maps; the short runtimes and paths in failed cases should not be interpreted as better solutions.

TFDP with obstacle-aware initializations. Table 11 shows that Voronoi and RRT restore 99–100\% success on Room and Shelf. Voronoi yields lower total runtime in every row, while RRT yields shorter paths on the structured maps: on Room with 18 robots, path length decreases from 2.00 to 1.56, at a runtime increase from 0.82 to 2.06 seconds. On Dense with 18 robots, RRT also raises success from 77\% to 92\%. Initialization therefore affects feasibility, efficiency, and path quality.

MPPI with simple initializations. Table 12 asks whether the same initialization difficulty appears with sampling-based updates. MPPI reaches 96–98\% success on Basic with straight lines, but at most 17\% on Room and 25\% on Shelf. With 18 robots on Dense, Brownian bridges reduce success from 59\% to 42\%. The similar pattern for MPPI and TFDP indicates that poor initial routes are a shared obstacle for local refinement, rather than a limitation specific to analytical scores.

MPPI with obstacle-aware initializations. Table 13 reports 98–100\% success on Room and Shelf, confirming that informative initial routes also benefit MPPI. RRT shortens paths on both layouts, generally at higher runtime; on Room with 18 robots, path length decreases from 2.05 to 1.77 while runtime increases from 1.09 to 1.66 seconds. On Dense with 18 robots, RRT instead improves success from 77\% to 94\% at the cost of longer paths. No initializer dominates all three metrics.

A.9 MPPI CPU Runtime

Table 14 compares MPPI runtime on the CPU used for TFDP. As robot count grows from 6 to 18, runtime increases from 8.18 to 32.36 seconds on Basic and from 10.84 to 40.98 seconds on Dense. All entries exceed the corresponding TFDP times in Table 1. Thus, TFDP retains its runtime advantage on shared hardware, although this comparison does not isolate the cost of individual algorithmic components.

A.10 Effect of Noise

Table 15 compares stochastic refinement with deterministic annealed updates. Removing noise matches or slightly improves success on the standard maps. In the crowded stress tests, noise instead improves the point estimates: with 12 robots, Bottleneck rises from 0.38 to 0.45, and Standoff from 0.39 to 0.45. This suggests that stochastic exploration is most useful when many robots compete for limited passage space. The uncertainty ranges overlap, so these gains describe observed trends without establishing statistical significance.

A.11 Effect of \sigma and T

We vary the initial smoothing scale \sigma and temperature T, which are exponentially annealed to \sigma=0.001 and T=0.0001. These experiments use straight-line initialization to examine whether the refinement schedule can compensate for a simple initial trajectory. Rows vary \sigma, columns vary T, and each entry reports the success fraction.

Dense maps. Table 16 shows that smoothing and temperature must be selected jointly. At \sigma=0.05, increasing T from 0.0001 to 0.8 raises success from 0.40 to 0.72; at \sigma=0.2, the same change reduces it from 0.64 to 0.04. The maximum of 0.72 occurs at several parameter pairs. Additional exploration can therefore improve refinement from straight lines, but excessive noise at large smoothing scales can sharply reduce feasibility.

Basic maps. Table 17 reaches 0.96 success at (\sigma,T)=(0.05,0.8) and (0.1,0.5), compared with 0.72 at the lowest temperature for either smoothing scale. This shows that suitable stochastic refinement can substantially improve a simple initialization in this setting. The benefit is not monotonic: at \sigma=0.2, success falls from 0.84 at T=0.1 to 0.08 at T=0.8. Even on Basic, increasing temperature alone is insufficient.

A.12 Density/Stress Tests

We test maps with randomized start and goal positions and a wall opening wide enough for one robot. In Bottleneck, robots start on the same side; in Standoff, half the start–goal pairs are reversed to create opposing traffic. Figure 4 shows the layouts.

Bottleneck. Table 18 measures feasibility when robots must traverse a shared narrow opening in the same direction. TFDP has higher success point estimates at every tested count; with 8 robots, success is 0.69 versus MPPI’s 0.20. However, TFDP falls to 0.31 with 12 robots, while MPPI reaches 0.02. The results show a substantial advantage under congestion, but also identify crowded passages as a remaining source of failure.

Standoff. Table 19 introduces opposing traffic through the same type of opening, requiring robots moving in different directions to coordinate passage. TFDP achieves 0.70 success with 8 robots, compared with 0.23 for MPPI; with 12 robots, the values fall to 0.32 and 0.03. The advantage therefore persists under opposing traffic, while the low success at the largest count shows that analytical refinement does not consistently resolve these tightly coupled interactions.

A.13 Locality of Learned Scores

We test how much temporal context is useful for score estimation by training a multilayer perceptron with AdaLN-Zero conditioning on noise level for a simple trajectory distribution. This network is a diagnostic model; TFDP itself remains training-free. Table 20 reports final-epoch mean squared error as the temporal window and noise level vary.

Results. Expanding the window from 1 to 3 reduces error at every noise level, showing that neighboring waypoints carry useful information. At \sigma=0.05, error decreases from 0.8679 to 0.3849, then reaches its minimum of 0.2988 at window 7; window 9 gives no further improvement. At \sigma=0.2, error continues to decrease through window 9, reaching 0.2037. Thus, short neighborhoods are effective in this diagnostic, while broader context remains useful at higher noise. This supports the use of local score approximations at low noise, without establishing exact temporal independence or directly measuring downstream planning performance.

A.14 Confidence Bounds for 250-Step TFDP Results

Table 21 quantifies uncertainty for TFDP with 250 denoising steps. Basic and Shelf have 100\% observed success at every robot count, but their Wilson lower bounds are 98.5\%, distinguishing empirical success from guaranteed feasibility. Dense with 18 robots is the least reliable reported setting, at 96\% with a [92.7,97.9]\% interval. Runtime increases with robot count on every map, while mean path length changes more modestly. Together, the estimates support high observed reliability at these scales while making the uncertainty in that conclusion explicit.

Confidence intervals. Success uses 95\% Wilson score intervals, which remain within [0,100]\% even near the boundaries. Runtime and path length use mean \pm 2 standard errors. These summaries quantify uncertainty in the reported estimates; they do not separate variability due to sampled instances from variability due to random seeds.

A.15 Additional Planning Visualizations

Benchmark geometry. Figure 5 shows the four map types without trajectory overlays. Basic and Dense vary obstacle density, while Room and Shelf impose structured routes through openings and corridors. These layouts probe complementary difficulties: local obstacle avoidance, coordination in crowded spaces, and selection of routes around extended barriers. This distinction helps explain why the simple initializations in Appendix A.8 perform much worse on the structured maps.

Larger environment. Figure 6 illustrates trajectories in the large map used for the scalability experiment. The routes span open regions, dense obstacle clusters, and narrow passages, showing the geometric variety handled within one planning instance. The figure complements the scalability experiment with up to 300 robots, which reports an average runtime of 5.39 seconds on an A100 GPU. Spatial crossings in this static view do not by themselves indicate collisions, which depend on when robots traverse them.

A.16 Optimization Timelines

Figure 7 tracks the fraction of feasible plans over 250 refinement iterations on each benchmark map. TFDP uses \eta=0.5; the two CHOMP-style SDF variants use \alpha=0.05 with \eta\in\{0.2,0.5\}. SDF guidance produces feasible plans earlier, while TFDP improves sharply during the middle of the schedule and finishes with the highest feasible fraction on all four maps. On Dense, the final fractions are approximately 0.96 for TFDP and 0.84 for both SDF variants; on Room, they are approximately 0.98, 0.86, and 0.73 for TFDP and SDF with \eta=0.5 and 0.2, respectively. These curves show why final feasibility and early progress need to be assessed separately. Since the horizontal axis counts iterations, the figure describes refinement behavior rather than wall-clock efficiency.