Prediction of route and destination intent shibumon alampatta
1 like789 views
This document discusses predicting a driver's intended route and destination using a Hidden Markov Model approach. It begins by outlining the problem and applications, such as route guidance and fuel efficiency. It then discusses using a probabilistic model to capture the sequential and routine nature of driving behavior. The model represents routes as a graph and states as links and goals. It is trained on past trip data to learn transition probabilities and predict the next link and destination. The approach achieves over 80% accuracy on average but has limitations for non-routine trips. Possible enhancements include additional parameters and expanding to other domains.
![Algorithmic Techniques
Hidden Markov Model [Simmons 2006][Froehlich
2008][Nagaraj 2011]
Artificial Neural Network [Miklu邸叩k 2012]
Nearest Neighbour algorithm [Yu 2011]
Genetic Algorithm [Kanoh 2008]
Bayesian Classifier [Cook 2004]
Support Vector Machines [Yu 2011]
Choice set Generation Model [Prato 2009]
Pattern Matching [Hattab 2012]
Plan Recognition [Cook 2004]
6](https://image.slidesharecdn.com/predictionofrouteanddestinationintentshibumonalampatta-130313113045-phpapp02/85/Prediction-of-route-and-destination-intent-shibumon-alampatta-6-320.jpg)
![References
[1] Reid Simmons, Brett Browning, Yilu Zhang, Varsha Sadekar, Learning to predict driver route and
destination intent, IEEE Intelligent Transportation System Conference, 2006
[2] Hitoshi Kanoh, Kenta Hara, Hybrid genetic Algorithm for Dynamic Multi Objective Route Planning
with Predicted Traffic in a Real World Road Network, Proceedings of the 10th Annual Conference
on Genetic and Evolutionary Computation, 2008
[3] John Froehlich, John Krumm, Route Prediction from Trip Observation, Society of Automotive
Engineers (SAE) World Congress, 2008
[4] Uma Nagaraj, N N Kadam, Study of Statistical Models for Route Prediction Algorithms in VANET,
Journal of Information Engineering and Applications, Vol 1, No. 4, 2011
[5] Carlo Giacomo Prato, Route Choice Modeling: Past, Present and Future Research Directions,
Journal of Choice Modeling, 2(1), pp. 65-100, 2009
[6] http://en.wikipedia.org/wiki/Hidden_Markov_model
[7] http://en.wikipedia.org/wiki/Markov_property
[8] Diane J Cook, Prediction Algorithms for Smart Environments, Chapter 8, Smart Environments:
Technology, Protocols and Applications, John Wiley & Sons, 2004
[9] M Al-Hattab, M Takruri, J Agbinya, Mobility Prediction using Pattern Matching, International
Journal of Electrical and Computer Sciences, Vol.12 No.3, 2012
[10] Tom叩邸 Miklu邸叩k, Michal Gregor, Ale邸 Janota, Using Neural Networks for Route and Destination
Prediction in Intelligent Transport Systems, 12th International Conference on Transport Systems
Telematics, 2012
[11] Bin Yu, William H.K. Lam, Mei Lam Tam, Bus Arrival Time Prediction at Bus Stop with Multiple
Routes, Transportation Research Part C: Emerging Technologies, Volume 19 Issue 6 pp. 1157
1170, 2011
25](https://image.slidesharecdn.com/predictionofrouteanddestinationintentshibumonalampatta-130313113045-phpapp02/85/Prediction-of-route-and-destination-intent-shibumon-alampatta-25-320.jpg)
Prediction of route and destination intent shibumon alampatta
- 1. Prediction of Route and Destination Intent Shibumon Alampatta (Roll No. 12CS60D02) Guided by: Prof. Arobinda Gupta 1
- 2. What is it About? Predict drivers intent intended route and destination Predict the goal and route; given current location Predict the route; given a goal(destination) and current location Image Courtesy: http://exploringthemind.com 2
- 3. Application Area Route Guidance in Navigation Improving Hybrid Fuel Economy 7.8% fuel economy, Research by Nissan (Froehlich 2008) Intelligent Transportation System VANET Points of interest and Advertisement 3
- 4. Ability to predict something normally comes from the Experience, Knowledge and Analytical skill to understand Patterns 4
- 5. A Prediction Model Real Time Input Past Future Model Data Prediction 5
- 6. Algorithmic Techniques Hidden Markov Model [Simmons 2006][Froehlich 2008][Nagaraj 2011] Artificial Neural Network [Miklu邸叩k 2012] Nearest Neighbour algorithm [Yu 2011] Genetic Algorithm [Kanoh 2008] Bayesian Classifier [Cook 2004] Support Vector Machines [Yu 2011] Choice set Generation Model [Prato 2009] Pattern Matching [Hattab 2012] Plan Recognition [Cook 2004] 6
- 7. Markov Model Captures sequential model of behavior Markov Property: Future is independent of past; given present <S, A, T> S(t-1) S(t) S(t+1) S : Set of States A : Set of Actions T: Transition function T: S x A x S R T(si, a, sj) = P(si| sj, a) Probability of transitioning to a state si; given that the system is in state sj and action a is executed In some cases explicit actions may not be there 7
- 8. Hidden Markov Model (HMM) A Markov Model with Hidden(Unobservable) States <S, A, O, T, Z, > Observation Hidden State O Finite set of Observations Z Observation function Current Intentions in Drivers Link Z:OxSxAR Mind Z(o, s, a) = P(o| s, a) Probability of receiving observation o, given system ends up in state s on executing action a For many problems Z(o, s, ai) = Z(o, s, aj), so we write Z(o, s) - Initial state distribution 8
- 9. HMM s1 s2 State Transition Representation o1 o2 o3 S(t-1) S(t) S(t+1) Sequential Representation O(t-1) O(t) O(t+1) 9
- 10. Predicting Drivers Intent Build the Intent Prediction Model Train the Model using Collected Trip Data Use the Model for Prediction 10
- 11. Building the Model Assumption Driving is mostly routine Past performance can be used to predict what the driver will do in future Route map and a GPS is available and can compute segment of the map the vehicle is on Routine nature of driving Tend to go to same destination again and again Tend to follow same route Same time Even when better alternatives exists (shorter or faster) 11
- 12. Building the Model Perfect prediction is not possible Example scenarios Conclusion: Prediction of driver intent is probabilistic So, we can make prediction with certain probability only But never be 100% sure about the prediction So we can use a probabilistic approach 12
- 13. Building the Model Road Graph Representation Model a Graph G(V, E) from the road map Vertices (v) for each intersection Link (l) unique labeling for an edge between two intersections Map Courtesy: maps.google.com 13
- 14. Building the Model We want to predict the intention that driver is going to have in his mind Based on intention in his mind he take turns State s = <l, g> ; l link, g - goal State Transition Function T(si, sj) = p(si|sj) <l, g> g l Image Courtesy: 14 depositphotos.com Map Courtesy: maps.google.com
- 15. Building the Model What we can observe? Current link ; ie segment on the road corresponding to current location Observation function Z(ol, s) = p(ol|<l, g>) which is 1 here Probability of current link being l given the system is in state s = <l, g> 15
- 16. Building the Model We can write the transition probability p(si|sj) as p(<li, gi> | sj ) = p(li | sj) p(gi | li) Given the current state, gi we first predict the next link that the driver will go li and then we predict his goal destination based lj on that link 16 Map Courtesy: maps.google.com
- 17. Building the Model Probability Computation gj li To compute p(gi|li) lj To compute p(li | sj) = p(li | <lj, gj>) 17
- 18. Building the Model Next Link Prediction Possible next states <l1,gi> <l2,gi> <l3, gi> Link li which scores maximum is predicted as c next link Map Courtesy: maps.google.com 18
- 19. Building the Model Next Link Prediction p(si|sj) = p(<li, gi> | sj) <l1, g1> <l1, g2> Score for l1 <l1, g3> <l2, g1> <l2, g2> Score for l2 <l2, g3> <l3, g1> <l3, g2> Score for l3 <l3, g3> 19
- 20. Building the Model - Prediction Predicting the goal/route given current link Using the ability to predict next link continue the prediction until we reach some goal or most probable goal Predicting route given goal Use this to bias the prediction of next link and continue prediction until we reach g 20
- 21. Training the Model Collect Trips data A Trip is an ordered list of links (<l1, t1>, <l2, t2>..) Go through and trip sequence, fill or update the tables. This helps in computing the probabilities Training data shall be reliable More the data; better accuracy Once Training is done; Use for prediction with real- time data 21
- 22. Past Trip Data Ability to predict something normally comes from the Experience, Knowledge and Analytical skill to understand Patterns Probabilistic Model 22
- 23. Observations Achieves more than 80% accuracy in average Can be harnessed for , route planning, traffic prediction, smarter route guidance emergency route etc. We can include the parameters like time of the day, day of the week etc. to state tuple to enhance the model Scenarios where routine nature is not maintained (sales people or delivery boys) Ad-hoc predictions are difficult (Like terrorists) 23
- 24. Summary Problem Definition Applications and Motivation Various Algorithmic Techniques HMM based model Limitations Possible enhancements Extension of application domains 24
- 25. References [1] Reid Simmons, Brett Browning, Yilu Zhang, Varsha Sadekar, Learning to predict driver route and destination intent, IEEE Intelligent Transportation System Conference, 2006 [2] Hitoshi Kanoh, Kenta Hara, Hybrid genetic Algorithm for Dynamic Multi Objective Route Planning with Predicted Traffic in a Real World Road Network, Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008 [3] John Froehlich, John Krumm, Route Prediction from Trip Observation, Society of Automotive Engineers (SAE) World Congress, 2008 [4] Uma Nagaraj, N N Kadam, Study of Statistical Models for Route Prediction Algorithms in VANET, Journal of Information Engineering and Applications, Vol 1, No. 4, 2011 [5] Carlo Giacomo Prato, Route Choice Modeling: Past, Present and Future Research Directions, Journal of Choice Modeling, 2(1), pp. 65-100, 2009 [6] http://en.wikipedia.org/wiki/Hidden_Markov_model [7] http://en.wikipedia.org/wiki/Markov_property [8] Diane J Cook, Prediction Algorithms for Smart Environments, Chapter 8, Smart Environments: Technology, Protocols and Applications, John Wiley & Sons, 2004 [9] M Al-Hattab, M Takruri, J Agbinya, Mobility Prediction using Pattern Matching, International Journal of Electrical and Computer Sciences, Vol.12 No.3, 2012 [10] Tom叩邸 Miklu邸叩k, Michal Gregor, Ale邸 Janota, Using Neural Networks for Route and Destination Prediction in Intelligent Transport Systems, 12th International Conference on Transport Systems Telematics, 2012 [11] Bin Yu, William H.K. Lam, Mei Lam Tam, Bus Arrival Time Prediction at Bus Stop with Multiple Routes, Transportation Research Part C: Emerging Technologies, Volume 19 Issue 6 pp. 1157 1170, 2011 25
- 26. Thank You 26