A Priority Map for Vision-and-Language Navigation with Trajectory Plans and Feature-Location Cues

Prior work on VLN agents has demonstrated reliance for navigation decisions on environment features and location-related references (Zhu et al., 2021). In the definition of $\phi_{VLN}$ above, we consider this information as the supervisory signal contained in both sets of inputs $(x_{\varsigma},x_{\psi})_{t}$. As illustrated in Figure 2, our PM-VLN module is introduced into a framework FL_PM. This framework takes outputs from a transformer-based main model $Enc_{Trans}$ together with path traces ahead of cross-modal prioritisation and classification with maxout activation $Clas_{max\ x_{i}}$. Inputs for $Enc_{Trans}$ comprise cross-modal embeddings $\bar{e}_{\eta}$ proposed by Zhu et al. (2021) and a concatenation of perspectives up to the current step $\psi_{cat}$

where $tr_{t}$ is a path trace, $z^{\prime}$ is the concatenation of the outputs of the two encoders, and $d\bar{}\hskip 1.00006pt$ is a dropout operation.

This section provides a theoretical basis for a hierarchical process of cross-modal prioritisation that optimises attention over linguistic and visual inputs. In this section we use $q$ to denote this process for convenience. During the main task $\phi_{VLN}$, $q$ aligns elements in temporal sequences $\uptau$ and $Route$ and localises spans and visual features w.r.t. a subset of all entities $Ent$ in the routes:

Inputs in $\phi_{VLN}$ consist of a linguistic sequence $\uptau$ and a visual sequence $Route$ or each trajectory $j$ in a set of trajectories. As a result of the process followed by Chen et al. (2019) to create the Touchdown task, these inputs conform to the following definition.

Definition 1 (Sequences refer to corresponding entities). At each step in $j$, $|x_{l}|$ and $|x_{v}|$ are finite subsequences drawn from $\uptau_{j}$ and $Route_{j}$ that refer to corresponding entities appearing in the trajectory $ent_{j}\subset Ent$.

In order to simplify the notation, these subsequences are denoted in this section as $x_{l}$ and $x_{v}$. Touchdown differs from other outdoor navigation tasks (Hermann et al., 2020) in excluding supervision on the alignment over cross-modal sequences. Furthermore $len(\uptau_{j})\neq len(Route_{j})$ and there are varying counts of subsequences and entities in trajectories. In an approach to $\phi_{VLN}$ formulated as supervised classification, an agent’s action at each step $\alpha_{t}\equiv$ classification $c_{t}\in\{0,1\}$ where $c$ is based on corresponding $ent_{t}$ in the pair $(x_{l},x_{v})_{t}$. The likelihood that $c_{t}$ is the correct action depends in turn on detecting $S$ signal in the form of $ent_{t}$ from noise in the inputs. The objective of $q$ then is to maximise $P_{S}$ for each point in the data space.

The process defining $q$ is composed of multiple operations to perform two functions of high-level alignment $g_{Align}$ and localisation $g_{Loc}$. At the current stage $stg$, function $g_{Align}$ selects one set of spans $\varphi_{stg}\in(\varphi_{1},\varphi_{2},…,\varphi_{n})$
where $stg$ $\begin{cases}Start,\,\textit{if }t=0\\ End,\,\textit{if }t=-1\\ \forall\ stg_{other},\,n\in N\in\sum_{n=1}^{n_{1}}>t_{-1}\ otherwise.\end{cases}\\$
This is followed by the function $g_{Loc}$, which predicts one of $\varsigma_{scnt_{0}}\lor\varsigma_{scnt_{0-1}}$ as the span $\varsigma$ relevant to the current trajectory step $scnt$

where $scnt$ $\begin{cases}scnt_{0},\,\textit{if }(\uptau,\psi_{t})=0\\ scnt_{0-1},\ otherwise.\end{cases}$

We start by describing the learning process when the agent in $\phi_{VLN}$ is a transformer-based architecture $Enc+Clas$ excluding an equivalent to $q$ (e.g. VisualBERT in Table 1 of the main report). $Enc+Clas$ is composed of two core subprocesses: cross-modal attention to generate representations $q(\bigoplus(L\Longleftrightarrow\widetilde{V}))$ and a subsequent classification $Clas(\widetilde{{e}_{\eta}}\textquoteright)$.

Definition 2 (Objective in $Enc+Clas$). The objective $Obj_{1}(\theta)$ for algorithm $q(\bigoplus(L\Longleftrightarrow\widetilde{V})$, where $L$ and $V$ are each sequences of samples $\{x_{1},x_{2},…,x_{n}\}$, is the correspondence between samples $x_{l}$ and $x_{v}$ presented at step $t$ in $\sum^{n}_{i=1}t_{i}=t_{1}+t_{2},…+t_{n}$.

It is observed that in the learning process for $Enc+Clas$, any subprocesses to align and localise finite sequences $x_{l}$ and $x_{v}$ w.r.t. $ent_{j}$ are performed as implicit elements in the process of optimising $Obj_{1}(\theta)$. In contrast the basis for the hierarchical learning process enabled by our framework FL_PM - which incorporates $q_{PM}$ with explicit functions for these steps - is given in Theorem 1.

Theorem 1. Assuming $x_{l}$ and $x_{v}$ conform to Definition 1 and that $\forall\ x\in L\ \exists\ x\in V$, an onto function $g_{Map}=mx+b,m\neq 0$ exists such that:

In this case, additional functions $g_{Align}$ and $g_{Loc}$ - when implemented in order - maximise $g_{Map}$:

Remark 1 Let $P(max\ g_{Map})$ in Theorem 1 be the probability of optimising $g_{Map}$ such that the number of pairs $N^{(x_{l},x_{v})}$ corresponding to $ent_{j}\in L_{j}\cap V_{j}$ is maximised. It is noted that $N^{(x_{l},x_{v})}$ is determined by all possible outcomes in the set of cases $\{(x_{l},x_{v})\Leftrightarrow ent_{j}$, $(x_{l},x_{v})\nLeftrightarrow ent_{j}$, $x_{l}\nLeftrightarrow x_{v}$}. As the sequences of instances $i$ in $x_{l}$, $x_{v}$ and $ent_{j}$ are forward-only, it is also noted that $N^{(x_{l},x_{v})}_{t+1}<N^{(x_{l},x_{v})}_{t}$ if $ent_{i}\not\in{x_{l}}_{i}$, $ent_{i}\not\in{x_{v}}_{i}$, or $ent^{x_{l}}_{i}\neq ent^{x_{v}}_{i}$. By definition, $N^{(x_{l},x_{v})}_{t+1}>N^{(x_{l},x_{v})}_{t}$ if $P(ent_{i}={x_{l}}_{i}={x_{v}}_{i})$ - where the latter probability is s.t. processes performed within finite computational time $CT(n)$ - which implies that $P(max\ g_{Map})|P(ent_{i}={x_{l}}_{i}={x_{v}}_{i})$.

Remark 2. Following on from Remark 1,
$CT(n^{P(ent_{i}={x_{l}}_{i}={x_{v}}_{i})})$  when  $q$  contains  $g_{t}$,  and  function
$g_{t}(max(N^{(x_{l},x_{v})}\Rightarrow ent_{j}\in L_{j}\cap V_{j}),\ where\ g_{t}\in G<\\ CT(n^{P(ent_{i}={x_{l}}_{i}={x_{v}}_{i})})$  when  $q$  does  not  contain  $g_{t}<\\ CT(n^{P(ent_{i}={x_{l}}_{i}={x_{v}}_{i})})$  when  $q$  contains  $g_{t}$,  and  function
$g_{t}(max(N^{(x_{l},x_{v})}\nRightarrow ent_{j}\in L_{j}\cap V_{j})$.

Discussion In experiments, we expect from Remark 1 that results on $\phi_{VLN}$ for architectures such as $Enc+Clas$ - which exclude operations equivalent to those undertaken by the onto function $g_{Map}$ - will be lower than the results for a framework FL_PM over a finite number of epochs. We observe this in Table 1 when comparing the performance of respective standalone and + FL_PM for VisualBERT and VLN Transformer systems. Poor results for variants (a) and (h) in Tables 2 and 3 in comparison to FL_PM + VisualBERT(4l) also support the expectation set by Remark 2 that performance will be highly impacted in an architecture where operations in $g_{Map}$ increase the number of misalignments.

Proof of Theorem 1 We use below $a*$ for a generic transformer-based system that predicts $\alpha$ on $(L,V)$, $\nabla x$ for gradients, and $\Theta^{a*}$ to denote $\Theta^{Enc+Clas}\ \nu\ \Theta^{Enc+q}$. Let sequence $x_{l}=[ent_{1},ent_{2},…,ent_{n_{1}}]$ and sequence $x_{v}=[ent_{1},ent_{2},…,ent_{n_{2}}]$, where $n_{1}$ and $n_{2}$ are unknown. We note that at any point during learning, $P_{S}(x_{l},x_{v})$ is spread unevenly over $ent_{j}$ in relation to $\Theta^{a*}\approx\mathcal{X}$.

Propositions We start with the case that $\exists\ ent_{j}:ent^{(x_{l})}$ $\ and\ ent^{(x_{v})}$. Here  $CT(n^{Ent\in L\cap V})\ for\ \Theta^{a*+g_{t}}<CT(n^{Ent\in L\cap V})\ for\ \Theta^{a*}\ where\ g_{t}$ accounts for $\Delta(Len_{1},Len_{2})$. We next consider the case where  $\nexists\ ent_{j}:\ ent^{(x_{l})}\ \nu\ ent^{(x_{v})}$. $Where\ \nexists\ g_{Loc}\ then\ P_{S}^{(x_{l},x_{v})}<\exists\ g_{Loc}\ P_{S}^{(x_{l},x_{v})}$.
We conclude with the case where $\exists\ Ent:x_{l}\ \nu\ x_{v}$.  $In\ P_{S}^{A*}\ ent^{(x_{l})}\ \bigoplus\ ent^{(x_{v})}\ when\ ent^{(x_{l})}\ \neq\ ent^{(x_{v})}.$

As  $(Ent_{L},Ent_{V})\ \Rightarrow\ Ent$, $\Theta^{a*}\ \approx\ max(N^{(x_{l},x_{v})})\ \in\ \mathcal{X}.$
 $P_{S}^{(x_{l},x_{v})}\ where\ ent_{i}\ =\ {x_{l}}_{i}\ =\ {x_{v}}_{i}\ >\ ent_{i}\ \in\ \Theta^{a*}\ \approx\\ max(N^{(x_{l},x_{v})}).$ Furthermore $P\ \exists\ ent\in\ Ent\approx(ent_{i})\ >\nexists\\ \ ent\ \not\approx\ ent_{i}.$ Therefore  $slope\ \nabla x\ increases\ and\ CT(n^{Ent\in L\cap V})\\ for\ \Theta^{a*+q}<CT(n^{Ent\in L\cap V}).$

Metrics   We align with Chen et al. (2019) in reporting task completion (TC), shortest-path distance (SPD), and success weighted edit distance (SED) for $\phi_{VLN}$. All metrics are derived using the Touchdown navigation graph. TC is a binary measure of success ${0,1}$ in ending a route with a prediction $c_{t-1}^{o}=y_{t-1}^{o}$ or $c_{t-1}^{o}=y_{t-1}^{o-1}$ and SPD is calculated as the mean distance between $c_{t-1}^{o}$ and $y_{t-1}^{o}$. SED is the Levenshtein distance between the predicted path in relation to the defined route path and is only applied when TC = 1.

Hyperparameter Settings   Frameworks are trained for 80 epochs with batch size=30. Scores are reported for the epoch with the highest SPD on $\mathcal{D}_{\phi_{VLN}}^{Dev}$. Pretraining for the PM-VLN module is conducted for 10 epochs with batch sizes $\phi_{1}=60$ and $\phi_{2}=30$. Frameworks are optimised using AdamW with a learning rate of 2.5 x 10^-3 (Loshchilov and Hutter, 2017).

Experiment Design: Chen et al. (2019) define two separate tasks in the Touchdown benchmark: VLN and spatial description resolution. This research aligns with other studies (Zhu et al., 2021, 2022) in conducting evaluation on the navigation component as a standalone task. Dataset and Data Preprocessing: Frameworks are evaluated on full partitions of Touchdown with $D^{Train}=6,525$, $D^{Dev}=1,391$, and $D^{Test}=1,409$ routes. Trajectory lengths vary with $D^{Train}=34.2$, $D^{Dev}=34.1$, and $D^{Test}=34.4$ mean steps per route. Junction Type and Heading Delta are additional inputs generated from the environment graph and low-level visual features (Schumann and Riezler, 2022). M-50 + style is a subset of the StreetLearn dataset with $D^{Train}=30,968$ routes of 50 nodes or less and multimodal style transfer applied to instructions (Zhu et al., 2021). Embeddings: All architectures evaluated in this research receive the same base cross-modal embeddings $x_{\eta}$ proposed by Zhu et al. (2021), which are learned by a combination of the outputs of a pretrained BERT-base encoder with 12 encoder layers and attention heads. At each step, a fully connected layer is used for textual embeddings $\varsigma_{t}$ and a 3 layer CNN returns the perspective $\psi_{t}$. FL_PM frameworks also receive an embedding of the path trace $tr_{t}$ at step $t$. As this constitutes additional signal on the route, we evaluate a VisualBERT model (4l) that also receives $tr_{t}$, which in this case is combined with $\psi_{t}$ ahead of inclusion in ${x_{\eta}}_{t}$. Results: In Table 1 the first block of frameworks consists of architectures composed primarily of convolutional and recurrent layers. VLN Transformer is a framework proposed by Zhu et al. (2021) for the Touchdown benchmark and consists of a transformer-based cross-modal encoder with 8 encoder layers and 8 attention heads. VLN Transformer + M50 + style is a version of this framework pretrained on the dataset described above. To our knowledge, this was the transformer-based framework with the highest TC on Touchdown preceding our work. ORAR (ResNet 4th-to-last) (Schumann and Riezler, 2022) is from work published shortly before the completion of this research and uses two types of features to attain highest TC in prior work. Standalone VisualBERT models are evaluated in two versions with 4 and 8 layers and attention heads. A stronger performance by the smaller version indicates that adding self-attention layers is unlikely to improve VLN predictions. This is further supported by the closely matched results for the VLN Transformer(4l) and VLN Transformer(8l). FL_PM frameworks incorporate the PM-VLN module pretrained on auxiliary tasks $(\phi_{1},\phi_{2})$ - and one of VisualBERT (4l) or VLN Transformer(8l) as the main model. Performance on TC for both of these transformer models doubles when integrated into the framework. A comparison of results for standalone VisualBERT and VLN Transformer systems with path traces supports the use of specific architectural components that can exploit this additional input type. Lower SPD for systems run with the FL_PM framework reflect a higher number of routes where a stop action was predicted prior to route completion. Although not a focus for the current research, this shortcoming in VLN benchmarks has been addressed in other work (Xiang et al., 2020; Blukis et al., 2018).

Ablations are conducted on the framework with the highest TC i.e. FL_PM + VisualBERT(4l). The tests do not provide a direct measure of operations as subsequent computations in forward and backward passes by retained components are not accounted for. Results indicate that initial alignment is critical to cross-modal prioritisation and support the use of in-domain data during pretraining.

Ablation 1: PM-VLN   Prioritisation in the PM-VLN module constitutes a sequential chain of operations. Table 2 reports results for variants of the framework where the PM-VLN excludes individual operations. Starting with $g_{PMTP}$, trajectory estimation is replaced with a fixed count of 34 steps for each route $tr_{t}$ (see variant (a)). This deprives the PM-VLN of a method to take account of the current route when synchronising $\uptau$ and sequences of visual inputs. All subsequent operations are impacted and the variant reports low scores for all metrics. Two experiments are then conducted on $g_{PMF}$. In variant (b), visual boost filtering is disabled and feature-level localisation relies on a base $\psi_{t}$. A variant excluding linguistic components from $g_{PMF}$ is then implemented by specifying $\imath_{t}$ as the default input from $\uptau_{t}$ (see variant (c)). In practice, span selection in this case is based on trajectory estimation only.

Ablation 2: FL_PM   Ablations conclude with variants of FL_PM where core functions are excluded from other submodules in the framework. Results for variant (d) demonstrate the impact of replacing the operation defined in Equation 3 with a simple concatenation on outputs from PM-VLN $e_{l}$ and $e_{v}^{\prime}$. A final experiment compares methods for generating action predictions: in variant (e), $g_{Clas_{max\ x_{i}}}$ is replaced by the standard implementation for classification in VisualBERT. Classification with dropout and a single linear layer underperforms our proposal by 1.3 points on TC.

A final set of experiments is conducted to measure the impact of training data for auxiliary tasks $(\phi_{1},\phi_{2})$.

Training Strategy 1: Exploiting Street Pattern in Trajectory Estimation   We conduct tests on alternate samples to examine the impact of route types in $D^{Train}_{\phi_{1}}$. The module for FL_PM frameworks in Table 1 is trained on path traces drawn from an area in central Pittsburgh (see SupMat:Sec.3) with a rectangular street pattern that aligns with the urban grid type Lynch (1981) found in the location of routes in Touchdown. Table 3 presents results for modules trained on routes selected at random outside of this area. In variants (f) and (g), versions V2 and V3 of $D^{Train}_{\phi_{1}}$ each consist of 17,000 samples drawn at random from the remainder of a total set of 70,000 routes. Routes that conform to curvilinear grid types are observable in outer areas of Pittsburgh. Lower TC for these variants prompts consideration of street patterns when generating path traces. A variant (h) where the $g_{PMTP}$ submodule receives no pretraining underlines - along with variant (a) in Table 2 - the importance of the initial alignment step to our proposed method of cross-modal prioritisation.

Training Strategy 2: In-domain Data and Feature-Level Localisation   We conclude by examining the use of in-domain data when pretraining the $g_{PMF}$ submodule ahead of feature-level localisation operations in the PM-VLN. In Table 3, versions of FL_PM are evaluated subsequent to pretraining with varying sized subsets of the Conceptual Captions dataset Sharma et al. (2018). This resource of general image-text pairs is selected as it has been proposed for pretraining VLN systems (see below). Samples are selected at random and grouped into two training partitions equivalent in number to $100\%$ (variant(i)) and $150\%$ of $D^{Train}_{\phi_{2}}$ (variant (j)). In place of the multi-objective loss applied to the MC-10 dataset, $\theta_{g_{PMF}}$ are optimised on a single goal of cross-modal matching. Variant (k) assesses FL_PM when no pretraining for the $g_{PMF}$ submodule is undertaken. Lower results for variants (i), (j), and (k) support pretraining on small sets of in-domain data as an alternative to optimising VLN systems on large-scale datasets of general samples.