Its 2007

Recovery of Vehicle Trajectories from  Tracking Data for Analysis Purposes Dalia Tiešytė, Christian S. Jensen  {dalia,csj}@cs.aau.dk

ITS 2007, Aalborg, Denmark

The TransDB Project  • TransDB: www.cs.aau.dk/TransDB)   

Vehicle tracking with focus on scheduled journeys Historical data analysis Prediction of travel times and improvement of  schedules

Historical  positions

Statistical  analysis

Travel patterns

Tracking GPS data

Tracking

Prediction

PerTrans, 23 March 2007, White Plains, NY, USA

Scheduling

2

The Tracking System ­ Example Historical data repository

GPS Position Position

2 18:05 AAU Busterm

Central server

Position-related information

Threshold­ based  tracking

Process  position­related  data PerTrans, 23 March 2007, White Plains, NY, USA

3

Roadmap • Background 

Tracking, prediction, and historical data analysis

• Problem statement  

The trajectory function The most optimal trajectory

• The recovery algorithm • Analysis and experimental results • Discussion

PerTrans, 23 March 2007, White Plains, NY, USA

4

Background • Tracking algorithms 

Shared movement prediction  [Čivilis et al., Wolfson et al., etc.]

pos (t ) = f ( posup , tup ) • Movement prediction functions   

Linear movement function. Deviation from the schedule. Advanced prediction (e.g., neural networks).

• Recovery of vehicle trajectories 

Assume linear movement in­between updated points.

PerTrans, 23 March 2007, White Plains, NY, USA

5

Position Threshold­Based Tracking • Share the vehicle’s movement function between  the server and the vehicle. • Update when the GPS position deviates by  threshold thr from the server’s predicted position. • Position accuracy guarantees (thr).

PerTrans, 23 March 2007, White Plains, NY, USA

6

Problem Statement • Available data: 



A sequence of position updates with accuracy  guarantees. Movement prediction function.

• Recover vehicle’s trajectory that:  

Is as close as possible to the actual trajectory. Preserves accuracy guarantees.

PerTrans, 23 March 2007, White Plains, NY, USA

7

Recovery of Trajectories   v = vmax

The updated position is  later than expected

The updated position is  later than expected

Assume the max. speed       v      max  before the update

Assume the min. speed (0)  before the update

PerTrans, 23 March 2007, White Plains, NY, USA

8

Analytical Study • The recovered (expected) trajectory fexp 

Preserves accuracy guarantees thr:

| f exp (t) – f act(t)| ≤ thr 

Is at least as close to the actual trajectory fact  as the initial prediction.

| f exp (t) – f act(t)| ≤ | f pred (t) – f act(t)|



Is the “best” recovery with the given data.

′ (| f exp (t) – f act(t)| ≤ | f exp ′ (t) – f act(t)|) ∀f exp PerTrans, 23 March 2007, White Plains, NY, USA

9

Experimental Results

PerTrans, 23 March 2007, White Plains, NY, USA

10

Discussion • The proposed techniques recover close­to­actual  trajectories of vehicles. 

The “best” with the given data.

• They may be used for…   

pattern mining, better predictions of future trajectories, better scheduling,…

• Possible future research directions  

Use all available constraints (e.g., speed limits). Investigate, how the recovered trajectories can be used  by similarity functions, clustering algorithms, etc. PerTrans, 23 March 2007, White Plains, NY, USA

11

Acknowledgements •             

Nordjyllands Trafikselskab (NT) www.nordjyllandstrafikselskab.dk

•                Telenor Connect A/S (TNC Connect)                    www.telenorconnect.com

•                Forskningsstyrelsen (Danish research  agency) www.forsk.dk

•              Aalborg University and           Daisy group daisy.aau.dk

PerTrans, 23 March 2007, White Plains, NY, USA

12

Thank you! 



 

Questions

?

PerTrans, 23 March 2007, White Plains, NY, USA

13