Efficient Cost­based Tracking Of Scheduled Vehicle Journeys

Efficient Cost­Based Tracking  of Scheduled Vehicle Journeys Dalia Tiesyte, Christian S. Jensen, Aalborg University, Denmark MDM 2008, April 27­30

 

Outline • • • • • •

Introduction Update policies The cost function Experimental results Conclusions Q/A

 

Problem Setting Aim: To track bus locations with accuracy guarantees

Objective: To reduce cost of communication between bus  and server  

3

Problem Setting (cont.) •

Assumptions  

 

•

The vehicles are traveling on known routes. The vehicle receives its position from GPS and forms movement  f act function       . f sh The vehicle and the server share the prediction function       . The central tracker (server) can change its prediction to new  f ct prediction      .

Problem 



Minimize the number of updates in­between the vehicle and the  server. Preserve the accuracy guarantees.

Predicted position Actual position within circle

 

Tracking and Prediction Prediction

Vehicle

position  update

position

Shared Prediction

prediction  update

14 18:05 Center 2 18:25 Airport

Server predicted position

Shared Prediction Server’s  Prediction

 

Traffic Information

State of the Art • Tracking algorithms 

Shared prediction function and accuracy guarantees.  [Čivilis et al., Wolfson et al., etc.]

• Travel time prediction algorithms for vehicle  trajectories on known routes (e.g., buses) 

Kalman filter [Cathey and Dailey 2003, Shalaby and Farhan 2001, Dailey et  al. 2004]



Artificial Neural Networks [Chien et al. 2002, Park et al. 2004, Hee  and Rilett 2004]

 

Existing Tracking Approach Client

Server predict position fact

compare with GPS

receive update

[out of threshold thr]

update DB

[existing trip] [within threshold thr]

get GPS

[finish]

[initialize trip]

store update data

[continue]

send update

store settings

receive settings

 

new  prediction fsh [initialize trip]

send new prediction

7

New Tracking Approach Client

Server predict position fact

compare with GPS

receive update

[out of threshold thr]

update DB

[existing trip] [within threshold thr]

get GPS

[finish]

[initialize trip]

store update data

[continue]

send update

store settings

receive settings

 

[new  information]

new  prediction fsh [existing trip]

[initialize trip]

send new prediction

8

Position update Policies •

Timing point­based tracking 

•

Position­based tracking 



•

The updates are issued at  defined points on the route.  Update when the GPS position  deviates by threshold from the  server’s predicted position. Provides position accuracy  guarantees.

Time­based tracking 



Update when the vehicle’s  predicted arrival time deviates  by threshold from the server’s  predicted arrival time. Can be more efficient than  position­based tracking, but  provides poor position accuracy  guarantees.

 

Server’s Updates • The server and the vehicle split the threshold. 

thrv + thrs = thr

• Always update when the server’s prediction changes. Problem: possibly too frequent  updates from the server to the vehicle.

• Update only when the server’s threshold is reached. Problem: possibly too frequent updates from the vehicle to the server.

• Update either when:  

the server’s threshold has been reached, or the update would reduce further communication costs.

 

Tracking Example Actual movement fact

update Shared Prediction fsh thrv Server’s Prediction fct < thrs  

The COST Function • Assumptions:  

The prediction can only improve. The prediction error has Gaussian distribution with mean 0.

• The cost function depends on:    

The difference between the old and the new prediction functions. The reliability of the server’s prediction. The accuracy thresholds. The COST function itself.

 

The Cost Function (cont.) • Estimates further communication costs of the  journey. • Actual costs:

costtotal = update _ number × costup • Estimated costs (costs of the expected average  number of updates):

costtotal = ∑ P (update _ number = i ) × i × costup i

 

The Cost Function (cont.) •

Assuming that no server updates happen,

Shared prediction

P(upv = i ) = P(thrv i <| f act (t ) − f sh (t ) |< thrv (i + 1)) Actual prediction The deviation between the actual and the predicted trajectories is the  prediction error: 

err (t ) =| f act (t ) − f sh (t ) | Estimate how often the server’s prediction changes

t = tcur + ∆t  

Assume Gaussian distribution

Experimental Settings •

Compare the policies:   

• •

Update the vehicle when server’s prediction has changed. Update the vehicle when the threshold thrct is reached. Update the vehicle according to the cost function.

Evaluate the total number of updates. Default parameters: Initial prediction variance  GPS delay GPS delay start  GPS delay end  Server prediction variance  Average delay detection time  Server and vehicle thresholds thrct,thrv

100 s 600 s 0.25 0.75 50 s 300 s 400m (100 s) 1 50

Single update cost Number of timing points 

 

Experimental Results – Variance (PBT) up

up

Only slight increase

More gain with less accuracy var

var

 

Experimental Results – Threshold (PBT)

Small thr – update always Small thr – large increase

 

Conclusions • We have defined update policies:   

Timing­point based. Time­based threshold. Position­based threshold.

• We have defined a cost function. • Communication costs can be reduced significantly  compared to the timing­point based update policy. • In the future, we need to 



Develop a cost model that would compute the minimum  communication costs. Reduce updates by improving prediction.

 

Q/A

Thank You! 

 

Problem Setting (cont.) Minimize costs

14 18:05 Center 2 18:25 Airport

Maintain accurate state

GPS

Prediction Position

Central server Traffic Information

Problems: • • •

The algorithms that predict  travel times are not accurate. The communication is costly. Accuracy guarantees are  required.