{'fraction_non_alphanumeric': 0.03374265507899089, 'fraction_numerical': 0.006966679567925126, 'mean_word_length': 4.93609022556391, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Kinematic Models for Physically Realistic Prediction of Vehicle Trajectories

Self-driving vehicles (SDVs) hold great potential for improving traffic safety and are poised to positively affect the quality of life of millions of people. One of the critical aspects of the autonomous technology is understanding and predicting future movement of vehicles surrounding the SDV. This work presents a deep-learning-based method for physically realistic motion prediction of such traffic actors. Previous work did not explicitly encode physical realism and instead relied on the models to learn the laws of physics directly from the data, potentially resulting in implausible trajectory predictions. To account for this issue we propose a method that seamlessly combines ideas from the AI with physically grounded vehicle motion models. In this way we employ best of the both worlds, coupling powerful learning models with strong physical guarantees for their outputs. The proposed approach is general, being applicable to any type of learning method. Extensive experiments using deep convnets on large-scale, real-world data strongly indicate its benefits, outperforming the existing state-of-the-art.


Introduction
Self-driving vehicles (SDVs) have transformative potential benefits [1], not least of which is traffic safety. A recent study by NHTSA showed that human related errors such as distracted driving, illegal maneuvers, poor vehicle control, or drowsy driving are linked to nearly 94% of crashes [2]. SDV technology could prevent such avoidable accidents, and help reverse negative safety trends observed on the US roads in the past decade [3]. Beyond road safety, SDVs may provide social benefits due to easier and cheaper access to transportation, and environmental benefits through increased traffic efficiency and a transition from infrequently used private vehicles to shared vehicle fleets [4].
In order to operate an SDV in a safe and effective manner in a complex traffic environment, a number of complex problems need to be solved [1]. These include perceiving and understanding the current state of the traffic actors around the SDV, accurately predicting their future state, and efficiently planning future motion for the SDV through an uncertaint estimate of the future. In this work we focus on the problem of motion prediction of the surrounding vehicles, another key component necessary for safe autonomous operations.
There has been a significant recent interest by the research community in the task of predicting the future motion of nearby actors such as vehicles and pedestrians [5,6,7]. Most published work directly predicts future actor position with deep learning models. While this was shown to outperform previous state-of-the-art approaches, directly predicting future Cartesian positions imposes two issues, both of which are important for improved prediction and safe motion planning of the SDV [1]. First, it does not provide any guarantee of the kinematic feasibility for the predicted trajectories. Second, it often fails to accurately predict the actor's future headings (i.e., bounding box orientations) due to the lack of vehicle kinematics priors. In reality the vehicle motion is constrained by well-understood physical motion models, which need to be taken into account to improve SDV performance and safety. In this work we address these issues by embedding vehicle motion models [8] directly within a deep learning framework to predict the motion of vehicle actors. In this way we obtain powerful learning methods which have strong physical guarantees on their outputs. An Figure 1: Predicted right-turn trajectory before and after introduction of a kinematic vehicle model example of a predicted right-turning trajectory before and after introduction of kinematic vehicle model is shown in Figure 1. While the trajectory without the vehicle model appears reasonable, it is physically impossible for a two-axle vehicle to execute its motion in such manner because its rear wheels cannot turn. The proposed approach outputs a trajectory that is kinematically feasible and correctly predicts that the actor will encroach into the neighboring lane.
We summarize the main contributions of our work below: • We combine powerful deep methods with a kinematic two-axle vehicle motion model in order to output trajectory predictions with guaranteed physical realism; • While the idea is general and applicable to any deep architecture, we present an example application to a recently proposed state-of-the-art motion prediction method, using rasterized images of vehicle context as input to convolutional neural networks (CNNs) [7]; • We evaluate the method on a large-scale, real-world data set collected by a fleet of SDVs, showing that the system provides accurate, kinematically feasible predictions that outperform the existing state-of-the-art.
2 Related work

Motion prediction in autonomous driving
Accurate motion prediction of other vehicles is a critical component in many autonomous driving systems [9,10,11]. Prediction provides an estimate of future world state, which can be used to plan an optimal path for the SDV through a dynamic traffic environment. The current state (e.g., position, speed, acceleration) of vehicles around a SDV can be estimated using techniques such as a Kalman filter (KF) [12,13]. A common approach for short time horizon predictions of future motion is to assume that the driver will not change any control inputs (steering, accelerator) and simply propagate vehicle's current estimated state over time using a physical model (e.g., a vehicle motion model) that captures the underlying kinematics [9]. For longer time horizons the performance of this approach degrades as the underlying assumption of constant controls becomes increasingly unlikely. An alternative method explicitly models lane-following driving behavior by using map information as a constraint on the future position of other vehicles [10]. This approach first associates detected vehicles with one or more lanes from the map. Then, all possible paths are generated for each (vehicle, associated lane) pair based on map topology, lane connectivity, and vehicle's state. While the resulting predictions are reasonable for common cases, unusual scenarios are difficult to model.

Learned prediction models
An alternative to manually engineered prediction methods mentioned above is to learn a motion prediction model from the large amounts of driving data available. Classical machine learning approaches such as Hidden Markov Model [14], Bayesian networks [15], or Gaussian Processes [16] have been applied to motion prediction in autonomous driving. However, these methods require manually designed features and no longer provide state-of-the-art performance.
Most recent research on motion prediction employs deep networks. In one line of research, recurrent neural networks (RNN) with Long Short-Term Memory (LSTM) or gated recurrent unit (GRU) were applied to motion prediction, which have shown successful application in sequence prediction tasks [17]. Authors of [18] applied LSTM to predict pedestrian trajectories with social interactions. In [19] LSTM was applied to predict locations of a vehicle using past trajectory data. [20] used an LSTM-based graph neural network to simultaneously predict trajectories of vehicles, bicyclists, and pedestrians. Alternatively, [21] predicted motion of simple physical systems directly from image pixels by applying CNN to a sequence of visual glimpses. [22] presented a deployed system predicting short-term vehicle trajectories using feed-forward CNNs, using a bird's-eye view (BEV) raster image encoding actor's surroundings as an input. The approach was further extended to generate multimodal prediction output in [7]. [11] also encoded actor's surrounding context with a BEV image, but instead used an RNN to generate future occupancy maps of objects.
A related line of research is imitation learning, which addresses problems where future observations depend on previous predictions (actions) executed by the learner by learning to imitate expert demonstrations. Since previous predictions influence the future observation/state distributions encountered by the learner, [23] showed that a learner that makes mistakes with probability under the distribution of states visited in the expert demonstrations, may instead make as many as T 2 mistakes in expectation when executing its own predictions for T steps. As a consequence, the value of exploiting the regularization provided by an explicit motion model has long been recognized in the imitation learning community. For instance, inverse optimal control (IOC) approaches [24] reframe the problem as a learned reward function combined with an optimization function and an explicit state transition model (such as the bicycle kinematics model used in this work). The reward function can also be interpreted as a probability distribution over future action sequences, as done by [25] for taxi driver route prediction. More recently [26] presented R2P2, a novel normalizing flows version of this approach to predict a multimodal distribution over future vehicle trajectories, in conjunction with a simple constant velocity motion model with acceleration control inputs. However, R2P2 does not have the vehicle kinematics embedded in the model, and the actors can still get physically unrealistic trajectory predictions (e.g., a 90-degree turn). As is pointed out in the R2P2 work, training a multimodal trajectory predictor with a loss function that solely penalizes the log-likelihood of observed data under the model can lead to a lack of "precision" in the predicted trajectory set as low-probability predictions are only weakly penalized. They suggest adding an additional term to the loss function to penalize trajectory predictions by the model that are believed to be unlikely under the true distribution of predictions. In contrast to that work, here we improve the precision of multimodal predictions by enforcing constraints on the vehicle kinematic controls because only trajectories that obey these constraints are in the true distribution of predictions. Our proposed vehicle kinematic network is agnostic to the learning method and can be applied to related work (such as R2P2 [26] or ChauffeurNet [11]) as an alternative policy model that guarantees physical realism.

Vehicle motion models
Extensive work has been done on creating mathematical models of non-holonomic vehicle motion for the automotive industry [8]. Motion models for vehicles come in two broad classes, kinematic models that assume no wheel slip, and dynamic models that attempt to model complex interactions that occur when the tire forces are insufficient to fully overcome the inertia of the vehicle (i.e., the wheels are slipping). Past work on Model Predictive Control (MPC) has shown that a simple kinematic bicycle model is sufficient for modeling non-articulated vehicles performing normal driving maneuvers [27]. MPC typically uses known cost functions (i.e., behavior preferences of the predicted actors) and known dynamics models to define an optimization problem over potential vehicle trajectories [28,29], and a solver is used to find the sequence of vehicle control inputs that produces a minimum-cost vehicle trajectory (when integrated through the chosen vehicle model). By contrast, in our approach we leave both the cost functions and the optimization algorithm implicit in a deep neural network, similarly to an unrolled optimization approach described in [30].

Physically-realistic motion prediction
We assume there exists a functioning tracking system onboard an SDV, ingesting sensor data and allowing detection and tracking of traffic actors in real-time (e.g., using KF taking lidar, radar, or camera data as inputs). State estimates contain information describing an actor at fixed time intervals, bounding box, position, velocity, acceleration, heading, and turning rate. Moreover, assume access to map data of an operating area, comprising road locations, lane boundaries, and other relevant info. The resulting tracking and map data is used as an input to the proposed deep system.
.   Let us introduce the used notation. We denote overall map data by M, and a set of discrete times at which tracker outputs state estimates as T = {t 1 , t 2 , . . . , t T }, where time gap τ between consecutive time steps is constant (e.g., τ = 0.1s for tracker running at frequency of 10Hz). State output of a tracker for the i-th actor at time t j is denoted as s ij , where i = 1, . . . , N j with N j being a number of tracked actors at time t j . Then, given data M and all actors' state estimates up to and including t j (denoted by S j ), the task is to predict sequence of future states [s i(j+1) , . . . , s i(j+H) ], where s i(j+h) denotes state of the i-th actor at time t j+h , and H denotes the number of future consecutive time steps for which we predict states (or prediction horizon). Past and future states are represented in an actor-centric coordinate system derived from actor's state at time t j , where forward direction defines x-axis, left-hand direction defines y-axis, and actor's bounding box centroid defines the origin.

Unconstrained motion prediction
In this section we revisit the current state-of-the-art for vehicle motion prediction. The existing methods follow the same basic idea, as illustrated in Figure 2a. More specifically, the deep backbone network is trained to directly predict xand y-positions of future trajectory points (along with the estimated varianceσ), and full actor states are then derived from the inferred positions (i.e., velocities are derived from difference of consecutive positions, accelerations from consecutive velocities, and so on), without being constrained by vehicle kinematics. As we show in the experiments, this is suboptimal as it may lead to positions and higher derivatives (e.g., acceleration, heading) that are unrealistic and inaccurate. In the remainder, we use a recent method by [22] and [7] as an example of a state-of-the-art unconstrained method for motion prediction, using convnets as the backbone network operating on BEV rasters.
Let us assume a predictive model with parameter set θ, taking map M and state info S j as inputs at time t j (in the following we denote model outputs using the hat notation•, and for simplicity do not explicitly specify (θ, M, S j ) as arguments). The inputs are encoded as an overhead raster image to represent surrounding context for the i-th actor, used to predict trajectory of length H. Then, we introduce displacement error for the trajectory at horizon h ∈ {1, . . . , H}, defined as Euclidean distance between predicted and observed positions. Assume d i(j+h) is sampled from a half-Gaussian distribution as d i(j+h) ∼ F N (0,σ 2 i(j+h) ), whereσ 2 i(j+h) is the error variance at horizon h that the model outputs. Then, we write overall loss for the i-th actor at time t j as a negative log-likelihood of the observed data, equal to As described in [7], this formulation can be extended to multimodal predictions. In particular, instead of predicting one trajectory, the model outputs M modes and their associated probability p ijm modeled by a soft-max, with m ∈ {1, . . . , M }. At each step during training we find a predicted mode closest to the ground-truth trajectory, indexed by m * . Then, the final loss is defined as where I c is a binary indicator function equal to 1 if the condition c is true and 0 otherwise, L ijm is computed as (2) taking only the m-th mode into account, and α is a hyper-parameter used to tradeoff the two losses (i.e., log-likelihood of the observed data given a winning mode on one side, and a mode selection cross-entropy loss on the other). Note that, according to (3), we update the position outputs only for the winning mode and the probability outputs for all modes.
We can optimize eq. (3) over all actors and times in the training data to learn the optimal parameters, We refer to the method as Unconstrained Model (UM), producing multiple modes and their corresponding uncertainties (example of input raster and outputs is shown in Figure 3).

Constrained motion prediction
In this section we introduce a new kinematic layer between the final hidden layers of UM and its output layer, which explicitly encodes kinematics of a tracked two-axle vehicle. Assuming H prediction horizons, the kinematic layer consists of H kinematic nodes in a sequence, each implementing the same update equations of a kinematic vehicle model introduced below.
When predicting motion of the i-the actor at time t j , a kinematic node at horizon h implements the following function that governs the actor's motion at time t j+h , where state s i(j+h) comprises xand y-positions (x i(j+h) and y i(j+h) ), velocity v i(j+h) , and heading ψ i(j+h) , while a i(j+h) and γ i(j+h) are scalars representing longitudinal acceleration and steering angle applied at time t j+h , respectively. Then, we can compute the actor's state at the next timestamp t j+h+1 using the following equations [27], where we compute the above values as follows, Figure 4 illustrates the kinematic model, with variable subscripts representing actor and time removed for clarity. As can be seen, β is an angle between velocity vector and heading ψ, while l r and l f are distances from the vehicle center to the rear and front wheels, respectively. To ensure the predicted trajectories are physically realistic, controls a and γ are clipped to be within the vehicle physical constraints (−8 to +4m/s 2 , and ±45 • , respectively), while l r and l f are set to 1.41m, roughly equal to half-wheelbase of a midsize sedan.
The novel kinematic layer at the end of the deep network implements the above equations. The first kinematic node at h = 0 takes state at current time t j as input, and each subsequent node takes output of a previous node as its input. In addition, each node's control inputs a and γ are computed by a fully-connected layer (see Fig. 2b). It is important to emphasize that as the model still outputs positions, we solve the same optimization problem given in (3) and (4). Moreover, the kinematic model presented in equations (6) and (7) is fully differentiable, and lends itself to standard backprop training using exactly the same training data as the UM approach.
In the experiments we refer to the resulting deep architecture as Deep Kinematic Model (DKM). Note that the proposed method is a general solution, and while we introduce and evaluate it in the context of standard supervised learning and feed-forward convnets used in UM, it is straightforward to plug in the kinematic layer into other types of learning problems (e.g., imitation learning) and other types of deep models (e.g., RNNs).

Experiments
We collected 240 hours of data by manually driving in various conditions (e.g., varying times of day, days of the week, in several US cities), with data rate of 10Hz. This is the same frequency our internal Unscented Kalman filter (UKF) with the described kinematic state-transition model (using camera, lidar, and radar as inputs) was run on [31]. The filter is a default tracker on our fleet, trained on a large amount of labeled data. Each tracked vehicle at each discrete tracking time step amounts to a single data point, and once we removed all non-moving vehicles there remained 7.8 million data points. We considered horizons of up to 6s (i.e., H = 60), set α = 1, and used 3 : 1 : 1 split for train/validation/test data. We compared the following motion prediction methods: • UKF, propagating tracked state forward in time; • poly-n, modeling output trajectory with an n-degree polynomial curve, inferring scalar parameters q and r of the polynomial in the last hidden layer, as where we experimented with n ∈ {1, 2, 3}; • UM, unconstrained model from Section 3.1; • UM-velo, where instead of actual positions the model predicts differences between two consecutive positions, amounting to predicting velocity at each horizon without constraints (note that this is logically the same as policy model used in R2P2 [26]); • UM-LSTM, unconstrained model where an additional LSTM layer of size 128 is used to recursively output positions instead of simultaneously outputting positions for all horizons; • constrained model using the popular Constant Turning Rate and Acceleration (CTRA) motion model [32] in the last hidden layer; • DKM, the proposed deep model with a kinematic layer.
All models except the pretrained UKF were trained using the multimodal loss (4), outputting trajectories and their probabilities (we set M = 3). Models were implemented in TensorFlow using deep architecture and same training setup introduced in [7], with a per-GPU batch size of 64 and Adam optimizer [33]. The learning rate was set to 10 −4 and further decreased by a factor of 0.9 every 20,000 iterations, training for 400,000 iterations.

Results
For evaluation we considered each method's top-ranked trajectory, and report position errors (displacement, along-track, and cross-track [34]), as well as heading error that is of critical importance for downstream motion planning modules of the autonomous system. We also report percentage of unrealistic trajectories. We use simple conditions to label a trajectory as unrealistic: if for any horizon the turning radius is less than 3m or the absolute acceleration is larger than 10m/s 2 . For methods that do not output headings (e.g., UM), we interpolate their headings from the predicted positions. The results at 3sand 6s-horizons are shown in Table 1.  Figure 5: Log-scale histogram of ground-truth and predicted states at 6s horizon (left two: UM, right two: DKM); also shown Wasserstein distance between the two distributions Expectedly, the naïve UKF baseline gave the largest errors. Furthermore, we found that poly-n methods of varying degrees yielded very different results. The poly-1 approach amounts to a constantvelocity model that does not capture real-world behavior well, although it does guarantee predicted trajectories to be physically realistic, and it is not a surprise it is one of the worst-performing approaches. Nevertheless, we see that all metrics improved across the board compared to UKF, indicating that even simple curve fitting could provide benefits. The second-and third-degree polynomials (constant-acceleration and constant-jerk models, respectively) further improved position errors that were competitive compared to other methods, however with large heading errors and no physical realism guarantees. This can be explained by the fact that while curve fitting captured tracked positions well in a geometric sense, it overfitted to tracker noise thus resulting in unrealistic outputs.
Moving forward, we see that the three unconstrained state-of-the-art models, UM, UM-velo, and UM-LSTM, gave strong results in terms of the centroid position prediction. This especially holds true in the short term, where position errors are on par with the best-performing DKM method. Interestingly, although outputs of UM and UM-velo are quite different (where former directly predicts positions, and latter predicts velocities), the results are near-identical, and both of them have about 30% of their trajectory predictions being physically unrealistic, mostly due to the predicted turning radius being too small. Since the proposed DKM infers vehicle controls, we specifically included UM-velo as it gives outputs that can be interpreted as controls as well. Through this comparison we wanted to evaluate if such unconstrained controls outputs could lead to improvements over unconstrained position outputs, however this is not corroborated by the empirical results. It is interesting to discuss UM-LSTM, which showed very good performance in terms of position errors but poor in terms of heading and unrealism metrics. The recurrent structure of LSTM mirrors structure of the kinematic layer, and in theory the LSTM could learn to approximate the update function of the proposed vehicle model given enough data. However, we can see that directly encoding prior knowledge in a form of the proposed kinematic layer leads to better-performing, simpler architecture.
Lastly, we evaluated constrained approaches using two different vehicle models at their output. CTRA is a model shown to capture vehicle motion well [32]. However, when compared to unconstrained models it is clear that the method underperformed, although it is competitive in terms of physical realism. The DKM method gave the best performance, as it improves the heading errors by a large margin and its trajectories are guaranteed to be physically realistic. This strongly suggests benefits of combining powerful deep methods with well-grounded kinematic models.
In Figure 5 we provide a more detailed analysis of the higher derivatives of output trajectories for UM (top) and DKM (bottom) methods. In particular, we investigated the distributions of acceleration  Figure 6: Actor states predicted by competing methods for commonly encountered traffic situations; first column shows input raster with overlaid output trajectories, followed by columns showing profiles of output velocity, acceleration, heading, and turning rate, respectively and turning rate of the inferred trajectories, and how they compared to the distribution of the groundtruth values. We report Wasserstein distance (WD) to quantify differences between the distributions, given in each subfigure. While in both cases distribution of DKM-computed values was closer to the ground truth, this especially holds true for turning rate where the improvement was substantial, as indicated by more than two times smaller WD. Note that y-axes are given in log-scale, and both tails of the ground-truth distribution represent rare events and outliers.

Case studies
Next we provide a deeper analysis of situations often encountered on roads, and compare performance of several methods (representative unconstrained method UM, and two best-performing constrained methods, poly-2 and DKM). We analyzed the following cases: a) actor in a right-turn lane; b) approaching red traffic light and braking for stopped vehicles. We present the results in Figure 6, where the first column gives input raster image with overlaid color-coded top-ranked output trajectory of each method, followed by time series of predicted actor states.
In the first case all three models correctly predicted that the actor is going to make a right turn at the intersection. We can see that DKM, in addition to accurate position estimates, also outputs smooth acceleration and heading profiles. On the other hand, UM does predict reasonable positions, however acceleration and turning rate are very noisy. It is interesting to consider poly-2, which similarly to DKM also gives smooth outputs. While this results in more realistic profiles of all physical measures, the method is too constrained and gives a trajectory that cuts the corner and then overshoots the turn (shown as a dark green trajectory in the first column). Similarly to the CTRA method (results not shown), these approaches may be overly constrained and not capable of fully capturing vehicle motion during more complex maneuvers.
In the second case all models predicted the actor to come to a stop. Note that poly-2, which amounts to a constant acceleration method, at one point starts predicting that the actor will move in reverse. On the other hand, acceleration profile of DKM best corresponds to the ground truth with a very smooth deceleration, while UM again gives noisy acceleration and heading estimates.

Conclusion
We presented a method addressing a critical task of motion prediction of traffic actors, guaranteeing that predicted motion is kinematically feasible. The approach combines powerful deep learning algorithms on one side and vehicle models developed in robotics on the other. While the method is general and can be used with any machine learning algorithm, including convolutional and recurrent deep networks, we evaluated the approach using convnets as an example. Extensive experiments on real-world, large-scale data collected by a fleet of SDVs strongly indicated its benefits, with the proposed method outperforming the existing state-of-the-art.