Analytics & Cognitive Feature in CVI Series: Part-4 Most Probable Path & Destination Prediction

Overview

What is Most Probable Path & Destination Prediction (MPP&DP)

• Predicts the route in the near future and the destination by giving a partial route of current on-going trip and its context
  • In below example diagram, there are 4 candidates of destination and 5 probable path extracted from historical trips
  • A partial route of on-going trip is represented by orange colored arrow, and most probable path is represented by blue dot line where the predicted destination is office and the most probable path is Path 2.
• Based on the unsupervised machine learning
• Extracts the prediction model from historical car probe data per vehicle

Use-case examples with route/destination prediction

• Notification of dynamic road/traffic/weather condition information
• Route recommendation.
• Route optimization, for example based on gasoline or battery level.
• POI recommendation along the predicted route.
• Assistance information delivery around destination. For example, parking place availability, shopping mall coupon and so on.
• Arrival time estimation considering with current traffic information.

Architecture of MPP&DP

How to use: Steps to enable and execute MPP&DP

Summarized steps

1. Model generation
   1. Gather car probe data.
   2. Optional step. Configure parameters of prediction model generation.
   3. Create prediction model per moving object (vehicle).
   4. Optional step. Query Origin/Destination (O/D) patterns per moving object (vehicle).
2. Prediction
   1. Execute prediction per moving object (vehicle)

Detailed steps by sequence diagram

Algorithm overview: how to predict most probable path & destination

About MPP&DP model

• Actually, CVI's MPP&DP is based on the ensemble model consisting of 2 different types of prediction model
  • TPM: Trajectory pattern model (tpm_weight)
  • HMM: Hidden markov model (hmm_weight)
• Both models are based on unsupervised learning

Steps of model generation

• [Step 1] Common step for both model
  • Trajectory pattern algorithm extracts O/D pattern and its route patterns
    • See - Analytics & Cognitive Feature in CVI Series: Part-3 Trajectory Pattern Analysis about detail
• Each extracted route pattern has following information
  • The pattern id (unique id by uuid)
  • The related historical trip list
  • The list of link-id map-matched by DMM
    • The list of link-id comes from a representative trip from the related historical trip list
  • Context
    • weekday/weekend
    • day of the week
• [Step 2] Generation of prediction model
  • [Step 2-1] TPM: Trajectory pattern model
    • TPM utilizes the route pattern data extracted in [Step 1]
  • [Step 2-2] HMM: Hidden markov model
    • [Step 2-2-1] Extract the all of car probe data related to each route pattern extracted in [Step 1]
    • [Step 2-2-2] Count the <link-id, day of the week, time slot in a day>
      • Time slot period is 20 minutes
      • With this information, it is possible to calculate the transition probability from a <link-id, day of the week, time slot in a day> to each route pattern extracted from historical data
      • Briefly, this step generates below kind of matrix (below matrix only includes link-id)

Steps of prediction

• TPM
  • TPM compares the similarity between on-going trip and the list of link-id of each TPM model extracted in prediction phase
    • The incoming trip is translated into list of link-id
    • In addition, it considers the weekday/weekend context by comparing with incoming trip's timestamp
    • See Analytics & Cognitive Feature in CVI Series: Part-3 Trajectory Pattern Analysis how to calculate the similarity
• HMM
  • HMM compares the incoming trip and the matrix table extracted in [Step 2-2]
    • The incoming trip is translated to list of link-id, day of the week, time slot in a day
    • Briefly, the prediction calculation with the [Step 2-2]'s matrix can be presented by below diagram

• The ratio of TPM/HMM weight can be configurable as REST API parameters
  • Please refer to KC: Driver Behavior REST API > MPP&DP.prediction > GET/POST /mppdp/stateless/prediction
    • tpm_weight and hmm_weight

Characteristics

• TPM
  • Pros
    • It is faster to find UNKNOWN route because there is a threshold of minimum length to be matched
      • UNKNOWN means a new route that is different from the patterned routes
  • Cons
    • The comparison target is only a representative trip, therefore, it might tend to fail to predict especially around startup of trip
• HMM
  • Pros
    • It could support wider range of variation in patterned route
    • It is tolerant to DMM map matching error
  • Cons
    • It could pick up too much the possibilities
      • It might be difficult to judge the new route as UNKNOWN
      • There could be a lot of candidates of predicted routes with very small probability

Summary

• MPP&DP can predict the route in the near future and the destination by giving a partial route of current on-going trip and its context
• MPP&DP is ensemble model consisting of 2 different types of prediction model and utilizes the results of Trajectory Pattern Analysis

References

• Analytics & Cognitive Feature in CVI Series: Part-1 CVI Analytics Overview & Data Schema for Analytics
• Analytics & Cognitive Feature in CVI Series: Part-2 Driving Behavior Analysis
• Analytics & Cognitive Feature in CVI Series: Part-3 Trajectory Pattern Analysis

Notice

• Information in this blog is based on CVI SaaS V3.1. Information is subject to change in the future.

Revision History

• 2020-10-26: Initial release