Evolving Graphical Planner: Contextual Global
Planning for Vision-and-Language Navigation

Zhiwei Deng

Karthik Narasimhan Olga Russakovsky
Neural Information Processing Systems (NeurIPS), 2020

Human communicates with robots

Human language- through language
Planning

Robots interact with environments- perceive visual information- perform planning, take actions

Environment observation

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task
Unseen environment

Vision-and-Language Navigation: Interpreting visually-grounded navigation
instructions in real environments, Peter Anderson et al., CVPR 2018

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Photorealistic images

Vision-and-Language Navigation: Interpreting visually-grounded navigation
instructions in real environments, Peter Anderson et al., CVPR 2018

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination
Photorealistic images
Human annotated instructions

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination
Photorealistic images
Human annotated instructions
Navigation in a room

Start

Target
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Challenge 1: Reason over observation and languages

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Challenge 1: Reason over observation and languages

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Challenge 2: Perform error correction and recovery

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Challenge 2: Perform error correction and recovery

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Deviate from correct path

Challenge 2: Perform error correction and recovery

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Incorrect action

Correct action

Deviate from correct path

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Vision-and-Language Navigation Task

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Current navigation architectures

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Agent

ActionDecision space

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Current navigation architectures

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Agent

ActionDecision space

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Current navigation architectures

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Agent

ActionDecision space

Existing navigation architectures for VLN:
constrained local decision space
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Current navigation architectures

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Alignment confusion

Observation + decision space

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Current navigation architectures

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Action

Agent

?

?

Decision space?

?

Need to make multi-step decisions, making error correction harder
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner

Evolving Graphical Structure

Proxy graphs for planning

Graph
Pool
Message
Passing

Graph
UnpoolCondensation

Graph-augmented supervisionStandard VLN navi-agent

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Agent

ActionDecision space

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: global decision space helps

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Topological map

Agent

ActionDecision space

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner

Unseen environment

Facing the end of the bed, take an immediate right and exit the
bedroom through the open doorway. Walk straight until you see a large
red painting. At the painting make a turn towards and go through thedoorway on the right of the painting. Enter the bedroom, you will reachyour destination

Encoder

Visit to stop
Topological map

Agent

ActionDecision space

Visit to expand
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Graphical memory – topological connection + raw feat.
Instructions
Facing the end of the bed, take an
immediate right and exit the bedroom
through the open doorway. Walkstraight until you see a large red
painting. At the painting make a turntowards and go through the doorway
on the right of the painting…

CA

Gt = (Vt , Et )vti = (visualti ,angleti )Graphical memory
Observations(visual + angle)

Topological map

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Graphical memory
Instructions
Facing the end of the bed, take an
immediate right and exit the bedroom
through the open doorway. Walkstraight until you see a large red
painting. At the painting make a turntowards and go through the doorway
on the right of the painting…

CAo Grounding: global alignment

Graphical memory
Observations(visual + angle)

Topological map

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Graphical memory
Instructions
Facing the end of the bed, take an
immediate right and exit the bedroom
through the open doorway. Walkstraight until you see a large red
painting. At the painting make a turntowards and go through the doorway
on the right of the painting…

CAo Follow the memorized patho Decision made in single stepo Easier error correction

Graphical memory
Observations(visual + angle)

Topological map

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Instructions
Facing the end of the bed, take an
immediate right and exit the bedroom
through the open doorway. Walkstraight until you see a large red
painting. At the painting make a turntowards and go through the doorway
on the right of the painting…

C

A

Ever expanding graph…
Observations(visual + angle)

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Instructions
Facing the end of the bed, take an
immediate right and exit the bedroom
through the open doorway. Walkstraight until you see a large red
painting. At the painting make a turntowards and go through the doorway
on the right of the painting…

C

A

Operate on the full graph:high planning costEver expanding graph…
Observations(visual + angle)

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )
G
t
t
Pool

V! t = At TVt

Ever expanding graph…

!
E t = At T Et At

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )
G
t
t
Pool

Pooling matrix At : soft “attention” or aggregation from the original graph

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )
G
t
t
Pool

Pooling matrix At : obtained from f (Gt ,language,agent − state)

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )
G
t
t
Pool

Neural message passing: GraphNeuralNetworks(Gt ,k = steps)

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Relational inductive biases, deep learning, and graph networks, arxiv’18

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )Gtt
Un-pool

Pooling matrix At : transpose as the un-pool matrix

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs
Gt = (Vt , Et )CA

! t = (V , E )Gtt
Un-pool

Propose next action

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: Proxy graphs – multi-channelk!
{G t (Vt k , Etk )},k = 1,..., K

Gt = (Vt , Et )CAUn-pool

Propose next action

Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. NeurIPS’18
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Expert trajectories are provided

S

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

How to use expert trajectory supervision?

S

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 1: “teacher forcing”

S

a1

a2

a3
Expert trajectory dataset: D = {(a1 ,a2 ,...,aT ) i }i

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 1: “teacher forcing”

S

a1

a2

a3
T

P(a1 ,a2 ,...,aT | s) = P(a1 | s)∏ P(at | a1 ,a2 ,...,at−1 ,s)t=2

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 1: “teacher forcing” – drifting issue in unseen data

S

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing”

S

a1*

a2*
a3*

a4*
Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing” – generate new supervision (shortest path)

S

*
1

a

a2*

D * = {(a1* ,a2* ,...,aT* )i }i*
3

D ∪ D*aa4*
Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing” – shortest path supervision
mismatchS

Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing” – graph augmented supervision

S

Decision space
Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing” – graph augmented supervision

a5*
S

*
1

a

a2*

D * = {(a1* ,a2* ,...,aT* )i }i*
3

D ∪ D*aa4*
Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: how to supervise the imitation learner?
Facing the end of the bed, take an immediate right and exit the bedroom through the open doorway. Walk straight
until you see a large red painting. At the painting make a turn towards and go through the doorway on the right ofthe painting…

Option 2: “student forcing” – graph augmented supervisionSo Ground truth always exists
o No mismatch problem
o No need to access the ENV
Self-Monitoring Navigation Agent for Vision-and-Language Navigation, Ma et al., ICLR’19
Speaker-Follower Models for Vision-and-Language Navigation, Fried&Hu et al., NeurIPS’18
The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation, Ma et al., ICCV’19

Our work: Evolving Graphical Planner
A differentiable graphical planner: full training process

Instructions

Observations(visual + angle)

Graphical
memoryMulti-channel
planner

ActionLossOur work: Evolving Graphical Planner
A differentiable graphical planner: test inference matches the training

Instructions

Observations(visual + angle)

Graphical
memoryMulti-channel
planner

ActionExperiments• Room-to-Room (R2R): all trajectories are generated through shortest-path, emphasize on goal reaching

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Contribution of each component• Room-to-Room (R2R): all trajectories are generated through shortest-path, emphasize on goal reaching

Does global decision space
help (success rate %)
53
52
51
50
49
48
47
46
45
44

Supervision strategy for
imitation learner(success rate %)Proxy graph choices(success rate %)
60
50

54

40

52

30

50

20

48
46

10

44

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

Message
Message Multi-channel
passing steps passing steps planner
=0
=3

42
Shortest path

Graph-augmented(ours)The global decision space, the planner and the new supervision strategy help on navigation success rate
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Compare to existing backbones• Room-to-Room (R2R): all trajectories are generated through shortest-path, emphasize on goal reaching

We outperform previous backbone architecture
Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Room-for-room with pure imitation learning• Room-for-Room (R4R): measured by Coverage weighted by Length Score (CLS), normalized dynamic time
warping (DTW), Success rate weighted normalized Dynamic Time Warping (SDTW), emphasize on pathfollowing

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Room-for-room with pure imitation learning• Room-for-Room (R4R): measured by Coverage weighted by Length Score (CLS), normalized dynamic time
warping (DTW), Success rate weighted normalized Dynamic Time Warping (SDTW)

We achieve the state-of-the-art using pure imitation learning

Evolving Graphical Planner: Contextual Global Planning for Vision-and-Language Navigation

Contributionso A differentiable graphical planner that extends the decision space globallyo A new supervision strategy for training imitation agent in navigationo Introduce proxy graphs for improving the efficiency of planning

Email: zhiweid@cs.princeton.edu