Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation
Zhiwei Deng, Karthik Narasimhan, and Olga Russakovsky
Princeton University

Overview

Evolving Graphical Planner

Experiments

Problem setting

Graphical memory

Room-to-room (R2R)

Goal: building an autonomous agent that navigates through an unseen environment
by following instructions and dynamically planning the path to reach the goal location.
Turn around and exit the bedroom. Walk along
the corridor and keep straight. Walk pass thesofa and the painting on the bedroom wall.
Enter the bathroom and stop in front of the tub.

The EGP keeps a dynamic graphical memory that stores the raw observations ofeach location. The connectivity of nodes is determined by the topological connectionsof the environments.

G1sS

Discrete topological connections•

Primitive actions: turnleft/right/up/down, forward•

Teleport actions: choose
a location to navigate toDecision making with instructions and observations

Our navigation agent
Standard navigation – local decision spacesc
Turn around and exit the bedroom. Walk along thecorridor and keep straight. Walk pass the sofa and thepainting on the bedroom wall. Enter the bathroom andstop in front of the tub.

Local decision making

Multi-step error correction

Evolving Graphical Planner – global decision spaces

Limited observation features
for groundingssCompare with previous navigation backbone architecturesc

Step 3

Step 1

Step 2

Gt = (Vt , Et )vti = (visualti ,angleti )etij = (vti ,vtj )Compared to FAST, EGP:
(1) doesn’t need hand-crafted search procedure, extra info (speaker, self-monitor, etc.)(2) Is differentiable and have much shorter path length

The ever-expanding sizes of the graphical memory will lead to two problems:(1) The memory cost grows rapidly (memory issue);(2) The topological long-range nodes make communication harder (performance issue)
Our solution:!tGc

Unpooling!t
G

Turn around and exit the bedroom. Walk along thecorridor and keep straight. Walk pass the sofa and thepainting on the bedroom wall. Enter the bathroom andstop in front of the tub.

Pooling matrix
Global decision making

Single-step error correction

Full observation features forgroundingContributions
v We propose a differentiable Evolving Graphical Planner that expands thedecision-making process to a global spacev The planner can achieve efficient planning over the ever-expanding
graph memory along with the navigation

At = GNN (Gt )!
E t = At T Et AtGt

Proxy graphs! t = (V , E )GttGraph-augmented imitation supervision

Supervision strategy for
imitation learner (successrate %)

50

55

48

50

46

45

44

40
Top-K = 3 Top-K = 5 Top-K = Top-K =10All

Shortest path

Graph-augmented(ours)

Room-for-room (R4R)R4R is a Matterpord3D-based 3D photorealistic dataset that
extends R2R by concatenating two paths to create long andtwisted paths for testing path following.
Metrics: success rate(SR); navigation error(NE); path length(PL);dynamic time warping(DTW); coverage weighted by length score(CLS)

Current widely used supervision strategy for student sampling in training navigation imitation
agent requires re-computing a new shortest path to the goal location. This leads to:(1) A potential mismatch issue between the new path and the given instruction;(2) The need to access more information in the environment
Student sampling with new shortest paths… Walk pass the sofa
and the painting on thebedroom wall. Enterthe bathroom and stopin front of the tub.

cv A new graph-based imitation supervision is proposed to alleviate themismatch issue in student sampling trainingv We show superior performance compared to previous backbone
navigation architectures

V! t = At TVt

Does global decision space help
(success rate %)52

Messagepassing

Pooling

The contribution of each component

54

Multi-channel proxy graphs

Original full graphGtsc

G3

Proxy graphs

sc

G2

R2R is a Matterpord3D-based 3D photorealistic dataset withhuman generated instructions as guidance for navigation.
Paths are generated by shortest-path algorithm
Metrics: success rate(SR); navigation error(NE); path length(PL);success rate per path length unit(SPL); oracle success rate(OSR)

Re-computed shortest-path
Graph-augmented supervision strategy (our solution)sGtc

Blue circled nodes areused in the loss function
as the supervision

Ground-truth nodes are guaranteed to existin the graphs

We are the first model that uses pure imitation learning to train and achieves the stateof-the-art performance.

References[1] Fried, Daniel, et al. "Speaker-follower models for vision-and-language navigation." NeurIPS. 2018.
[2] Wang, Xin, et al. "Reinforced cross-modal matching and self-supervised imitation learning for vision-language navigation." CVPR. 2019.
[3] Ma, Chih-Yao, et al. "Self-monitoring navigation agent via auxiliary progress estimation." ICLR 2019[4] Ma, Chih-Yao, et al. "The regretful agent: Heuristic-aided navigation through progress estimation." CVPR 2019.
[5] Ke, Liyiming, et al. "Tactical rewind: Self-correction via backtracking in vision-and-language navigation." ICCV 2019.
[6] Jain, Vihan, et al. "Stay on the path: Instruction fidelity in vision-and-language navigation." arXiv preprint arXiv:1905.12255 (2019).
[7] Landi, Federico, et al. "Perceive, Transform, and Act: Multi-Modal Attention Networks for Vision-and-Language Navigation." arXiv preprint
arXiv:1911.12377 (2019).