Navigation made personal: inferring driving preferences from GPS traces

ABSTRACT

All current navigation systems return efficient source-to-destination routes assuming a "one-size-fits-all" set of objectives, without addressing most personal preferences. Although they allow some customization (like "avoid highways" or "avoid tolls"), the choices are very limited and require some sophistication on the part of the user. In this paper we present, implement, and test a framework that generates personalized driving directions by automatically analyzing users' GPS traces. Our approach learns cost functions using coordinate descent, leveraging a state-of-the-art route planning engine for efficiency. In an extensive experimental study, we show that this framework infers user-specific driving preferences, significantly improving the route quality. Our approach can handle continental-sized inputs (with tens of millions of vertices and arcs) and is efficient enough to be run on an autonomous device (such as a car navigation system) preserving user privacy.

References

1. I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 24--35. Springer, 2012.
2. I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Alternative Routes in Road Networks. ACM Journal of Experimental Algorithmics, 18(1):1--17, 2013.
3. M. Agrawala and C. Stolte. Rendering effective route maps: improving usability through generalization. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pages 241--249. ACM, 2001.
4. A. Auslender. Optimisation Métodes Numériques. Masson, Paris, 1976.
5. R. Bader, J. Dees, R. Geisberger, and P. Sanders. Alternative Route Graphs in Road Networks. In A. Marchetti-Spaccamela and M. Segal, editors, Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11), volume 6595 of Lecture Notes in Computer Science, pages 21--32. Springer, 2011.
6. H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route Planning in Transportation Networks. CoRR, abs/1504.05140, 2015.
7. H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast Routing in Road Networks with Transit Nodes. Science, 316(5824):566, 2007.
8. D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts, second edition, 1999.
9. J. Biagioni and J. Eriksson. Map inference in the face of noise and disparity. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pages 79--88. ACM, 2012.
10. S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases, pages 853--864. VLDB Endowment, 2005.
11. K.-P. Chang, L.-Y. Wei, M.-Y. Yeh, and W.-C. Peng. Discovering personalized routes from trajectories. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks, pages 33--40. ACM, 2011.
12. N. Cohn. Real-time traffic information and navigation. Transportation Research Record: Journal of the Transportation Research Board, 2129(1):129--135, 2009.
13. E. R. da Silva, C. de Baptista, L. Menezes, and A. Paiva. Personalized path finding in road networks. In Proceedings of the Fourth International Conference on Networked Computing and Advanced Information Management, volume 2, pages 586--591. IEEE, 2008.
14. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 376--387. Springer, 2011.
15. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 2015. online preprint.
16. D. Delling, M. Kobitzsch, and R. F. Werneck. Customizing driving directions with GPUs. In Proceedings of the 20th International Conference on Parallel Processing (Euro-Par 2014), volume 8632 of Lecture Notes in Computer Science, pages 728--739. Springer, 2014.
17. D. Delling and R. F. Werneck. Faster customization of road networks. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 30--42. Springer, 2013.
18. E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1:269--271, 1959.
19. M. Dimond, G. Smith, and J. Goulding. Improving route prediction through user journey detection. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 466--469. ACM, 2013.
20. D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10:112--122, 1973.
21. M. Duckham and L. Kulik. "simplest" paths: Automated route selection for navigation. In Spatial Information Theory. Foundations of Geographic Information Science, pages 169--185. Springer, 2003.
22. S. Funke, A. Nusser, and S. Storandt. On k-path covers and their applications. In Proceedings of the 40th International Conference on Very Large Databases (VLDB 2014), pages 893--902, 2014.
23. R. Geisberger, M. Rice, P. Sanders, and V. Tsotras. Route Planning with Flexible Edge Restrictions. ACM Journal of Experimental Algorithmics, 17(1):1--20, 2012.
24. M. Kobitzsch. HiDAR: An alternative approach to alternative routes. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA'13), volume 8125 of Lecture Notes in Computer Science, pages 613--624. Springer, 2013.
25. J. Krumm and D. Rouhana. Placer: semantic place labels from diary data. In Proceedings of the 2013 ACM international Joint Conference on Pervasive and Ubiquitous Computing, pages 163--172. ACM, 2013.
26. J. Letchner, J. Krumm, and E. Horvitz. Trip router with individualized preferences (trip): Incorporating personalization into route planning. In Proceedings of the National Conference on Artificial Intelligence, volume 21, page 1795. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
27. R. Maxunder, J. H. Friedman, and T. Hastie. SparseNet: Coordinate descent with nonconvex penalties. Journal of the American Statistical Association, 106(495), 2011.
28. P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 336--343. ACM, 2009.
29. S. Rogers, P. Langley, and C. Wilson. Mining GPS data to augment road models. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 104--113. ACM, 1999.
30. R. E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990.
31. C. Sommer. Shortest-path queries in static networks. ACM Computing Surveys, 46:547--560, 2014.
32. J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 99--108. ACM, 2010.
33. B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10th International Conference on Ubiquitous Computing, pages 322--331. ACM, 2008.

Index Terms

• Computing methodologies

  • Machine learning

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics