GDTS: Goal-Guided Diffusion Model with Tree Sampling for Multi-Modal Pedestrian Trajectory Prediction

In general, pedestrian trajectory is goal-conditioned, as goals seldom change rapidly during the prediction horizon. Precise prediction of goals could reduce uncertainty and increase the accuracy of further trajectory prediction [20]. Several methods have been proposed to incorporate goal information into trajectory prediction. For exmaple, Dendorfer et al. [23] trained multiple generators, and each generator is used to a different distribution associated with a specific mode. Mangalam et al. [24] proposed a method that estimates goal points and generates multi-modal prediction using VAE conditioned on these estimated goal points. In Y-Net [20], a U-Net architecture is employed for goal and trajectory prediction, where the predicted goal information is also fed into the trajectory prediction decoder. Chiara et al. [21] proposed a recurrent network, Goal-SAR, which predicts the position of each future time step in recurrent way based on the goal and all history information before this time step. NSP-SFM [25] proposed by Yue et al.also took advantage of goal estimation network with a similar structure. By predicting the parameter of goal attraction, inter-agent repulsion and environment repulsion in each timestep and generating future using CVAE, this NSP-SFM method reached SOTA performance. However, the recurrent prediction way could be time-comsuming. Moreover, it is unfair for NSP-SFM to tune hyperparameters separately for different scenes in ETH/UCY while other methods (including ours) use only one set of hyperparameters. In this paper, we also divide the pedestrian trajectory prediction task into goal estimation and trajectory prediction.

The diffusion probabilistic model was first proposed by Sohl-Dickstein et al. [26] and has developed rapidly since DDPM [13] was proposed. It has achieved great success in various fields, such as computer vision [14, 15] and seq-to-seq models [27, 28]. Diffusion models have also been adopted in robotics applications. For instance, Diffuser [29] generates trajectories for robot planning and control using diffusion models. In Trace and Pace [30], the diffusion model is used to produce realistic human trajectories. In the context of pedestrian trajectory prediction, MID [16] was the first work to adopt the diffusion model for this task. Following the standard DDPM algorithm, a transformer acts as the diffusion network to generate multiple predictions conditioned on the history trajectory.

Despite its effectiveness in trajectory prediction, the diffusion model faces challenges due to the large number of denoising steps, which hampers real-time performance. To address this issue, various improvements have been proposed to accelerate the inference speed of the diffusion models [31]. DDIM [32] generalizes the forward process of the diffusion model as a non-Markovian process to speed up the sampling procedure. Salimans et al. [33] repeated knowledge distillation on a deterministic diffusion sampler to distill a new diffusion model with fewer sampling steps. Specific to multi-modal trajectory prediction, Mao et al. [17] proposes LED which trains an additional leapfrog initializer to accelerate sampling. Similar to our sampling algorithm, LED divides the diffusion sampling procedure into two stages and leverages an extra leapfrog initializer, which can estimate the roughly denoised distribution to skip the first stage. Instead of using an additional neural network, we use the same diffusion network to learn this distribution.

The pedestrian trajectory prediction problem can be formulated as follows: Given the current frame $t=0$, where the semantic map of the scene $\mathcal{S}$ and history positions of the targeted agent in the past $t_{h}$ frames $X=\{x_{t}\in\mathbb{R}^{2}|t=-t_{h}+1,-t_{h}+2,...,0\}$ are available, the objective is to obtain $N$ possible future trajectory prediction of the agents in the next $t_{f}$ frames $\widetilde{Y}_{n}=\{\widetilde{y}_{t}\in\mathbb{R}^{2}|t=1,2,...,t_{f}\}$. The notation with tilde represents the predicted result.

Our proposed framework divides the overall trajectory prediction task into goal estimation and trajectory prediction, as illustrated in Fig. 2. First, a network is applied to predict the probability distribution heat-map of the goal position. Then, a set of possible goals of the target agent is sampled from this distribution heat-map. Extracting the feature of these goal estimations and history information as guidance, a diffusion denoising network using the two-stage tree sampling algorithm is applied to get the multi-modal future trajectory prediction $\widetilde{Y}_{n}$ of the target agent. In the following part of this section, we will introduce the proposed framework in detail. Furthermore, we will introduce the loss function and the training scheme.

Considering the state-of-the-art performance of Y-Net [20] and Goal-SAR[21] on pedestrian trajectory prediction, we adapt their goal predictor for goal estimation. The goal predictor takes the semantic map and history trajectory as input. Since our work focuses on trajectory prediction, we assume that the semantic network is pre-trained to obtain semantic map $\mathcal{S}$ $\in$ $\mathbb{R}^{H\times W\times C}$, where $H$ and $W$ are the height and width of the input image, and $C$ is the number of semantic classes. Since we use a probability heat-map to describe the goal distribution, to keep the consistency of the input and output, pre-processing is needed before goal estimation to convert the inputted history positions of the frame $x_{t}$ to a 2D Gaussian probability distribution heat-map $\mathcal{H}_{t}$ $\in$ $\mathbb{R}^{H\times W}$ for each frame, and the highest probability is assigned to the ground truth position $x_{t}$. These position heat-maps are then stacked together to form a trajectory heat-map $\mathcal{H}_{h}$ $\in$ $\mathbb{R}^{H\times W\times t_{h}}$. Finally, $\mathcal{H}_{h}$ and $\mathcal{S}$ are concatenated and fed into a U-Net architecture network to predict the future trajectory heat-map $\widetilde{\mathcal{H}}_{f}\in$ $\mathbb{R}^{H\times W\times t_{f}}$, and the last channel represents the position distribution of the last frame $t={t_{f}}$, i.e., the goal distribution. By sampling from the goal probability distribution heat-map, $N$ estimated goals $g_{n},n=1,...,N$ are obtained, referred to as diverse goals. Meanwhile, the position with the highest probability is selected as the common goal $g_{*}$. Therefore, a total of $N+1$ estimated goals $G$ are generated.

The trajectory prediction module receives the estimated goals $G$ and the history trajectory $X$ as input. Following previous works [12, 16], we augment the history state $X$ with velocity and acceleration. Additionally, we integrate the goal information into the state by concatenating the vector from the position of this frame $x_{t}$ to the goal $g\in G$, as shown in lines 3-6 of Algorithm 1. After obtaining the augmented state $\hat{X}$ for each goal estimation, an LSTM encoder is trained to extract the feature f of the state. Similarly, We refer to the feature $\textbf{f}_{n}$ obtained using $g_{n}$ as diverse feature, and the feature $\textbf{f}_{*}$ obtained using $g_{*}$ as common feature. And f then serves as the guidance of the diffusion. During the forward process of diffusion, noise is added to the ground truth trajectory $Y^{0}$, and this noise addition is repeated for $K$ times to obtain a series of noisy future trajectories $\{Y^{1},...,Y^{K}\}$; While in step $k$ of the reverse denoising process, the diffusion network predicts a noise conditioned on $k$ and f. This predicted noise is then used to denoise the noisy future trajectory $\widetilde{Y}^{k}$ to $\widetilde{Y}^{k-1}$. With the iterative denoising process, the future trajectory prediction $\widetilde{Y}=\widetilde{Y}^{0}$ can be gradually reconstructed from a Gaussian distribution $Y^{K}\sim\mathcal{N}(0,\mathbf{I})$. Standard sampling algorithms (DDPM [13] and DDIM [32]) repeat the whole sampling procedure to generate multiple modalities, which could be time-consuming. To alleviate this drawback, we propose tree sampling, as shown in Algorithm 1. Our tree sampling algorithm is designed especially for multi-modal prediction and is divided into two stages: the trunk stage and the branch stage. The total number of DDPM diffusion steps is $K$, and the number of DDIM diffusion steps is $K_{I}$. The trunk stage consists of $K_{t}$ steps, and the branch stage consists of $K_{b}$ steps. In the trunk stage (lines 10-12), we begin by utilizing the common feature $\textbf{f}_{*}$ to denoise the trajectory. By applying a variant of DDPM which removes the noise term $\sigma_{t}\textbf{z}$ (we call this variant deterministic-DDPM or d-DDPM in short), the deterministic denoised result of the trunk stage $\widetilde{Y}^{K-K_{t}}$ is obtained, which could serve as general initialization for further denoising conditioned on different diverse features $\textbf{f}_{n}$, i.e., the trunk which links to different branches of this tree. In the subsequent branch stage (lines 15-22), different $\textbf{f}_{n}$ are used for refinement of $\widetilde{Y}^{K-K_{t}}$ to obtain final multi-modal predictions $\widetilde{Y}^{0}_{n}$. Since the branch stage needs to be run multiple times for different modalities, we apply DDIM in this stage to increase the inference speed. Experiments demonstrate our combination scheme generates more accurate results in real-world datasets.

Our training scheme consists of two stages to train two modules separately. First, the goal estimation module is trained solely using Binary Cross-Entropy loss, which measures the dissimilarity between the ground truth of future trajectory heat-map $\mathcal{H}_{f}$ and predicted heat-map $\widetilde{\mathcal{H}}_{f}$:

In the second stage, we train the goal estimation module together with the trajectory prediction module. The training objective of the trajectory prediction module is to learn a distribution $\epsilon\sim\mathcal{N}(0,\mathbf{I})$ for each step $k$ of diffusion, following the regular setting of diffusion models [13, 32]:

To evaluate the performance of our model, we conducted experiments on three public real-world pedestrian datasets: the ETH/UCY dataset, the Stanford Drone Dataset (SDD) and the intersection Drone Dataset (inD). These datasets capture the movement of pedestrians from a bird’s-eye view perspective and positions are manually annotated. The sample rate of datasets is 2.5 FPS. Given the pedestrian position of the last $t_{h}=8$ frames, the task is to predict the trajectory of the following $t_{f}=12$ frames.

Datasets The ETH/UCY [36, 37] dataset consists of 5 scenes: ETH, Hotel, Univ, Zara1, and Zara2. Following the common leave-one-scene-out strategy in previous work [4, 20], we use four scenes for training and the remaining one for testing. SDD [38] is a large-scale dataset that contains 11,216 unique pedestrians on the university campus. We use the same dataset split as several recent works [21, 24]: 30 scenes are used for training, and the remaining 17 scenes are used for testing. inD [39] includes 4 different intersection scenes in German and we follow the same evaluation protocol applied in  [21, 40, 41], where only pedestrian trajectories are retained and split into train, validation, and test sets by a 70%/10%/20% portion.

Evaluation Metrics Average Displacement Error (ADE) measures the average Euclidean distance between the ground truth and the predicted positions of the entire future trajectory, while Final Displacement Error (FDE) considers only the Euclidean distance between the final positions. Since our model generates multi-model predictions for stochastic future, we report the best-of-$N$ ADE and FDE of the predictions, denoted as ADE_N and FDE_N.

Implementation Details All the experiments were conducted on an NVIDIA 3080Ti GPU with PyTorch implementation. The goal predictor is implemented using a 5-layer U-Net as the backbone. The architecture of the diffusion network is a three-layer transformer encoder similar to MID [16], and readers can refer to the original paper for more details. We adopt a batch size of $64$. An Adam optimizer is employed with an initial learning rate of $10^{-3}$, and exponential annealing is applied for the learning rate. The goal estimation module is trained for $150$ epochs first and then trained with trajectory prediction module for $250$ epochs. The DDPM diffusion step $K$ is $100$, the DDIM diffusion step $K_{I}$ is $20$, and the trunk step $K_{t}$ is $30$. Additionally, we utilize Test-Time-Sampling-Trick (TTST) in our model to improve the accuracy of goal estimation [20], and the number of TTST samples $N_{ttst}$ is selected to be $1000$. The goal estimation loss coefficient $\lambda=20$ and The final number of predictions $N=20$.

Baseline We compare GDTS to different methods: Goal-based methods include Goal-GAN [34], MG-GAN [23], PECNet [24], Y-net [20], Goal-SAR [21]. We do not include NSP-SFM [25] here due to its unfair hyperparameters tuning for each scene in ETH/UCY. MID [16], LED [17] and SingularTrajectory [35] are methods which leverage diffusion model for pedestrian trajectory prediction. Specifically for inD, besides goal-based methods, we also compare our model with some SOTA methods: Social-GAN [4], ST-GAT [42], AC-VRNN [40] and GSGFormer [41], which are all training with the same dataset split as our model. Note that recent works with different evaluation protocal [43] are not included for fair comparison.

Discussion Results in Table I show that our model achieves comparable accuracy in the ETH/UCY dataset. Furthermore, results of experiments on the SDD are reported in Table II. With the combination of explicit guide guidance and diffusion denoising, our model achieves the best ADE₂₀ and FDE₂₀ among all compared methods. Results in inD shown in Table III are in line with the previous table, further confirming the effectiveness of GDTS. Since SDD and inD are substantially larger than the ETH/UCY dataset, we argue that our method is more suitable for datasets with larger sizes.

Sampling Algorithm of Diffusion To investigate the influence of different sampling algorithms, we replace tree sampling (TS) with DDPM and DDIM, and conduct the experiment on SDD. We report the average inference time for one agent in addition to the ADE₂₀ and FDE₂₀. Since LED [17] and SingularTrajectory [35] do not have an official implementation nor reported inference time on SDD, we only include MID which uses DDPM for comparison. The results in Table IV verify that our proposed tree sampling algorithm performs the best and has a shorter inference time than DDPM and DDIM, indicating the superiority of our sampling algorithm. Compared with MID, our GDTS method reduces the inference time from 139 ms to around 25 ms.

Trunk Step of Tree Sampling We also explore the effect of the trunk step $K_{t}$. As shown in Table IV, $K_{t}$ does not significantly influence the inference time since we use DDIM in the branch stage which already has a fast sampling speed. However, the accuracy of our method decreases when $K_{t}$ is either too large or too small. When $K_{t}$ is large, small $K_{b}$ makes it challenging for the branch stage to drive the roughly denoised trajectory to various modalities, limiting the diversity of the results. When $K_{t}$ is small, the branch stage that uses DDIM undertakes most of the denoising task, without obtaining enough guidance from the trunk stage, which degrades the performance.

Combination scheme of Tree Sampling We compare different combinations of DDPM, d-DDPM, and DDIM in tree sampling algorithm to verify the effectiveness of our scheme. Note that the result of the trunk stage must be deterministic, hence only d-DDPM and DDIM ($\eta=0$) can be used in the trunk stage. Results in Table V demonstrate that using d-DDPM in both stages gets the lowest ADE₂₀ and FDE₂₀, probably because d-DDPM focuses on reconstruction rather than generation, i.e., accuracy rather than diversity. However, the inference time is much longer than our scheme, and our scheme achieves a good balance between prediction accuracy and inference speed.

Fig. 3 presents the qualitative results of our GDTS method on the ETH/UCY and SDD datasets. The target pedestrian in the scene (a) turns right while moving straight in the scene (b) and (c). From the left column, it can be observed that the goals from the final prediction (in cyan) are closer to the ground truth (in yellow) compared to the goal estimations obtained from the goal estimation module (in blue), indicating that the diffusion models can improve FDE. The middle column shows the common goal $g_{*}$ and the roughly denoised trajectory generated by the trunk stage, demonstrating that the common goal can guide the denoised trajectory growing toward the correct direction. The right column shows the final prediction results, demonstrating the ability of GDTS to generate future trajectory predictions with different modalities.