Generating Landmark Navigation Instructions from Maps as a Graph-to-Text Problem (2021)

Abstract: Car-focused navigation services are based on turns and distances of named streets, whereas navigation instructions naturally used by humans are centered around physical objects called landmarks. We present a neural model that takes OpenStreetMap representations as input and learns to generate navigation instructions that contain visible and salient landmarks from human natural language instructions. Routes on the map are encoded in a location- and rotation-invariant graph representation that is decoded into natural language instructions. Our work is based on a novel dataset of 7,672 crowd-sourced instances that have been verified by human navigation in Street View. Our evaluation shows that the navigation instructions generated by our system have similar properties as human-generated instructions, and lead to successful human navigation in Street View.

## introduction current navigation services provided by the automotive industry or by google maps generate route instructions based on turns and distances of named streets. in contrast, humans naturally use an efficient mode of navigation based on visible and salient physical objects called landmarks. as shown by @xcite , route instructions based on landmarks are easier processed and memorized by humans. @xcite recommend that in pedestrian navigation systems, "landmarks should be used as the primary means of providing directions". another navigation scenario where landmarks are useful is if gps tracking is poor or not available, and if information is inexact regarding distances (e.g., in human estimates) or street names (e.g., for users riding a bicycle). we present a neural model that takes a real-world map repre-sentation from openstreetmap foot_0 as input and generates navigation instructions that contain salient landmarks, learned directly from human natural language instructions. in our framework, routes on the map are learned by discretizing the street layout, connecting street segments with adjacent points of interest, thus encoding visibility of landmarks, and encoding the route and surrounding landmarks in a location-and rotation-invariant graph. based on crowd-sourced natural language instructions for such map representations, a graph-to-text mapping is learned that decodes graph representations into natural language route instructions that contain salient landmarks. our work is accompanied by a dataset of 7,672 instances of routes in openstreetmap and corresponding crowd-sourced natural language instructions. the navigation instructions were generated by workers on the basis of maps including all points of interest, but no street names. they were verified by different workers who followed the navigation instructions on google street view foot_1 . experimental results on randomly sampled test routes show that our graph-to-text model produces landmarks with the same frequency found in human reference instructions. furthermore, the timenormalized success rate of human workers finding the correct goal location on street view is 0.664. since these routes can have a partial overlap with routes in the training set, we further performed an evaluation on completely unseen routes. the rate of produced landmarks drops slightly compared to human references, and the time-normalized success rate also drops slightly to 0.629. while there is still room for improvement, our results showcase a promising direction of research, with a wide potential of applications in various existing map applications and navigation systems. the main contributions of this paper are: • we collect and publish a large scale dataset of natural language landmark navigation instructions that are validated by human navigation runs in street view. mirowski et al. (2018) published a subset of street view covering parts of new york city and pittsburgh. street view is a navigable environment that is build from connected real-world 360 • panoramas. this data is used by hermann et al. (2020) to train a visual agent to follow turn-by-turn instructions generated by google maps api. chen et al. (2019) published a street view dataset 3 with more recent and higher resolution panorama images that covers the lower half of manhattan. they further introduce the touchdown task that has the goal to navigate 3 www.streetlearn.cc street view in order to find a hidden teddy bear. the data for that task is obtained from annotation workers that follow a predefined route in street view and write down navigation instructions along the way. a central difference between touchdown and our dataset is the annotation modality: touchdown annotators use panorama images along the route, while our instruction writers only see the rendered route on a map. see section 4.3 for a more detailed discussion. our work puts the task of natural language navigation upside down by learning to generate humanlike navigation instructions from real-world map data instead of training an agent to follow human generated instructions. prior work in this area has used rule-based systems to identify landmarks @xcite or to generate landmarkbased navigation instructions @xcite . despite having all points of interest on the map available, our approach learns to verbalize only those points of interest that have been deemed salient by inclusion in a human navigation instruction. previous approaches that learn navigation instructions from data have been confined to simplified grid-based representations of maps for restricted indoor environments @xcite . @xcite tackles the problem in a more sophisticated outdoor environment but the model fails to verbalize useful instructions when conditioned on more than one possible landmark. other work generates navigation instructions from indoor panoramas along a path but provides no explicit evaluation like human navigation success. they rather use the instructions to augment the training routes for a vision and language navigation agent @xcite . ## task the task addressed in our work is that of automatically generating natural language landmark navigation instructions (nllni) from realworld open-source geographical data from open-streetmap. the instructions are generated a priori @xcite for the whole route. training data for nllni was generated by human crowdsourcing workers who were given a route on an openstreetmap rendering of lower manhattan, with the goal of producing a succinct natural language instruction that does not use street names or exact distances, but rather is based on landmarks. landmarks had to be visible on the map and included, e.g., churches, cinemas, banks, shops, and public amenities such as parks or parking lots. each generated navigation instruction was validated by another human crowdsourcing worker who had to reach the goal location by following the instruction on google street view. nllni outputs are distinctively different from navigation instructions produced by openroute-service, google maps, or car navigation systems. while these systems rely on stable gps signals such that the current location along a grid of streets can be tracked exactly, we aim at use cases where gps tracking is not available, and knowledge of distances or street names is inexact, for example, pedestrians, cyclists, or users of public transportation. the mode of nllni is modeled after human navigation instructions that are naturally based on a small number of distinctive and visible landmarks in order to be memorizable while still being informative enough to reach the goal. a further advantage of nllni is that they are based on map inputs which are more widely available and less time dependent than street view images. ## data collection because there is no large scale dataset for nllni that is generated from map information only, we collect data via crowdsourcing. the annotator is shown a route on the map and writes navigation instructions based on that information (figure 1 , top). we take the approach of @xcite and determine correctness of navigation instructions by showing them to other annotators that try to reach the goal location in street view (figure 1 , bottom). ## method the underlying osm geodata of the rendered map is an xml tree of nodes located in the latitudelongitude coordinate system. the nodes are composed into ways and polygons foot_5 . these elements in connection with their annotations are used to render the visual map. in the next subsection we propose our approach to represent a route and its surrounding map features as a graph that includes all necessary information for generating landmark navigation instructions. the second subsection describes the neural graph-to-text architecture that is trained to learn inductive representations of the individual route graphs and to decode navigation instructions from them. ## experiments 6.1 baselines we consider two baselines. a rule based system that uses a single heuristic to construct instructions by stringing together all pois and intersections along the route, and following each intersection by the turning direction. similar, pois are followed by 'left' or 'right' depending on which side ## conclusion we presented a dataset and suitable graph-to-text architecture to generate landmark navigation instructions in natural language from openstreetmap geographical data. our neural model includes novel aspects such as a graphical representation of a route using angle labels. our dataset consists of a few thousand navigation instructions that are verified for successful human navigation. the dataset is large enough to train a neural model to produce navigation instructions that are very similar in several aspects to human-generated instructions on partially seen test data. however, performance naturally drops on unseen data including new types of landmarks in new combinations.