William Groves
ABSTRACT
We propose a novel framework for predicting the paths of vehicles that move on a road network. The framework leverages global and local patterns in spatio-temporal data. From a large corpus of GPS trajectories, we predict the subsequent path of an in-progress vehicle trajectory using only spatio-temporal features from the data. Our framework consists of three components: (1) a component that abstracts GPS location data into a graph at the neighborhood or street level, (2) a component that generates policies obtained from the graph data, and (3) a component that predicts the subsequent path of an in-progress trajectory. Hierarchical clustering is used to construct the city graph, where the clusters facilitate a compact representation of the trajectory data to make processing large data sets tractable and efficient. We propose four alternative policy generation algorithms: a frequency-based algorithm (FreqCount), a correlation-based algorithm (EigenStrat), a spectral clusteringbased algorithm (LapStrat), and a Markov Chain-based algorithm (MCStrat). The algorithms explore either global patterns (FreqCount and EigenStrat) or local patterns (MCStrat) in the data, with the exception of LapStrat which explores both. We present an analysis of the performance of the alternative prediction algorithms using a large real-world taxi data set.
- J. Bergstra, R. Bardenet, Y. Bengio, B. Kégl, et al. Algorithms for hyper-parameter optimization. In Conf. on Neural Information Processing Systems (NIPS), 2011.Google Scholar
- F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.Google Scholar
- J. Froehlich and J. Krumm. Route prediction from trip observations. In Society of Automotive Engineers (SAE) 2008 World Congress, 2008.Google ScholarCross Ref
- W. Groves, E. Nunes, and M. Gini. Predicting globally and locally:. In Proc. of the 2013 Int'l Workshop on Ubiquitous Data Mining at IJCAI, pages 5--9, 2013.Google Scholar
- J. Krumm. Where will they turn: predicting turn proportions at intersections. Personal and Ubiquitous Computing, 14(7):591--599, 2010. Google ScholarDigital Library
- A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. D. Kolaczyk, and N. Taft. Structural analysis of network traffic flows. Perform. Eval. Rev., 32(1):61--72, 2004. Google ScholarDigital Library
- B. Li, D. Zhang, L. Sun, C. Chen, S. Li, G. Qi, and Q. Yang. Hunting or waiting? discovering passenger-finding strategies from a large-scale real-world taxi dataset. In IEEE Int'l Conf. on Pervasive Computing and Communications Workshops, pages 63--68, 2011.Google Scholar
- W. Liu, Y. Zheng, S. Chawla, J. Yuan, and X. Xing. Discovering spatio-temporal causal interactions in traffic data streams. In Proc. ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining, pages 1010--1018, 2011. Google ScholarDigital Library
- J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000. Google ScholarDigital Library
- M. Veloso, S. Phithakkitnukoon, and C. Bento. Urban mobility study using taxi traces. In Proc. 2011 Int'l Workshop on Trajectory Data Mining and Analysis, pages 23--30, 2011. Google ScholarDigital Library
- J. H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236--244, 1963.Google ScholarCross Ref
- J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In Proc. 18th SIGSPATIAL Int'l Conf. on Advances in GIS, pages 99--108, 2010. Google ScholarDigital Library
- J. Zhang, P. Niyogi, and M. S. McPeek. Laplacian eigenfunctions learn population structure. PLoS ONE, 4(12):e7928, 12 2009.Google ScholarCross Ref
- Y. Zhu, Y. Zheng, L. Zhang, D. Santani, X. Xie, and Q. Yang. Inferring Taxi Status Using GPS Trajectories. ArXiv e-prints, May 2012.Google Scholar
- B. Ziebart, A. Maas, A. Dey, and J. Bagnell. Navigate like a cabbie: probabilistic reasoning from observed context-aware behavior. In Proc. Conf. on Ubiquitous Computing (UbiComp), pages 322--331, 2008. Google ScholarDigital Library
Index Terms
- A framework for predicting trajectories using global and local information
Recommendations
Data-Driven Vehicle Trajectory Prediction
SIGSIM-PADS '16: Proceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete SimulationVehicle trajectory or route prediction is useful in online, data-driven transportation simulation to predict future traffic patterns and congestion, among other uses. The various approaches to route prediction have varying degrees of data required to ...
Predicting taxi pickups in cities: which data sources should we use?
UbiComp '17: Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable ComputersIn this paper we use machine learning to evaluate the predictability of taxi pickups in New York City's busiest neighborhoods using data available from the Taxi and Limousine Commission and from Twitter. We found that these pickups can be accurately ...
A Cluster-based Framework for Predicting Large Scale Road-Network Constrained Trajectories
PE-WASUN '20: Proceedings of the 17th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, & Ubiquitous NetworksThe increasing availability of vehicle trajectory and road network datasets is crucial for the development of novel trajectory data mining-based applications. For instance, we can design more efficient routing protocols by applying vehicle trajectory ...
Comments