Learning to Follow Navigational Directions

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 806–814, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Learning to Follow Navigational Directions Adam Vogel and Dan Jurafsky Department of Computer Science Stanford University {acvogel,jurafsky}@stanford.edu Abstract We present a system that learns to fol- low navigational natural language direc- tions. Where traditional models learn from linguistic annotation or word distri- butions, our approach is grounded in the world, learning by apprenticeship from routes through a map paired with English descriptions. Lacking an explicit align- ment between the text and the reference path makes it difficult to determine what portions of the language describe which aspects of the route. We learn this corre- spondence with a reinforcement learning algorithm, using the deviation of the route we follow from the intended path as a re- ward signal. We demonstrate that our sys- tem successfully grounds the meaning of spatial terms like above and south into ge- ometric properties of paths. 1 Introduction Spatial language usage is a vital component for physically grounded language understanding sys- tems. Spoken language interfaces to robotic assis- tants (Wei et al., 2009) and Geographic Informa- tion Systems (Wang et al., 2004) must cope with the inherent ambiguity in spatial descriptions. The semantics of imperative and spatial lan- guage is heavily dependent on the physical set- ting it is situated in, motivating automated learn- ing approaches to acquiring meaning. Tradi- tional accounts of learning typically rely on lin- guistic annotation (Zettlemoyer and Collins, 2009) or word distributions (Curran, 2003). In con- trast, we present an apprenticeship learning sys- tem which learns to imitate human instruction fol- lowing, without linguistic annotation. Solved us- ing a reinforcement learning algorithm, our sys- tem acquires the meaning of spatial words through 1. go vertically down until you’re underneath eh diamond mine 2. then eh go right until you’re 3. you’re between springbok and highest view- point Figure 1: A path appears on the instruction giver’s map, who describes it to the instruction follower. grounded interaction with the world. This draws on the intuition that children learn to use spatial language through a mixture of observing adult lan- guage usage and situated interaction in the world, usually without explicit definitions (Tanz, 1980). Our system learns to follow navigational direc- tions in a route following task. We evaluate our approach on the HCRC Map Task corpus (Ander- son et al., 1991), a collection of spoken dialogs describing paths to take through a map. In this setting, two participants, the instruction giver and instruction follower, each have a map composed of named landmarks. Furthermore, the instruc- tion giver has a route drawn on her map, and it is her task to describe the path to the instruction follower, who cannot see the reference path. Our system learns to interpret these navigational direc- tions, without access to explicit linguistic annota- tion. We frame direction following as an apprentice- ship learning problem and solve it with a rein- forcement learning algorithm, …

Content truncated to 500 words