You will be shown sections from a scientific research paper, together with a question about the paper. Your task is to answer the question based on the contents of the paper. Your response should be a `json` object with two fields:

"answer": An array of strings extracted directly from the paper which, collectively, answer the question.
"evidence": An array of strings. Each should be an excerpt from the paper, in which one or more of the extracted answers can be found.

For instance, for the question "What baselines did the authors compare against?", a sample response might be:

{
  "answer": ["BERT", "RoBERTa"],
  "evidence": ["In our experiments, we compare the performance of our model against BERT and RoBERTa."]
}

Do not include any text in your response other than the json.

If the question is unanswerable given the provided excerpts, respond with the single word "null".

Paper: RUN through the Streets: A New Dataset and Baseline Models for Realistic Urban Navigation

Following navigation instructions in natural language requires a composition of language, action, and knowledge of the environment. Knowledge of the environment may be provided via visual sensors or as a symbolic world representation referred to as a map. Here we introduce the Realistic Urban Navigation (RUN) task, aimed at interpreting navigation instructions based on a real, dense, urban map. Using Amazon Mechanical Turk, we collected a dataset of 2515 instructions aligned with actual routes over three regions of Manhattan. We propose a strong baseline for the task and empirically investigate which aspects of the neural architecture are important for the RUN success. Our results empirically show that entity abstraction, attention over words and worlds, and a constantly updating world-state, significantly contribute to task accuracy.

Introduction and Background
The task of interpreting and following natural language (NL) navigation instructions involves interleaving different signals, at the very least the linguistic utterance and the representation of the world. For example, in turn right on the first intersection, the instruction needs to be interpreted, and a specific object in the world (the intersection) needs to be located in order to execute the instruction. In NL navigation studies, the representation of the world may be provided via visual sensors BIBREF0, BIBREF1, BIBREF2, BIBREF3, BIBREF4 or as a symbolic world representation. This work focuses on navigation based on a symbolic world representation (referred to as a map).
Previous datasets for NL navigation based on a symbolic world representation, HCRC BIBREF5, BIBREF6, BIBREF7 and SAIL BIBREF8, BIBREF9, BIBREF10, BIBREF11, BIBREF12, BIBREF13, BIBREF14, BIBREF15 present relatively simple worlds, with a small fixed set of entities known to the navigator in advance. Such representations bypass the great complexity of real urban navigation, which consists of long paths and an abundance of previously unseen entities of different types.
In this work we introduce Realistic Urban Navigation (RUN), where we aim to interpret navigation instructions relative to a rich symbolic representation of the world, given by a real dense urban map. To address RUN, we designed and collected a new dataset based on OpenStreetMap, in which we align NL instructions to their corresponding routes. Using Amazon Mechanical Turk, we collected 2515 instructions over 3 regions of Manhattan, all specified (and verified) by (respective) sets of humans workers. This task raises several challenges. First of all, we assume a large world, providing long routes, vulnerable to error propagation; secondly, we assume a rich environment, with entities of various different types, most of which are unseen during training and are not known in advance; finally, we evaluate on the full route intended, rather than on last-position only.
We then propose a strong neural baseline for RUN where we augment a standard encoder-decoder architecture with an entity abstraction layer, attention over words and worlds, and a constantly updating world-state. Our experimental results and ablation study show that this architecture is indeed better-equipped to treat grounding in realistic urban settings than standard sequence-to-sequence architectures. Given this RUN benchmark, empirical results, and evaluation procedure, we hope to encourage further investigation into the topic of interpreting NL instructions in realistic and previously unseen urban domains.
[1]The task defined by BIBREF6 is of moving between entities only.

Models for RUN
We model RUN as a sequence-to-sequence learning problem, where we map a sequence of instructions to a sequence of actions that should be performed in order to pin the actual path on the map. The execution system we provide for the task defines three types of actions: *TURN, *WALK, *END. *TURN is one of the following: right-turn, left-turn, turn-around. The turning move is not necessarily an exact 90-degree turn; the execution system looks for the closest turn option. *WALK is a change of position in the direction we are facing. The streets can be curved, so *WALK is relative to the street that the agent is on. Each street is an ordered-list of tiles, so an action of walking two steps is in fact two actions of *WALK, in the direction the agent is facing. The *END action defines the end of each route. The input consists of an instruction sequence $x_{1:N}$, a map $M$, and a starting point $p_0$ on the map. The output is a sequence of actions $a^*_{1:T}$ to be executed.
Where $x_i$ denote sentences, $a_i$ denotes actions, $M$ is the map and $p_0$ is the starting point.
Our basic model for RUN is a sequence-to-sequence model similar to the work of BIBREF19 on SAIL, and inspired by BIBREF20. It is based on Conditioned Generation with Attention (CGA). To this model we added an Entity abstraction layer (CGAE) and a World-state representation (CGAEW). It thus consists of six components we describe in turn – Encoder, Decoder, Attention, Entity Abstraction, World-State Processor, Execution-System. The complete architecture is depicted in Fig. FIGREF7.
The Encoder takes the sequence of words that assembles a single sentence and encodes it as a vector using a biLSTM BIBREF21. The Decoder is an LSTM generating a sequence of actions that the execution-system can perform, according to weights defined by an Attention layer. The Entity Abstraction component deals with out-of-vocabulary words (OOV). We adopt a similar approach to BIBREF22, BIBREF23, replacing phrases in the sentences which refer to previously unseen entities with variables, prior to delivering the sentence to the Encoder. E.g., Walk from Macy's to 7th street turns into Walk from X1 to Y1. Variables are typed (streets, restaurants, etc.) and are numbered based on their order of occurrence in the sentence. The numbering resets after every utterance, so the model remains with a handful of typed entity-variables. The World-State Processor maps variables to the entities on the map which are mentioned in the sentence. The world-state representation consists of two vectors, one representing the entities at the current position, and one representing the entities in the path ahead. The Attention layer considers the sequence of encoded words as well as current world-state, and provides weights on the words for each of the decoder steps. In both training and testing, the Execution-System executes each action separately to produce the next position.

Experiments
We evaluate our model on RUN and assess the contribution of the particular components that we added on top of the standard CGA model.
We train the model using a negative log-likelihood loss, and used Adam BIBREF24 optimization. For weights initialization we rely on BIBREF25. We used a grid search to validate the hyper-parameters. The model converged at around 30 epochs and produced good results with 0.9 drop-out and a beam of size 4. During inference, we seek the best candidate path using beam-search and normalize the scores of the sequences according to BIBREF26.
We follow the evaluation methodology defined by BIBREF9 for SAIL where we use three-fold validation, and in each fold, we use two maps for training (90%) and validation (10%) and test on the third one. We report a sized-weighted average test result. For all models we report the accuracy per single sentences and full paragraphs. Success is measured by generating an exact route, not striding away from the path. The last position on the path should be within five tile euclidean distance from the intended destination, as the position explained in the instruction might not be specific enough for one tile. In single-sentences, the last position should also be facing the correct direction.
We provide three simple baselines for the RUN task: (1) NO-MOVE: the only position considered is the starting point; (2) RANDOM: As in BIBREF4, turn to a randomly selected heading, then execute a number of *WALK actions of an average route; (3) JUMP: at each sentence, extract entities from the map and move between them in the order they appear. If the *WALK action is invalid we take a random *TURN action.
Table TABREF8 shows the results for the baseline models as well as the HUMAN measured performance on the task. The human performance provides an upper bound for the RUN task performance, while the simple baselines provide lower bounds. The best baseline model is NO-MOVE, reaching an accuracy of 30.3% on single sentences and 0.3 on complete paragraphs. For the HUMAN case, paragraph accuracy reaches above 80.
Table TABREF8 shows the results of our model as an ablation study, and Table TABREF9 shows typical errors of each variant. We see that CGAE outperforms CGA, as the swap of entities with variables lowers the complexity of the language that the model needs to learn, allowing the model to effectively cope with unseen entities at test time. We further found that, in many cases, CGAE produces the right type of action, but it does not produce enough of it to reach the intended destination. We attribute these errors to the absence of a world-state representation, resulting in an incapability to ground instructions to specific locations. CGAEW improves upon CGAE as the existence of world-state in the score of the attention layer allows the model better learn the grounding of entities in the instruction to the map. However our best model still fails on features not captured by our world-state: abstract unmarked entities such as blocks, intersections, etc, and generic entities such as traffic-lights (Tab. TABREF9).

Conclusion
We introduce RUN, a new task and dataset for NL navigation in realistic urban environments. We collected (and verified) NL navigation instructions aligned with actual paths, and propose a strong neural baseline for the task. Our ablation studies show the significant contribution of each of the components we propose. In the future we plan to extend the world-state representation, and enable the model to ground generic and abstract concepts as well. We further intend to add additional signals, for instance coming from vision (cf. BIBREF16), for more accurate localization.

Acknowledgments
We thank Yoav Goldberg and Yoav Artzi, for their advice and comments. We thank the ONLP team at the Open University of Israel, for fruitful discussions throughout the process. We further thank the anonymous reviewers for their helpful comments. This research was presented at Georgetown University, Cornell University, and Tel-Aviv University. This research is supported by European Research Council, ERC-StG-2015 scheme, Grant number 677352, and by the Israel Science Foundation (ISF), Grant number 1739/26, for which we are grateful.

Table 1: Data Statistics of RUN: statistics over different maps and the full corpus. The table is divided into features of the symbolic world representation and the written paragraphs.

Table 2: Linguistic Analysis of RUN: we analyze 30 randomly sampled instructions in RUN. The table characterizes linguistic phenomena in RUN, categorized according to the catalogue presented in Chen et al. (2018).

Table 3: Quantitative Comparison of the HCRC (Anderson et al., 1991), SAIL (MacMahon et al., 2006), TTW (de Vries et al., 2018), and the new RUN Dataset. *We average over three randomly chosen maps. **de Vries et al. (2018) assume perfect perception: all entities at each location are known in advance.

Figure 1: An Example of a Short Navigation Paragraph: showing a navigation paragraph at the bottom and two images - full map (left image) and a small part of the map (right image). In the full map, many entities are not seen until zoom-in is applied. The navigation paragraph is divided into four sentences: (1) sentence requires a turn action; (2) requires implicit walk actions and an explicit turn; (3) requires walk actions; the last (4) sentence is a verification only and no action is required.

Figure 2: Our Model, Conditioned Generation with Attention over Words and World-States, an Entity Abstraction Layer and an Execution System (CGAEW). The light color (yellow) parts presents a standard Encoder-Decoder with attention, while the dark color (red) are components added on top of a standard CGA.

Table 5: Error analysis of all models, for different instructions, showing succeeded / failure on predicting the path.

Question: How well did the baseline perform?
{"answer": ["accuracy of 30.3% on single sentences and 0.3 on complete paragraphs"], "evidence": ["Table TABREF8 shows the results for the baseline models as well as the HUMAN measured performance on the task. The human performance provides an upper bound for the RUN task performance, while the simple baselines provide lower bounds. The best baseline model is NO-MOVE, reaching an accuracy of 30.3% on single sentences and 0.3 on complete paragraphs. For the HUMAN case, paragraph accuracy reaches above 80."]}