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

Raphael Schumann, Stefan RiezlerACL 2021

TL;DR

This paper introduces a novel neural model that generates natural language navigation instructions using landmarks, learned from human-generated examples and OpenStreetMap data. The system represents routes as graphs and uses a graph-to-text architecture to produce instructions that are more human-like and potentially useful in GPS-denied environments compared to traditional turn-by-turn directions.

What Problem Does This Paper Address?

Current navigation systems, like Google Maps, rely heavily on precise street names and distances, often assuming reliable GPS signals. However, humans naturally use landmarks – visible physical objects – to navigate, which are more intuitive and easier to remember. This approach is particularly valuable in scenarios where GPS is unreliable or unavailable, or for users who may not be familiar with street names (e.g., cyclists). The paper addresses the challenge of automatically generating these landmark-based navigation instructions from readily available map data, bridging the gap between machine-readable map information and human-understandable directions.

Methods

The core of the proposed method involves two main components:

  • Graph Representation: Routes are first converted into a location- and rotation-invariant graph representation. This involves discretizing street layouts, connecting street segments with points of interest (POIs), and encoding visibility of landmarks. Edges in the graph can represent geometric relationships (angles) between nodes, which is crucial for capturing directional information without relying on absolute coordinates.
  • Graph-to-Text Architecture: A neural network, based on the Transformer architecture but incorporating graph attention layers, is used to learn the mapping from the graph representation to natural language instructions. The encoder processes the graph, and the decoder generates the text. This architecture is designed to attend to relevant nodes and their relationships within the graph to produce coherent and informative instructions.

Datasets

The paper introduces a new dataset:

  • map2seq Dataset: This dataset comprises 7,672 crowd-sourced navigation instructions. Routes were generated from OpenStreetMap data, and instructions were written by annotators who were given map renderings without street names, focusing on landmarks. Crucially, these instructions were validated by other annotators who attempted to follow them in Google Street View, ensuring their practical usability. This dataset is made publicly available.

The authors also reference and compare their work to existing datasets like Room-to-Room and Touchdown, noting key differences in annotation modality and data source.

Key Insights and Ideas

  • Landmarks as Primary Navigation Cues: The research strongly supports the idea that landmarks are a more natural and effective way for humans to navigate than abstract street names and distances, especially in complex urban environments.
  • Graph Representation for Spatial Reasoning: Representing routes as graphs, incorporating geometric information like angles, allows the model to capture spatial relationships in a way that is invariant to location and orientation, facilitating generalization.
  • Learning Saliency from Human Data: Instead of pre-defining what constitutes a "salient" landmark, the model implicitly learns this by observing which landmarks humans choose to include in their navigation instructions.
  • Validation in Street View is Crucial: The use of Google Street View for validating the generated instructions provides a robust, real-world measure of their effectiveness and usability.

Key Results

  • Performance on Partially Seen Data: The proposed graph-to-text model achieved competitive results on partially seen test routes, outperforming baseline rule-based and seq2seq models in terms of success rate, especially when weighted by navigation time.
  • Performance on Unseen Data: While performance naturally dropped on completely unseen routes, the model still demonstrated promising results, generating instructions with a high success rate (0.629 when normalized by time).
  • Human-like Instructions: The generated instructions were found to have similar properties to human-generated ones, including the frequency of landmark usage and sequential positioning.
  • Rule-based vs. Learned Instructions: Rule-based systems generated more landmarks but were less natural and harder to follow (indicated by lower success rates weighted by time). Seq2seq models produced more human-like language but often failed to generate correct directions.

Limitations and Future Work

  • Performance Drop on Unseen Data: The paper acknowledges that performance naturally decreases on unseen data, particularly with new types of landmarks or novel combinations, suggesting room for improvement in generalization.
  • Complexity of Routes: The model's performance, like other learned systems, drops with increasing route complexity (e.g., more turns or intersections), whereas human reference instructions remain more stable.
  • Future Work: The authors suggest exploring more sophisticated graph representations, potentially incorporating richer semantic information from POIs, and further investigating how to improve generalization to unseen environments and landmark types. They also highlight the potential for applications in various existing map-based services.

Summary updated

BibTeX
@inproceedings{schumann2021generating,
  author = {Raphael Schumann and Stefan Riezler},
  title = {{Generating Landmark Navigation Instructions from Maps as a Graph-to-Text Problem}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure