Part of the book series:Lecture Notes in Computer Science ((LNISA,volume 4206))
Included in the following conference series:
7255Accesses
Abstract
We describe a method calledPredestination that uses a history of a driver’s destinations, along with data about driving behaviors, to predict where a driver is going as a trip progresses. Driving behaviors include types of destinations, driving efficiency, and trip times. Beyond considering previously visited destinations, Predestination leverages anopen-world modeling methodology that considers the likelihood of users visiting previously unobserved locations based on trends in the data and on the background properties of locations. This allows our algorithm to smoothly transition between “out of the box” with no training data to more fully trained with increasing numbers of observations. Multiple components of the analysis are fused via Bayesian inference to produce a probabilistic map of destinations. Our algorithm was trained and tested on hold-out data drawn from a database of GPS driving data gathered from 169 different subjects who drove 7,335 different trips.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hu, P.S., Reuscher, T.R.: Summary of Travel Trends, 2001 National Household Travel Survey. U.S. Department of Transportation, U.S. Federal Highway Administration, p. 135 (2004)
Patterson, D.J., et al.: Opportunity Knocks: A System to Provide Cognitive Assistance with Transportation Services. In: Davies, N., Mynatt, E.D., Siio, I. (eds.) UbiComp 2004. LNCS, vol. 3205, pp. 433–450. Springer, Heidelberg (2004)
Cheng, C., Jain, R., Berg, E.v.d.: Location Prediction Algorithms for Mobile Wireless Systems. In: Wireless Internet Handbook: Technologies, Standards, and Application, pp. 245–263. CRC Press, Boca Raton (2003)
Krumm, J., Horvitz, E.: The Microsoft Multiperson Location Survey. Microsoft Research (MSR-TR-2005-103), Redmond, WA, USA (2005)
Karbassi, A., Barth, M.: Vehicle Route Prediction and Time of Arrival Estimation Techniques for Improved Transportation System Management. In: Proceedings of the Intelligent Vehicles Symposium (2003)
Marmasse, N., Schmandt, C.: A User-Centered Location Model. Personal and Ubiquitous Computing 2002(6), 318–321
Ashbrook, D., Starner, T.: Using GPS To Learn Significant Locations and Predict Movement Across Multiple Users. Personal and Ubiquitous Computing 7(5), 275–286 (2003)
Hariharan, R., Toyama, K.: Project Lachesis: Parsing and Modeling Location Histories. In: Egenhofer, M.J., Freksa, C., Miller, H.J. (eds.) GIScience 2004. LNCS, vol. 3234, pp. 106–124. Springer, Heidelberg (2004)
Liao, L., Fox, D., Kautz, H.: Learning and Inferring Transportation Routines. In: Proceedings of the 19th National Conference on Artificial Intelligence (AAAI 2004), San Jose, CA, USA (2004)
Gogate, V., et al.: Modeling Transportation Routines using Hybrid Dynamic Mixed Networks. In: Uncertainty in Artificial Intelligence (UAI 2005) (2005)
Letchner, J., Krumm, J., Horvitz, E.: Trip Router with Individualized Preferences (TRIP): Incorporating Personalization into Route Planning. In: Eighteenth Conference on Innovative Applications of Artificial Intelligence, Boston (2006)
Krumm, J.: Real Time Destination Prediction Based on Efficient Routes. In: Society of Automotive Engineers (SAE) 2006 World Congress, Detroit (2006)
Rish, I.: An Empirical Study of the Naive Bayes Classifier. In: IJCAI 2001 Workshop on Empirical Methods in AI (2001)
Angermann, M., et al.: Software Representation for Heterogeneous Location Data Sources Using Probability Density Functions. In: International Symposium on Location Based Services for Cellular Users (LOCELLUS 2001), Munich (2001)
Elfes, A.: Using Occupancy Grids for Mobile Robot Perception and Navigation. IEEE Computer 22(6), 46–57 (1989)
Author information
Authors and Affiliations
Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA, 98052, USA
John Krumm & Eric Horvitz
- John Krumm
You can also search for this author inPubMed Google Scholar
- Eric Horvitz
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Donald Bren School of Information and Computer Sciences, University of California, Irvine, 92697-3440, Irvine, CA, USA
Paul Dourish
Computing Department, Lancaster University, InfoLab 2, South Drive, LA1 4WA, Lancaster, UK
Adrian Friday
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krumm, J., Horvitz, E. (2006). Predestination: Inferring Destinations from Partial Trajectories. In: Dourish, P., Friday, A. (eds) UbiComp 2006: Ubiquitous Computing. UbiComp 2006. Lecture Notes in Computer Science, vol 4206. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11853565_15
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-39634-5
Online ISBN:978-3-540-39635-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative