Many tasks that we do on a regular basis, such as navigating a city, cooking a
meal, or loading a dishwasher, require planning over extended periods of time.
Accomplishing these tasks may seem simple to us; however, reasoning over long
time horizons remains a major challenge for today’s Reinforcement Learning (RL)
algorithms. While unable to plan over long horizons, deep RL algorithms excel
at learning policies for short horizon tasks, such as robotic grasping,
directly from pixels. At the same time, classical planning methods such as
Dijkstra’s algorithm and A$^*$ search can plan over long time horizons, but
they require hand-specified or task-specific abstract representations of the
environment as input.
To achieve the best of both worlds, state-of-the-art visual navigation methods
have applied classical search methods to learned graphs. In particular, SPTM [2]
and SoRB [3] use a replay buffer of observations as nodes in a graph and learn
a parametric distance function to draw edges in the graph. These methods have
been successfully applied to long-horizon simulated navigation tasks that were
too challenging for previous methods to solve.
Nevertheless, these methods are still limited because they are highly sensitive
to errors in the learned graph. Even a single faulty edge acts like a wormhole
in the graph topology that planning algorithms try to exploit, which makes
existing methods that combine graph search and RL extremely brittle. For
example, if an artificial agent navigating a maze thinks that two observations
on either side of a wall are nearby, its plans will involve transitions that
collide into the wall. Adopting a simple model that assumes a constant
probability $p$ of each edge being faulty, we see that the expected number of
faulty edges is $p|E| = O(|V|^2)$. In other words, errors in the graph scale
quadratically with the number of nodes in the graph.
We could do a lot better if we could minimize the errors in the graph. But how?
Graphs over observations in both simulated and real-world environments can be
prohibitively large, making it challenging to even identify which edges are
faulty. To minimize errors in the graph, then, we desire sparsity; we want to
keep a minimal set of nodes that is sufficient for planning. If we have a way
to aggregate similar observations into a single node in the graph, we can
reduce the number of errors and improve the accuracy of our plans. The key
challenge is to aggregate observations in a way that respects temporal
constraints. If observations are similar in appearance but actually far away,
then they should be aggregated into different nodes.
So how can we sparsify our graph while guaranteeing that the graph remains
useful for planning? Our key insight is a novel merging criterion called
two-way consistency. Two-way consistency can be viewed as a generalization of
value irrelevance to the goal-conditioned setting. Intuitively, two-way consistency
merges nodes (i) that can be interchanged as starting states and (ii) that can be
interchanged as goal states.
For an example of two-way consistency, consider the above figure. Suppose
during our node merging procedure we ask: can we merge the nodes with pink and
orange bottles according to two-way consistency? First, we note that moving
from the blue bottle to the pink bottle requires roughly the same work as
moving from the blue bottle to the orange bottle. So the nodes with pink and
orange bottles satisfy criterion (ii) because they can be interchanged as goal
states. However, while it is possible to start from the pink bottle and move to
the blue bottle, if we instead start at the orange bottle, the orange bottle
will fall to the floor and crash! So the nodes with pink and orange bottles
fail criterion (i) because they cannot be interchanged as starting states.
In practice, we can’t expect to encounter two nodes that can be perfectly
interchanged. Instead, we merge nodes that can be interchanged up to a
threshold parameter $tau$. By increasing $tau$, we can make the resulting
graph as sparse as we’d like. Crucially, *we prove in the paper that merging
according to two-way consistency preserves the graph’s quality up to an error
term that scales only linearly with the merging threshold $tau$.
Our motivation for sparsity, discussed above, is robustness: we expect smaller
graphs to have fewer errors. Furthermore, our main theorem tells us that we can
merge nodes according to two-way consistency while preserving the graph’s
quality. Experimentally, though, are the resulting sparse graphs more robust?
To test the robustness of Sparse Graphical Memory to errors in learned distance
metrics, we thinned the walls in the PointEnv mazes of [3]. While PointEnv is a
simple environment with $(x, y)$ coordinate observations, thinning the walls is
a major challenge for parametric distance functions; any error in the learned
distance function will cause faulty edges across the walls that destroy the
feasibility of plans. For this reason, simply thinning the maze walls is enough
to break the previous state-of-the-art [3] resulting in a 0% success rate.
How does Sparse Graphical Memory fare? With many fewer edges, it becomes
tractable to perform self-supervised cleanup: the agent can step through the
environment to detect and remove faulty edges from its graph. The below figure
illustrates the results of this process. While the dense graph shown in red has
many faulty edges, sparsity and self-supervised cleanup, shown in green,
overcome errors in the learned distance metric, leading to a 100% success rate.
We see a similar trend in experiments with visual input. In both ViZDoom [4]
and SafetyGym [5] – maze navigation tasks that require planning from raw
images – Sparse Graphical Memory consistently improves the success of baseline
methods including SoRB [3] and SPTM [2].
In addition to containing fewer errors, Sparse Graphical Memory also results in
more optimal plans. On a ViZDoom maze navigation task [4], we find that SGM
requires significantly less steps to reach the final goal across easy, medium,
and hard maze tasks, meaning that the agent follows a shorter path to the final
destination.
Overall, we found that state aggregation with two-way consistency resulted in
substantially more robust plans over the prior state-of-the-art. While
promising, many open questions and challenges remain for combining classical
planning with learning-based control. Some of the questions we’re thinking
about are – how can we extend these methods beyond navigation to manipulation
domains? As the world is not static, how should we build graphs over changing
environments? How can two-way consistency be utilized beyond the scope of
graphical-based planning methods? We are excited about these future directions
and hope our theoretical and experimental findings prove useful to other
researchers investigating control over extended time horizons.
References
- Emmons*, Jain*, Laskin* et al. Sparse Graphical Memory for Robust Planning. NeurIPS 2020.
- Savinov et al. Semi-parametric Topological Memory for Navigation. ICLR 2019.
- Eysenbach et al. Search on the Replay Buffer: Bridging Planning and Reinforcement Learning. NeurIPS 2020.
- Wydmuch et al. ViZDoom Competitions: Playing Doom from Pixels. IEEE Transactions on Games, 2018.
- Ray et al. Benchmarking Safe Exploration in Deep Reinforcement Learning. Preprint, 2019.