Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Mathematics for trajectory extrapolation
using vehicle and human traffic data
towards zero traffic fatalities
Final Presentation, G-RIPS 2023
August 7, 2023
Melissa Adrian,

The University of Chicago

Mentors:

Namito Asano,Musashino University

Natsuo Miyatake, Tohoku University

Ann Mwangi,

African Institute for Mathematical Sciences

Masao Ono,

Tomoki Okamoto, Musashino University
Aaron Scheiner,

Northwestern University

IHI Corporation

Date of presentation August 7, 2023.
Revised August 8, 2023.
Finalized by mentors August 10, 2023.
Available online August 25, 2023.
IHI Doc. No. HAPD116432.

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Outline● Introduction● Data Exploration & Preprocessing● Methods● Gaussian State-Space Model● Ensemble Kalman Filter (EnKF) and Smoother (EnKS)● Car Following Model● 2D to 1D Coordinate Conversion● Conclusion● Future Directions
2

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Introduction

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Motivation [1]Why do we analyze traffic data?
● Drastically improve both safety and mobility in traffic systems● Feed data to autonomous vehicles both for in-house development and on-road transmission
What is our group doing?
● Filtering out noise● Extrapolating trajectories from partial data
What are our main end goals?
● To reduce the number of traffic sensors needed at an intersection● To develop an advanced technology for traffic flow analysis
based on actual driver’s behavior
4

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Problem Statement●●●A traffic sensor inevitably yields occluded regions due to overlapping objects.
This leads to incomplete trajectories, hindering the analysis of incidents and congestion.
At a typical crossroad, 4 sensors give full data, and anything less results in incomplete data.
Traffic sensor
Occluded region

VehicleVehicleTraveling direction
5

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Problem Statement●●●A traffic sensor inevitably yields occluded regions due to overlapping objects.
This leads to incomplete trajectories, hindering the analysis of incidents and congestion.
At a typical crossroad, 4 sensors give full data, and anything less results in incomplete data.
Traffic sensor

AA
pair
pair
ofof
sensors
sensors
is isneededneededfor
foreacheachtravelingtravelingdirection.
direction.

VehicleTraffic sensor

VehicleTraveling direction
6

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Problem Statement●To address the issue, we want to generate continuous data of driving behaviors
by extrapolating physically probable values from incomplete traffic flow data.
Traffic sensor

AA
pair
pair
ofof
sensors
sensors
is isneededneededfor
foreacheachtravelingtravelingdirection.
direction.

VehicleTraffic sensor

VehicleTraveling direction
7

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Data Description●●●

Each vehicle has 2D time series position (x, y) on the local coordinate system.
Each vehicle is given labels of an inflow direction and an outflow direction at an intersection.
“Unknown” is given to the vehicles whose trajectory is incomplete in the intersection.
Examples of trajectories at an intersectiony [m]Complete trajectoryfrom “East” to “North”

Intersection

East sidex [m]North side8

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Data Description●●●

Each vehicle has 2D time series position (x, y) on the local coordinate system.
Each vehicle is given labels of an inflow direction and an outflow direction at an intersection.
“Unknown” is given to the vehicles whose trajectory is incomplete in the intersection.
Examples of trajectories at an intersection

y [m]Incomplete trajectoryfrom “East” to “Unknown”

Intersection

East sidex [m]North side9Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Data Exploration & Preprocessing

10

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Lanes and Lane Changesy [m]Examples of intersection behavioraround lanes include:● Inner, outer, and center lanes● Lane changes before the intersection● Lane changes in the intersection

Intersection

x [m]

11

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Our Spatial Region of Interesty [m]We decided to only estimate
trajectories within the box.
This box represents the intersection,
where each edge is a crosswalk inthe intersection.

x [m]

12

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Preprocessing the Reference Trajectoryy [m]We experimented with linear interpolation,
cubic spline and quadratic spline techniques
to come up with a suitable smooth curve
representing the reference trajectories.

A smooth curvex [m]A reference trajectory (shown by some way-points)
which represents an average path of vehicles
13

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Methods

14

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Defining terms in our traffic context
Latent statescar 1’s position and velocity at time t
car 2’s position and velocity at time t

Observations

car 1’s position at time t
car 2’s position at time t
Example:Observation operator
both cars visiblecar 1 hidden
15

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Gaussian State-Space Model [2]car-following model: latent states at time t: operator mapping the latent space from time t-1 to t
parameterized by: measurement error variance-covariance matrix
parameterized by16

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Gaussian State-Space Model [2]: latent states at time t: observations at time t: operator mapping the latent space from time t-1 to t
parameterized by: operator mapping the latent space to theobservation space at time t (known): measurement error variance-covariance matrix
parameterized by(can also depend on time): observation error matrix at time t (known)

17

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Gaussian State-Space Model [2]assumed known: latent states at time t: observations at time t: operator mapping the latent space from time t-1 to t
parameterized by: operator mapping the latent space to theobservation space at time t (known): measurement error variance-covariance matrix
parameterized by: observation error matrix at time t (known)

18

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Gaussian State-Space Model [2]: latent states at time t: observations at time t: operator mapping the latent space from time t-1 to t
parameterized by: operator mapping the latent space to theobservation space at time t (known): measurement error variance-covariance matrix
parameterized by: observation error matrix at time t (known)

Goal: Estimatefor19

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Filter [2]Two step procedure:
1. Forecast into the future using the car following model

ensemble index(forecast)car-following model20

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Filter [2]Two step procedure:
1. Forecast into the future using the car following model(forecast)2. Analysis based on observational data up to time t(analysis)

𝜂𝑡𝑛Kalman gain
- specifies the weight given tothe observations vs. the predictions
21

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Filter [2]Forecast ensemble𝑋෠𝑡Analysis ensemble
𝑋𝑡−1

𝑌𝑡+1

forward model

𝑋𝑡+1
KF update

KF updateObservational data
𝑌𝑡−1forward model

𝑋𝑡

𝑋෠𝑡+1

𝑌𝑡
Time𝑡−1𝑡
Assimilation steps𝑡+122

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Filter [2]Forecast

Forecast ensemble𝑋෠𝑡Analysis ensemble
𝑋𝑡−1

forward model

Observational data
𝑌𝑡−1

A car following model forecasts its latent states.
(How many steps ahead should be forecasted depends on reaction time of drivers)
𝑌𝑡Time𝑡−1𝑡Assimilation steps

𝑡+1
23

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Filter [2]Analysis

Forecast ensemble𝑋෠𝑡Analysis ensemble
𝑋𝑡−1

forward model

KF update withKalman gain 𝐾𝑡
and observation operator 𝐻𝑡

Observational data
𝑌𝑡−1𝑋𝑡𝐾𝑡 specifis
the weight given to𝑌𝑡 vs. 𝑋෠𝑡 .

𝐻𝑡 specifies the binary:visible or hidden.

𝑌𝑡Time𝑡−1𝑡Assimilation steps𝑡+1
24

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Smoother [3]Two step procedure:
1. Perform EnKF to obtain estimatesfor.

2. Analysis based on observational data up to time t+L𝑛𝜂𝑡+𝑙(analysis)
EnKF analysis(result with no look-ahead )25

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Smoother [3]Two step procedure:
1. Perform EnKF to obtain estimatesfor.

2. Analysis based on observational data up to time t+L(analysis)# of look-ahead time steps
𝑛𝜂𝑡+𝑙

26

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Smoother [3]Two step procedure:
1. Perform EnKF to obtain estimatesfor.

2. Analysis based on observational data up to time t+L𝑛
𝜂𝑡+𝑙(analysis)-Kalman gain between times t and t+l
Scales the residuals based on:- covariance between times t and t+l27

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Ensemble Kalman Smoother [3]Two step procedure:
1. Perform EnKF to obtain estimatesfor.

2. Analysis based on observational data up to time t+L(analysis)𝑛𝜂𝑡+𝑙
Residual of observation vs. prediction

28

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Car Following Model [4]Gipps model is a car following model featured by a safety distance between vehicles.
・The purpose of this model is to have a following vehicle maintain the distance.

・The following vehicle can safely stop even if the preceding vehicle brakes suddenly.
Traveling direction

Following (modeling target)

𝑛Safety distancePreceding𝑛−129

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Car Following Model [4]Gipps model is a car following model featured by a safety distance between vehicles.
・This model is relatively simple compared to other models.
・However, it seems to have sufficient expressive power for modeling of
the driver’s behavior in typical intersections.
Traveling direction

Following (modeling target)

𝑛Safety distancePreceding𝑛−130

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Car Following Model [4]Velocity of the following vehicle 𝑛deceleration
is estimation of maximum deceleration desired by n-1

31

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Car Following Model [4]Velocity of the following vehicle 𝑛Issue: the above model can describe the behavior of a following vehicle
only in the one-dimensional space such as a straight lane.
32

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Curvilinear Coordinate Conversion [5]We decided to use curvilinear coordinate conversion in order to change a 2-D problem
to a 1-D problem.
In Cartesian coordinates, the position is represented by straight vertical and horizontal axes.
In Curvilinear coordinates, the position is represented by a straight axis and a curved axis:
lateral (n) and longitudinal (s) along the lane.

Cartesian coordinates

Curvilinear coordinates

1𝜅𝑏𝑦(𝑥, 𝑦)𝑛𝑠𝜅𝑏𝑠𝑥33

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Curvilinear Coordinate Conversion [5]We decided to use curvilinear coordinate conversion in order to change a 2-D problem
to a 1-D problem.
In Cartesian coordinates, the position is represented by straight vertical and horizontal axes.
In Curvilinear coordinates, the position is represented by a straight axis and a curved axis:
lateral (n) and longitudinal (s) along the lane.

Cartesian coordinates

Curvilinear coordinates1
𝜅𝑏𝑦(𝑥, 𝑦)𝑛𝑠𝜅𝑏𝑠𝑥Assume that the lateral motion is sufficiently small so that the n-coordinates can be ignored.

34

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Computationally Tractable Method
Then, we attempted the conversion using the curvature 𝜅𝑏 , but faced computational
issues such as difficulty in applying to straight lines and complicated curves.

(x, y) reference trajectory

converted trajectory
only using s coordinate35

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Computationally Tractable Method
By considering that “s” stands for the distance along reference trajectories,
we had conclusion that the line segment distance method is suitable.
We add these up to the closest reference trajectory point to an x and y point,
and that sum is the s coordinate.

(x, y) reference trajectory

converted trajectory
only using s coordinate

36

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results37

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results● We are describing the following results :○ Assigning Labels to Unknown Trajectory Directions.
○ Denoising.
○ Extrapolating Trajectories.

38
38

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Assigning Labels to Unknown Trajectory Directions● We :
1. Pulled out vehicles' data having unknown trajectory directions
from the given dataset.

3939Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Assigning Labels to Unknown Trajectory Directions● We :
2. Quantified the similarities between the observational trajectory andeach reference trajectory by calculating mean squared error (MSE).

40
40

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Assigning Labels to Unknown Trajectory Directions● We :
3. Assigned directions of the reference trajectory having minimum MSE(MSEmin) to the observational trajectory.

41

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Assigning Labels to Unknown Trajectory Directionsy [m]East sideThis trajectory was marked“East” to “Unknown.”(orange makers)
We matched it to the “fromEast to North Outer Lane”
reference trajectory.
(blue markers)

North sidex [m]42Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Denoising

Parameters (not optimized yet)
● Forward model: Gipps ● Gipps noise level: 𝑄 = 𝑞𝐼 = 0.5𝐼
● Obs. noise level: 𝑅 = 𝑟𝐼 = 0.05𝐼● EnKS lookahead: 7

Results for tracking one vehicle through the intersection
Gipps forecast and EnKF/EnKS analysis can be assimilated into the trend of velocity.
Position

Velocity

Acceleration

4343

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Denoising

Parameters (not optimized yet)
● Forward model: Gipps ● Gipps noise level: 𝑄 = 𝑞𝐼 = 0.5𝐼
● Obs. noise level: 𝑅 = 𝑟𝐼 = 0.05𝐼● EnKS lookahead: 7

Results for tracking one vehicle through the intersection
The forward model have no information on 2nd or higher derivative of “s.”Thus, the acceleration cannot be estimated, and the noise is amplified compared to the complete observation.
Position

VelocityAcceleration

4444

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Denoising

Parameters (not optimized yet)
● Forward model: Gipps ● Gipps noise level: 𝑄 = 𝑞𝐼 = 0.5𝐼
● Obs. noise level: 𝑅 = 𝑟𝐼 = 0.05𝐼● EnKS lookahead: 7

Results for tracking one vehicle through the intersection
The forward model have no information on 2nd or higher derivative of “s.”Thus, the acceleration cannot be estimated, and the noise is amplified compared to the complete observation.

Important takeaways:
If both vehicles are visible, we should pay attention to the forward model as follows:• Suppress its forecast (in practice, specifying 𝑟 to be very small and 𝑞 to be very large)• Adopt a forward model whose errors are on a smaller scale compared to theobservations (whose errors, however, are very small as far as vehicles are visible) .
45
45

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Extrapolating Trajectory(See the next side)46
46

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Results
Objective : Extrapolating Trajectory

47
47

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Conclusion

48

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Conclusion● We worked on :○ Filtering out observation data noise.
○ Extrapolating trajectories from given partial data.
In order to● Reduce the number of traffic sensors needed at an intersection.
● Develop an advanced technology for traffic flow analysis
using continuous data of actual driver’s behavior
49
49

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Conclusion● We used :○ Ensemble Kalman smoother (EnKS).
○ Gipps model.
When● We :○ Filtered out observation data noise.
○ Completed partial vehicle trajectories.
5050

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Conclusion● We :○ Implemented a tractable method for assigning probable labeles
to trajectories with “unknown” directions.

○ Validated estimation performance of a proposed smoothing method
based on Gipps model and EnKS.

○ Devised an algorism for extrapolating incomplete trajectoryby integrating all proposed methods in this project.

51
51

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Future Directions

52

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Future Directions● Improvements to the forward model○ Fine-tune the Gipps model parameters based on our dataset○ Consider more expressive models, such as a 2D prediction framework
and a model with higher order derivative (acceleration and jerk)● Improvements to the data assimilation framework○ Account for spatial correlations between vehicles
to increase effective ensemble size○ Assimilate temporally intermediate observations
between the forward model passes
5353

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

Acknowledgements
We appreciate everyone involved in the program, such as● g-RIPS staff● our academic mentor, Natsuo-san● our industrial mentor, Ono-san● Institute for Pure and Applied Mathematics (IPAM) at UCLA
● Tohoku University Advanced Institute for Materials Research (AIMR)

Thank you for listening!

54
54

Copyright © 2023 IHI Corporation and Tohoku University All Rights Reserved.

References[1] Realizing a sustainable mobility society with traffic flow data, IHI Engineering Review, 56(1), 2023.
Available online: https://www.ihi.co.jp/en/technology/techinfo/contents_no/1199408_13586.html[2] Geir Evensen.
The Ensemble Kalman Filter: Theoretical formulation and practical implementation,
Ocean Dynamics, 53(4), 343–367, 2003.

[3] Geir Evensen, Peter Jan, and Van Leeuwen.
An ensemble kalman smoother for nonlinear dynamics,
Monthly Weather Review, 128, 1852–1864, 2000.
[4] Johan Janson Olstam and Andreas Tapani.
Comparison of Car-following models,Swedish National Road and Transport Research Institute: Linkoping, Sweden, 2004.
[5] Junsoo Kim, K. Jo, Wontaek Lim, Minchul Lee, and M. Sunwoo.
Curvilinear-Coordinate-Based Object and Situation Assessment for Highly Automated Vehicles,IEEE Transactions on Intelligent Transportation Systems, 16, 1559–1575, 2015.
5555