Stochastic Trajectory Prediction via Motion Indeterminacy Diffusion

In plain words

Predicting where a pedestrian will walk next is not a single answer. Many paths are plausible, and a useful system has to produce several of them. Older methods do this by feeding random numbers into a neural network and hoping the spread comes out right. This one works differently. It starts from a blur of possible positions that covers every walkable area, and then removes uncertainty step by step until one clear path is left.

The idea comes from diffusion models, which learn to undo noise. Here the "noise" is uncertainty about where the person goes. A network looks at the person's recent track and the people nearby, and at each step it nudges the future path toward a more definite shape. Running more steps gives a more precise answer, and running fewer steps keeps more variety among the sampled paths. That lets you choose how much diversity you want.

The approach is slow, since the network runs once per step for every sampled path. The authors say so themselves and leave faster sampling for later work.

TL;DR

Motion indeterminacy diffusion (MID) learns a reverse Markov chain over future trajectory positions, conditioned on the observed path and social interactions §3.2 §3.5. The chain runs for K = 100 steps §5. The denoiser is a three-layer Transformer encoder with width 512, fed by a Trajectron++ state embedding §3.5 app. B. It is trained with a noise-prediction MSE eq. 10 and sampled with 20 draws per history (Best-of-20) §4.1. Author-reported results are state of the art among trajectory-only methods on SDD and comparable on ETH/UCY tab. 1 tab. 2. Sampling is about 39 times slower than Trajectron++ in the authors' test §5.

Problem

Pedestrian futures are multimodal: the same observed path can continue in many plausible ways §1. The authors argue that latent-variable generators, GANs and CVAEs, have known weaknesses. GANs can train unstably, and CVAEs tend to produce unnatural trajectories §1. The target is a model that covers several plausible futures while staying accurate for the one that happens §1 §4.3.

The setting is fixed. Positions are sampled every 0.4 s. The model sees 3.2 s of history, which is 8 frames, and predicts the next 4.8 s, which is 12 frames §4.1. Evaluation uses Best-of-N with N = 20 §4.1. On ETH/UCY it uses leave-one-scene-out cross-validation §4.1.

Method

The authors frame prediction as a reverse diffusion process over future positions. Their steps are below.

1. Forward chain (fixed). The future y_0 is corrupted over K steps with Gaussian transitions that use fixed variance schedule β_1..β_K eq. 1. In closed form, y_k is a scaled copy of y_0 plus Gaussian noise, with alpha-bar_k the cumulative product of (1 − β) eq. 2. By the last step the chain is close to standard Gaussian noise §3.2.
2. Reverse chain (learned). A parameterised Gaussian transition p_θ(y_{k−1} | y_k, f) runs from noise to a trajectory, conditioned on a state feature f from the observed path and neighbours eq. 3 §3.2. The transition variance is fixed to β_k I, and all steps share parameters §3.2.
3. Training objective. The negative variational bound eq. 4 eq. 5 is rewritten as a sum of KL terms between Gaussians eq. 6 eq. 7 eq. 8. Reparameterising the mean through a noise predictor eq. 9 gives the simplified loss used in practice: predict the noise that was added eq. 10 app. A.
4. State encoder. The authors use the Trajectron++ encoder for f. The paper says the method is encoder-agnostic and that the encoder's default configuration is used §3.5 app. B.
5. Denoiser. The denoiser takes the noisy future, a time embedding and f. It lifts each point to the Transformer width with an MLP, adds sinusoidal positional encoding, passes the sequence through three Transformer encoder layers, and projects back to two coordinates §3.5 app. B.
6. Joint training. The diffusion model and the encoder are trained together on the diffusion loss §3.2 §3.3.
7. Sampling. Start from standard Gaussian noise at step K, then apply the reverse update for k = K..1. The noise term is zero at the last step eq. 11 alg. 2. Draw 20 independent samples per history for Best-of-20 §4.1.

Algorithm 1, training. alg. 1

# One training step on a batch  [alg. 1] [eq. 10]
# history: (B, 8, 2) observed positions; future: (B, 12, 2) positions
def training_step(history, neighbours, future):
    # State embedding f from history and social context  [§3.5]
    state = encoder(history, neighbours)              # (B, 256)
    # One diffusion step per sample, drawn uniformly from 1..K  [alg. 1]
    steps = sample_uniform(1, K, size=B)              # (B,)
    # Gaussian noise that will corrupt the future  [alg. 1] [eq. 2]
    noise = sample_normal(shape=future.shape)         # (B, 12, 2)
    # Closed-form corruption of the future to step k  [eq. 2]
    noisy = (
        sqrt(alpha_bar[steps]) * future
        + sqrt(1 - alpha_bar[steps]) * noise
    )
    # Predict the added noise from noisy future, step and state  [§3.5]
    predicted = denoiser(noisy, steps, state)         # (B, 12, 2)
    # Mean squared error between true and predicted noise  [eq. 10]
    return mean((noise - predicted) ** 2)

Algorithm 2, sampling. alg. 2

# Draw one future from the reverse chain  [alg. 2] [eq. 11]
# Repeat 20 times per history for Best-of-20  [§4.1]
def sample_future(history, neighbours):
    # State embedding, same as during training  [§3.5]
    state = encoder(history, neighbours)              # (256,)
    # Start from standard Gaussian noise at step K  [alg. 2]
    current = sample_normal(shape=(12, 2))            # (12, 2)
    for step in range(K, 0, -1):
        # No fresh noise at the final step  [alg. 2]
        if step > 1:
            noise = sample_normal(shape=(12, 2))      # (12, 2)
        else:
            noise = zeros(shape=(12, 2))              # (12, 2)
        # Predicted noise from the denoiser  [§3.4]
        predicted = denoiser(current, step, state)    # (12, 2)
        # Reverse mean from the predicted noise  [eq. 9] [alg. 2]
        mean = (
            current
            - beta[step] / sqrt(1 - alpha_bar[step]) * predicted
        ) / sqrt(alpha[step])
        # Add noise with standard deviation sqrt(beta_k)  [alg. 2] [eq. 11]
        current = mean + sqrt(beta[step]) * noise
    return current

Key equations, as the paper states them:

q(\mathbf{y}_{k}|\mathbf{y}_{0}) = \mathcal{N}(\mathbf{y}_{k}; \sqrt{\bar\alpha_k}\,\mathbf{y}_{0}, (1-\bar\alpha_k)\mathbf{I}) eq. 2

\mathbf{y}_{k-1} = \frac{1}{\sqrt{\alpha_k}}\left(\mathbf{y}_{k} - \frac{\beta_k}{\sqrt{1-\bar\alpha_k}}\epsilon_\theta(\mathbf{y}_{k}, k, \mathbf{f})\right) + \sqrt{\beta_k}\,\mathbf{z} eq. 11

L(\theta,\psi) = \mathbb{E}_{\epsilon,\mathbf{y}_0,k}\,\Vert \epsilon - \epsilon_{(\theta,\psi)}(\mathbf{y}_k, k, \mathbf{x}) \Vert eq. 10

Notation: alpha_k = 1 − β_k and alpha-bar_k = ∏ alpha_s §3.2. The paper writes the condition as f in §3.2 and as x in eq. 10 §3.3.

Hyperparameters

Results

Author-reported. Setup: the SDD and ETH/UCY benchmarks, Best-of-20, 8 observed and 12 predicted frames, one V100 §4.1. Baselines are listed in each table. Rows marked † were reproduced by the authors with the official code tab. 1.

Stanford Drone Dataset (pixel units, trajectory-only input is marked T; tab. 1):

ETH/UCY (metres; leave-one-scene-out; ADE/FDE; tab. 2):

On ETH/UCY the paper says MID is comparable rather than best. Y-Net with TTST, which uses image input and 10000 samples, is better §4.2 tab. 2.

Ablation, architecture and diffusion (SDD, ADE / FDE; tab. 3):

Group 4 removes the diffusion model and keeps the Transformer decoder. The authors report that this does not recover the gain §4.3.

Sampling number (SDD; tab. 4):

The authors discourage this trick because it costs more compute app. C.

Cost. For 512 trajectories on ZARA1 with 100 steps, Trajectron++ takes 0.443 s and MID takes 17.368 s §5.

Trade-off. Plotting ADE and FDE against the number of reverse steps shows that fewer steps give more diversity and worse determinacy. More steps give the reverse §4.3 fig. 3.

Paper vs code

Code at commit 3b61674bd4beb13dbd662ec3b95542911176189d. The repository belongs to the first author (github.com/gutianpei) and the README links it from the paper README.md.

• Diffused variable. The paper diffuses future positions y_0 §3.1 eq. 1. The code diffuses future velocities. The prediction target is set to velocity trajectron_hypers.py, the training loss uses the raw, unstandardised value autoencoder.py [code: dataset/preprocessing.py#L92], and sampled velocities are integrated as a cumulative sum times the scene's dt, plus the last observed position [code: models/encoders/dynamics/single_integrator.py#L261]. Only the sampled output differs in meaning; the training target differs too.
• Time embedding. The paper's denoiser input is [k, sin k, cos k, f] app. B. The code embeds β at the step, [β_k, sin β_k, cos β_k] [code: models/diffusion.py#L192], with β taken from the schedule at step t [code: models/diffusion.py#L74] diffusion.py.
• Sampling noise. Algorithm 2 adds noise with standard deviation sqrt(β_k) alg. 2 eq. 11. The code's default flexibility = 0.0 selects the posterior standard deviation sqrt(β̃_k) instead [code: models/diffusion.py#L55-L58] diffusion.py [code: models/autoencoder.py#L32].
• Output MLP. The paper gives 512 → 256 → 2 app. B. The code uses three layers, 512 → 256 → 128 → 2 diffusion.py.
• Input fusion. The paper projects y_k and f separately and sums the results §3.5. The code has no separate sum. The state enters as a gate and bias in each ConcatSquash layer diffusion.py [code: models/common.py#L58-L72].
• Loss scale. Eq. 10 writes a plain norm, and Algorithm 1 uses a squared norm §3.3 alg. 1. The code uses MSE averaged over every element [code: models/diffusion.py#L83].
• Learning-rate schedule. Not stated in the paper. The code builds an exponential scheduler (γ = 0.98) but never calls scheduler.step() [code: mid.py#L225]. The learning rate stays at 0.001.
• Gradient clipping. Not stated in the paper. grad_clip: 1.0 is defined in the hyperparameter file but no clipping call appears in the training loop trajectron_hypers.py mid.py.
• Evaluation unit conversion. The paper reports ETH/UCY in metres and SDD in pixels §4.1 tab. 1. The code multiplies by 1/0.6 for ETH and by 50 for SDD before reporting mid.py mid.py. The paper does not mention these factors.
• Evaluation sampler. The paper's sampling is DDPM over 100 steps §3.4. main.py sets eval sampling to "ddim" and computes 100//step, but step is never defined main.py.
• Unused config. k_eval: 25 is in the config [code: configs/baseline.yaml#L14] but the MID path uses 20 samples, hard-coded [code: mid.py#L140]. The k_eval value is consumed by the MGCVAE path [code: models/encoders/mgcvae.py#L911].
• Repo-reported speed-up. The README says DDIM with two steps gives 0.41 / 0.71 on ETH, against 0.39 / 0.66 with 100 DDPM steps README.md. The paper does not report this.
• Unused file. models/transformer.py is not imported anywhere. The denoiser is TransformerConcatLinear in models/diffusion.py [code: models/diffusion.py#L172-L202].

Pitfalls

• Diffusion target is velocity in the code, position in the paper. An implementation that follows the paper's position target will differ from the reported numbers. Velocity is also unstandardised in the code. Pick one convention and say which in your implementation notes.
• The time embedding carries little signal. The code embeds β, which lies between 1e-4 and 0.05 app. B diffusion.py [code: models/autoencoder.py#L22]. Over that range sin β moves by at most 0.05, and cos β changes by less than 0.002, so the step information is small in magnitude. The paper's embedding uses the step index k, which spans 1 to 100 app. B.
• Which σ to use in sampling. The paper's Algorithm 2 uses sqrt(β_k). The code's default is the posterior sqrt(β̃_k) diffusion.py. The two differ, and the paper does not say which the reported numbers use.
• The β schedule is ambiguous. The appendix says β_k is "uniformly sampled between the bounds" app. B. The code uses torch.linspace, which gives evenly spaced, deterministic values diffusion.py.
• Dataset argument. main.py keeps args.dataset[:-1], which drops the last character main.py. Pass a name with a trailing character, e.g. eth/, or the wrong dataset file loads.
• Eval entry point. In eval mode the call on main.py#L46 references the undefined name step and fails before sampling, as the file reads. This is a reading of the source; the path was not executed here.
• Unit conversions decide the numbers. To compare with the reported ETH and SDD values, apply the same conversions as the code (see Paper vs code). Without them the metrics are in different units.
• Sampling cost. One sample needs 100 denoiser calls. The authors report about 39 times slower than Trajectron++ on one test §5. The repo's DDIM option cuts the step count but is not in the paper README.md.
• Best-of-20 is an oracle metric. Scores take the best of 20 samples against the ground truth. This is the paper's protocol §4.1, but it is not a single-prediction error.
• Sampling-number tricks change the comparison. The 20×20 rows and Expert + GMM use far more samples than 20 tab. 1 tab. 2 tab. 4. Compare them only with the same budget.
• Not stated in the paper: dropout, Transformer activation, epochs, LR schedule, gradient clipping, and seed. The code's values are listed in Hyperparameters.
• Training and encoder are coupled. The encoder's parameters are updated by the diffusion loss alone §3.2 mid.py. There is no separate Trajectron++ loss.

Lineage

• Builds on: denoising diffusion probabilistic models (Ho et al., NeurIPS 2020) and Sohl-Dickstein et al. (2015), both cited in §2 §2. The paper's bibliography has no arXiv ids for them, so no ids are given here. The state encoder is Trajectron++ (Salzmann et al., ECCV 2020) §3.5; it is not a card yet.
• Compared against: Social-GAN, PECNet, Trajectron++, LB-EBM, PCCSNET, Expert, Y-Net, STAR, Causal-STGCNN, SoPhie, CGNS, Social-BiGAT, MG-GAN, SimAug tab. 1 tab. 2.
• Superseded by: not stated in this wiki.