SOON: Scenario Oriented Object Navigation with Graph-based Exploration

In plain words

Most robot navigation tests give the agent a fixed starting spot and a long list of turn-by-turn directions. This paper asks for something closer to real life: the robot is dropped anywhere in a house and told what the target looks like, what is near it, and which room it is in. It then has to find that one object.

The method keeps a map of the places it has seen, as a graph whose nodes are rooms and viewpoints and whose edges are the paths it has walked. At each step it looks at the places it could go next and chooses one, or chooses to stop. It learns in three ways: by copying a teacher's moves, by trying moves and being rewarded for getting closer, and by also learning from the next move that brings it closest to the target, even when it wandered off the path a teacher would have taken. The paper also builds a large dataset of such descriptions with long trips, so the task is hard enough to show the gap between people and current agents.

TL;DR

• Task: find an object in a Matterport3D house from an arbitrary start, using a multi-part description; success is stopping within 3 m and then locating the object in the panoramic view §3.
• Method: GBE, a graph planner over visited and observed viewpoints with a GCN, plus a policy trained with imitation, A2C and a "graph-based exploration" term §4.
• Data: FAO, 3,848 instruction sets built on 90 Matterport scenes; long trajectories with a start at least 18 m from the goal at first §5.1.
• Results are author-reported: GBE reaches R2R test SPL 43.4, and FAO test SFPL 1.4 against 51.1 for humans tab. 2 tab. 3.
• The paper gives few hyperparameters (optimizer, learning rate, training length); the official code fixes many more and differs from the text in several places (see Paper vs code).

Problem

Standard vision-language navigation (for example R2R) starts the agent at a fixed pose and gives step-by-step instructions, so a wrong turn counts as an error §1. The paper argues that real requests describe the target and let the robot start anywhere §1 §3. Existing datasets do not cover this combination: the authors compare instruction-based, dialogue and object-goal benchmarks on whether instruction context, starting independence and target orientation tab. 1. Plain object-goal navigation cannot tell apart several objects of the same class, which is why the paper adds scene and region descriptions §5.2 tab. 5.

Method

Task. At step t the agent sees a panoramic view v_t with RGB and depth, and the observations u of its k reachable neighbours. The house is discretised into a navigation graph; each step moves to a neighbour or stops §3. The GPS and the node indices of the current and candidate positions are available §3.

Polar target representation. Targets are labelled as a heading and an elevation instead of a 2D box in a split view. The authors annotate the box corners, take its centre, and convert the centre to an angle offset from the camera ray. The exact conversion is not written out in the paper §3 fig. 2 fig. 3.

Graph planner (GBE). The planner keeps three sets: node features V, edges E and node embeddings M. A visited node keeps its own visual feature; an observed but unvisited node keeps the average of all features seen for it §4. Each step adds the current node and its neighbours, joins the current node to each neighbour and updates M with a GCN over V and E §4 eq. 1 eq. 2 eq. 3 eq. 4. The planner output at the current node is a mean of the embeddings of the current node and its neighbours §4 eq. 5. A cross-modal match with the language feature gives a vector f~; a fully connected layer scores each candidate and a stop action, and a second linear map regresses heading and elevation from f~ §4 eq. 6.

# One GBE navigation step  [§4] [eq. 1-6]
# Input:  view, neighbours, graph state (V, E, M), instruction
# Output: p_t over candidates and stop; heading and elevation

def gbe_step(view, neighbours, graph, instruction):
    # Embed the current view; keep the observed neighbour features  [§4] [eq. 1]
    node_feat = visual_encoder(view)
    graph.V[current] = node_feat                    # visited feature
    for each neighbour u in neighbours:
        graph.observations[u].append(u.feature)     # unvisited: mean of views
        graph.V[u] = mean(graph.observations[u])
    # Add edges from the current node to its neighbours  [§4] [eq. 3]
    graph.E = graph.E + {(current, n) for n in neighbours}
    # One GCN update over all nodes  [§4] [eq. 4]
    graph.M = gcn(graph.M, graph.E)
    # Average the current node and its neighbours  [§4] [eq. 5]
    f_g = mean(graph.M[n] for n in [current] + neighbours)
    # Match with language; f_tilde feeds both heads  [§4] [eq. 6]
    f_tilde = cross_modal_match(f_g, instruction)
    # Logits per candidate; index 0 is the stop action  [§4] [eq. 6]
    z = [W_nav @ concat(f_tilde, graph.V[c]) for c in candidates]
    p_t = softmax(z)
    heading, elevation = W_loc @ f_tilde
    return p_t, heading, elevation

Graph-based exploration. Training rollouts are sampled from the current policy rather than from the ground-truth path §4. For each sampled step, a teacher picks the candidate whose shortest-path distance to a target is smallest. If the current node is itself a target, the teacher picks stop. Several targets may exist, because an object can be seen from several viewpoints §4 eq. 7.

# Graph-based exploration teacher  [§4] [eq. 7]
# Input:  current node, candidates, target nodes, distance D
# Output: index of the action to supervise

def teacher_action(current, candidates, targets, D):
    # Stop when the agent already stands on a target  [§4]
    if current in targets:
        return STOP
    # Otherwise pick the candidate nearest to any target  [§4] [eq. 7]
    return argmin over c in candidates of min over n in targets: D(c, n)

Objective. The navigation loss sums three parts with weights λ1, λ2, λ3: imitation on ground-truth actions (λ1), an A2C policy-gradient term with the advantage A_t (λ2), and a cross-entropy term on the graph-based exploration teacher's action (λ3) §4 eq. 8. The reward is the Dijkstra distance between the current position and the target §4. The localisation loss is a mean squared error on heading and elevation §4 eq. 9. The paper does not state the values of λ1, λ2 and λ3 §4.

# Training loss  [§4] [eq. 8-9]
# Input:  ground-truth actions, sampled actions, teacher actions, advantages
# Output: scalar loss

def gbe_loss(il_steps, sampled_steps, lam1, lam2, lam3):
    # Imitation on ground-truth actions  [§4] [eq. 8]
    loss_il = -sum(log(p[a_star]) for each step in il_steps)
    # A2C term with advantage A_t on the sampled actions  [§4] [eq. 8]
    loss_rl = -sum(log(p[a]) * A for each step in sampled_steps)
    # Graph-based exploration term on sampled steps  [§4] [eq. 8]
    loss_ge = -sum(log(p[a_hat]) for each step in sampled_steps)
    loss_nav = lam1 * loss_il + lam2 * loss_rl + lam3 * loss_ge
    # Localisation: mean squared error on heading and elevation  [§4] [eq. 9]
    loss_loc = mean((h_hat - h) ** 2 + (e_hat - e) ** 2)
    return loss_nav + loss_loc

Backbone. The visual encoder is a ResNet-101 §5.2. The language encoder is a word embedding followed by an LSTM §5.2. Training uses RMSProp with a learning rate of 10^-4 §5.2. The vision-language backbone follows RCM and related work §4.

FAO construction. Annotators label boxes in panoramic views, convert them to polar form, and mark every position from which the object can be reached §5.1. Each instruction has five subtasks: attributes, relations, region, nearby regions, and a final rewrite into three sentences §5.1. Start points are sampled so that the shortest path to the target exceeds 18 m; after every five failed samples the threshold is multiplied by 0.8 §5.1.

Hyperparameters

Results

Author-reported. Setup: R2R with the standard splits, and FAO with 90 Matterport scenes §5.1 §5.2. Baseline numbers are copied from the paper. The table has only the rows needed for headline comparisons; the paper's rows for AuxRN and other baselines are in tab. 2 and tab. 3.

R2R (NE lower is better; OSR, SR, SPL higher is better) tab. 2

FAO (SR, SPL and SFPL on the unseen-house test split, all percentages) tab. 3

On the validation-seen-instruction split GBE is listed at SR 98.4, SPL 97.9 and SFPL 44.2 tab. 3. The validation-seen-house row is discussed under Pitfalls.

Modality and granularity ablations on FAO tab. 4 tab. 5

The paper reports that the graph-based exploration term improves test OSR, SR, SPL and SFPL by 0.7%, 0.5%, 1.5% and 0.6% respectively over the same model without it §5.2.

The localisation metric SFPL averages, over episodes, the product of the navigation success, the localisation success and a path-length ratio §5.2 eq. 10. Its ratio is written in the paper with the navigation length in the numerator (see Paper vs code).

Paper vs code

Official code: https://github.com/ZhuFengdaaa/SOON at commit 84d6285ffbe32cfdf2c0ccd362dcb1a855dfab18. The owner is the first author. The repository is a fork of the EnvDrop R2R code and reuses its agent, A2C loop and data pipeline agent.py. The code was cloned at the commit above; the SOON annotations (tasks/SOON/) and the precomputed image features are not in the repository, and the README gives no download step for SOON data README.md param.py. The SOON-specific paths were read, not run.

• Visual features. Paper: ResNet-101 §5.2. Code: README downloads ResNet-152 features README.md.
• Training length. Paper: 10K "interactions" §5.2. Code: 80,000 iterations by default param.py. The README command does not change this [README.md#L41].
• Graph-based exploration is masked. Paper applies the teacher to sampled steps without restriction §4. Code computes, for each step, the minimum hop distance from the current node to any node on the reference path; the term is only applied where that distance is 0 (rl_ml_th defaults to 0) nav_graph.py agent.py.
• Exploration weight off by default. --rl_ml_weight defaults to 0, so the term is disabled unless the flag is passed param.py. The README command turns it on [README.md#L41].
• Imitation teacher. Code's imitation step uses the ground-truth next viewpoint from the data nav_graph.py, which matches §4. The teacher for the sampled rollout uses the nearest-candidate rule of eq. 7, but returns stop when no candidate reaches a target nav_graph.py.
• Reward. Paper: the reward is the Dijkstra distance change §4. Code: each non-stop step gets +1 or -1 by the sign of the distance change; stopping gets +2 within 3 m of the last node of the reference path and -2 otherwise agent.py.
• A2C extras. Code adds a critic loss with factor 0.5 agent.py, an entropy bonus of 0.01 agent.py, and gradient clipping at 40 on the encoder and decoder only agent.py. None appear in eq. 8.
• Loss normalisation. Code divides the imitation and exploration terms by batch size agent.py and the A2C term by the number of valid steps agent.py. The paper's eq. 8 does not state a normalisation.
• Localisation head. Paper: MSE on heading and elevation §4 eq. 9. Code: one sigmoid output per angle with binary cross-entropy against targets scaled to [0, 1] (heading divided by 2π, elevation shifted by π and divided by 2π) model.py agent.py utils.py.
• Localisation gating. The head is only trained when --det_loss is set param.py, only in the imitation pass, and only for trajectories whose last node is one of the target views agent.py.
• Unused parameters. det_lr (the localisation head learning-rate multiplier) and explore_ratio are defined but never read param.py. gnn_order is passed to the graph class but no order-dependent code uses it nav_graph.py.
• Planner output. Paper eq. 5 averages the current node and its neighbours §4. Code takes only the GCN embedding of the current node agent.py.
• Graph convolution. Paper eq. 4 gives no normalisation or depth. Code symmetrises the adjacency, binarises it, adds self-loops and divides each row by its degree (mean aggregation), then applies one linear layer with no non-linearity nav_graph.py model.py.
• Candidate features. Paper: candidates use features from V §4. Code: candidates use the linear encoding of the mean of their observed image features, not the GCN output nav_graph.py nav_graph.py.
• Visited node features. Paper: g(v_t), with no further detail §4. Code: attends over the panoramic view features with the instruction encoding at position 0 as the query model.py.
• Revisited nodes. The guard in update_vfeat checks a viewpoint string against a dictionary keyed by integer ids, so it is always true and a revisit overwrites the stored feature. The pdb branch is unreachable nav_graph.py.
• SFPL ratio is inverted in the paper. Eq. 10 writes the path ratio as l_nav / max(l_nav, l_gt) §5.2 eq. 10. The standard SPL, and the code, use the shortest length in the numerator: shortest / max(shortest, path length), multiplied by the 3 m success indicator eval.py. Under the paper's form a short path would score lower than a long one, so implement the code's form and note the difference.
• Localisation scoring. The code multiplies the localisation hit by that SPL term, so SFPL is a mean of hit × SPL eval.py. The code counts localisation as a miss when the stop node is not a target view eval.py.
• Checkpoint selection. The code keeps the checkpoint with the best validation success rate on each validation split train.py. The paper does not say which checkpoint it reports on test.
• Licence. The repository's LICENSE file is MIT, but its copyright line names Hao Tan, Licheng Yu and Mohit Bansal, the authors of the code it builds on LICENSE. The card records MIT as the licence text says.

Pitfalls

• Unstated λ values. The paper does not give λ1, λ2 or λ3 §4. The code's defaults are not a single setting: 0.2 for imitation under sampled feedback, 1 for A2C, and 0 for the exploration term unless the flag is set train.py param.py. Treat any reproduction as unvalidated until these are fixed.
• Head learning rate. A det_lr multiplier for the localisation heads is defined but never read, so the heads train at the full learning rate param.py.
• Target scaling. Heading and elevation labels are scaled to [0, 1] in the data pipeline, and the code's BCE loss depends on that scale. The raw SOON annotation files are not in the repository, so the scale cannot be checked from the code alone utils.py.
• Stop label as fallback. When no candidate reaches any target, the teacher label becomes stop rather than an ignore index nav_graph.py. The paper does not say whether this is intended.
• Memory and compute grow with the graph. The adjacency is built dense per episode, padded to the largest graph in the batch, and rebuilt every step nav_graph.py nav_graph.py. The paper does not discuss cost.
• Dataset numbers disagree within the paper. The introduction says FAO has 40K trajectories §1 while §5.1 says "over 30K" §5.1. The average R2R instruction length is 26 words in §1 and 18.3 in §5.1 §1 §5.1. Use the §5.1 figures, which are tied to the splits in the table.
• Validation-seen-house row. In tab. 3 the GBE row for the validation-seen-house split lists OSR 64.1 below SR 76.3. Success rate cannot exceed oracle success rate by definition, so at least one of these numbers is a typo. Do not use this row for comparison until the authors confirm it.
• Localisation only counts at the stop node. A correct direction given anywhere else scores zero eval.py. The paper's text on localisation does not state this explicitly §3.
• Supplementary material not included. The paper defers details to supplementary material §5.1. The supplement was not available to this compilation, so anything not in the main text is "not stated".
• Simulator dependency. The environment needs the Matterport3D simulator as a git submodule with its own licence file, and the SOON annotations are not shipped README.md. A reproduction needs both.

Lineage

• Builds on: RCM, the reinforced cross-modal matching agent (Wang et al., 2018), for the backbone and the imitation plus RL combination §2 §4.
• Builds on: graph convolution (Kipf and Welling, 2016) for the planner update §4; A2C (Mnih et al., 2016) for the advantage §4.
• Compared against: Speaker-Follower, RCM, AuxRN, Seq2Seq, Ghost, Monitor, Regretful and EGP on R2R; Speaker-Follower, RCM, AuxRN and a GBE ablation on FAO tab. 2 tab. 3.
• Related graph methods: EGP (Deng et al., 2020) builds a graph planner for VLN but trains with imitation only §2.
• Superseded by: not stated in this wiki.