How do pedestrians choose their paths within city street networks? Researchers have tried to shed light on this matter through strictly controlled experiments, but an ultimate answer based on real-world mobility data is still lacking. Here, we analyze salient features of human path planning through a statistical analysis of a massive dataset of GPS traces, which reveals that (1) people increasingly deviate from the shortest path when the distance between origin and destination increases and (2) chosen paths are statistically different when origin and destination are swapped. We posit that direction to goal is a main driver of path planning and develop a vector-based navigation model; the resulting trajectories, which we have termed pointiest paths, are a statistically better predictor of human paths than a model based on minimizing distance with stochastic effects. Our findings generalize across two major US cities with different street networks, hinting to the fact that vector-based navigation might be a universal property of human path planning.
This is a preview of subscription content
Subscribe to Journal
Get full journal access for 1 year
only 7,71 € per issue
All prices are NET prices.
VAT will be added later in the checkout.
Tax calculation will be finalised during checkout.
Get time limited or full article access on ReadCube.
All prices are NET prices.
Due to privacy constraint policies and a signed data usage agreement, we are not allowed to share the full GPS tracks considered in this work. For this reason, we generated a small sample of 100 trajectories for Boston. We also make available the pre-processed pedestrian street networks for Boston and San Francisco. The sample dataset and street network data can be accessed at Zenodo60. Figures 1c, 2a and 3a used basemap from Open Street Map (https://www.openstreetmap.org) under an Open Database license (https://www.openstreetmap.org/copyright). Figure 3b uses Google Map data (2021) under fair-use guidelines (https://about.google/brand-resource-center/products-and-services/geo-guidelines/#general-guidelines-copyright-fair-use). Source data are provided with this paper.
The version of PedNav package used in this study and a guide to reproducing the results is available through GitHub under a GNU GPL-3.0 license (https://github.com/cbongiorno/pednav). The specific version of the package used to generate the results in the current study is available at Zenodo60. A pseudo-code description of the algorithms used for human navigation based on stochastic distance minimization and vector navigation is reported in Supplementary Section 4.
Newell, A., Shaw, J. C. & Simon, H. A. Elements of a theory of human problem solving. Psychol. Rev. 65, 151–166 (1958).
Zhu, S. & Levinson, D. Do people use the shortest path? An empirical test of Wardrop’s first principle. PLoS ONE 10, e0134322 (2015).
Lima, A., Stanojevic, R., Papagiannaki, D., Rodriguez, P. & González, M. C. Understanding individual routing behaviour. J. R. Soc. Interface 13, 20160021 (2016).
Javadi, A.-H. et al. Hippocampal and prefrontal processing of network topology to simulate the future. Nat. Commun. 8, 14652 (2017).
Griffiths, T. L., Lieder, F. & Goodman, N. D. Rational use of cognitive resources: levels of analysis between the computational and the algorithmic. Top. Cogn. Sci. 7, 217–229 (2015).
Huys, Q. J. et al. Interplay of approximate planning strategies. Proc. Natl Acad. Sci. USA 112, 3098–3103 (2015).
Gershman, S. J., Horvitz, E. J. & Tenenbaum, J. B. Computational rationality: a converging paradigm for intelligence in brains, minds and machines. Science 349, 273–278 (2015).
Baker, C. L., Jara-Ettinger, J., Saxe, R. & Tenenbaum, J. B. Rational quantitative attribution of beliefs, desires and percepts in human mentalizing. Nat. Hum. Behav. 1, 0064 (2017).
Liu, S., Ullman, T. D., Tenenbaum, J. B. & Spelke, E. S. Ten-month-old infants infer the value of goals from the costs of actions. Science 358, 1038–1041 (2017).
Gershman, S. J. Origin of perseveration in the trade-off between reward and complexity. Cognition 204, 104394 (2020).
Hillier, B. & Iida, S. Network and psychological effects in urban movement. In International Conference on Spatial Information Theory (eds Cohn, A. G. & Mark, D. M.) 475–490 (Springer, 2005).
Brockmann, D., Hufnagel, L. & Geisel, T. The scaling laws of human travel. Nature 439, 462–465 (2006).
Gonzalez, M. C., Hidalgo, C. A. & Barabasi, A.-L. Understanding individual human mobility patterns. Nature 453, 779–782 (2008).
Simini, F., González, M. C., Maritan, A. & Barabási, A.-L. A universal model for mobility and migration patterns. Nature 484, 96–100 (2012).
Alessandretti, L., Sapiezynski, P., Sekara, V., Lehmann, S. & Baronchelli, A. Evidence for a conserved quantity in human mobility. Nat. Hum. Behav. 2, 485–491 (2018).
Hamedmoghadam, H., Ramezani, M. & Saberi, M. Revealing latent characteristics of mobility networks with coarse-graining. Sci. Rep. 9, 7545 (2019).
Kraemer, M. U. et al. Mapping global variation in human mobility. Nat. Hum. Behav 4, 800–810 (2020).
Verbavatz, V. & Barthelemy, M. The growth equation of cities. Nature 587, 397–401 (2020).
Alessandretti, L., Aslak, U. & Lehmann, S. The scales of human mobility. Nature 587, 402–407 (2020).
Er-Jian, L. & Xiao-Yong, Y. A universal opportunity model for human mobility. Sci. Rep. 10, 4657 (2020).
Gallotti, R., Bazzani, A., Rambaldi, S. & Barthelemy, M. A stochastic model of randomly accelerated walkers for human mobility. Nat. Commun. 7, 12600 (2016).
Gillner, S. & Mallot, H. A. Navigation and acquisition of spatial knowledge in a virtual maze. J. Cogn. Neurosci. 10, 445–463 (1998).
Foo, P., Warren, W. H., Duchon, A. & Tarr, M. J. Do humans integrate routes into a cognitive map? Map-versus landmark-based navigation of novel shortcuts. J. Exp. Psychol. Learn. Mem. Cogn. 31, 195–215 (2005).
Norman, J. F., Crabtree, C. E., Clayton, A. M. & Norman, H. F. The perception of distances and spatial relationships in natural outdoor environments. Perception 34, 1315–1324 (2005).
Sun, Y. & Wang, H. Perception of space by multiple intrinsic frames of reference. PLoS ONE 5, e10442 (2010).
Weisberg, S. M. & Newcombe, N. S. How do (some) people make a cognitive map? Routes, places and working memory. J. Exp. Psychol. Learn. Mem. Cogn. 42, 768–785 (2016).
Vuong, J., Fitzgibbon, A. W. & Glennerster, A. No single, stable 3D representation can explain pointing biases in a spatial updating task. Sci. Rep. 9, 12578 (2019).
Bécu, M. et al. Age-related preference for geometric spatial cues during real-world navigation. Nat. Hum. Behav. 4, 88–99 (2020).
van der Ham, I. J., Claessen, M. H., Evers, A. W. & van der Kuil, M. N. Large-scale assessment of human navigation ability across the lifespan. Sci. Rep. 10, 3299 (2020).
Marshall, J. M. et al. Mathematical models of human mobility of relevance to malaria transmission in Africa. Sci. Rep. 8, 7713 (2018).
Yan, X.-Y., Wang, W.-X., Gao, Z.-Y. & Lai, Y.-C. Universal model of individual and population mobility on diverse spatial scales. Nat. Commun. 8, 1639 (2017).
Yan, X.-Y. & Zhou, T. Destination choice game: a spatial interaction theory on human mobility. Sci. Rep. 9, 9466 (2019).
Coutrot, A. et al. Virtual navigation tested on a mobile app is predictive of real-world wayfinding navigation performance. PLoS ONE 14, e0213272 (2019).
Manley, E., Addison, J. & Cheng, T. Shortest path or anchor-based route choice: a large-scale empirical analysis of minicab routing in London. J. Transport Geogr. 43, 123–139 (2015).
Malleson, N. et al. The characteristics of asymmetric pedestrian behavior: a preliminary study using passive smartphone location data. Trans. GIS 22, 616–634 (2018).
Dijkstra, E. A note on two problems in connexion with graphs. Numerische Math. 1, 269–271 (1959).
Fechner, G. T. Elements of Psychophysics (eds Howes, D. H. & Boring, E. G.) (Holt, Rinehar and Winston, 1860).
Newcombe, N., Huttenlocher, J., Sandberg, E., Lie, E. & Johnson, S. What do misestimations and asymmetries in spatial judgement indicate about spatial representation. J. Exp. Psychol. Learn. Mem. Cogn. 25, 986–996 (1999).
Bailenson, J. N., Shum, M. S. & Uttal, D. H. Road climbing: principles governing asymmetric route choices on maps. J. Environ. Psychol. 18, 251–264 (1998).
Bailenson, J. N., Shum, M. S. & Uttal, D. H. The initial segment strategy: a heuristic for route selection. Mem. Cogn. 28, 306–318 (2000).
Christenfeld, N. Choices from identical options. Psychol. Sci. 6, 50–55 (1995).
Howard, L. R. et al. The hippocampus and entorhinal cortex encode the path and euclidean distances to goals during navigation. Curr. Biol. 24, 1331–1340 (2014).
Marchette, S. A., Vass, L. K., Ryan, J. & Epstein, R. A. Anchoring the neural compass: coding of local spatial reference frames in human medial parietal lobe. Nat. Neurosci. 17, 1598–1606 (2014).
Collett, T. S. & Graham, P. Animal navigation: path integration, visual landmarks and cognitive maps. Curr. Biol. 14, R475–R477 (2004).
Hafting, T., Fyhn, M., Molden, S., Moser, M.-B. & Moser, E. I. Microstructure of a spatial map in the entorhinal cortex. Nature 436, 801–806 (2005).
de Cothi, W. & Spiers, H. J. Spatial cognition: goal-vector cells in the bat hippocampus. Curr. Biol. 27, R239–R241 (2017).
Toledo, S. et al. Cognitive map-based navigation in wild bats revealed by a new high-throughput tracking system. Science 369, 188–193 (2020).
Poucet, B., Thinus-Blanc, C. & Chapuis, N. Route planning in cats, in relation to the visibility of the goal. Animal Behav. 31, 594–599 (1983).
Epstein, R. A., Patai, E. Z., Julian, J. B. & Spiers, H. J. The cognitive map in humans: spatial navigation and beyond. Nat. Neurosci. 20, 1504–1513 (2017).
Poulter, S., Lee, S. A., Dachtler, J., Wills, T. J. & Lever, C. Vector trace cells in the subiculum of the hippocampal formation. Nat. Neurosci 24, 266–275 (2021).
Tolman, E. C. Cognitive maps in rats and men. Psychol. Rev. 55, 189–208 (1948).
Fu, E., Bravo, M. & Roskos, B. Single-destination navigation in a multiple-destination environment: a new later-destination attractor bias in route choice. Mem. Cogn. 43, 1043–1055 (2015).
Brunyé, T. T. et al. Planning routes around the world: international evidence for southern route preferences. J. Environ. Psychol. 32, 297–304 (2012).
Peer, M., Brunec, I. K., Newcombe, N. S. & Epstein, R. A. Structuring knowledge with cognitive maps and cognitive graphs. Trends Cogn. Sci. 25, 37–54 (2020).
Stern, E. & Leiser, D. Levels of spatial knowledge and urban travel modeling. Geogr. Anal. 20, 140–155 (1988).
Newson, P. & Krumm, J. Hidden Markov map matching through noise and sparseness. In Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’09, 336–343 (Association for Computing Machinery, 2009); https://doi.org/10.1145/1653771.1653818
Douglas, D. H. & Peucker, T. K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartogr. Int. J. Geogr. Inf. Geovis. 10, 112–122 (1973).
Wilks, S. S. The large-sample distribution of the likelihood ratio for testing composite hypotheses. Ann. Math. Stat. 9, 60–62 (1938).
Zhang, P. Model selection via multifold cross validation. Ann. Stat 21, 299–313 (1993).
Buongiorno, C. et al. Pednav (1.1) (Zenodo, 2021); https://doi.org/10.5281/zenodo.5187718
Wilson, E. B. Probable inference, the law of succession and statistical inference. J. Am. Stat. Assoc. 22, 209–212 (1927).
P.S. and C.R. thank the Amsterdam Institute for Advanced Metropolitan Solutions, Enel Foundation, DOVER and all of the members of the MIT Senseable City Laboratory Consortium for supporting this research. This material is based on work supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award no. CCF-1231216. C.B. and A.R. acknowledge support from the MISTI/MITOR fund. A.R. acknowledges support from Compagnia di San Paolo. This work was performed using HPC resources from the ‘Mésocentre’ computing center of CentraleSupélec and Ecole Normale Supérieure Paris-Saclay supported by CNRS and Région Île-de-France. Y.Z. acknowledges B. Huang and the Chinese University of Hong Kong for supporting his academic visit at the MIT Senseable City Laboratory.
The authors declare no competing interests.
Peer review information Nature Computational Science thanks Nora Newcombe, Steven Weisberg, Daniel Montello and Laura Alessandretti for their contribution to the peer review of this work. Handling editor: Fernando Chirigati, in collaboration with the Nature Computational Science team.
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supplementary Figs. 1–8, Tables 1–3 and additional analyses.
Statistical source data for Supplementary Fig. 4.
Statistical source data for Supplementary Fig. 5.
Statistical source data for Supplementary Fig. 6.
Statistical source data for Supplementary Fig. 7.
Statistical source data for Supplementary Fig. 8.
About this article
Cite this article
Bongiorno, C., Zhou, Y., Kryven, M. et al. Vector-based pedestrian navigation in cities. Nat Comput Sci 1, 678–685 (2021). https://doi.org/10.1038/s43588-021-00130-y
Nature Computational Science (2021)