---
abstract: 'Predicting the behavior of surrounding vehicles is a critical problem in automated driving. We present a novel game theoretic behavior prediction model that achieves state of the art prediction accuracy by explicitly reasoning about possible future interaction between agents. We evaluate our approach on the NGSIM vehicle trajectory data set and demonstrate lower root mean square error than state-of-the-art methods.'
author:
- |
    Mihir Jain\
    Qualcomm AI Research Kyle Brown$^{*}$\
    Stanford University\
    Ahmed K. Sadek\
    Qualcomm AI Research\
bibliography:
- 'egbib.bib'
title: 'Multi-Fidelity Recursive Behavior Prediction'
---

=1

Introduction {#sec:Introduction}
============

Predicting the future motion of surrounding vehicles is a critical problem in autonomous driving research and development. One of the key difficulties associated with behavior prediction is *interaction* between traffic participants. Existing models vary in the way they reason about interactive driver behavior. Some models ignore interaction completely, predicting the future behavior of a target vehicle based solely on that vehicle’s previous motion [@Ammoun2009; @Barth2008; @Hillenbrand2006; @Kaempchen2004IMMOT; @Miller; @Polychronopoulos2007]. Other models *implicitly* reason about interaction by conditioning motion prediction on the local traffic scene (including the current state or motion history of other nearby vehicles) [@Altche2018; @Deo; @Deo2018MultiModalTP; @Khosroshahi; @Morton2017; @Phillips2017].

Still other models reason *explicitly* about interaction, addressing the prediction task from a game-theoretic perspective [@Galceran2017; @HongYoo; @Sadigh2016; @Schmerling2017; @Yoo2012].

We present a novel game theoretic behavior prediction model that we call Multi-Fidelity Recursive Behavior Prediction (). achieves better prediction accuracy (as measured by root mean squared error) than previous state-of-the-art models by explicitly reasoning about possible future interaction between agents. The proposed algorithm employs a recursive trajectory prediction scheme inspired by the Level-$k$ [@Costa-Gomes2001] and Cognitive Hierarchy [@Camerer2004] recursive reasoning paradigms.

This paper gives a condensed overview of the general Multi-Fidelity Recursive Behavior Prediction algorithm. We also discuss several specific implementations of our model, all of which incorporate specific elements from Convolutional Social Pooling for Vehicle Trajectory Prediction as proposed by Deo and Trivedi [@Deo] in 2018. All experiments are conducted with the publicly available NGSIM data set.

Methods {#sec:Methods}
=======

Consider a traffic scene consisting of $\numcars$ agents. The motion history of the traffic scene from the initial time $\initialtime$ to the current time $\currenttime$ can be compactly represented by the set of time histories $\trafficscene_{\text{hist}} = \lbrace \carstate_1^{\initialtime:\currenttime}, \ldots,\carstate_\numcars^{\initialtime:\currenttime} \rbrace$, where $\carstate_i^{(\currenttime)}$ is the state of agent $i$ at time $\currenttime$. The corresponding set of future trajectories (from time $\currenttime+1$ to time $\finaltime$) is $\trafficscene_{\text{future}} = \lbrace \carstate_1^{\currenttime+1:\finaltime}, \ldots, \carstate_\numcars^{\currenttime+1:\finaltime} \rbrace$. The input to our model is $\trafficscene_{\text{hist}}$, and the output is $\hat{P}(\trafficscene_{\text{future}})$, a probability distribution over the future trajectories of all agents. In all experiments presented here, we choose to model $\hat{P}(\trafficscene_{\text{future}})$ as a set of Gaussian trajectory predictions $\lbrace (\hat{\carstate}_{1}^{(\currenttime+1:\finaltime)}, \Sigma_{1}), \ldots,(\hat{\carstate}_{\numcars}^{(\currenttime+1:\finaltime)},\Sigma_{\numcars}) \rbrace$, where $\hat{\carstate}_i$ and $\Sigma_i$ represent the mean vector and covariance matrix of a Gaussian distribution over the future trajectory of the $i$th agent.

The general Multi-Fidelity Recursive Behavior Prediction algorithm is outlined in Algorithm \[alg:general\_MFRBP\]. In the remainder of this section, we discuss two important characteristics of our model: *recursive prediction* and *multi-fidelity modeling*.

#### Recursive Prediction

Our model employs a game-theoretic recursive prediction scheme inspired by Level-$k$ Reasoning [@Costa-Gomes2001] and Cognitive Hierarchy [@Camerer2004]. Within this paradigm, a “level $k$” agent model assumes that all other agents act according to a level $k-1$ (or lower) agent model.

First, the algorithm assigns a reasoning level $\level_i$ and a corresponding sequence of policy models $(\pi_{i,0}, \ldots, \pi_{i,\level_i})$ to each agent $i \in \lbrace 1, \ldots, \numcars \rbrace$ in the scene. At each level $\level$ (starting from $\level = 0$ and proceeding upward) a predicted trajectory is generated for each agent $i \in \lbrace 1, \ldots, \numcars \rbrace$ if that agent’s assigned reasoning level $\level_i$ is greater than or equal to $\level$. The crucial detail is that, for $\level>0$, the level $\level$ trajectory prediction for a given agent is *explicitly conditioned* on the highest level (up to $\level-1$) previously computed trajectory predictions associated with each other agent.

When the highest reasoning level has been reached (i.e. when $\level = \max_{i \in \lbrace 1, \ldots, \numcars \rbrace } \level_i$), the algorithm returns a set containing the final predicted trajectory for each agent.

#### Multi-Fidelity Behavior Modeling

For a given traffic scene history $\trafficscene_{\text{hist}}$, the output of our model depends entirely on the reasoning levels and sequences of policy models assigned to the agents. These assignments are determined by the user-defined methods on lines \[line:assign\_level\] and \[line:assign\_policies\] of Algorithm \[alg:general\_MFRBP\].

In our experiments, we show that this design flexibility can be used for *multi-fidelity modeling*, meaning higher-fidelity motion prediction for some agents than for others. *Multi-fidelity modeling* can be useful in applications (e.g. automated driving) where we may know and/or care more about some agents than others.

$\level_i \gets \assignlevel(\trafficscene_{\text{hist}},i)$ \[line:assign\_level\] $( \pi_{i,0}, \ldots, \pi_{i,\level_i} ) \gets \assignpolicies(\trafficscene_{\text{hist}},i,\level_i)$ \[line:assign\_policies\] $(\hat{\carstate}_{i,0}^{(\currenttime+1:\finaltime)},\Sigma_{i,0}) = \policy_{i,0}
                        \big(
                            \lbrace
                            \carstate_{j}^{ (\initialtime:\currenttime)
                            } \mid j \in \lbrace 1, \ldots, \numcars \rbrace, j \neq i
                            \rbrace
                        \big)$ \[line:level\_0\_policy\] \[line:begin\_recursion\] $(\hat{\carstate}_{i,k}^{(\currenttime+1:\finaltime)},\Sigma_{i,k}) = \policy_{i,k}\big( \lbrace 
                            (
                            \carstate_{j}^{
                            (\initialtime:\currenttime)},
                            \hat{\carstate}_{j,
                            min(\level_j,k-1)}^{
                            (\currenttime+1:\finaltime)}
                            )
                            \mid j \in \lbrace 1, \ldots, \numcars \rbrace, j \neq i
                        \rbrace \big)$ \[line:level\_k\_policy\] \[line:end\_recursion\] **return** $\lbrace (\hat{\carstate}_{1,\level_1}^{(\currenttime+1:\finaltime)}, \Sigma_{1,\level_1}), \ldots, 
        (\hat{\carstate}_{\numcars,\level_\numcars}^{(\currenttime+1:\finaltime)},
        \Sigma_{\numcars,\level_\numcars}) \rbrace$ \[line:returnvalue\]

#### Policy models used in our experiments

Our simple experiments incorporate three distinct policy models. The first two policy models condition only on motion *history* $\trafficscene_{\text{hist}}$. whereas, the third policy model explicitly conditions on previously computed level $0$ trajectory predictions.

The *Constant Velocity ($\CV$) model* simply predicts that a target vehicle will travel at constant velocity equal to the average velocity vector (both longitudinal and lateral components) over the last second. This can be thought of as “low-fidelity” motion prediction.

The *Convolutional Social Pooling ($\CSP$) model* was originally proposed by Deo and Trivedi [@Deo]. $\CSP$ combines a Long Short-Term Memory network (LSTM) encoder-decoder architecture with a convolution neural network (CNN) “social pooling” architecture to generate multimodal trajectory predictions. This model is depicted in blue in Figure \[fig:FC-CSP\_architecture\]. For each target, $\CSP$ accepts as input the state-histories of both the target vehicle and its neighbors (vehicles that fall in a rectangular region around the target). The final output is a set of six Gaussian distributions, each with an associated likelihood, that represent six possible trajectories. In our experiments, we take only the mode with the highest probability for prediction. In contrast to $\CV$, $\CSP$ is a “high-fidelity” motion prediction model.

The *Future-Conditional Convolutional Social Pooling ($\FCCSP$) model*, shown in Figure \[fig:FC-CSP\_architecture\], is a novel extension of $\CSP$, allowing the model to explicitly condition on predicted motion in addition to the motion history. This is accomplished by adding a “future” social pooling block (lower block), which is architecturally identical to the history social pooling block but receives as input the predicted future trajectories of the vehicles surrounding the target vehicle. The decoder LSTM layer in $\FCCSP$ receives the concatenation of both past and future “social context” tensors, and outputs a multimodal Gaussian trajectory distribution of the same form as the output of $\CSP$. As with $\CSP$, our experiments use only the highest probability mode.

![**Future-Conditional Convolutional Social Pooling ($\FCCSP$) Architecture.** All components shown in blue are part of the original $\CSP$ architecture as proposed by Deo and Trivedi [@Deo]. The yellow elements represent the portion of the model that processes the predicted future trajectories.[]{data-label="fig:FC-CSP_architecture"}](ModelArchitecture.pdf){width="90.00000%"}

Experiments {#sec:Experiments}
===========

We perform three experiments to evaluate the performance of Multi-Fidelity Recursive Behavior Prediction. The first experiment is designed to compare our model against the existing state-of-the-art (the $\CSP$ baseline), while the other two experiments are intended to evaluate our algorithm in a setting that is more representative of an autonomous driving scenario.

All three experiments are conducted on the publicly available NGSIM I-80 [@I80] and US101 [@US101] datasets. There are 3 subsets of both US-101 and I-80, consisting of vehicle trajectories recorded by overhead camera at a frequency of 10 Hz. The test set consists of one quarter of the vehicle trajectories from each of the subsets of the US-101 and I-80 datasets. We split the trajectories into segments of 8 s (sampled at 10 Hz), where we use 3 s of track history and a 5 s prediction horizon. We use the common metric of *Root Mean Square Error* (RMSE) for evaluating the performance of our models.

Experiment 1: Level 1 Recursive Behavior Prediction
---------------------------------------------------

Our first experiment compares a specific implementation of Multi-Fidelity Recursive Behavior Prediction against the performance of the $\CSP$ baseline. This implementation is called Level $1$ Recursive Behavior Prediction (). In , all agents are assigned a reasoning level of $1$. The level $0$ policy model for each agent is *Convolutional Social Pooling* ($\CSP$), and the level $1$ policy for each agent is *Future-Conditional Convolutional Social Pooling* ($\FCCSP$). Formally: ($\level_i, \policy_{i,0}, \policy_{i,1}) := (1, \CSP, \FCCSP) \ \forall i \in \lbrace 1, \ldots, n \rbrace$.

We train both the $\CSP$ (level $0$ policy) model and $\FCCSP$ (level $1$ policy) models jointly from scratch. As in the original $\CSP$ implementation, we use the leaky-ReLU activation with $\alpha=0.1$ for all layers and use Adam for optimization.

#### Results for Experiment 1

We compare the output of () against the $\CSP$ baseline. The left part of Table \[table:RMSE\] shows RMSE values obtained at varying time horizons for $\CSP$ and . Note that $\CSP$$^\dotplus$ corresponds to the original values reported by Deo and Trivedi [@Deo] and $\CSP$$^\ast$ is our own implementation of the baseline $\CSP$ model.

Experiment 2: Level 1 Multi-Fidelity Recursive Behavior Prediction
------------------------------------------------------------------

For experiment 2, we introduce *Level 1 Multi-Fidelity Recursive Behavior Prediction ()* (). targets the “ego-centric” prediction task, which is more representative of the autonomous driving use case: We randomly select a vehicle to treat as an “ego” agent, limiting the set of other agents in the scene to those within a plausible “sensor range” of this agent. This is repeated for many different “ego” agents during both training and testing. is identical to , except that it incorporates a multi-fidelity scheme wherein agents at the periphery of the designated ego agent’s sensor range are assigned to a lower reasoning level ($\level_i = 0$) and a lower fidelity ($\policy_{i,0} = \CV$) policy model. The $\CSP$ and $\FCCSP$ policies are jointly trained. The training process includes generating and using lower-fidelity constant velocity trajectory predictions for the peripheral agents.

#### Results for Experiment 2

It would take too long to exhaustively evaluate on the full test set (i.e. by treating every single vehicle in turn as the ego agent). Instead, we sample enough ego agents to ensure that a single level $1$ prediction can be computed for each vehicle in the test set. We report the average results of the level $1$ predictions from $10$ full iterations through the test set in this manner. Our results are presented in Table \[table:RMSE\] alongside the results from Experiment 1. exhibits slight improvement over $\CSP$, indicating that a multi-fidelity recursive prediction scheme can enhance performance even if the “low-fidelity” models are very naive. Improvement is more pronounced over longer prediction horizons.

Experiment 3: conditioned on Ego Future
---------------------------------------

Experiment 3 seeks to quantify the performance improvement that results from conditioning motion prediction on a candidate future ego trajectory. To explore this question, we use the ground truth future trajectory as a surrogate for the ego agent’s “planned” trajectory. This takes the place of the ego agent’s level $0$ trajectory in a “planning-aware” version of . In other words, we “cheat” by allowing the model to observe the ground truth future trajectory for each designated ego agent during training and testing. We wish to make it clear, therefore, that experiment 3 is not meant to compete with the other models.

#### Results for Experiment 3

RMSEs for planning-aware are shown in italics in the last column of Table \[table:RMSE\]. The numbers are better than for , which suggests that conditioning on a planned trajectory (as in a real automated driving scenario) can improve motion prediction.

Conclusion {#sec:Conclusion}
==========

We have demonstrated that motion prediction in traffic scenes can be improved by recursively reasoning about future interaction between agents. We have also shown that multi-fidelity modeling can be effectively incorporated in the recursive prediction process.

Immediate directions for future work include extending our method to reason about multiple possible future scenarios (i.e. multi-modal scene motion prediction), incorporating a more flexible and diverse set of policy models, reasoning about input state uncertainty, and devising a more comprehensive set of experiments and performance metrics to evaluate our models. We aim to eventually implement a refined version of our algorithm on a real automated vehicle.

#### Acknowledgment

We appreciate the support of Prof. Mykel J. Kochenderfer for his thorough reviews and insightful suggestions.
