The Garden of Forking Paths: Towards Multi-Future Trajectory Prediction

In plain words

Forecasting where a person will walk next is usually scored against the one path that actually happened. But the same past can lead to several sensible futures: a pedestrian may head for a car, a shop or a doorway. Real footage shows only one of them, so there was no fair way to test a model that claims several.

This paper does two things. It builds a test set in a 3D simulator: the real scene is rebuilt, and people are asked to steer the same walker to different destinations from the same starting point. That gives several human-made futures per past. It also proposes a model that splits the prediction in two. First it guesses which small patch of the floor plan the person will enter, using a map of the scene's semantics (roads, sidewalks, cars) and a network that lets probability spread only to nearby patches. Then a second head nudges the guess to an exact point. Running a beam search over the patch guesses gives several different paths with weights.

TL;DR

• Predicts several weighted future paths for one person, instead of one.
• Works on a grid of scene cells: a convolutional RNN plus graph attention gives cell probabilities, and a second head adds an exact offset §3.
• Introduces Forking Paths, a simulated dataset with several human-annotated futures per observed past §4.
• Author-reported: the best minADE/minFDE on Forking Paths and the best single-future ADE/FDE on VIRAT/ActEV §5.2, §5.3.
• The public code is Apache-2.0; several settings in the code differ from the paper (see Paper vs code).

Problem

Real datasets record one future per observed past, so models can only be scored against a single path, while the future is in fact uncertain §1. Earlier multi-future methods produced alternatives from random input vectors or mixture densities and did not model the distribution over future cells explicitly §1. The paper also notes that no benchmark with several true futures per past existed for this setting §1, §4.

Method

The task is to output a distribution over future trajectories given the observed locations L_{1:h} and frames V_{1:h} §3. The model discretises the scene into an H \times W grid G and treats each future step as a choice of cell followed by an offset §3.2, §3.3.

Step 1. History encoding §3.1. Each observed location is mapped to the nearest grid cell and one-hot encoded. Frames pass through a frozen DeepLab model pretrained on ADE20K, giving a per-cell semantic map with K=13 classes §3.1. A convolutional RNN consumes the masked semantic features at each observed step eq. 1. Its final state initialises the decoders, and the temporal average of the semantic map is appended to the context at every decoding step §3.1.

H^e_t = \mathrm{ConvRNN}\big(\mathrm{onehot}(Y_t) \odot (W * S_t),\; H^e_{t-1}\big) eq. 1

Step 2. Coarse cell belief §3.2. A convolutional head with one filter turns the hidden state into a belief over cells, flattened and passed through a softmax eq. 2. The hidden state is updated by a convolutional RNN whose input is a graph-attention transform of the previous hidden state together with an embedding of the previous belief eq. 3. The graph has one node per cell and edges to neighbouring cells; the code uses the 3×3 block around each cell (see Paper vs code) §3.2. The attention edge function is an MLP in the paper's experiments §3.2.

\tilde h_i = \frac{1}{|\mathcal{N}_i|} \sum_{j \in \mathcal{N}_i} f_e([v_i, v_j]) + h_i eq. 4

Step 3. Fine offset decoder §3.3. A second convolutional RNN, also using graph attention, produces for every cell a two-dimensional offset from the cell centre eq. 5. The final location is the centre of the chosen cell plus that cell's offset eq. 6. For single-future output the chosen cell is the argmax of the belief (greedy) §3.3.

L_t = Q_i + \tilde O_{t,i} eq. 6

Step 4. Training §3.4. The classification loss is cross-entropy against the true cell at each future step eq. 7. The regression loss is a smoothed L1 applied to the offset of every cell, not only the true one eq. 8. The total loss adds these with weight \lambda_1 = 0.1 on regression and an L2 weight decay term eq. 9. During training the recurrent input is the soft predicted belief rather than its argmax; teacher forcing was considered and not used §3.4.

Step 5. Multi-future inference §3.5. Diverse beam search [Li et al. 2016] keeps K partial paths. At each step every (beam, cell) pair is scored by the beam's accumulated log-probability plus the log belief of the cell plus a diversity term \gamma(i), and the top K are kept eq. 10. The chosen cell centres then receive their offsets to give K trajectories §3.5.

B_t = \mathrm{topK}\big(\{P^k_{t-1} + \log C^k_t(i) + \gamma(i)\}\big) eq. 10

# Training loss for one future sequence  [§3.4] [eq. 7-9]
# Input:  belief (T, H*W), target one-hot cells (T, H*W),
#         offsets and target offsets (T, H*W, 2)
# Output: scalar loss

def training_loss(belief, target_cells, offsets, target_offsets):
    # Cross-entropy over cells, averaged over future steps  [eq. 7]
    cls_loss = -mean(sum(target_cells * log(belief), axis=cells))
    # Smooth L1 on the offset of every cell, not only the true one  [eq. 8]
    reg_loss = mean(smooth_l1(offsets - target_offsets))
    # Weighted sum; the L2 weight decay term is added by the optimiser  [eq. 9]
    return cls_loss + 0.1 * reg_loss

# Diverse beam search for K future paths  [§3.5] [eq. 10]
# Input:  encoder state, beam size K, number of future steps
# Output: K trajectories, each a list of (x, y) points

def predict_futures(history, beam_size, horizon):
    # Start K beams from the encoder state  [§3.1]
    beams = init_beams(history, beam_size)
    for step in range(horizon):
        # Coarse belief for every beam  [§3.2] [eq. 2-4]
        beliefs = coarse_belief(beams)               # (K, H*W)
        # Score each (beam, cell) pair  [§3.5] [eq. 10]
        scores = beams.log_prob + log(beliefs)       # (K, H*W)
        # Add the diversity term gamma(i)  [§3.5] [eq. 10]
        scores = scores + diversity_term(scores)     # (K, H*W)
        # Keep the K best pairs; each new beam inherits its parent state
        beams = top_k_pairs(scores, beam_size)
    # Add the fine offset of each chosen cell  [§3.3] [eq. 6]
    return [beam.cell_center + beam.offset for beam in beams]

Hyperparameters

Results

Author-reported. Setup: models are trained on real VIRAT/ActEV videos and tested on the synthetic Forking Paths data, with 45-degree views averaged over three camera angles and a top-down view §5.2, tab. 1. Five runs with random initialisation give the mean and standard deviation, except the linear baseline §5.2. Hardware is not stated.

Multi-future, Forking Paths (minADE and minFDE with K=20; lower is better) tab. 1

Source: tab. 1. The paper reports that the margin over Social-GAN is at least 8 points on all metrics §5.2.

Negative log-likelihood, Forking Paths tab. 2. For methods that output several trajectories, the coordinates are quantised onto the proposed model's grid before scoring tab. 2 caption.

Single-future, VIRAT/ActEV (ADE / FDE; lower is better) tab. 3

Source: tab. 3 and §5.3. The paper reports the largest gain on FDE and attributes it to the coarse classification head §5.3.

Ablation tab. 4. The multi-future columns are averaged over all views §5.4.

Source: tab. 4. Figures fig. 5 and fig. 6 show qualitative outputs and four typical errors (wrong direction, going through a car instead of around it, heading toward a moving car, and a person who has just left a vehicle) §5.2.

Paper vs code

Code: the official repository JunweiLiang/Multiverse at commit c1756f0cef0fd0be1c0be952554e9e913eb8126d, Apache-2.0. The owner is the first author. The project page named in the paper's footnote did not resolve when checked, so the repository was used [abstract footnote].

• Graph attention is not the paper's formulation. The paper uses a learned MLP edge function and a mean over neighbours plus a residual term [§3.2, eq. 4]. The code's edge weight is the dot product of L2-normalised node features, with no learned edge function pred_models.py. The neighbour aggregation is a softmax-weighted sum with no residual term pred_models.py. Neighbours are restricted to the 3×3 block around each cell, including the cell itself, before the softmax pred_models.py.
• Scene features in the node input depend on a flag. The paper concatenates averaged semantic features into each node §3.2. The code adds them only with --use_scene_enc train.py. The documented training command omits this flag TRAINING.md, while the documented inference command sets it TESTING.md.
• Diversity term differs. The paper gives the penalty as a term in \gamma(i) with no value §3.5, eq. 10. The code adds \log(\gamma) times the rank of each cell pred_models.py, applied at the beam step pred_models.py. The default \gamma is 1.0, which gives zero penalty multifuture_inference.py. The documented inference command uses 0.01 TESTING.md, and a code comment says \gamma should exceed 1.0 pred_models.py.
• Regression weight. The paper uses \lambda_1 = 0.1 §3.4. The documented training command uses 0.2 TRAINING.md. The training default is 0.1 train.py.
• Learning rate and weight decay. The paper states Adadelta with initial learning rate 0.3 and weight decay 0.001 §5.2. The training default is 0.2 train.py and 0.0001 train.py. The documented command uses 0.3 and 0.001 TRAINING.md.
• Embedding and batch settings. The paper states an embedding size of 32 §5.2. The training default is 128 train.py; the documented command uses 32 TRAINING.md. The default batch size is 64 train.py and the default epoch count is 100 train.py. The documented command uses 20 and 80 TRAINING.md. The paper states neither value.
• Grid sizes. The paper's finest grid is 36 × 18 and the second is 18 × 9 §3.1. The code's scene size defaults to 36 × 64 train.py, with strides 2 and 4 in the documented command TRAINING.md. The grid dimensions that result from these strides were not verified here.
• Prediction horizon. The documented commands use 8 observed steps and 12 predicted steps TRAINING.md, and the code default is also 12 train.py. At the 2.5 fps the paper states §5.2, 12 steps is 4.8 s.
• Dropout. The documented command sets keep probability 1.0 [code: TRAINING.md#L35], i.e. no dropout. The paper does not mention dropout.

The loss forms match the paper: cross-entropy over cells, and a smoothed L1 (implemented as Huber loss) on the offsets of every cell by default pred_models.py. The only loss-weight difference found is the regression weight above.

Pitfalls

• Stale LaTeX in the source archive. The arXiv source contains older sections and tables that the compiled paper does not use, for example raw/src/1912.06445/experiments.tex and raw/src/1912.06445/dataset.tex. Their numbers differ (one uncompiled table lists the proposed model at 170.0 for 45-degree minADE and 336.2 for 45-degree minFDE, against 168.9 and 333.8 in the compiled Table 1). This card uses only the compiled kevin/ inputs.
• Equation and float numbers were counted in compiled order. Commented-out equations are not numbered. Table 1 is the multi-future table; Figures 1 to 6 are counted in the same order.
• Ablation numbers are a four-view average. Table 4's multi-future column equals the weighted average of Table 1's values (three 45-degree views plus top-down): (3 × 168.9 + 157.7) / 4 = 166.1 for minADE and (3 × 333.8 + 316.5) / 4 = 329.5 for minFDE. Do not compare the Table 1 45-degree column directly with Table 4.
• Diversity term is undefined in the paper. The code default of 1.0 turns the penalty off, so beam search becomes plain beam search. The documented value 0.01 and the code comment (gamma should exceed 1.0) disagree. Verify the value against the documented run before reusing it.
• Prediction horizon conflicts. The dataset section says the future length is 10.4 s and that the 10.4 s value allows longer-term evaluation §4. The same value is also the annotators' time limit §4. The documented commands predict 12 steps, which is 4.8 s at 2.5 fps §5.2. The paper does not reconcile these.
• NLL depends on the grid. Multi-trajectory methods are quantised onto the proposed model's grid before scoring tab. 2 caption, so the NLL values depend on that grid choice. The meaning of T_{pred} in tab. 2 is not stated.
• Train-real, test-synthetic. Table 1 models are trained on real VIRAT/ActEV videos and tested on the synthetic dataset tab. 1 caption. Table 3 reports both training regimes. Do not compare Table 1 with Table 3 as the same setting.
• Single-run baseline. The linear baseline in Table 1 is not repeated and so has no standard deviation §5.2.
• Data is not bundled. The testing instructions download prepared ActEV data from an external host TESTING.md, and the Forking Paths README points to a separate download README.md. The dataset's license is not stated in the repository and was not checked, so it is not recorded here. Only the code's license (Apache-2.0) is recorded.
• Training feeds soft beliefs. The recurrent input during training is the soft predicted belief, not its argmax §3.4. An implementation that feeds argmax or one-hot targets will not match the paper.
• Single-future uses greedy cell selection. Only multi-future output uses beam search §3.3, §3.5. Reporting single-future numbers from beam outputs changes the setting.

Lineage

• Builds on: convolutional LSTM for the recurrent cells §3.1; graph attention for neighbour aggregation §3.2; the classification-plus-regression split, partly inspired by object-detection methods §3.3; diverse beam search §3.5.
• Compared against: Linear, LSTM, Social-LSTM and Social-GAN, plus the authors' earlier single-future model Next, all as reported in tab. 1 and tab. 3.
• Concurrent work: a two-stage model whose classification targets are predefined anchor trajectories, which the paper contrasts with its free grid prediction §3.3.
• Superseded by: not stated in this card's sources.