# One Step at a Time:
Long-Horizon Vision-and-Language Navigation with Milestones

Chan Hee Song1 Jihyung Kil1 Tai-Yu Pan1 Brian M. Sadler2 Wei-Lun Chao1 Yu Su1
1The Ohio State University 2U.S. Army Research Laboratory
{song.1855, kil.5, pan.667, chao.209<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We study the problem of developing autonomous agents that can follow human
instructions to infer and perform a sequence of actions to complete the
underlying task. Significant progress has been made in recent years,
especially for tasks with short horizons. However, when it comes to long-
horizon tasks with extended sequences of actions, an agent can easily ignore
some instructions or get stuck in the middle of the long instructions and
eventually fail the task. To address this challenge, we propose a model-
agnostic milestone-based task tracker (M-Track) to guide the agent and monitor
its progress. Specifically, we propose a milestone builder that tags the
instructions with navigation and interaction milestones which the agent needs
to complete step by step, and a milestone checker that systemically checks the
agent’s progress in its current milestone and determines when to proceed to
the next. On the challenging ALFRED dataset, our M-Track leads to a notable
$33\%$ and $52\%$ relative improvement in unseen success rate over two
competitive base models. Check our code at https://github.com/chanhee-
luke/M-Track.

##  1 Introduction

As autonomous agents (_e.g_., robots) become more integrated into our daily
life, it is increasingly important to develop autonomous agents that can
understand natural language commands and carry out the corresponding tasks. To
facilitate such a goal, various benchmarks have been proposed in the realm of
robot instruction following such as vision-and-language navigation (VLN) [1,
5, 42, 7, 55, 19, 12, 41, 64], together with a number of novel algorithms that
consistently push forward the state of the art [30, 50, 31, 54]. Specifically,
to succeed in VLN, an agent must comprehend the language instruction, ground
it into the partially-observable environment with only visual perception, and
plan and perform navigation and interaction actions in the environment to
complete the task.

Figure 1: Illustration of our M-Track approach. We show an ALFRED task [46],
which consists of an overall goal (text on the top) and six subtasks (text
below each image). The blue/red text box within each image is our extracted
navigation/interaction milestones from the subtask instructions. An agent
needs to reach the milestone of the current subtask (_e.g_., reaching
proximity to the target object for navigation milestones, or having interacted
with the target objects for interaction milestone; green masks for target
objects) before it can proceed to the next subtask.

One critical challenge in VLN arises when the task horizon becomes
substantially longer [46]. That is, a task is so complex that it essentially
consists of multiple “subtasks” that need to be completed _sequentially_ to
fulfill the whole task. For example, in Figure 1 the task “put a hot potato on
the counter to the right of the sink” can be decomposed into six subtasks.
Moreover, the subtask “heat the potato” must be carried out before the subtask
“put the potato on the counter”; otherwise, the final task is doomed to fail
no matter how accurate the subsequent planning is. Such a sequential
dependency requires the agent to closely monitor its progress and ensure it is
staying on the right track when carrying out a long-horizon task.

At first glance, this challenge may seem trivial if the language instruction
is detailed enough (like in Figure 1), such that it already defines the
subtasks and their order. However, as shown in the literature [47, 54, 20, 30,
61, 4] and our experiments, an agent fed with detailed instructions still
frequently skips subtasks, or wanders around within a subtask even when it is
already completed. In essence, what an agent truly struggles with is the lack
of awareness of _where it currently is in the long subtask sequence and how
much progress it has made within a subtask_.

To address this issue, we propose to equip VLN agents with an _explicit task
tracker_ , which keeps track of the agent’s progress within a subtask and
guides it for when to move on to the next. Concretely, we propose the concept
of milestone, which renders the necessary condition of completing a subtask.
Namely, for a subtask to be considered as completed, the milestone must be
reached. Take the subtask “take a cold potato out of the fridge” in Figure 1
as example. To complete it, the necessary condition is that the agent must see
the potato and the fridge, be close enough to them, and perform an interaction
action with the potato. We argue that by explicitly extracting such milestones
from the instructions and _grounding_ them to the environment state, we can
systematically determine if the agent should continue working on the current
subtask or proceed to the next.

To this end, we propose the milestone-based task tracker (M-Track), which
consists of two components: milestone builder and milestone checker. The
milestone builder extracts the milestone (_i.e_., the necessary completion
condition) of each subtask from the corresponding language instruction. We
model it as a named entity recognition problem and train a BERT-CRF tagger [9,
48] to accurately extract both the target objects and their action type
(_i.e_., navigation or interaction). The milestone checker then tries to
_ground_ (_i.e_., identify and localize) the extracted target objects in the
perceived environment using an object detection model [14] and checks if the
agent is close enough to them and/or is about to interact with them — to
decide if the agent is completing the current subtask and ready to move on. It
is worth noting that our M-Track only needs to access the language
instructions, the visual input to the agent, and the agent’s action, not any
internal states of the agent. Thus, it is model-agnostic and can be easily
integrated with any agent model with minimal changes.

_How can M-Track interacts with the agent to affect its action (_e.g_., to not
skip a subtask)?_ We propose two simple yet effective ways. First, at any time
step, we feed the agent with only the part of the instructions that
corresponds to the current subtask determined by the milestone tracker. This
explicitly guides the agent to focus on the current subtask. Second, and more
importantly, we apply the milestone checker _proactively_ — before the agent
executes its predicted action — to reject actions that will lead to subtask
failures. For instance, we reject the action of taking a “sponge” if the
milestone object is “fork” (Figure 2).

We validate M-Track on ALFRED [46], a recently released large-scale VLN
dataset for common household tasks. The tasks in ALFRED are considered long-
horizon because on average each task needs $50$ actions to complete. In
contrast, another popular dataset R2R [1] needs only $5$. We integrate M-Track
into two baseline VLN models LSTM [46] and VLN$\circlearrowright$BERT [18],
and demonstrate notable and consistent performance gains. When tested in seen
environments, M-Track leads to $16\%$–$57\%$ relative improvement in success
rate. In more challenging unseen environments, the relative gain increases to
$33\%$–$52\%$. Our ablation studies and qualitative results further verify
that the improvement indeed comes from agents able to better follow the
sequence of subtasks and stay on the right track.

##  2 Related Work

VLN datasets. Significant efforts have been devoted to creating simulated
environments and datasets for VLN, where a virtual agent has egocentric
perception of the environment and takes actions to navigate in it [1, 5, 42,
7, 55, 19, 12, 41, 64]. However, most datasets do not consider interaction
actions with objects, significantly limiting the complexity of tasks that an
agent can perform. The recent ALFRED dataset [46] is among the first to
provide tasks that involve both navigation and interaction actions, providing
a more challenging benchmark with much longer task horizons.

VLN models. Most early VLN models follow an LSTM-based sequence-to-sequence
architecture, taking language and visual sequences as input and predicting a
sequence of actions [46, 1, 11, 30, 50, 23]. Because of the recent success of
the Transformer [51] in vision tasks, Transformer-based models are
increasingly adopted for VLN [49, 40, 27, 32, 18]. Our M-Track is model-
agnostic and is compatible with models of both types (cf. §4.3).

Natural language instructions. ALFRED provides each task with both a high-
level (_i.e_., goal) instruction and more detailed low-level instructions.
Most previous studies train the agent with the whole instruction (_i.e_.,
concatenation of the high-level and low-level instructions) at each time step
[46, 40, 49, 47, 21]. However, for long-horizon tasks like those in ALFRED,
the low-level instructions can be quite long (six sentences on average). An
agent fed with the whole instruction thus could have difficulty digesting the
long instruction and easily lose track of the progress. M-Track helps agents
focus their attention on the most pertinent instruction and reduce
distraction.

Figure 2: Overview of the milestone checking process. Milestones are extracted
from the current low-level instruction by our milestone builder (§4.1.1).
After an action is predicted, our milestone checker (§4.1.2) examines, based
on objects with reachability information (text in images) from its object
detector, if the resultant state satisfies the milestone. Only when the
milestone is satisfied, the next low-level instruction is provided to the
agent. The agent is prevented from picking up a wrong object (sponge) by our
proactive checking (§4.2).

Step-by-step language guidance. To address the issues with long instructions,
learning low-level instructions step by step has been explored in several
prior studies [35, 63, 61, 8, 17]. BabyWalk [63] learns the low-level
instruction step by step using curriculum learning. HiTUT [61] decomposes the
whole instruction into hierarchical sub-problems and learns sequentially with
a hierarchical task network. Concurrent to this work, FILM [35] decomposes the
instruction into subtasks and learns them sequentially with the help of a
semantic map. M-Track shares a similar rationale. However, M-Track is notably
different from existing methods, especially regarding when to feed the next
low-level instruction during _test time_. First, M-Track explicitly and
systematically checks the agent’s progress, during both training and test
time, by 1) defining the completion condition, _i.e_., the milestone, of each
subtask and 2) verifying the milestone by grounding it into the environment
via a visual object detector. In contrast, existing methods either train a
binary classifier to determine subtask completion [7], or simply set an upper
bound for the number of actions to execute within each subtask [61, 63], or
only checks if the agent needs to stop using a separate module [57]. As will
be seen in §5, M-Track notably outperforms these methods in tracking the
agent’s progress and feeding the right instruction. Second, M-Track also
proactively guides the agent for better action prediction, creating another
gain in performance (cf. §4.2). Finally, M-Track is not embedded in any
specific VLN model; it is model-agnostic and can be easily integrated into
different VLN models (cf. §4.3).

##  3 VLN Background

A VLN task is generally defined as follows: given a language instruction $I$,
an agent needs to infer and perform a sequence of actions
$\\{a_{0},a_{1},\cdots,a_{t},\cdots\\}$ in the environment $E$ to complete the
task. In datasets like ALFRED [46], the instruction $I$ is composed of a high-
level instruction $I_{H}$ and a list of low-level instructions $I_{L}$, as
exemplified in Figure 1. A VLN task can thus be represented by a tuple
$(I,E,G)$, in which $G$ is the goal test of the task.

For an agent to perform the task, it will be placed in the environment $E$ and
have a certain pose at time step $t$, from which it can receive a visual input
$v_{t}$. Based on $v_{t}$ and the instruction $I$, the agent then predicts an
action $a_{t}$, which can either be a navigation one that changes the agent’s
pose (_e.g_., MoveAhead) or an interaction one that interacts with the
environment (_e.g_., PickupObject). The agent also needs to predict a binary
mask for the target object if it predicts an interaction action. Both types of
actions can potentially change the visual input $v_{t+1}$ of the next time
step. The agent will stop when it believes the task has been completed. The
final state of the environment is then compared with the goal state $G$ to
determine task completion.

Following ALFRED, we discretize an agent’s action space into $5$ navigation
action (MoveAhead, RotateRight, RotateLeft, LookUp, and LookDown), $7$
interaction actions (PickupObject, PutObject, OpenObject, CloseObject,
ToggleOnObject, ToggleOffObject, and SliceObject), and $1$ stop action (Stop).

Agent model. Without loss of generality, we define an agent model as
$a_{t}=f(v_{t},I_{t},h_{t})$, where $h_{t}$ is the memory from the previous
time steps (_e.g_., the hidden state of an LSTM). $a_{t}$ is a tuple (action,
object mask); the mask is null for stop and navigation actions. $I_{t}$ is the
instruction input at time $t$, which can be the entire $I$ or a portion of it.

##  4 Milestone-based Task Tracker (M-Track)

For long-horizon VLN tasks, an agent needs to complete multiple subtasks,
usually in a specific order, to complete the whole task. More specifically,
each low-level instruction in $I_{L}$ can be seen as a subtask. Agents then
have to decide, often implicitly, which subtask it is doing at each time step
and when to move on to the next subtask, which itself is a challenging problem
for the agent. To address that, we introduce an auxiliary module, milestone-
based task tracker (M-Track), to explicitly and interactively guide the agent
to make such decisions (see Figure 2 for an overview).

Next, we first introduce the design of M-Track (§4.1), followed by how to
integrate it with agent models (§4.2). We then introduce two base agent models
(§4.3) and how to train the base models with reinforcement learning (§4.4).

###  4.1 Design of M-Track

The core functionality of M-Track is to decide when an agent should move on to
the next subtask. On the surface, this may be done simply by training a
(binary) classifier, which takes all the language/visual signals as input.
Doing so, however, does not exploit the fact that the (sub)tasks are
compositional, composed of entities (_e.g_., objects) that are identifiable
and localizable both in the environment and in the instruction. Leveraging the
compositional nature of the (sub)tasks has multiple advantages. First, it
reduces the input space for making the decision from the space of
language/visual signals to that of discrete entities. Second, it makes the
decision rule systematic and explainable: we can make the decision by directly
comparing the entities detected in both modalities. Both of them could improve
the generalizability of the decision function.

We design M-Track to explicitly consider the compositional nature of
(sub)tasks. Specifically, we introduce the concept of milestone, which is the
_necessary condition for completing a subtask_ , _i.e_., an agent must reach
the milestone in order for the corresponding subtask to be considered as
completed. For example, if the subtask is “move to the mug”, then the agent
must navigate to the mug, see it, and be close enough to the it. If the
subtask is “pick up the mug”, then the agent must see the mug, be close enough
to it so that it can then interact with it. These two examples render the key
ingredients of a milestone, which are its target entities and its type
(navigation or interaction). Meanwhile, we say an agent has reached a
milestone only when it can perceive (see) the target entities, is already
close to them, and is doing the right type of action with them.

To this end, we represent a milestone by a tuple (type, target), and decompose
our M-Track into two components: 1) a milestone builder which constructs
milestones from the low-level instructions $I_{L}$, and 2) a milestone checker
that checks if a milestone has been reached by an agent.

####  4.1.1 Milestone Builder

We generate the milestone of a subtask according to its corresponding low-
level instruction in $I_{L}$ using named entity recognition [9]. For example,
given an instruction “Turn to the left and face the toilet”, the milestone
builder should output the tag (navigation, toilet). For the instruction “Pick
the soap up from the back of the toilet”, the milestone builder should output
(interaction, soap).

For an interaction milestone, it should contain the target objects that the
agent is going to newly interact with in the current subtask. For instance, if
the subtask is “Put down the potato on the counter” (Figure 1), the agent is
supposed to already be holding a potato (from previous subtasks). Thus,
“potato” is not a milestone target for the current subtask but “counter”
should be. For a subtask that has multiple objects to be interacted with, the
builder is designed to tag all of them. For instance, in the subtask “Grab a
potato from the fridge” (Figure 1), the agent needs to 1) open the fridge, 2)
pick up the potato, and 3) close the fridge. In this case, the builder tags
both the potato and the fridge as the targets for an interaction milestone. In
cases that the builder does not extract any target from the current subtask,
it will merge the current subtask with the next one and use the milestone
extracted from the next subtask.

Without loss of generality, we adopt a BERT-CRF model [9, 48] for the
milestone builder, and train it with data derived from the ALFRED training
data. Training data is prepared using the metadata from the ALFRED simulator.
More details are in the supplementary materials. We show that our milestone
builder reaches a fairly high F1 score (see Table 1). More analysis will be
discussed in §5.3.2.

Target Type | Val Seen | Val Unseen
---|---|---
Navigation | 90.16 | 90.62
Interaction | 96.85 | 97.17
Table 1: F1 score of milestone builder on ALFRED validation.

####  4.1.2 Milestone Checker

We introduce a milestone checker that determines if an agent has reached a
milestone (see Figure 2). Specifically, we design it to be _explicit_ : we
directly estimate the state of the agent/environment from the visual input and
compare it with the milestone. A navigation milestone is reached if the target
object is detected in the visual input and located within a reachable distance
to the agent ($1.5$ meters in ALFRED). An interaction milestone is reached
with an extra condition: the agent has to interact with the target.

State estimation. We train an object detector using data from the ALFRED
simulator that can not only localize and identify all $116$ ALFRED object
classes but also estimate their reachability (_i.e_., within $1.5$m or not).
We build upon the Mask R-CNN model [14] and introduce an additional binary
classification head for the reachability of each detected object. The ground-
truth labels for reachability are obtained from the ALFRED simulator for
training.

Milestone checking. As mentioned earlier, to reach either a navigation or an
interaction milestone, the target objects must be detected and located within
a reachable distance. To check this, we compare the target object names, which
are extracted from the language instruction (_e.g_., “kitchen island”), to the
class labels (_e.g_., countertop) of the objects detected by Mask R-CNN,
essentially a symbol grounding task. We only consider the detected objects
that are estimated to be reachable. We apply an off-the-shelf word similarity
tool based on Wordnet [10] with WUP [56] similarity from NLTK [29] to match
the target names with the object labels. The reachable object whose label has
the highest similarity (above a threshold) to a milestone target is considered
as the _grounded instance_ of that target; the target is then marked as a
success.

For interaction milestones, we need to further check if the agent is
interacting/has interacted with the target. As defined in §3, an interaction
action is a tuple of (action, object mask); the object mask is simply a binary
map over the input image. To determine if the agent’s action is for the
milestone target, we calculate the intersection-over-union (IoU) score between
the object mask and the milestone target (provided by Mask R-CNN): if the IoU
score is over a certain threshold ($0.5$), it is considered matched with the
target object of the milestone. For an interaction milestone with multiple
targets, the agent has to perform multiple interaction actions to interact
with all of them. We keep a checklist of all the milestone targets. The
milestone is reached after all the targets have been interacted with.

###  4.2 Planning with M-Track

The discussion of M-Track so far is detached from the agent. The next question
is, _how can M-Track affect an agent’s actions, _e.g_., to prevent it from
skipping a subtask?_ We propose two simple yet effective ways. First, at any
time step, we feed the agent with only the instruction of the current subtask
determined by M-Track. This explicitly guides the agent to focus on the
current subtask. Specifically in ALFRED, we feed the concatenation of $I_{H}$
and the one sentence in $I_{L}$ for the current subtask as opposed to the
entire $I_{L}$. We do so starting from the beginning of a task, when the first
sentence of $I_{L}$ is guaranteed to be the first subtask. We then proceed to
the next sentence only after the current subtask is marked as completed by
M-Track. The use of M-Track frees the agent from solely relying on its
internal mechanism like attention and hidden states to decide subtask
switching.

Second, we apply the milestone checker _proactively_ for interaction
milestones — before the agent executes its predicted action. This can prevent
an agent from interacting with a wrong object, as opposed to trying to correct
the mistake after it has happened. For example, if the milestone is
(interaction, fork) but the agent’s predicted binary mask for interaction does
not overlap with the grounded instance of fork in the image, M-Track will
reject the agent’s action by asking it to select another (action, object mask)
tuple (Figure 2). This saves the agent from having to generate an action
sequence for recovery, for example, to put the incorrectly picked-up object
back down.

In our implementation, if the first interaction action is rejected, we move on
to the next action in the agent’s top $N$ list (_e.g_., from a softmax
classifier). We iterate over the $N$ actions until we find an interaction
action whose mask matches with the milestone target or we find a navigation
action instead (_e.g_., when the right object is not in sight). If none of
those happens, the agent will take its top ranked navigation action. We set
$N$ to be $5$ in the experiments.

###  4.3 Agent Models

####  4.3.1 VLN$\circlearrowright$BERT Baseline

Figure 3: Architecture of VLN$\circlearrowright$BERT with M-Track.

Recently, Transformer-based models are becoming increasingly popular for VLN
tasks [40, 40, 61, 49]. Following this line of work, we build upon the
VLN$\circlearrowright$BERT [18] model which introduces the concept of
recurrent state vector into the Transformer architecture. Since
VLN$\circlearrowright$BERT was designed for the R2R dataset, which contains
mostly short-horizon navigation tasks, we adapt it for ALFRED with a series of
modifications. Input-wise, we utilize a pre-trained vision encoder111For
simplicity, we use the same Mask R-CNN model that is used in our milestone
checker, but it is not necessary. to extract a scene feature from $8$
panoramic views and also object features from each view as our visual input.
For action prediction, unlike VLN$\circlearrowright$BERT that only deals with
navigation actions, we employ a pointer network [52] to choose between
navigation, interaction, and stop actions: if the pointer network chooses a
scene feature, agent outputs the navigation actions needed to navigate to that
scene; if it chooses an object feature, agent outputs the mask for that
object, and additionally use an MLP to predict the interaction action type; if
it chooses a stop feature (added to the list of visual features as an all-zero
vector), agent outputs Stop. The MLP takes the concatenation of the chosen
object feature and the updated state embedding as input. The architecture as
well as its integration with M-Track is illustrated in Figure 3, and more
implementation details are provided in the supplementary materials.

####  4.3.2 LSTM Baseline

To further show the model-agnostic nature of our M-Track, we use the LSTM
baseline introduced in ALFRED [46], and extend the architecture with the same
pre-trained vision encoder used in VLN$\circlearrowright$BERT. Furthermore, to
leverage the power of the pre-trained vision encoder, we follow [40, 47] and
ask our agent to select an object from the detected objects instead of
directly predicting a binary mask. The corresponding pixel mask is retrieved
from the selected object. Refer to supplementary materials for details.

###  4.4 Learning

As shown in the ALFRED paper [46], base models like the LSTM performs rather
poorly on ALFRED when simply trained with behavior cloning. Prior studies on
other VLN tasks have demonstrated the importance of reinforcement learning
(RL) [18, 63, 50], but its effectiveness has not been validated on ALFRED. We
train the models with a combination of behavior cloning (using the cross-
entropy loss between the predicted action sequence and the ground truth),
object feature selection loss (for interaction actions), and RL. We apply the
A2C algorithm [37] which, at time $t$, samples an action $a_{t}$ according to
agent’s predicted log probability distribution $\log(p^{a}_{t})$, and measures
the advantage for that action $adv_{t}$ with a critic network and a reward. We
consider four different types of reward: 1) the straight line distance between
the agent and the current navigation/interaction target, 2) the interaction
action matching with the ground-truth interaction action which we can compute
from the environment state, 3) the visibility of the target, _i.e_., whether
the target is reachable (within 1.5m in ALFRED) and is in sight by the agent,
and 4) the final task success. Following VLNBERT [18], we combine behavior
cloning loss, cross-entropy loss for object selection and A2C.

##  5 Evaluation

Model | Test Unseen | Test Seen
---|---|---
SR | PLWSR | GC | SR | PLWSR | GC
MOCA [47] | 5.30 | 2.72 | 14.28 | 22.05 | 15.10 | 28.29
LAV [39] | 6.38 | 3.12 | 17.27 | 13.35 | 6.31 | 23.21
EmBERT [49] | 7.52 | 3.58 | 16.33 | 31.77 | 23.41 | 39.27
E.T. [40] | 8.57 | 4.10 | 18.56 | 38.42 | 27.78 | 45.44
LWIT [38] | 9.42 | 5.60 | 20.91 | 30.92 | 25.90 | 40.53
HiTUT [61] | 13.87 | 5.86 | 20.31 | 21.27 | 11.10 | 29.97
ABP [21] | 15.43 | 1.08 | 24.76 | 44.55 | 3.88 | 51.13
HLSM [4] | 16.29 | 4.34 | 27.24 | 25.11 | 6.69 | 35.79
LSTM-L | 8.70 | 4.05 | 16.97 | 14.04 | 7.20 | 21.73
LSTM-L + M-Track | 13.28 | 6.25 | 20.20 | 22.05 | 12.83 | 30.48
VLN$\circlearrowright$BERT-L | 12.23 | 5.60 | 19.64 | 21.46 | 11.56 | 28.99
VLN$\circlearrowright$BERT-L + M-Track | 16.29 | 7.66 | 22.60 | 24.79 | 13.88 | 33.35
Table 2: Performance on the ALFRED test set. We evaluate M-Track on LSTM-L and
VLN$\circlearrowright$BERT-L. M-Track notably improves all evaluation metrics
on both test unseen and seen splits. Note that M-Track using
VLN$\circlearrowright$BERT-L (or LSTM-L) achieves comparable gains to other
existing methods. Bold refers to the highest score and underline refers to the
second highest score.

###  5.1 Experimental Setup

ALFRED. We validate our approach on the ALFRED [46] dataset which evaluates an
agent’s language-guided navigation and interaction abilities for common
household tasks. ALFRED consists of $8,055$ expert demonstrations annotated
with $25,743$ natural language instructions. The standard
training/validation/test splits contain $21,023$/$1,641$/$3,062$ examples,
respectively. The validation and test sets are further split into 1) a seen
set where the environments have been seen during training and 2) an unseen set
that contains new environments. The validation/test sets include $820$/$1,533$
seen and $821$/$1,529$ unseen examples.

Evaluation metrics. We report the three main metrics used by the ALFRED
leaderboard. Success Rate (SR): a binary indicator of whether all subtasks
were completed. Path-Length Weighted Success Rate (PLWSR): SR weighted by
(expert demonstration path length)/(agent path length). Goal-Condition Success
Rate (GC): ratio of completed goal-conditions.222For example in Fig. 1, there
are 3 goal conditions: a potato is heated, a potato is on the counterop, and a
heated potato is on the counter. We note that success rate on the unseen test
set is considered the primary metric for ranking because models are prone to
memorizing the seen environments and often fail to generalize to unseen
environments.

Models for comparison. We denote the base models described in §4.3.1 and
§4.3.2 as VLN$\circlearrowright$BERT and LSTM, respectively. To improve their
competence on ALFRED, we further augment them with 1) pre-training their
vision encoder on ALFRED images, and 2) reinforcement learning (§4.4). We
denote the enhanced models as VLN$\circlearrowright$BERT-L and LSTM-L,
indicating their improved capability for long-horizon tasks. Finally, we
integrate each of them with M-Track. Even though the focus of our evaluation
is to test the effectiveness of M-Track on improving different base models, we
still compare our results with other methods that are already published.
Please refer to the supplementary materials for implementation details.

| LSTM-L | VLN$\circlearrowright$BERT-L
---|---|---
Train/Test | $\bm{-}$ | $\bm{+}$ | $\bm{-}$ | $\bm{+}$
$\bm{-}$ | 9.37 | 10.48 | 10.35 | 13.29
$\bm{+}$ | 12.20 | 15.83 | 13.17 | 17.29
Table 3: Unseen SR on ALFRED validation set with ($\bm{+}$) or without
($\bm{-}$) M-Track during training and/or test. For example, the $17.29$ cell
indicates when M-Track is integrated into VLN$\circlearrowright$BERT-L during
both training and test.

###  5.2 Main Results

We summarize the main results on the ALFRED test set in Table 2. First of all,
the results show that both of our base models are highly competitive,
performing on par or better than many recent VLN models such as E.T., LWIT,
and HiTUT. On top of that, M-Track is highly effective in improving both base
models: it improves the unseen SR of LSTM-L and VLN$\circlearrowright$BERT-L
by 4.6% and 4.1% absolute (53% and 33% relative). Finally,
VLN$\circlearrowright$BERT-L + M-Track performed as much as the best published
method, HLSM, on unseen SR (main metric), better on PLWSR for both seen and
unseen, similarly on seen SR. The higher seen and unseen PLWSR indicate that
our method successfully reduced the path length by focusing on the current
subtask to complete the task.

###  5.3 Fine-grained Analyses

####  5.3.1 When to Apply M-Track?

The flexibility of M-Track makes it possible to be applied at training time,
test time, or both. In Table 3, we show that M-Track is already beneficial
when applied only during training or test time, but the gain is most
significant when it is applied during both training and test, suggesting that
M-Track may be helping the base models in different ways during different
phases.

Model | Component | Val Unseen | Val Seen
---|---|---|---
RL | ALFRED-OD | Binary | Passive | Proactive | GT | SR | GC | SR | GC
LSTM |  |  |  |  |  |  | 1.82 | 3.09 | 9.26 | 11.09
| ✓ |  |  |  |  |  | 8.03 | 9.83 | 11.88 | 17.75
LSTM-L | ✓ | ✓ |  |  |  |  | 9.37 | 12.56 | 15.00 | 18.37
| ✓ | ✓ | ✓ |  |  |  | 10.83 | 13.39 | 17.68 | 20.46
| ✓ | ✓ |  | ✓ |  |  | 15.22 | 18.88 | 20.97 | 24.73
LSTM-L + M-Track | ✓ | ✓ |  |  | ✓ |  | 15.83 | 20.34 | 21.70 | 25.45
| ✓ | ✓ |  |  |  | ✓ | 20.36 | 30.79 | 25.12 | 31.41
VLN$\circlearrowright$BERT |  |  |  |  |  |  | 3.66 | 7.19 | 14.51 | 20.11
| ✓ |  |  |  |  |  | 9.37 | 16.42 | 16.83 | 23.12
VLN$\circlearrowright$BERT-L | ✓ | ✓ |  |  |  |  | 10.35 | 18.94 | 21.32 | 25.67
| ✓ | ✓ | ✓ |  |  |  | 14.85 | 22.13 | 22.92 | 28.90
| ✓ | ✓ |  | ✓ |  |  | 17.05 | 27.37 | 25.48 | 32.07
VLN$\circlearrowright$BERT-L + M-Track | ✓ | ✓ |  |  | ✓ |  | 17.29 | 28.98 | 26.70 | 33.21
| ✓ | ✓ |  |  |  | ✓ | 24.38 | 39.34 | 31.95 | 46.27
Table 4: Ablation studies on the validation set. RL: Reinforcement learning.
ALFRED-OD: Mask R-CNN object detector pre-trained on ALFRED training images.
Binary: Binary milestone classifier. Passive: Milestone checking after an
action is executed. Proactive: Milestone checking before an action is
executed. GT: M-Track with ground-truth milestones (an upper bound).

####  5.3.2 Ablation Studies

Table 4 shows the effectiveness of different components.

Reinforcement learning. We show that RL, with our reward design, dramatically
improves the performance of both base models, especially in unseen
environments. This clearly demonstrates the importance of RL for long-horizon
VLN tasks. While similar findings have been discussed for tasks with shorter
horizons like R2R [18, 63, 50], we are among the first to validate its
importance on ALFRED.

Pre-training object detector on ALFRED. The default Mask R-CNN model is pre-
trained on COCO [28]. We continue pre-training it on ALFRED (ALFRED-OD), which
further improves the performance.

Different milestone checking strategies. For milestone checking, we compare
the passive checking and proactive checking strategies discussed in §4.1.2. As
shown in Table 4, proactive checking performs better than passive checking,
suggesting that preventing a wrong action from happening is more preferable
than correcting the mistake afterwards. In contrast to our milestone checking,
prior work [7] has proposed a binary classifier to check the completeness of
current instruction. To compare with that, we implement a binary classifier
using an MLP conditioned on the hidden state (LSTM-L) or the state encoding
(VLN$\circlearrowright$BERT-L) that predicts if the current milestone has been
reached. While it also helps, our milestone checking strategy is still
advantageous by a large margin. Finally, we also estimate an upper bound for
M-Track using ground-truth milestones from the environment instead of our
milestone builder. While the results still show a decent room for improvement,
the gap is not dramatic, indicating that our milestone builder is reasonably
accurate, echoing Table 1.

###  5.4 Case Studies

We compares VLN$\circlearrowright$BERT-L (top) with
VLN$\circlearrowright$BERT-L + M-Track (bottom) on two validation examples
(left and right) to show the importance of M-Track (see Figure 4). First,
VLN$\circlearrowright$BERT-L (top-left) skips the current instruction without
completing it (“take the egg out from the fridge”), showing its limitation on
the long-horizon task. In contrast, VLN$\circlearrowright$BERT-L + M-Track
(bottom-left) completes all subtasks and eventually completes the whole task.
Second, VLN$\circlearrowright$BERT-L (top-right) chooses the wrong object
pencil instead of the correct object pen. The agent may be confused between
the two objects since “pencil” also appears in the current instruction and
indeed is semantically/visually similar to a pen. In contrast,
VLN$\circlearrowright$BERT-L + M-Track (bottom-right) correctly performs the
interaction task because of proactive milestone checking.

Figure 4: Case studies for M-Track.

##  6 Discussion and Conclusions

We introduce a novel milestone-based task tracker (M-Track) for vision-and-
language navigation (VLN) and show that explicit milestone detection and
checking significantly benefits long-horizon VLN tasks such as those in ALFRED
[46]. Our empirical results show the effectiveness of M-Track with two strong
baseline models. In summary, this work clearly demonstrates the importance of
explicit progress monitoring (as opposed to, _e.g_., resorting to a single
policy network for both planning and implicit progress monitoring), especially
for long-horizon tasks. To make the point, we propose one instantiation with
reference to the conditions in ALFRED, and different (or more generic)
instantiations for different conditions can be explored in the future. We note
the following limitations of the current design that warrant further
development:

Assumptions in milestone builder. Our current instantiation assumes divisible
language instructions corresponding to subtasks. It is worth mentioning that
prior work (_e.g_., BabyWalk [63]) does try a similar task decomposition idea
on the R2R dataset and shows promising results, and we believe M-Track could
be adapted similarly, though it is a less interesting setting for our purpose
because of the short horizons. Nonetheless, in more general, realistic
settings, accurate milestone building will likely be more challenging,
especially when milestones are implicit (_e.g_., “fetch a cold beer”). One
interesting direction is to discover milestones by inductive reasoning over
training instances instead of solely from language instructions. Event process
mining techniques [60] could potentially be leveraged to discover that “fetch
a cold X” generally entails going to a fridge and fetching X (_e.g_., “beer”)
from it.

Assumptions in milestone checker. To date, most VLN tasks are declarative.
Milestone/goal checking thus can be done by checking solely against the
environment state. For procedural instructions (_e.g_., “turn around twice”)
the milestone checker may need to check against the agent’s action history,
though such instructions are rare in existing datasets.

Non-unique golden trajectories. Though uncommon in ALFRED, in more complex
tasks and/or environments, there could exist multiple viable trajectories
(_e.g_., different execution orders of subtasks leading to the same goal
state) to complete a task. Currently milestones are assumed to be hard
constraints that an agent has to achieve in order to proceed. It may be
helpful to (learn to) soften the constraints imposed by milestones to provide
more flexibility.

## Acknowledgement

The authors would like to thank the colleagues from the OSU NLP group for
their thoughtful comments. This research was supported in part by NSF OAC
2118240 and NSF OAC 2112606. J. Kil, T. Pan, and W. Chao are also partially
supported by NSF IIS 2107077 and the OSU GI Development funds.

## References

  * [1] Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In CVPR, 2018.
  * [2] Valts Blukis, Nataly Brukhim, Andrew Bennett, Ross A Knepper, and Yoav Artzi.  Following high-level navigation instructions on a simulated quadcopter with imitation learning.  arXiv preprint arXiv:1806.00047, 2018.
  * [3] Valts Blukis, Ross A Knepper, and Yoav Artzi.  Few-shot object grounding and mapping for natural language robot instruction following.  arXiv preprint arXiv:2011.07384, 2020.
  * [4] Valts Blukis, Chris Paxton, Dieter Fox, Animesh Garg, and Yoav Artzi.  A persistent spatial semantic representation for high-level natural language instruction execution.  arXiv preprint arXiv:2107.05612, 2021.
  * [5] Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely, and Yoav Artzi.  Touchdown: Natural language navigation and spatial reasoning in visual street environments.  In CVPR, 2019.
  * [6] Kevin Chen, Juan Pablo de Vicente, Gabriel Sepulveda, Fei Xia, Alvaro Soto, Marynel Vázquez, and Silvio Savarese.  A behavioral approach to visual navigation with graph localization networks.  arXiv preprint arXiv:1903.00445, 2019.
  * [7] Abhishek Das, Samyak Datta, Georgia Gkioxari, Stefan Lee, Devi Parikh, and Dhruv Batra.  Embodied question answering.  In CVPR, 2018.
  * [8] Abhishek Das, Georgia Gkioxari, Stefan Lee, Devi Parikh, and Dhruv Batra.  Neural modular control for embodied question answering.  In Conference on Robot Learning, 2018.
  * [9] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [10] Christiane Fellbaum.  WordNet: An Electronic Lexical Database.  Bradford Books, 1998.
  * [11] Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Taylor Berg-Kirkpatrick, Kate Saenko, Dan Klein, and Trevor Darrell.  Speaker-follower models for vision-and-language navigation.  arXiv preprint arXiv:1806.02724, 2018.
  * [12] Daniel Gordon, Aniruddha Kembhavi, Mohammad Rastegari, Joseph Redmon, Dieter Fox, and Ali Farhadi.  Iqa: Visual question answering in interactive environments.  In CVPR, 2018.
  * [13] Weituo Hao, Chunyuan Li, Xiujun Li, Lawrence Carin, and Jianfeng Gao.  Towards learning a generic agent for vision-and-language navigation via pre-training.  In CVPR, 2020.
  * [14] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In ICCV, 2017.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [16] Yicong Hong, Cristian Rodriguez-Opazo, Yuankai Qi, Qi Wu, and Stephen Gould.  Language and visual entity relationship graph for agent navigation.  arXiv preprint arXiv:2010.09304, 2020.
  * [17] Yicong Hong, Cristian Rodriguez-Opazo, Qi Wu, and Stephen Gould.  Sub-instruction aware vision-and-language navigation.  arXiv preprint arXiv:2004.02707, 2020.
  * [18] Yicong Hong, Qi Wu, Yuankai Qi, Cristian Rodriguez-Opazo, and Stephen Gould.  A recurrent vision-and-language bert for navigation.  In CVPR, 2021.
  * [19] Vihan Jain, Gabriel Magalhaes, Alexander Ku, Ashish Vaswani, Eugene Ie, and Jason Baldridge.  Stay on the path: Instruction fidelity in vision-and-language navigation.  arXiv preprint arXiv:1905.12255, 2019.
  * [20] Liyiming Ke, Xiujun Li, Yonatan Bisk, Ari Holtzman, Zhe Gan, JJ (Jingjing) Liu, Jianfeng Gao, Yejin Choi, and Siddhartha Srinivasa.  Tactical rewind: Self-correction via backtracking in vision-and-language navigation.  In CVPR, 2019.
  * [21] Byeonghwi Kim, Suvaansh Bhambri, Kunal Pratap Singh, Roozbeh Mottaghi, and Jonghyun Choi.  Agent with the big picture: Perceiving surroundings for interactive instruction following.  In Embodied AI Workshop CVPR, 2021.
  * [22] Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi.  AI2-THOR: An Interactive 3D Environment for Visual AI.  arXiv, 2017.
  * [23] Shuhei Kurita and Kyunghyun Cho.  Generative language-grounded policy in vision-and-language navigation with bayes’ rule.  arXiv preprint arXiv:2009.07783, 2020.
  * [24] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In Proceedings of the Eighteenth International Conference on Machine Learning, ICML ’01, page 282–289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
  * [25] Jialu Li, Hao Tan, and Mohit Bansal.  Improving cross-modal alignment in vision language navigation via syntactic information.  arXiv preprint arXiv:2104.09580, 2021.
  * [26] Juncheng Li, Xin Wang, Siliang Tang, Haizhou Shi, Fei Wu, Yueting Zhuang, and William Yang Wang.  Unsupervised reinforcement learning of transferable meta-skills for embodied navigation.  In CVPR, 2020.
  * [27] Xiujun Li, Chunyuan Li, Qiaolin Xia, Yonatan Bisk, Asli Celikyilmaz, Jianfeng Gao, Noah Smith, and Yejin Choi.  Robust navigation with language pretraining and stochastic sampling.  arXiv preprint arXiv:1909.02244, 2019.
  * [28] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [29] Edward Loper and Steven Bird.  Nltk: The natural language toolkit.  In Proceedings of the ACL Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics. Philadelphia: Association for Computational Linguistics, 2002.
  * [30] Chih-Yao Ma, Jiasen Lu, Zuxuan Wu, Ghassan AlRegib, Zsolt Kira, Richard Socher, and Caiming Xiong.  Self-monitoring navigation agent via auxiliary progress estimation.  arXiv preprint arXiv:1901.03035, 2019.
  * [31] Chih-Yao Ma, Zuxuan Wu, Ghassan AlRegib, Caiming Xiong, and Zsolt Kira.  The regretful agent: Heuristic-aided navigation through progress estimation.  In CVPR, 2019.
  * [32] Arjun Majumdar, Ayush Shrivastava, Stefan Lee, Peter Anderson, Devi Parikh, and Dhruv Batra.  Improving vision-and-language navigation with image-text pairs from the web.  In ECCV, 2020.
  * [33] Bar Mayo, Tamir Hazan, and Ayellet Tal.  Visual navigation with spatial attention.  In CVPR, 2021.
  * [34] Drew McDermott, Malik Ghallab, Adele E. Howe, Craig A. Knoblock, Ashwin Ram, Manuela M. Veloso, Daniel S. Weld, and David E. Wilkins.  Pddl-the planning domain definition language.  1998\.
  * [35] So Yeon Min, Devendra Singh Chaplot, Pradeep Ravikumar, Yonatan Bisk, and Ruslan Salakhutdinov.  Film: Following instructions in language with modular methods.  arXiv preprint arXiv:2110.07342, 2021.
  * [36] Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi.  Mapping instructions to actions in 3d environments with visual goal prediction.  arXiv preprint arXiv:1809.00786, 2018.
  * [37] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In ICML, 2016.
  * [38] Van-Quang Nguyen, Masanori Suganuma, and Takayuki Okatani.  Look wide and interpret twice: Improving performance on interactive instruction-following tasks.  arXiv preprint arXiv:2106.00596, 2021.
  * [39] Kolby Nottingham, Litian Liang, Daeyun Shin, Charless C Fowlkes, Roy Fox, and Sameer Singh.  Modular framework for visuomotor language grounding.  arXiv preprint arXiv:2109.02161, 2021.
  * [40] Alexander Pashevich, Cordelia Schmid, and Chen Sun.  Episodic transformer for vision-and-language navigation.  arXiv preprint arXiv:2105.06453, 2021.
  * [41] Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba.  Virtualhome: Simulating household activities via programs.  In CVPR, 2018.
  * [42] Michaela Regneri, Marcus Rohrbach, Dominikus Wetzel, Stefan Thater, Bernt Schiele, and Manfred Pinkal.  Grounding action descriptions in videos.  In TACL, 2013.
  * [43] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  NeurIPS, 2015.
  * [44] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  IJCV, 2015.
  * [45] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun.  Semi-parametric topological memory for navigation.  arXiv preprint arXiv:1803.00653, 2018.
  * [46] Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox.  ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.  In CVPR, 2020.
  * [47] Kunal Pratap Singh, Suvaansh Bhambri, Byeonghwi Kim, Roozbeh Mottaghi, and Jonghyun Choi.  Factorizing perception and policy for interactive instruction following.  In CVPR, 2021.
  * [48] Fábio Souza, Rodrigo Nogueira, and Roberto de Alencar Lotufo.  Portuguese named entity recognition using bert-crf.  ArXiv, abs/1909.10649, 2019.
  * [49] Alessandro Suglia, Qiaozi Gao, Jesse Thomason, Govind Thattai, and Gaurav Sukhatme.  Embodied bert: A transformer model for embodied, language-guided visual task completion.  arXiv preprint arXiv:2108.04927, 2021.
  * [50] Hao Tan, Licheng Yu, and Mohit Bansal.  Learning to navigate unseen environments: Back translation with environmental dropout.  arXiv preprint arXiv:1904.04195, 2019.
  * [51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NeurIPS, 2017.
  * [52] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In NeurIPS, 2015.
  * [53] Hanqing Wang, Wenguan Wang, Wei Liang, Caiming Xiong, and Jianbing Shen.  Structured scene memory for vision-language navigation.  In CVPR, 2021.
  * [54] Hanqing Wang, Wenguan Wang, Tianmin Shu, Wei Liang, and Jianbing Shen.  Active visual information gathering for vision-language navigation.  In ECCV, 2020.
  * [55] Erik Wijmans, Samyak Datta, Oleksandr Maksymets, Abhishek Das, Georgia Gkioxari, Stefan Lee, Irfan Essa, Devi Parikh, and Dhruv Batra.  Embodied question answering in photorealistic environments with point cloud perception.  In CVPR, 2019.
  * [56] Zhibiao Wu and Martha Palmer.  Verb semantics and lexical selection.  In ACL, 1994.
  * [57] Jiannan Xiang, Xin Wang, and William Yang Wang.  Learning to stop: A simple yet effective approach to urban vision-language navigation.  In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 699–707, Online, Nov. 2020. Association for Computational Linguistics.
  * [58] Jiannan Xiang, Xin Eric Wang, and William Yang Wang.  Learning to stop: A simple yet effective approach to urban vision-language navigation.  arXiv preprint arXiv:2009.13112, 2020.
  * [59] Wei Yang, Xiaolong Wang, Ali Farhadi, Abhinav Gupta, and Roozbeh Mottaghi.  Visual semantic navigation using scene priors.  arXiv preprint arXiv:1810.06543, 2018.
  * [60] Hongming Zhang and et al.  Analogous process structure induction for sub-event sequence prediction.  In EMNLP, 2020.
  * [61] Yichi Zhang and Joyce Chai.  Hierarchical task learning from language instructions with unified transformers and self-monitoring.  arXiv preprint arXiv:2106.03427, 2021.
  * [62] Fengda Zhu, Yi Zhu, Xiaojun Chang, and Xiaodan Liang.  Vision-language navigation with self-supervised auxiliary reasoning tasks.  In CVPR, 2020.
  * [63] Wang Zhu, Hexiang Hu, Jiacheng Chen, Zhiwei Deng, Vihan Jain, Eugene Ie, and Fei Sha.  Babywalk: Going farther in vision-and-language navigation by taking baby steps.  arXiv preprint arXiv:2005.04625, 2020.
  * [64] Yuke Zhu, Daniel Gordon, Eric Kolve, Dieter Fox, Li Fei-Fei, Abhinav Gupta, Roozbeh Mottaghi, and Ali Farhadi.  Visual semantic planning using deep successor representations.  In ICCV, 2017.

## Appendices

In this supplementary material, we provide details omitted in the main text.

  * •

Appendix A: More related work

  * •

Appendix B: M-Track implementation details

  * •

Appendix C: Model implementation details

  * •

Appendix D: Additional experiments

##  Appendix A More Related Work

Due to the space constraint, we only include the most related works in the
main text. Here, we add some extra related works to show recent trends in VLN.

Auxiliary information in VLN. M-Track can be viewed as an auxiliary
information to the agent. A variety of auxiliary information has indeed been
explored to improve the VLN models [33, 59, 4, 53, 45, 6, 62, 25, 26, 3, 2,
58, 35]. Several prior works proposed to build a semantic map that encodes the
spatial semantic information to bridge the gap between instructions and visual
observations [33, 4, 2, 35]. Other studies suggested a topological map that
memorizes previous actions and locations to facilitate planning [53, 45, 6].
M-Track is different from them by its simplicity, functionality, and
compatibility — it is completely detached from VLN models and thus model-
agnostic.

Data Augmentation in VLN. A number of prior studies investigate data
augmentation to increase generalizability in unseen environments. One stream
of works focuses on generating synthetic language instructions [11, 40, 54,
17, 32]. E.T. [40] constructs synthetic instructions using the expert path
planner in ALFRED. Speaker-Follower [11] generates human-like textual
instructions based on a VLN model trained on ground-truth routes. The other
stream considers augmenting visual observations. Most of these works include
surrounding views to enlarge an agent’s field of view and thus enhance its
navigation ability [21, 16, 38, 4, 49, 13]. In line with these studies, we
augment visual observations using panoramic views with different angles and
headings.

Learning Strategies in VLN. Several studies train VLN models with imitation
learning [46, 40, 1, 23, 58, 27, 47] while some other works apply
reinforcement learning [26, 59, 36]. To balance exploration and exploitation
in navigation, some recent works leverage both imitation learning and
reinforcement learning [18, 63, 50, 25, 19, 16]. Following the recent studies,
M-Track exploits both of them and shows notable improvement on ALFRED.

Visual Input. There has been significant recent progress in learning visual
representations of views. Several studies take image features encoded by
ResNet [15] as visual input [46, 1, 11, 63]. VLN$\circlearrowright$BERT [32]
take as input object features from Faster R-CNN [43] to encode objects’
semantic information. Some other studies leverage both image and object
features to learn better visual representations [18, 16]. Recently, several
papers use a pre-trained segmentation model (_e.g_., Mask R-CNN [14]) to
obtain more accurate object information [35, 47, 21, 61, 40, 49]. Following
the recent trend in VLN, M-Track exploits Mask R-CNN to detect objects for
milestone checking and encode their visual representations to facilitate
interaction tasks.

##  Appendix B M-Track Implementation Details

###  B.1 Milestone Builder

To estimate an upper bound of M-Track, we first build a ground-truth dataset
using ground-truth tags derived from the ALFRED [46] expert demonstrations.
The ALFRED expert demonstrations are encoded in Planning Domain Definition
Language (PDDL) [34] rules. PDDL annotations include task-specific goal
conditions for each low-level instruction. Each low-level instruction in PDDL
language is defined by (d, i, p), where d = (action, argument) is a discrete
action tuple containing the description of the action and its argument
(object), i is the index of the low-level instruction, p = (action,
location/ObjectID) is a planner action which is an action tuple directly
applicable to the simulator. We use the discrete action tuple to tag the low-
level instruction with the ground-truth object labels. For example, “Go to the
trash can on the far side of the kitchen”, is labeled with the discrete action
(GotoLocation, trashcan), based on which we automatically tag the instruction
as (O, O, O, B-Nav, I-Nav, O, O, O, O, O, O, O). We apply BIO tagging
format333B- prefix indicates the tag is the beginning of an object label, I-
prefix indicates the tag is inside/end of the object label, and O refers to
all non-tagged words. to turn the object labels into tags. Every ALFRED low-
level instruction has annotated labels, enabling us to build the ground-truth
milestone training data easily. After tagging the ALFRED training and
validation data with the ground truth object labels in this way, we train a
BERT-CRF [9, 48] tagger on the training data to predict the milestone tags in
the instruction. We choose BERT to utilize its powerful context encoding
capability and add a CRF [24] layer on top of BERT to better model the
interdependence of tag predictions. BERT-CRF is trained end to end with
training data generated from the training split of ALFRED and validated with
validation set generated with validation seen and unseen annotations for
ALFRED. The model that has the highest F1 on the validation set is chosen.

During the main model (_e.g_., VLN$\circlearrowright$BERT-L + M-Track)
execution, BERT-CRF outputs tags for a given low-level instruction. For
instance, in the instruction, “Turn and go to the sink”, BERT-CRF outputs (O,
O, O, O, O, B-Nav). The (tag, word) pair is our predicted milestone for the
instruction. We freeze BERT-CRF during the main model training.

Figure 5: Examples of milestones.

###  B.2 Milestone Checking

Here we elaborate on the design decisions for some corner cases during
milestone checking.

  * •

What if an instruction contains multiple milestones?

    * 1.

Navigation + Navigation: Navigate to the first milestone then to the next.

    * 2.

Navigation + Interaction: Navigate to the navigation milestone first and
navigate/interact with the interaction milestone.

    * 3.

Interaction + Interaction: Interact with both objects without specifying a
fixed order.

  * •

What if an instruction contains no milestone? There are only less than 1% of
such cases in the validation unseen environments in ALFRED (_i.e_., $40$ out
of $5,140$ instructions). For those cases, we concatenate the current
instruction with the next instruction that has milestones detected.

  * •

What happens if the milestone builder makes a mistake, _e.g_., missing a
milestone / extracting an unnecessary milestone / detecting a wrong object?
Generally the milestone builder is pretty accurate (c.f. Table 1 in the main
paper), so mistakes are not common. However, in the cases when a mistake does
occur, we currently have the agent skip the milestone if the checking fails
$15$ consecutive times. On the other hand, if the object detector fails to
detect the object, usually the failure is recovered later when the agent is in
a different pose to take a new view of the object.

##  Appendix C Model Implementation Details

###  C.1 VLN$\circlearrowright$BERT

Our modified VLN$\circlearrowright$BERT [18] consists of four modules: a
language encoder, a vision encoder, an action decoder, and a pointer network
with a multi-layer perceptron. Given a time step $t$, the language encoder
takes current instruction (_i.e_., the concatenation of the high-level
instruction and the current low-level instruction) as input and outputs the
contextualized token embeddings. Following VLN$\circlearrowright$BERT, we
consider the [CLS] embedding as a state embedding $s_{t}$ representing an
agent’s current state and denotes other textual token embedding as
$x_{i}$444We omit $t$ on other variables (_e.g_., textual token embeddings,
scene/object features, etc.) for simplicity except for the state embedding..
For the vision encoder, we leverage Mask R-CNN to obtain two types of visual
features: 1) a scene feature $v_{j}$ representing a view, and 2) an object
feature $o_{k}$ indicating an object in the view. In total, we extract 8 scene
features from panoramic views (4 headings of 90∘ and 2 elevation angles of
$\pm 30^{\circ}$) and 20 highest scoring object features from all scenes. The
action decoder then performs a grounded language learning by taking four
inputs: a previous state embedding $s_{t-1}$, a sequence of textual embeddings
$\\{x_{i}\\}$, a sequence of scene features $\\{v_{j}\\}$, and a sequence of
object features $\\{o_{k}\\}$.

$\displaystyle s_{t},{}$
$\displaystyle\\{x^{\prime}_{i}\\},\\{v^{\prime}_{j}\\},\\{o^{\prime}_{k}\\}=$
(1)
$\displaystyle\text{VLN$\circlearrowright$BERT}(s_{t-1},\\{x_{i}\\},\\{v_{j}\\},\\{o_{k}\\})$

Unlike VLN$\circlearrowright$BERT, we employ a pointer network [52] to let the
agent choose between navigation and interaction action. The pointer network
predicts an action for the time step $t$ by (2), (3), and (4).

$\displaystyle u_{n}{}$
$\displaystyle=z^{\top}\text{tanh}(W_{1}e_{n}+W_{2}s_{t}),$ (2) $\displaystyle
e_{n}\in\\{v^{\prime}_{j}\\}\cup\\{o^{\prime}_{k}\\},n\in(1,\cdots,J+K)$

where $z$, $W_{1}$, $W_{2}$ are learnable parameters, $e_{n}$ is either the
scene feature or the object feature, and $s_{t}$ is the updated state
embedding.

$\hat{n}=\operatorname*{argmax}_{n\in(1,\cdots,J+K)}\sigma(u)_{n}$ (3)

where $\sigma$ is the softmax normalizing the vector $u$. If $\hat{n}$
represents a scene, the agent should navigate to the scene $\hat{n}$ at the
time step $t$. In contrast, if $\hat{n}$ indicates an object, the agent should
interact with the object $\hat{n}$ at the time step $t$ by the corresponding
interaction action $\hat{a}$

$\hat{a}=\operatorname*{argmax}_{a\in\text{IA}}\sigma(W_{3}[s_{t};o^{\prime}_{\hat{n}}])_{a}$
(4)

where $W_{3}$ is the learnable parameter, $o^{\prime}_{\hat{n}}$ is the
feature of object $\hat{n}$, and IA is the set of 7 interaction actions.

###  C.2 LSTM

Figure 6: Architecture of LSTM-L with M-Track.

We modify the CNN-LSTM model presented in ALFRED [46] with support for a pre-
trained object encoder inspired by common VLN models’ approach [11, 50, 53] in
choosing between multiple scene features. Given a high level goal instruction
$G$ and step-by-step instructions $S=\\{s_{1},s_{2},\cdots s_{n}\\}$ of $n$
instruction sentences, we concatenate the goal instruction with only the
relevant step-by-step instruction such as $L=\\{G,\text{$<$SEP$>$},s_{n}\\}$
with $<$SEP$>$ token indicating the difference between the goal and step-by-
step instruction. Then we perform a soft-attention on the language feature
generated from BERT [9] to compute the attention distribution conditioned on
the previous hidden state of the LSTM:

$\displaystyle\alpha_{t}$
$\displaystyle=\text{softmax}((W_{x}h_{t-1})^{\top})x_{t}$ (5)
$\displaystyle\hat{x_{t}}$ $\displaystyle=\alpha_{t}^{\top}x_{t}$

where $W_{x}$ is the learnable parameter, $h_{t-1}$ is the previous LSTM
hidden state, $x_{t}$ is the current language feature, and $\hat{x_{t}}$ is
the weighted sum of $x_{t}$ over the attention distribution $\alpha_{t}$.
Furthermore, each visual observation of the agent’s view is encoded with a
pre-trained Mask R-CNN [14], where we take the scene feature from its
ResNet-50-FPN backbone. At each time step $t$, the LSTM takes in the object
feature $\\{o_{t,z}\\}$, which are 20 highest-scoring object features from the
vision encoder concatenated with spatial and reachability encoding as in
VLN$\circlearrowright$BERT, scene feature $v_{t}$, language feature
$\hat{x_{t}}$, previous action embedding $a_{t-1}$, and outputs a new hidden
state $h_{t}$:

$h_{t}=\text{LSTM}([\\{o_{t,z}\\};v_{t};\hat{x_{t}};a_{t-1}],h_{t-1})$ (6)

The agent interacts with the environment by choosing an action and providing a
binary mask (if the action is an interaction). To leverage the power of the
pre-trained vision encoder, we follow [40, 47] and ask our agent to choose an
object $o_{t,z}$. The corresponding pixel mask is retrieved from the predicted
object. We formulate object choosing in a same fashion as choosing navigable
directions in common VLN models [11, 50, 53]. Action and object are generated
from two different networks:

$\displaystyle a_{t}$
$\displaystyle=\operatorname*{argmax}(W_{a}[h_{t};u_{t}])$ (7) $\displaystyle
p(o_{t,z})$ $\displaystyle=\text{softmax}_{z}(o_{t,z}W_{o}h_{t})$
$\displaystyle\hat{o}_{t,z}$
$\displaystyle=\operatorname*{argmax}_{z}p(o_{t,z})$

where $W_{o}$ and $W_{a}$ are learnable parameters, and
$u_{t}=[v_{t};\hat{x_{t}};a_{t-1}]$. Action prediction is trained with the
ground-truth expert actions and reinforcement learning. The object feature is
learned end-to-end with the ground-truth object information.

###  C.3 Vision Encoder

For the vision encoder for M-Track, we train an instance segmentation model,
Mask R-CNN[14], as our vision encoder with training data generated from the
expert demonstration images from ALFRED and ground-truth segmentation
information from Ai2Thor simulator. Mask R-CNN is a two-stage detector, which
the first stage proposes region of interests (RoI) by Region Proposal Network
(RPN) [43] and the second stage extracts RoI features from the feature map by
RoI Align [14] and makes predictions with three heads, box classification, box
regression, and mask head. The box heads share the same RoI features extracted
with proposals, while the mask head extracts with the predictions by the box
regression head.

In the milestone checking, we not only are interested in objects and their
locations but also care about whether they are reachable by the agent.
Following the idea, we further implement the fourth head, using the same
manner as the mask head, to predict availability for each object. We simply
define objects within 1.5 meters as available for the binary classification by
using the distance information from Ai2Thor simulator. Finally, the overall
loss of pre-training our vision encoder is the summation of losses from four
heads,

$\mathcal{L}=\mathcal{L}_{cls}+\mathcal{L}_{reg}+\mathcal{L}_{mask}+\mathcal{L}_{avail}.$
(8)

With a pre-trained vision encoder, we use its ResNet [15] backbone to encode
scene features from environments and top-k RoI features from the mask head as
object features to attend with the language model. For milestone checking, it
also provides object labels and their reachability information.

Error Types |  | L | L+M-Track | V | V+M-Track
---|---|---|---|---|---
No error |  | 76 | 129 | 83 | 134
Interaction Failure |  | 231 | 255 | 178 | 199
| Collision | 87 | 99 | 100 | 121
| Interact with other object | 31 | 23 | 31 | 54
| Wander endlessly | 66 | 130 | 22 | 24
| Navigate to next subtask location | 47 | 0 | 33 | 0
Navigation Failure |  | 513 | 436 | 559 | 487
| Collision | 205 | 288 | 245 | 296
| Interact with other object | 24 | 18 | 33 | 13
| Wander endlessly | 183 | 130 | 203 | 172
| Navigate to next subtask location | 101 | 0 | 78 | 0
Table 5: Error cases on unseen validation. Interaction Failure: Agent gets
close to the target object but fails to interact with it. Navigation Failure:
Agent does not navigate to the target object at all. Next Action: Next action
that happens after the failure has happened. L stands for LSTM-L and V stands
for VLN$\circlearrowright$BERT-L.

###  C.4 Learning

####  C.4.1 Reward Shaping

In addition to the progress (navigation) and stop rewards defined in
VLN$\circlearrowright$BERT [18], we apply the interaction action matching as
an additional reward to guide the agent to perform interaction action when
needed. Furthermore, we introduce a visibility reward to make the agent learn
to face the correct direction during the interaction.

Navigation Reward. Following VLN$\circlearrowright$BERT, navigation reward
acts as a strong supervision for directing our agent to the target object.
Formally, $D_{t}$ is a distance from the agent to the target object at time
$t$, and $\Delta D_{t}=D_{t-1}-D_{t}$ is a change of distance by an action
$a_{t}$. Reward for each $a_{t}$ is defined as:

$r^{D}_{t}=\begin{cases}+1,&\Delta D_{t}>0\\\ -1,&\text{otherwise}\end{cases}$
(9)

Stop Reward. When the agent decides to stop $a_{t}==\text{{\footnotesize
stop}}$, we give the agent the final reward depending on if the task is
successful or not:

$r_{final}=\begin{cases}+3,&\text{Task}==\text{Success}\\\
-3,&\text{otherwise}\end{cases}$ (10)

where the task success means that the agent has completed all subtasks for the
task.

Interaction Reward. Since VLN$\circlearrowright$BERT trains the agent in a
navigation-only dataset, we need to define an additional interaction reward in
order for the agent to learn to choose between navigation and interaction
actions. Formally, at a given time step $t$, the agent will be rewarded if the
interaction action matches the ground-truth interaction action, which we
retrieve from the environment state. The reward for each $a_{t}$ is defined
as:

$r^{I}_{t}=\begin{cases}+1,&a_{t}==a^{*}_{t}\\\
-1,&\text{otherwise}\end{cases}$ (11)

Visibility Reward. We define an additional visibility reward to ensure the
agent learns to face the correct direction of the object to be interacted with
before predicting an interaction action to that object. This reward is paired
with the interaction reward, so the total reward that an agent can get from
interacting with the right object is $+2$.

$r^{V}_{t}=\begin{cases}+1,&o^{*}_{t}\text{ is reachable}\\\
-1,&\text{otherwise}\end{cases}$ (12)

####  C.4.2 Behavior Cloning

Following the prevalent approach in training VLN models [18, 50], we combine
reinforcement learning and imitation learning (_i.e_., behavior cloning) to
train our model. At each time step, the model is expected to produce the
ground-truth action and interaction mask (for interaction actions). We apply
cross-entropy loss between the predicted actions and the ground-truth action
and add it to our reinforcement learning loss to ensure that the current
trajectory is favored toward the expert demonstration trajectory. While we can
adapt the expert demonstration directly on the LSTM-L + M-Track, it is not
straightforward in VLN$\circlearrowright$BERT-L + M-Track because it requires
a panoramic input. Since ALFRED does not provide panoramic expert
demonstration, we generated panoramic ground-truth trajectory information from
ALFRED expert demonstration using its trajectory augmentation
tool555https://github.com/askforalfred/alfred/tree/master/gen.

###  C.5 Training Details

For the LSTM, we use a pre-trained BERT as the language encoder and randomly
initialize the rest of the model. For VLN$\circlearrowright$BERT, we use its
pre-trained weights on R2R [1] to initialize the model. For the vision encoder
in the milestone builder, we use a ResNet-50-FPN [14] as the backbone for Mask
R-CNN and finetune on ALFRED expert demonstrations from the Ai2Thor simulator
[22] with batch size 16. We finetune the Mask R-CNN pretrained on ImageNet
[44] on 4 Nvidia A6000 GPUs for 270k iterations, with a learning rate of 0.02,
which is decreased by 10 at the 210k and 250k iteration. A weight decay of
0.0001 and momentum of 0.9 are applied. For all the experiments with M-Track
and baseline models, we use a single Nvidia 2080TI GPU and AdamW optimizer is
applied with a fixed learning rate of $10^{-5}$ for VLN$\circlearrowright$BERT
and $10^{-4}$ for LSTM. The batch size is set to 4, and the agent is trained
for 20 epochs maximum. Early stopping is applied when the model shows no
improvement on 3 consecutive epochs, and the model that shows the highest SR
on the validation unseen split is adopted for testing. For all model training,
only training split was used for training and validation split was held out.

##  Appendix D Additional Experiments

Task Type | Valid Unseen | Valid Seen
---|---|---
Pick & Place | 48 | 63
Stack & Place | 28 | 25
Place Two | 32 | 38
Examine | 50 | 69
Heat & Place | 19 | 18
Cool & Place | 32 | 29
Clean & Place | 27 | 29
Table 6: Validation completion rate (%) by task type for
VLN$\circlearrowright$BERT-L + M-Track.

Agent frequently skips subtask As mentioned in the main paper, we perform an
experiment that shows that the agent frequently skips a subtask and tries to
execute the next subtask. In Table 5, we perform an analysis of the first
fatal error that the agent encounters for the validation unseen split. We
first categorize the failure type by interaction failure, which the agent gets
close to the interaction target but fails to perform an interaction action,
and navigation failure, where the agent does not get close to a target object
at all. Then, we also retrieve the next sequence of actions after the failure
and sort them into four categories:

  * •

Collision: Agent gets stuck in the environment and can not get out

  * •

Interaction with other object: Agent interact with a wrong object or interacts
when interaction is not needed

  * •

Wander endlessly: Agent endlessly repeats a certain sequence of actions

  * •

Navigate to the next subtask location: Agent navigates to the location of the
next target object in the next subtask

We show that M-Track performs better on most error cases in both interaction
and navigation. Specifically, M-Track notably prevents the agent from
performing the next subtask without completing the current one (_e.g_., $101$
vs. $0$), reflecting M-Track’s idea.

M-Track completion rate by task type We further analyze M-Track’s completion
rate by task type in Table 6. We can see that M-Track excels at completing
relatively simple tasks such as “Pick & Place” or “Examine” effectively, while
suffers in complex tasks that require multiple interactions (_e.g_., “Heat &
Place”). We attribute this phenomenon due to the fact that the current M-Track
does not effectively learn the multi-interaction reasoning. However, by seeing
the notable improvement on the simple tasks, M-Track opens up the possibility
of leveraging more fine-grained milestone construction to improve the agent’s
task learning in VLN.


* Surcis et al. (2015) Surcis, G., Vlemmings, W. H. T., van Langevelde, H. J., et al. 2015, A&A, 578, A102, doi: 10.1051/0004-6361/201425420
  * Surcis et al. (2014) —. 2014, A&A, 565, L8, doi: 10.1051/0004-6361/201423877
  * Tobin et al. (2022) Tobin, T., Gray, M., & Kemball, A. 2022, tltobin/prism: 1.0.0, v1.0.0, Zenodo, doi: 10.5281/zenodo.7311595
  * Tobin (2019) Tobin, T. L. 2019, PhD thesis
  * Tobin et al. (2019) Tobin, T. L., Kemball, A. J., & Gray, M. D. 2019, ApJ, 871, 189, doi: 10.3847/1538-4357/aafac3
  * Tol (2012) Tol, P. 2012, Colour Schemes., SRON Technical Note, Doc. no. SRON/EPS/TN/09-002.  https://personal.sron.nl/~pault/colourschemes.pdf
  * van Straten et al. (2010) van Straten, W., Manchester, R. N., Johnston, S., & Reynolds, J. E. 2010, PASA, 27, 104, doi: 10.1071/AS09084
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261, doi: 10.1038/s41592-019-0686-2
  * Vitanov et al. (2001) Vitanov, N. V., Shore, B. W., Yatsenko, L., et al. 2001, Optics Communications, 199, 117, doi: 10.1016/S0030-4018(01)01495-X
  * Vlemmings et al. (2006) Vlemmings, W. H. T., Diamond, P. J., van Langevelde, H. J., & Torrelles, J. M. 2006, A&A, 448, 597, doi: 10.1051/0004-6361:20054275
  * Wallin & Watson (1997) Wallin, B. K., & Watson, W. D. 1997, ApJ, 481, 832, doi: 10.1086/304079
  * Watson & Wiebe (2001) Watson, W. D., & Wiebe, D. S. 2001, ApJ, 557, 967, doi: 10.1086/321694
  * Watson & Wyld (2001) Watson, W. D., & Wyld, H. W. 2001, ApJ, 558, L55, doi: 10.1086/323513
  * Weinreb et al. (1965) Weinreb, S., Meeks, M. L., & Carter, J. C. 1965, Nature, 208, 440, doi: 10.1038/208440a0
  * Western & Watson (1984) Western, L. R., & Watson, W. D. 1984, ApJ, 285, 158, doi: 10.1086/162487
  * Wong et al. (2016) Wong, K. T., Kamiński, T., Menten, K. M., & Wyrowski, F. 2016, A&A, 590, A127, doi: 10.1051/0004-6361/201527867
  * Wyenberg et al. (2021) Wyenberg, C. M., Lankhaar, B., Rajabi, F., Chamma, M. A., & Houde, M. 2021, MNRAS, 507, 4464, doi: 10.1093/mnras/stab2222