Where Do We Go From Here? Multi-scale Allocentric Relational Inferencefrom Natural Spatial Descriptions (2024)

Abstract: The concept of acquired spatial knowledge is crucial in spatial cognitive research, particularly when it comes to communicating routes. However, NLP navigation studies often overlook the impact of acquired knowledge on textual descriptions. Current navigation studies concentrate on egocentric local descriptions (e.g., ‘it will be on your right’) that require reasoning over the agent’s local perception. These instructions are typically given in a sequence of steps, with each action-step explicitly mentioned and followed by a landmark that the agent can use to verify that they are on the correct path (e.g., ‘turn right and then you will see...’). In contrast, descriptions based on knowledge acquired through a map provide a complete view of the environment and capture its compositionality. These instructions typically contain allocentric relations, are non-sequential, with implicit actions and multiple spatial relations without any verification (e.g., ‘south of Central Park and a block north of a police station’). This paper introduces the Rendezvous (RVS) task and dataset, which includes 10,404 examples of English geospatial instructions for reaching a target location using map-knowledge. Our analysis reveals that RVS exhibits a richer use of spatial allocentric relations, and requires resolving more spatial relations simultaneously compared to previous text-based navigation benchmarks.

## introduction in today's world, cell phones with powerful mapping applications are widely used. however, even with this technology at our fingertips, many people still rely on geospatial instructions to arrange rendezvous locations by providing natural language the rvs input consists of (1) a bird's-eye instruction of the goal location (shown at the bottom), (2) a starting point (green marker), and (3) a map representation of the environment. the output is the goal (red marker). in spatial cognitive research, it is widely accepted that spatial language is associated with cognitive representations of the environment and originates from spatial memory @xcite . thus, navigation instructions are affected by the way individuals acquire spatial knowledge over their environment @xcite @xcite . the dominant theory for spatial knowledge acquisition, that of @xcite , describes three levels of human knowledge about their environment: instructions based on survey knowledge contain a bird's-eye view perception of the environment. these higher-level descriptions involve allocentric relations and cardinal directions ('east of'), are non-sequential, with implicit actions and multiple spatial relations without any verification (e.g., '3-4 blocks north of columbus circle and north of a police station'). they require geospatial numerical reasoning ('two buildings from') and understanding of complex shapes such as 'y-shaped street' @xcite . they contain a mix of indefinite descriptions referencing salient landmarks ('a building'), as well as proper names ('the empire state building'). despite the importance of geospatial instructions in daily life, current nlp geospatial datasets lack instructions that encompass all such levels of acquired knowledge @xcite . while many nlp geolocation tasks primarily involve instructions based on landmark knowledge @xcite ), text-based navigation tasks focus on the second level -route knowledgewith step-by-step local perception @xcite . however, current spatial datasets are missing the third level -survey knowledge -which involves global perception and requires reasoning over multiple spatial relations simultaneously. here, we introduce the rendezvous (rvs) task to advance systems that can interpret high-level survey knowledge-based navigation instructions that require global spatial reasoning. the input of the task is a starting point, a non-sequential instruction of a rendezvous location, and a map. the goal is to retrieve the coordinates of the rendezvous point. we crowdsourced 10,404 rendezvous instructions. to gather instructions based on survey knowledge, we presented participants with a map that provided them with precise information that would have otherwise required extensive exploration of the environment @xcite @xcite . we collected instructions over three cities in the usa: manhattan, pittsburgh and philadelphia. the use of multiple cities allows for a realistic zeroshot setup where a model is trained on one city and tested on another city unseen during training. this new zero-shot setup is a challenging testbed for models' ability to generalize to new environments. this is also relevant for handling changing environments @xcite . it is part of our contribution to create a realistic and challenging setup and show that current models do not suffice in addressing this multifaceted challenge. our linguistically-driven analysis shows that the rvs task requires significantly more spatial allocentric reasoning, resolving more spatial relations simultaneously, and with fewer explicit actions and state verifications, compared with previous textbased navigation benchmarks (paz-argaman and tsarfaty, 2019; @xcite . ## the rvs task and environment in this work we address the task of following geospatial instructions given in colloquial language based on a dense urban map. the input to the rvs task is as follows: (i) a map with rich details, given as a knowledge graph; (ii) an explicit starting point, given in coordinates (latitude and longitude); and (iii) a geospatial instruction describing the location of the goal in relation to the landmarks on the map and the given starting point. the output of the rvs task is the coordinates of the goal within the boundaries of the map. the map was created using openstreetmap (osm). 3 we extracted landmarks and streets and connected them to form a graph. to connect landmarks that do not intersect with streets, we projected the landmarks onto the nearest streets (up to four) and added the projected nodes and edges connecting the landmarks and projections to the graph. ## data collection we frame the data collection process as an instructor-follower task, where an instructor needs to communicate to a follower the rendezvous location in relation to the follower's current location. the process is divided into two crowdsourced tasks: communicating the goal location in writing (here, instruction writing) and following (here, validation), corresponding to the two roles -instructor and follower. appendix d presents a display of the user-interface (ui) of the online assignment. task 1: instruction writing using the rvs map-graph (section 2), we generated the starting points and (within 2km) the respective goal points. the instructor could view the points on an interactive map with geo-data from osm, and displayed landmarks along the route, near the goal, in the general area and beyond the route. the goal and nearby landmarks were not shown by their proper names, e.g., instead of 'st. vincent de paul church' the marker displayed 'a church'. the instructor could zoom in/out and pan to view the environment. the instructor was requested to describe the location of the goal in relation to the starting point and landmarks, rather than providing a step-by-step route description. to prevent easy geolocation by current navigation and geolocation systems, such as street corners, the instructor was restricted to mentioning a maximum of one street by name. task 2: validation in this task, the follower is asked to follow the instruction displayed, by pinning the goal location on an interactive map. as the map includes sign symbols of places (e.g., a cross symbol to denote a church), the display also includes a legend with the equivalent symbols. an instruction is considered qualified if the follower pins the goal within 100 meters. this threshold is the maximum radius of the geoshape of the generated goal from task 1. participants were also requested to flag problematic instructions, i.e., those that did not follow the rules in the instruction writing task. to determine the agreement rate among participants, 50% of the instructions were validated by at least two participants. instructor training the main challenge of the collection process is training instructors to write high-quality instructions based on survey knowledge (rather than step-by-step agent-centered descriptions). to address this challenge, the following procedure was implemented: (1) the process starts by collecting an initial seed of 'well-formed' survey-based instructions written by a geospatial expert. ## data statistics and analysis the rvs dataset contains 10,404 validated instructions paired with start and goal coordinates. the locations are divided among three cities: manhattan, pittsburgh, and philadelphia (figure 2 and we conducted a qualitative linguistic analysis of rvs to understand the type of geospatial reasoning required to solve the rvs task. we randomly sampled and annotated 25 examples from the manhattan and pittsburgh areas of rvs and compared them to previous datasets: run (paz-argaman and tsarfaty, 2019), touchdown @xcite , and rxr @xcite . crucially, instructions based on survey knowledge use allocentric rather than egocentric spatial relations. since rxr and touchdown rely on a street/room-level view of the environment and their participants have only a short time to become familiar with the environment, the instructions contain less spatial allocentric reasoning than rvs. the rvs dataset displays more allocentric phenomena than the run dataset, even though both datasets include a map. this is because the run dataset encourages participants to use egocentric relations by displaying examples of egocentric relations. accordingly, as shown in instruction in comparison to the other datasets. on top of that, run, rxr, and touchdown all contain sequential instructions that include many explicit actions and state verifications, making it easier for the model to predict the correct action and verify it after the action is taken. in contrast, the new rvs dataset includes non-sequential instructions with relatively few state verifications and no explicit actions. to prevent simple string-match solutions, the goal location in rvs is always given by its type (e.g., 'restaurant', 'parking' etc.) and not by its proper name. in our out-of-vocabulary (oov) analysis shows that, unlike previous navigation datasets @xcite @xcite , rvs presents a challenge with novel entities in a city-split setup, training on one city and testing on a different unseen city. specifically, our analysis of the vocabularies of two different cities -manhattan and pittsburgh -shows that 36.85% of the pittsburgh vocabulary is oov, i.e., the tokens do not appear in the manhattan vocabulary. ## models for rvs as rvs presents a new multimodal task with unique challenges, we aimed to provide a strong baseline based on our insights from section 4. we model rvs as a sequence-to-sequence problem, where we map the sequence of tokens in the instruction to a sequence of s2-cells. decoder since this is essentially a navigation task without a step-by-step path, we train our model to generate a high-level path, consisting of a sequence of locations starting with the starting point, followed by prominent landmarks ordered by their directional position from the goal, and ending with the goal. we extracted the prominent landmarks based on the rvs map-graph. as in the encoder, we represent the location in a 'locx, locy' format. the world as a graph a location can be represented by its position (where the location is) or by its semantics (what is present at the location, e.g., 'a bar'). semantic knowledge is crucial for grounding mentioned entities to their physical references in the environment. to this end, we aim to connect the semantic and positional knowledge using a novel rvs map-graph. the rvs map-graph is a heterogeneous graph containing location nodes (semantic) and s2-cell nodes (positional). first, we connected each location node to its smallest containing s2-cell (see figure 3 ), also instantiating each s2-cell as an independent node in the graph. then, as the s2-geometry is a hierarchical structure, we add both within-level and between-level edges between s2-cell nodes. specifically, we connect each s2-cell to its immediate neighbors at the same level, and we connect each s2-cell to its containing s2-cell at the next level up in the hierarchy (see figure 3 ). to learn a joint embedding space for locations and s2-cells, we compute random walks on the graph using node2vec algorithm @xcite . following @xcite , we use linear projection to cluster the graph embeddings into k categories using the k-means algorithm with cosine similarity distance. a new token is assigned to each category and added to the tokenizer's vocabulary. we perform multiple clusters and pass the graph's tokens with the instruction's tokens to the transformer encoder. ## experimental setup evaluation we use six evaluation metrics: (1) 100m accuracy, the task is considered completed if the agent is within a 100m distance from the goal; (2) 250m accuracy for coarse-grained accuracy evaluation; (3) mean distance error; (4) median distance error; (5) maximum distance error; and (6) area under the curve (auc) distance error. setup and data-split we use a zero-shot (zs) city-based split, where we train on one city, validate on a second city, and test on a third city. specifically, rvs's setup consists of (i) a trainingset containing 7,000 instructions from manhattan; (ii) a seen-city development-set containing 1,103 instructions from manhattan; (iii) an unseencity development-set containing 1,023 instructions from pittsburgh; and (iv) a test-set containing 1,278 instructions from philadelphia. the zs split raises profound challenges (e.g., oov) at inference time, as described in section 4. learning we use supervised learning by maximizing the log-likelihood of high-level paths. we train the model with adamw @xcite for optimization. details of the learning and hyperparameters are provided in appendix b.1. ## results despite the 2km maximum distance between the start and goal, we did not constrain our models or teach them s2-cell distances. so the maximum error of the learned models was greater than 2km. the improved performance of the t5+graph over the t5 indicates that the added graph can capture semantic geospatial information. the novel zs city-split setup we introduced provides a profound challenge for natural language understanding due to the appearance of new spatial relations and new entities in the environment. this can be seen in the inability of the learning model to generalize from seen to unseen environments, resulting in low performance, even underperforming the non-learning landmark baseline. tables 6 and 7 show an error analysis of 20 examples of the t5+graph's results in seen-city and unseen-city splits. as shown in following ## related work as people move they perceive their surroundings and acquire knowledge of the space, known as cognitive mapping @xcite . one influential cognitive mapping theory @xcite divides cognitive mapping ability into three levels. landmark knowledge, consisting of landmarks (e.g., mountains and buildings) and their attributes (e.g., location, size, color), route knowledge, altered by the traveler's changing viewpoint @xcite and coded directly (e.g., "turn right, then straight") @xcite , or as condition-action rules based on landmark-direction associations (e.g., "turn right at the church, then straight" @xcite ), and survey knowledge, where people form a 'cognitive map' of the environment, an overview of the geospatial layout, and gain awareness of relationships between different geospatial components, even outside the route. survey knowledge is independent of a person's own position, and enables her to form different routes, refer to cardinal directions, describe landmarks at different resolution levels, and describe complex shapes of abstract features such as 'blocks'. such information is less likely to be acquired from direct experience in the environment, but is portrayed on maps @xcite . thus, instructions based on such knowledge mirror the complex understanding of the environment. in grounded nlp tasks, participants acquire knowledge over an environment provided with the task. this environment can be based on different sources, most commonly visual sensors with real @xcite @xcite or synthetic imagery @xcite @xcite . in a visual environment, participants travel through the environment, view it from a point on the ground that is on the same plane as the objects, and acquire route knowledge. @xcite found that subjects who learned an environment by walking through it were limited to route-based knowledge and used egocentric spatial relation expressions (e.g., 'on your right') in their instructions. this observation was reinforced by @xcite analysis of touchdown @xcite and r2r @xcite -two navigation tasks with walk-through environments. another type of environment uses maps @xcite @xcite @xcite , where instructors can view the environment from above and gain survey knowledge of global geospatial relations. however, previous works with maps have either presented small, simplistic environments @xcite or the task's setup has encouraged participants to give egocentric sequential instructions limited to the route @xcite @xcite . in contrast, rvs focuses on instructions that encode survey knowledge and require configurational and allocentric reasoning over a large, entity-dense environment. there are sharp differences between indoor @xcite and outdoor @xcite @xcite @xcite navigation instructions. indoor environments contain many entities referred to as definite descriptions (e.g., 'the chair') and few landmarks that can be referred to by their proper name ('the blue room in the white house'). in outdoor environments, people tend to mix the use of proper names (e.g., 'the empire state building') and definite descriptions (e.g., 'the school'). however, previous outdoor navigation tasks either contain only definite descriptions @xcite or almost exclusively proper names (paz-argaman and tsarfaty, 2019). rvs contains a balanced amount of both. bridging the human-ai gap a substantial gulf separates current models' performance from human performance in the rvs task. in seen environments, models lag behind by 58.72% in 100-meter accuracy and 212 meters in median error. this gap widens further in unseen environments, with a staggering 93.33% difference in 100meter accuracy and 1,158 meters in median error. the challenge of bridging this gap could unlock thrilling research avenues that push the boundaries of this task. spatial large language models one promising approach to tackle this challenge lies in the development of spatial large language models (llms) specifically pre-trained for geolocation based on textual descriptions. such models could unlock the vast potential of textual geospatial information readily available online @xcite . they could empower natural language-driven geospatial queries and support geo-information retrieval (gir) processes. additionally, generating instructions that describe a location based on relative landmarks -rather than explicit actions like 'turn right', which are not always relevant or sufficient for navigation in many parts of the world -can enable people to follow instructions which are less 'robotic', more natural, and more relevant. looking beyond navigation, spatial llms could also play a crucial role in enhancing the accessibility and usability of geospatial data. by enabling users to interact with maps and spatial information using natural language, llms can bridge the gap between human language and spatial data representations, making these resources more accessible to a wider range of users. ## conclusion this work presents the rvs task and dataset, which present a new focus on understanding geospatial instructions based on survey knowledge of urban environments. our analysis shows that the data presents profound spatial-reasoning challenges such as allocentric relations, multiple relations, cardinal directions, and more, requiring models with novel representations of the environment that can enhance and complement the language understanding capacity of llms. our results show that our zero-shot city split set-up presents a major challenge, leaving ample space for further research on this benchmark and task.