Vector-based pedestrian navigation in cities.
Journal
Nature computational science
ISSN: 2662-8457
Titre abrégé: Nat Comput Sci
Pays: United States
ID NLM: 101775476
Informations de publication
Date de publication:
Oct 2021
Oct 2021
Historique:
received:
17
03
2021
accepted:
12
08
2021
medline:
1
10
2021
pubmed:
1
10
2021
entrez:
13
1
2024
Statut:
ppublish
Résumé
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.
Identifiants
pubmed: 38217198
doi: 10.1038/s43588-021-00130-y
pii: 10.1038/s43588-021-00130-y
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
678-685Informations de copyright
© 2021. The Author(s), under exclusive licence to Springer Nature America, Inc.
Références
Newell, A., Shaw, J. C. & Simon, H. A. Elements of a theory of human problem solving. Psychol. Rev. 65, 151–166 (1958).
doi: 10.1037/h0048495
Zhu, S. & Levinson, D. Do people use the shortest path? An empirical test of Wardrop’s first principle. PLoS ONE 10, e0134322 (2015).
doi: 10.1371/journal.pone.0134322
Lima, A., Stanojevic, R., Papagiannaki, D., Rodriguez, P. & González, M. C. Understanding individual routing behaviour. J. R. Soc. Interface 13, 20160021 (2016).
doi: 10.1098/rsif.2016.0021
Javadi, A.-H. et al. Hippocampal and prefrontal processing of network topology to simulate the future. Nat. Commun. 8, 14652 (2017).
doi: 10.1038/ncomms14652
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).
doi: 10.1111/tops.12142
Huys, Q. J. et al. Interplay of approximate planning strategies. Proc. Natl Acad. Sci. USA 112, 3098–3103 (2015).
doi: 10.1073/pnas.1414219112
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).
doi: 10.1126/science.aac6076
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).
doi: 10.1038/s41562-017-0064
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).
doi: 10.1126/science.aag2132
Gershman, S. J. Origin of perseveration in the trade-off between reward and complexity. Cognition 204, 104394 (2020).
doi: 10.1016/j.cognition.2020.104394
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).
doi: 10.1038/nature04292
Gonzalez, M. C., Hidalgo, C. A. & Barabasi, A.-L. Understanding individual human mobility patterns. Nature 453, 779–782 (2008).
doi: 10.1038/nature06958
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).
doi: 10.1038/nature10856
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).
doi: 10.1038/s41562-018-0364-x
Hamedmoghadam, H., Ramezani, M. & Saberi, M. Revealing latent characteristics of mobility networks with coarse-graining. Sci. Rep. 9, 7545 (2019).
doi: 10.1038/s41598-019-44005-9
Kraemer, M. U. et al. Mapping global variation in human mobility. Nat. Hum. Behav 4, 800–810 (2020).
doi: 10.1038/s41562-020-0875-0
Verbavatz, V. & Barthelemy, M. The growth equation of cities. Nature 587, 397–401 (2020).
doi: 10.1038/s41586-020-2900-x
Alessandretti, L., Aslak, U. & Lehmann, S. The scales of human mobility. Nature 587, 402–407 (2020).
doi: 10.1038/s41586-020-2909-1
Er-Jian, L. & Xiao-Yong, Y. A universal opportunity model for human mobility. Sci. Rep. 10, 4657 (2020).
doi: 10.1038/s41598-020-61613-y
Gallotti, R., Bazzani, A., Rambaldi, S. & Barthelemy, M. A stochastic model of randomly accelerated walkers for human mobility. Nat. Commun. 7, 12600 (2016).
doi: 10.1038/ncomms12600
Gillner, S. & Mallot, H. A. Navigation and acquisition of spatial knowledge in a virtual maze. J. Cogn. Neurosci. 10, 445–463 (1998).
doi: 10.1162/089892998562861
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).
doi: 10.1037/0278-7393.31.2.195
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).
doi: 10.1068/p5304
Sun, Y. & Wang, H. Perception of space by multiple intrinsic frames of reference. PLoS ONE 5, e10442 (2010).
doi: 10.1371/journal.pone.0010442
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).
doi: 10.1037/xlm0000200
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).
doi: 10.1038/s41598-019-48379-8
Bécu, M. et al. Age-related preference for geometric spatial cues during real-world navigation. Nat. Hum. Behav. 4, 88–99 (2020).
doi: 10.1038/s41562-019-0718-z
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).
doi: 10.1038/s41598-020-60302-0
Marshall, J. M. et al. Mathematical models of human mobility of relevance to malaria transmission in Africa. Sci. Rep. 8, 7713 (2018).
doi: 10.1038/s41598-018-26023-1
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).
doi: 10.1038/s41467-017-01892-8
Yan, X.-Y. & Zhou, T. Destination choice game: a spatial interaction theory on human mobility. Sci. Rep. 9, 9466 (2019).
doi: 10.1038/s41598-019-46026-w
Coutrot, A. et al. Virtual navigation tested on a mobile app is predictive of real-world wayfinding navigation performance. PLoS ONE 14, e0213272 (2019).
doi: 10.1371/journal.pone.0213272
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).
doi: 10.1016/j.jtrangeo.2015.01.006
Malleson, N. et al. The characteristics of asymmetric pedestrian behavior: a preliminary study using passive smartphone location data. Trans. GIS 22, 616–634 (2018).
doi: 10.1111/tgis.12336
Dijkstra, E. A note on two problems in connexion with graphs. Numerische Math. 1, 269–271 (1959).
doi: 10.1007/BF01386390
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).
doi: 10.1037/0278-7393.25.4.986
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).
doi: 10.1006/jevp.1998.0095
Bailenson, J. N., Shum, M. S. & Uttal, D. H. The initial segment strategy: a heuristic for route selection. Mem. Cogn. 28, 306–318 (2000).
doi: 10.3758/BF03213808
Christenfeld, N. Choices from identical options. Psychol. Sci. 6, 50–55 (1995).
doi: 10.1111/j.1467-9280.1995.tb00304.x
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).
doi: 10.1016/j.cub.2014.05.001
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).
doi: 10.1038/nn.3834
Collett, T. S. & Graham, P. Animal navigation: path integration, visual landmarks and cognitive maps. Curr. Biol. 14, R475–R477 (2004).
doi: 10.1016/j.cub.2004.06.013
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).
doi: 10.1038/nature03721
de Cothi, W. & Spiers, H. J. Spatial cognition: goal-vector cells in the bat hippocampus. Curr. Biol. 27, R239–R241 (2017).
doi: 10.1016/j.cub.2017.01.061
Toledo, S. et al. Cognitive map-based navigation in wild bats revealed by a new high-throughput tracking system. Science 369, 188–193 (2020).
doi: 10.1126/science.aax6904
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).
doi: 10.1016/S0003-3472(83)80083-9
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).
doi: 10.1038/nn.4656
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).
doi: 10.1038/s41593-020-00761-w
Tolman, E. C. Cognitive maps in rats and men. Psychol. Rev. 55, 189–208 (1948).
doi: 10.1037/h0061626
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).
doi: 10.3758/s13421-015-0521-7
Brunyé, T. T. et al. Planning routes around the world: international evidence for southern route preferences. J. Environ. Psychol. 32, 297–304 (2012).
doi: 10.1016/j.jenvp.2012.05.003
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).
doi: 10.1016/j.tics.2020.10.004
Stern, E. & Leiser, D. Levels of spatial knowledge and urban travel modeling. Geogr. Anal. 20, 140–155 (1988).
doi: 10.1111/j.1538-4632.1988.tb00172.x
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).
doi: 10.1214/aoms/1177732360
Zhang, P. Model selection via multifold cross validation. Ann. Stat 21, 299–313 (1993).
doi: 10.1214/aos/1176349027
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).
doi: 10.1080/01621459.1927.10502953