Background

In the context of this work, the issues of pedestrian path-finding intersect both theoretical urbanist ideas (particularly the concept of walkability) and classical topics in computer science (particularly graph search algorithms). However, to achieve our objectives, we also relate to much more modern computer science topics, specifically in natural language processing and transformer-based encoders.

The Issue of “Walkability”

To construct a better set of requirements than those traditionally used in path-finding algorithms, we turn to the urbanist concept of walkability. Unlike the exact yet simplistic measures of routing efficiency, walkability considers a wide range of factors closer aligned with realistic human preferences for walking, and can, therefore, provide a valuable perspective on finding paths walkers would actually prefer to take.

Urbanist Overview

In urbanist literature, the concept of walkability frequently encompasses a range of physical and social characteristics that collectively determine how conducive a neighborhood is to pedestrian activity.

Alfonzo draws a multi-level model to hierarchically structure the factors that contribute to walkability (Alfonzo 2005). They use individual-level characteristics (such as income and car ownership), regional-level attributes (that reflect broader geographic variation), and physical environment characteristics (including safety, traffic conditions, sidewalk availability, and the directness of pedestrian routes). They further distill the factors of the individual-level characteristics and physical environments in an analysis of the human needs. The resulting model is called “the five levels of walking needs”, and includes, in order: “feasibility” (reflecting, for instance, the mobility of individuals and environment), “accessibility” (referring to factors such as the presence of pedestrian infrastructure or the proximity to points of interest), “safety” (determined by, for example, land use or the fear of crime), “comfort” (for instance, the relationship between pedestrian and motorized traffic, or the presence of “street furniture”), and “pleasurability” (invoked by factors such as aesthetic appeal or presence of public spaces).

Nevertheless, a number of other publications emerge with more quantifiable approaches to measuring walkability. Grasser et. al. suggest using data of gross population, employment, and housing densities alongside land-use diversity indicators (such as the entropy index) and estimated “street connectivity” based on intersection density (Grasser et al. 2013). In a parallel effort, Frank et. al. introduce a composite index combining net residential density, street intersection density, and retail floor area ratio to capture both destination presence and ease of access (Frank et al. 2006). Broadening the scope, Shields et. al. catalog objective factors (including distance to key destinations, sidewalk continuity, road-network characteristics, intersection safety features, vehicular traffic volume and speed, pedestrian-support amenities, and various density measures), while also emphasizing subjective qualities such as aesthetics, comfort (such as lighting, shade, noise levels), personal security, attractiveness, and crowding (Shields et al. 2023). Finally, Frank et. al. later propose calculating z-scores for net residential density, retail floor area ratio, intersection density, and a five-category land-use mix entropy score, summing these standardized values to produce a regionally normalized composite index (Frank et al. 2010).

Summary and Criticisms of Walkability Literature

As such, the methods for the evaluation of walkability in urbanist literature utilize a large variety of approaches and tools. Walkability is frequently calculated based on both highly granular metrics (such as intersection density) and small, local elements (such as street furniture). Nevertheless, there are clear limitations to these approaches. For instance: while the approaches that aim to express walkability in numeric values are only concerned with quantifiable factors, it is only the more general, high-level frameworks (such as in Alfonzo (Alfonzo 2005)) that consider more subjective factors. Highly important influences of the physical environment, particularly in the domains of “comfort” and “pleasurability”, are often omitted, or expected to be correlated with the exact, quantifiable metrics. Considering the spatial diversity of cities (particularly if we’re comparing cities from different countries or regions), one may conclude that these general-purpose approaches can easily lead to inaccurate (or even biased) conclusions about what can be considered well or poorly walkable.

Walkability-focused Services

The potential shortcomings of the urbanist research seem to have been mirrored in both public and proprietary projects and services. High-visibility projects such as the National Walkability Index (Thomas, Zeller, and Reyes 2021) or WalkScore (Walk Score 2025) (both of which are limited to the United States) have been criticized for their positive emphasis on car-centric areas and proximity to points of interest, and neglecting more realistic pedestrian preferences, ultimately leading to inaccurate and misleading conclusions (Steuteville 2019). The NWI, curated by the U.S. Environmental Protection Agency, focuses on measures that can be consistently applied across the country, using data from the Smart Location Database (Ramsey and Bell 2014). These measures include intersection density, proximity to transit stops, and the diversity of land use. The underlying assumption is that each of these factors is positively correlated with the likelihood of walking trips, making them key indicators of walkability at the block group level. A notable alternative to NWI is WalkScore - originally an open-source project aimed at promoting walkable neighborhoods. However, Walkscore was later privately acquired, and currently releases walkability scores calculated only through proprietary methodologies (Walk Score 2025; Steuteville 2019).

Alternative: n-Minute Cities

Reflecting the limited supply of reliable walkability assessment tools and the demanding nature of the problem (requiring plentiful data and intricate technological solutions), alternative approaches, such as the concept of “n-minute cities”, have emerged. Instead of measuring walkability on the basis of actual physical environments, n-minute cities infer their walkability indices based on the proximity to points of interest. Exclusively aimed at urban environments, these projects generally focus on determining how long it would take to walk from a certain location to places essential for daily life (such as stores, schools, hospitals, etc.) - hence the n-minutes.

There are several projects, built by geographers and urbanists, that rely on this concept. A frontier example may be the project Close (Henry Spatial Analysis, LLC 2025; Bliss 2024), which combines information from public geospatial datasets (such as the Overture Maps (Overture Maps Foundation 2025)) and custom filtering logic. In Close, geospatial data points undergo a vetting process to refine and categorize destinations meaningfully. For instance, when identifying supermarkets, Close uses qualitative criteria (such as a number of different sorts of aisles) to distinguish full-service grocery stores from smaller convenience stores or bodegas. This labor-intensive process is partly automated using building size, business names, and other available metadata, but in the fifty largest U.S. cities, the authors of Close had to undergo volumes of manual reviewing to improve accuracy. Furthermore, Close also attempts to alleviate issues induced by reliance on manual maintenance with an iterative refinement implemented through a crowd-sourcing feedback mechanism.

Path-Finding Algorithms

The aim of path-finding is to identify a sequence of steps that would define a route between two points with the aim of maximizing some predefined objective. Path-finding problems are typically represented within graphs, and their applications are widespread - from transportation to robotics or video games. Nevertheless, the core of forefront path-finding frameworks has been consistent for a very long time, and very frequently revolves around the A* (Hart, Nilsson, and Raphael 1968) and the foundational Dijkstra (Dijkstra 2022) algorithms (viz. §3.1{reference-type=”ref” reference=”section:relatedwork-transportationrouting”}).

A* optimizes its search efficiency by using a heuristically-guided search (Hart, Nilsson, and Raphael 1968). It combines a Dijkstra-like greedy best-first search with an estimation of the cost to reach the target node. At each step, A* selects the node with the lowest cost $f(n) = g(n) + h(n)$, where $g(n)$ represents the exact cost from the start node to the considered node, and $h(n)$ the heuristic estimate of the cost from the currently iterated node to the target destination. In order for A* to find an optimal path, $h(n)$ must be admissible, which means that it must never overestimate the actual cost to reach the target node. If, for an A* algorithm, the equation $h(n)\leq c(n,n’) + h(n’)$ (where $c(n,n’)$ is the transition cost from node $n$ to node $n’$) holds, then the search guarantees not only optimality but also efficiency by never having to revisit a node. Furthermore, while frequently $h(n)$ is defined as a simple Euclidean or Manhattan distance, specific applications often benefit from more sophisticated strategies.

Search Optimizations

Search algorithms are frequently optimized with bidirectional search, which performs two simultaneous searches from both the start and the target until they meet. This reduces the number of visited nodes but generally requires more complex logic and balanced heuristics (Sturtevant and Felner 2018). Another approach, applicable in static graphs, is contraction hierarchies. This involves gradually removing less important nodes and replacing them with shortcut edges that preserve shortest paths. The resulting hierarchy allows for fast bidirectional search by restricting movement to higher-level nodes, greatly speeding up queries after preprocessing, which is typically worthwhile for large graphs (Geisberger et al. 2008).

Sentence Transformers

Sentence embedders (such as the foundational Sentence-BERT (Reimers and Gurevych 2019)) are neural networks based on the transformer architecture, designed to capture the semantic contents of textual data of arbitrary length (but typically standalone sentences) into vectorized representations of predetermined sizes. These models are frequently prepared by fine-tuning pretrained transformers on the objective of projecting semantically similar sentences close together in the resulting embedding space. This property can then be used to easily compare different data points, using measures like cosine similarity. Unlike some pre-existing approaches for measuring similarity (such as by relying on the original BERT network), sentence transformers do not compute pair-wise comparisons, but can encode inputs independently. Therefore, comparing similarities in large sets becomes much more computationally efficient. In order to output embeddings of fixed sizes, sentence transformers use various techniques, such as pooling over the transformer’s final layer. Under both supervised and unsupervised benchmarks in clustering, similarity, and retrieval tasks, sentence transformers (such as Sentence-BERT) consistently outperformed existing strategies (Reimers and Gurevych 2019).

Low-Rank Adaptation of Language Models

Low-Rank Adaptation (or LoRA) in language models is a technique that can be leveraged to perform light-weight fine-tuning of pre-trained language models. LoRA-based fine-tuning works by freezing the original model’s weights and injecting small trainable low-rank decomposition matrices into each of the transformer’s layers. Here, rank $r$ denotes the dimensionality of the low‑rank decomposition of a weight update. For a frozen pre‑trained weight matrix $W_0\in \mathbb{R}^{d\times k}$, the update is written as $\Delta W = B A,\; B \in \mathbb{R}^{d \times r},\; A \in \mathbb{R}^{r \times k}$. Then, “low‑rank” implies choosing $r\ll\min(d,k)$ so that $\Delta W$ lies in a small $r$‑dimensional subspace, hence dramatically reducing the number of trainable parameters. Before any training, the decomposition matrices are initialized so that their product equals zero, and therefore, the model’s initial behavior matches the pretrained baseline. During the training, the optimization is balanced by a scaling factor, making sure most hyperparameters do not require retuning with varying ranks. The underlying rationale of this approach is based on the observation that during task-specific adaptation of transformers, the change in the model’s weights lies in a much lower-dimensional subspace than the entire parameter space (Hu et al. 2022).

Furthermore, based on analyses published by Hu et. al. (Hu et al. 2022), effective weight updates in transformers have very low intrinsic ranks, and, in many cases, minimal ranks are sufficient to capture adaptations necessary for downstream tasks. Based on similarity measurements between adaptations of random initializations and different ranks, they conclude that the most important parameter updates lie in a very small subspace. Low-rank updates also tend to highlight features already present in the pre-trained network, rather than introduce new “concepts” into the model. Therefore, LoRA can reduce the number of trainable weights by orders of magnitude when applied to large semantic models and substantially lower the computational burden relative to full model fine-tuning. Furthermore, the injected low-rank matrices can be merged with the transformer’s frozen weights before inference, and subsequently achieve no additional latency compared to the original vanilla transformer.

Therefore, considering LoRA’s proven potential in the context of text-based transformers to match or exceed fully fine-tuned networks, LoRA presents a viable strategy for customization and adaptation of transformer-based models while alleviating the computational burden associated with full-model fine-tuning.

Contrastive Learning

Contrastive learning is a machine learning technique applicable in both supervised and unsupervised settings. Contrastive learning aims to leverage known relationships between training data points to learn how to project data into an embedding space such that points of the same or similar samples appear close together, whereas points from different samples are spread apart (Weng 2021). This is frequently accomplished via specialized contrastive loss functions, such as the contrastive loss (F. Wang and Liu 2021), the triplet loss (Tripathi and King 2024), or InfoNCE (Rusak et al. 2024). Contrastive learning has enjoyed much popularity due to (amongst other things) its ability to train under a self-supervised objective and its versatility across various domains, including multi-modal machine learning (Weng 2021).

Relevant for the context of this work is the triplet loss. The triplet loss paradigm uses three examples at a time: an “anchor” example, a “positive” example of the same or similar sample as the anchor, and a “negative” example of a sample different from the anchor. The trained model is then taught to effectively pull the anchor closer to the positive example in the representation space and push it away from the negative example. In this way, the model is prompted to represent contrasting samples in different parts of the embedding space (Weinberger and Saul 2009; Khosla et al. 2020; Tripathi and King 2024).

References

  • Alfonzo, Mariela A. (2005). To Walk or Not to Walk? The Hierarchy of Walking Needs. Environment and Behavior, 37(6), 808–836.
  • Bliss, Laura. (2024). How Walkable Is Your Neighborhood? A New Map Tool Offers an Answer – Bloomberg. https://www.bloomberg.com/news/newsletters/2024-09-11/how-walkable-is-your-neighborhood-a-new-map-tool-offers-an-answer
  • Dijkstra, Edsger W. (2022). A Note on Two Problems in Connexion with Graphs. In Edsger Wybe Dijkstra: His Life, Work, and Legacy (pp. 287–290).
  • Frank, Lawrence D., Sallis, J. F., Conway, T. L., Chapman, J. E., Saelens, B. E., & Bachman, W. (2006). Many Pathways from Land Use to Health: Associations Between Neighborhood Walkability and Active Transportation, Body Mass Index, and Air Quality. Journal of the American Planning Association, 72(1), 75–87.
  • Frank, Lawrence D., Sallis, J. F., Saelens, B. E., Leary, L., Cain, K., Conway, T. L., & Hess, P. M. (2010). The Development of a Walkability Index: Application to the Neighborhood Quality of Life Study. British Journal of Sports Medicine, 44(13), 924–933.
  • Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Experimental Algorithms: 7th International Workshop, WEA 2008 (pp. 319–333). Springer.
  • Grasser, G., Van Dyck, D., Titze, S., & Stronegger, W. (2013). Objectively Measured Walkability and Active Transport and Weight-Related Outcomes in Adults: A Systematic Review. International Journal of Public Health, 58, 615–625.
  • Hart, Peter E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
  • Henry Spatial Analysis, LLC. (2025). Close.city Project. https://close.city
  • Hu, Edward J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W., et al. (2022). LoRA: Low-Rank Adaptation of Large Language Models. ICLR, 1(2), 3.
  • Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., & Krishnan, D. (2020). Supervised Contrastive Learning. NeurIPS, 33, 18661–18673.
  • Overture Maps Foundation. (2025). Overture Maps Foundation. https://overturemaps.org
  • Ramsey, K., & Bell, A. (2014). Smart Location Database. Washington, DC.
  • Reimers, N., & Gurevych, I. (2019). Sentence-BERT: Sentence Embeddings Using Siamese BERT-Networks. In EMNLP 2019. https://arxiv.org/abs/1908.10084
  • Rusak, E., Reizinger, P., Juhos, A., Bringmann, O., Zimmermann, R. S., & Brendel, W. (2024). InfoNCE: Identifying the Gap Between Theory and Practice. arXiv Preprint arXiv:2407.00143.
  • Shields, R., Gomes da Silva, E. J., Lima e Lima, T., & Osorio, N. (2023). Walkability: A Review of Trends. Journal of Urbanism, 16(1), 19–41.
  • Steuteville, R. (2019). Walkability Indexes Are Flawed. Let’s Find a Better Method. CNU. https://www.cnu.org/publicsquare/2019/01/10/walkability-indexes-are-flawed-lets-find-better-method1
  • Sturtevant, N., & Felner, A. (2018). A Brief History and Recent Achievements in Bidirectional Search. In AAAI Conference on Artificial Intelligence, 32(1).
  • Thomas, J., Zeller, L., & Reyes, A. R. (2021). National Walkability Index: Methodology and User Guide. United States Environmental Protection Agency (EPA). https://www.epa.gov/sites/default/files/2021-06/documents/national_walkability_index_methodology_and_user_guide_june2021.pdf
  • Tripathi, S., & King, C. R. (2024). Contrastive Learning: Big Data Foundations and Applications. In CODS-COMAD 2024, 493–497.
  • Walk Score. (2025). Walk Score®: Walkability Index and Neighborhood Analytics. https://www.walkscore.com
  • Wang, F., & Liu, H. (2021). Understanding the Behaviour of Contrastive Loss. In CVPR, 2495–2504.
  • Weinberger, K. Q., & Saul, L. K. (2009). Distance Metric Learning for Large Margin Nearest Neighbor Classification. Journal of Machine Learning Research, 10(2).
  • Weng, L. (2021). Contrastive Representation Learning. https://lilianweng.github.io/posts/2021-05-31-contrastive/
← Previous: Walkability Chapter 1: Introduction
Next: Walkability Chapter 3: Related Work →