1. A method for providing a natural language voice user interface, comprising: receiving a natural language utterance from an input device associated with a computing device, wherein the natural language utterance relates to navigation, and wherein the computing device is moving; determining a current location and direction of travel of the computing device; selecting, from among a plurality of sets of location-specific grammar information, a set of location-specific grammar information based on proximity between the current location and a location associated with the set of location-specific grammar information and based on whether the direction of travel of the computing device corresponds with movement towards the location associated with the set of location-specific grammar information; generating a recognition grammar with the set of location-specific grammar information; generating one or more interpretations of the natural language utterance using the recognition grammar; identifying, by a navigation agent executing on the computing device, one or more requests in the natural language utterance that relate to navigation from the one or more interpretations of the natural language utterance; and resolving, by the navigation agent executing on the computing device, the one or more requests.