# PALMER: Perception-Action Loop with Memory
for Long-Horizon Planning

Onur Beker
&Mohammad Mohammadi
&Amir Zamir
Swiss Federal Institute of Technology (EPFL)

###### Abstract

To achieve autonomy in a priori unknown real-world scenarios, agents should be
able to: i) act from high-dimensional sensory observations (e.g., images), ii)
learn from past experience to adapt and improve, and iii) be capable of long
horizon planning. Classical planning algorithms (e.g. PRM, RRT) are proficient
at handling long-horizon planning. Deep learning based methods in turn can
provide the necessary representations to address the others, by modeling
statistical contingencies between observations. In this direction, we
introduce a general-purpose planning algorithm called PALMER that combines
classical sampling-based planning algorithms with learning-based perceptual
representations. For training these perceptual representations, we combine
Q-learning with contrastive representation learning to create a latent space
where the distance between the embeddings of two states captures how easily an
optimal policy can traverse between them. For planning with these perceptual
representations, we re-purpose classical sampling-based planning algorithms to
retrieve previously observed trajectory segments from a replay buffer and
restitch them into approximately optimal paths that connect any given pair of
start and goal states. This creates a tight feedback loop between
representation learning, memory, reinforcement learning, and sampling-based
planning. The end result is an experiential framework for long-horizon
planning that is significantly more robust and sample efficient compared to
existing methods.

##  1 Introduction

Figure 1: Top: Given a start-goal image pair, PALMER plans a path between them
by concatenating the endpoints of past trajectory segments retrieved from a
provided replay buffer. This is enabled by a state embedding function
$f_{\phi}$ that can identify close-by states, and results in robust long-
horizon planning. Bottom: To achieve this : i) it uses offline Q-learning to
obtain local reachability estimates between states, ii) uses these Q-values
for representation learning to train $f_{\phi}$, iii) uses $f_{\phi}$ to plan
over the replay buffer, iv) executes these plans, v) evaluates the resulting
trajectories and inserts them back into the replay buffer to improve its
contents.

Animals and humans operate on high-dimensional stimuli (e.g., vision) to
achieve diverse and ever-changing goals necessary for their survival [1, 2, 3,
4, 5]. Learning through trial-and-error plays a fundamental role in this [6,
7, 8, 9, 10, 5]. Even in simplest environments, a brute-force approach to
trial-and-error by trying every possible action for achieving every possible
goal is intractable. The complexity of this search motivates memory-based
mechanisms for compositional thinking. Examples of such mechanisms include :
i) remembering relevant segments of past experience, ii) recomposing them in
new counterfactual ways to form plans, and iii) executing such plans as part
of a targeted search strategy. Such mechanisms for recycling past successful
behavior can significantly accelerate trial-and-error compared to uniformly
sampling all possible actions. This is because the same behavior (i.e.,
sequence of actions) can remain valid for different goals and in different
contexts, due to the inherent compositional structure of real-world goals as
well as the commonality of the physical laws that govern real-world
environments.

What principles can allow for memory mechanisms to remember and recompose bits
of experience? The concept of dynamic programming (DP) is directly related to
this discussion, as it greatly reduces the computational cost of trial-and-
error by employing the principle of optimality [11]. This principle can be
colloquially stated as treating new and complex problems as a recomposition of
old and simpler sub-problems that were already solved before. Recent work [12,
13, 14] employs this perspective to build hierarchical reinforcement learning
(RL) algorithms for goal-reaching tasks. Such methods set edges between states
using a distance regression model to build a planning graph, perform shortest
path computations over it using DP-based graph search, and follow the
resulting shortest paths with a learning-based local policy. Our paper builds
upon this line of work.

Contribution: We describe a long-horizon planning method that directly
operates on high dimensional sensory input observable by an agent on its own
(e.g., images from an onboard camera). Our method combines classical sampling-
based planning algorithms with learning-based perceptual representations, to
retrieve and recompose previously observed sequences of state transitions in a
replay buffer. This is enabled by a two-step process. First, we learn a latent
space where the distance between two states captures how many timesteps it
takes for an optimal policy to go from one to the other. To achieve this, we
use goal-conditioned Q-values learned through offline hindsight relabelling
[15] for contrastive representation learning. Second, we threshold this
learned latent distance metric to define a neighborhood criterion between
states. We then define sampling-based planning algorithms that search over the
replay buffer [12] to retrieve and stitch together trajectory segments (i.e.,
past sequences of observed transitions) whose endpoints are neighboring
states. This trajectory stitching approach allows for creating planning graphs
to connect any pair of start and goal states that were observed before (as
depicted in Fig.1). Our approach operates on offline unlabeled data, and can
therefore be combined with any exploration method to populate the replay
buffer. Our experiments implement an image-based navigation policy in
simulation, using an offline replay buffer populated with uniform random-walk
exploration data.

##  2 Perception-Action Loop with Memory Retrieval111Most sub-sections have a
corresponding section in the supplementary for further elaboration.

Nomenclature: An environment is represented as a tuple
$\langle\mathcal{S},\mathcal{A},p_{env}\rangle$, where $\mathcal{S}$ and
$\mathcal{A}$ are the state and action spaces, and $p_{env}(s^{\prime}|s,a)$
is the Markovian transition dynamics. A trajectory $\tau\in\mathcal{T}$ is any
sequence of states and actions. $\tau_{0}$ , $\tau_{-1}$ , $\tau_{i}$ denote
the first, last, and $i$’th states in $\tau$ respectively. The length of a
trajectory in terms of timesteps is denoted as $len(\tau)$, and concatenation
of two trajectories is denoted as $\tau_{cat}=\tau_{1}\circ\tau_{2}$. We
assume an additive reward function
$\mathcal{R}:\mathcal{T}\rightarrow\mathbb{R}$ where
$\mathcal{R}(\tau)=\sum_{(s,a)\in\tau}r(s,a)$. We call a finite set of
trajectories $\mathcal{M}=\\{\tau_{i}\\}$ a replay buffer.

###  2.1 Perceptual Representations that Capture Local Reachability

A key component of our framework is a perceptual encoder
$f_{\phi}(s):\mathcal{S}\rightarrow\mathbb{R}^{d}$ that maps states into a
representation space where L2 distance
$d_{\phi}(s_{t},s_{g}):=\|f_{\phi}(s_{t})-f_{\phi}(s_{g})\|$ captures local
reachability (i.e., how many timesteps it takes for the optimal policy to go
from one state to another). To discuss this more rigorously, we follow the
work of [16, 12] and define a goal-conditioned reward function
$r(s_{t},a,s_{t+1},s_{g})=-\mathbbm{1}_{s_{t+1}\neq s_{g}}$ that returns $-1$
for all steps before reaching a goal. This means goal-conditioned Q-values
[16, 17] for the optimal policy correspond to negative shortest-path distances
(i.e., $max_{a}Q(s_{t},a,s_{g})=V(s_{i},s_{j})=-len(\tau_{sp})$). We can then
define a symmetric distance metric between states as
$d_{Q}(s_{c},s_{g}):=max(\ -V(s_{c},s_{g}),-V(s_{g},s_{c})\ )$. This in turn
corresponds to the two-way consistency criterion proposed in [13]. What we
want from $f_{\phi}(s)$ is for $d_{\phi}(s_{c},s_{g})$ and
$d_{Q}(s_{c},s_{g})$ to roughly correlate.

###  2.2 Representation Learning via Reinforcement Learning

Figure 2: An overview of the functions, inputs, and losses used in our method
(see Sec.2.2 for details). We aim to train a perceptual encoder $f_{\phi}$
with two properties: i) representations of two states should be close if they
were observed to be easily reachable from each other within a low number of
timesteps, ii) the representation of a state should capture a minimal
sufficient statistic to inform an agent about the actions needed to reach
nearby states.

Any perceptual encoder $f_{\phi}$ whose latent representations satisfy the
local reachability property defined in Sec.2.1 can be used to implement the
nearest neighbor retrieval and trajectory stitching mechanisms for the
upcoming sections 2.3 and 2.4. This section discusses one possible way to
obtain such a perceptual encoder, by using goal-conditioned Q-values for
contrastive representation learning.

We propose a model (depicted in Fig.2) that includes the following standard
components from the literature: i) $z=f_{\phi}(s)$, projecting a state into a
latent representation; ii) $p_{fwd}(z^{\prime}_{t+1}\ |\ z_{t},a_{t})$,
modelling the transition distribution induced by $p_{env}(s^{\prime}|s,a)$
over the latent space $z=f_{\phi}(s)$, as discussed in [18, 19]; iii)
$\pi_{inv}(a^{\prime}_{t}\ |\ z_{t},z_{g})$, defining a distribution of
actions to reach a goal state, as discussed in [18, 19, 14]; iv)
$p_{t}(T^{\prime}\ |\ z_{t},z_{g})$, modelling the distribution of timesteps
necessary to reach a goal state, as discussed in [20]; v)
$Q(s_{t},a_{t},s_{g})$, a Q-value function that provides local reachability
estimates between pairs of states, as discussed in [12, 16].

Following [12, 16], we train $Q(s_{t},a_{t},s_{g})$ over an offline replay
buffer $\mathcal{M}$, using hindsight relabelling [15, 16] with a reward
function $r(s_{t},a,s_{t+1},s_{g})=-\mathbbm{1}_{s_{t+1}\neq s_{g}}$. After
training $Q(s_{t},a_{t},s_{g})$ in isolation, we freeze its parameters and use
it to define a contrastive loss function [21] $L_{Q}$ as explained below. We
then train the remaining components using the same replay buffer
$\mathcal{M}$. We randomly sample a transition $(s_{t},a_{t},s_{t+1})$ and a
time difference $T$, and set the goal state as $s_{g}:=s_{t+T}$, as in
hindsight relabelling. We then minimize the following losses:

  * •

$L_{Q}(s_{t},s_{g})=l_{hinge}(d_{\phi}(s_{t},s_{g})-d_{p})\
\mathbbm{1}_{d_{Q}(s_{t},s_{g})\leq
c_{Q}}+l_{hinge}(d_{p}-d_{\phi}(s_{t},s_{g}))\
\mathbbm{1}_{d_{Q}(s_{t},s_{g})\geq c_{Q}}$, where $l_{hinge}$ is the hinge
loss [22]. This contrastive loss dictates that perceptual representations
should be close together (i.e., $d_{\phi}(s_{t},s_{g})\leq d_{p}$ holds) if
and only if two states are close to each other in terms of reachability (i.e.,
$d_{Q}(s_{t},s_{g})\leq c_{Q}$ holds). $d_{p}$ and $c_{Q}$ are
hyperparameters.

  * •

$L_{T}(T^{\prime},T)$, $L_{inv}(a_{t}^{\prime},a_{t})$, and
$L_{fwd}(z_{t+1}^{\prime},z_{t+1})$ are MSE and cross-entropy losses [19, 20].
$L_{T}$ and $L_{inv}$ dictate that perceptual representations should capture
enough information to know when and how an agent can reach from one state to
another, while $L_{fwd}$ dictates that they should capture only a minimal-
sufficient statistic for doing so ([19] presents a more elaborate discussion).

###  2.3 Perceptual Experience Retrieval (PER)

Given a perceptual encoder $f_{\phi}$ that captures local reachability, we go
over all states ${s_{i}}\in\mathcal{M}$ in the replay buffer and compute their
projections ${z_{i}=f_{\phi}(s_{i})}$, which are stored alongside the states
themselves. We then employ $z_{i}$ to implement two retrieval mechanisms from
the replay buffer: i) retrieving neighboring states, and ii) retrieving
neighboring trajectories.

i) Retrieving Neighboring States: Given a query state $s_{c}$ and radius
$d_{p}$ (i.e., the same one used in the contrastive loss $L_{Q}$ in Sec.2.2),
retrieving neighboring states amounts to computing the set
$\mathcal{N}_{d_{p}}(s_{c})=\\{s_{n}\ |\ d_{\phi}(s_{c},s_{n})\leq d_{p}\\}$,
which can be achieved by a straightforward L2 distance computation and
thresholding. The number of neighbors $|\mathcal{N}_{d_{p}}(s_{c})|$ of a
query state $s_{c}$ is an approximate measure of how many times the agent has
visited around $s_{c}$, which also makes it a good visitation-count that is
applicable to both discrete and continuous state spaces.

ii) Retrieving Neighboring Trajectories: Given a starting state $s_{c}$ and a
goal state $s_{g}$, we can search the replay buffer for the highest reward
trajectory segment $\tau$ that starts from a state $\tau_{0}$ in
$\mathcal{N}_{d_{p}}(s_{c})$ and ends in a state $\tau_{-1}$ in
$\mathcal{N}_{d_{p}}(s_{g})$. This corresponds to the following optimization
problem:

$\tau_{\mathcal{M}(s_{c},s_{g})}:=\operatorname*{arg\,max}_{\tau\in\mathcal{M}}{\mathcal{R}(\tau)}\quad\textrm{s.t.}\quad\tau_{0}\in\mathcal{N}_{d_{p}}(s_{c})\
,\ \tau_{-1}\in\mathcal{N}_{d_{p}}(s_{g})$ (1)

To find $\tau_{\mathcal{M}(s_{c},s_{g})}$, we first select all state pairs
$(s_{i},s_{j})\in\mathcal{N}_{d_{p}}(s_{c})\times\mathcal{N}_{d_{p}}(s_{g})$.
We then take all sequences of transitions
$\tau_{ij}=\\{s_{i},a_{i},s_{i+1},...,s_{j-1},a_{j-i},s_{j}\\}$ that start
from $s_{i}$, end at $s_{j}$, and are below a length threshold in terms of
timesteps. We sort them based on $\mathcal{R}(\tau_{ij})$, and return the
trajectory with the highest reward. We call this trajectory retrieval process
‘Perceptual Experience Retrieval’ (PER). We use PER only to retrieve short
trajectory segments between close-by states $(s_{c},s_{g})$ (i.e., hence the
length threshold on $\tau_{ij}$). These are then stitched together into long
global trajectories using the planning algorithms defined in the next section.

###  2.4 Long-Horizon Planning Through Stitching Trajectory Segments

This section discusses how PER can be employed for long-horizon planning.
Classical sampling-based planning algorithms such as RRT [23] or PRM [24]
connect points sampled from obstacle-free space with line segments in order to
build a planning graph. We instead reimagine them as memory search mechanisms
by altering their subroutines so that whenever an edge is created, a
trajectory is retrieved from the replay buffer through PER (eq.1) and stored
in that edge. Our new definitions for these subroutines directly mirror the
original ones given in [25]:
1) Sampling: Sampling originally returns a point from obstacle free space. We
instead return a state $s_{c}$ from the replay buffer $\mathcal{M}$ using any
distribution (e.g., uniform, or based on visitation-counts).
2) Lines and Their Cost: The equivalent of drawing a line segment in our
framework is retrieving a trajectory $\tau_{\mathcal{M}(s_{c},s_{g})}$, and
its length and cost are $len(\tau_{\mathcal{M}(s_{c},s_{g})})$ and
$-\mathcal{R}(\tau_{\mathcal{M}(s_{c},s_{g})})$ respectively. 3) Nearest State
and Neighborhood Queries: Given a query point $s_{i}$, these subroutines
return the closest point or a neighborhood of points within a distance, among
a set of vertices $V=\\{s_{j}\\}$. We preserve these definitions, and only
replace the metric from euclidean distance to
$len(\tau_{\mathcal{M}(s_{c},s_{g})})$.

$\displaystyle Nearest(V,s_{g})$
$\displaystyle:=\operatorname*{arg\,min}_{s_{c}\in
V}{\,len(\tau_{\mathcal{M}(s_{c},s_{g})})}$ $\displaystyle Near(V,s_{g},r)$
$\displaystyle:=\\{s_{c}\in V\ |\ len(\tau_{\mathcal{M}(s_{c},s_{g})})\leq
r\\}$

4) Collision Tests: Collision tests originally prevent the sampling and line
drawing subroutines from intersecting obstacles. Since we are planning in
retrospect, any such undesirable event can be handled during PER by adjusting
the reward function (i.e., if $\tau$ has such an event, this reflects on
$\mathcal{R}(\tau)$).

Algorithm 1 R-PRM (Roadmap Construction)

1:Input: $f_{\phi},\mathcal{M}$

2:$V\leftarrow\\{SampleFree_{i}\\}_{i=1,...,num\\_vertices};\>E\leftarrow\emptyset$
$\triangleright$ Initialize vertices and edges

3:for each $s_{i}\in V$ do

4: $U\leftarrow Near(V,s_{i},r)\setminus\\{s_{i}\\}$

5: for each $s_{j}\in U$ do $\triangleright$ Place PER trajectories in edges

6: $E\leftarrow
E\cup\\{(s_{i},s_{j}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{i},s_{j})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{i},s_{j})})\\}$ return $G=(V,E)$

Algorithm 2 R-PRM (Trajectory Restitching Given the Constructed Roadmap)

1:Input: $s_{c},s_{g},G=(V,E),\mathcal{R}(\tau),f_{\phi},\mathcal{M}$

2:for each $s_{i}\in V$ do $\triangleright$ Insert $s_{c}$ and $s_{g}$ into
the PRM graph

3: if $len(\tau_{\mathcal{M}(s_{c},s_{i})})\leq r$ then $\triangleright$ Place
PER trajectories in edges

4: $E\leftarrow
E\cup\\{(s_{c},s_{i}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{c},s_{i})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{c},s_{i})})\\}$

5: if $len(\tau_{\mathcal{M}(s_{i},s_{g})})\leq r$ then

6: $E\leftarrow
E\cup\\{(s_{i},s_{g}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{i},s_{g})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{i},s_{g})})\\}$

7:$\tau_{stitched}\leftarrow\emptyset$

8:$\\{s_{j}\\}\leftarrow ShortestPath(s_{c},s_{g},G,\mathcal{R}(\tau))$
$\triangleright$ Trajectory stitching by dynamic programming

9:for $0<i<|\\{s_{j}\\}|$ do $\triangleright$ Concatenate PER trajectories
along the shortest path

10:
$\tau_{stitched}\leftarrow\tau_{stitched}\circ\tau_{\mathcal{M}(s_{i-1},s_{i})}$
return $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}=\tau_{stitched}$

Using these subroutines directly in-place of their originals, we reimplement
experiential equivalents of PRM, RRT, and RRT*, which we call R-PRM, R-RRT,
R-RRT*. We denote the resulting planned trajectory as
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$. Algorithms 1, 2 describe R-PRM
as an example, and the supplementary contains descriptions for R-RRT, R-RRT*.

We note two things about our proposed planning algorithms. First, they can
optimize any general reward function $\mathcal{R}$. As the number of sampled
vertices increases, $\mathcal{R}(\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})})$
gets optimized through dynamic programming (i.e., by minimizing the Bellman
error between vertices of the roadmap $G$), therefore employing the same
mechanism as classical sampling-based planning algorithms [25]. Second, they
operate on an offline dataset of unlabeled transitions which solely consists
of high-dimensional on-board sensory data (e.g. images), without assuming any
auxiliary instrumentation in the environment or oracle information that cannot
be sensed by the agent on its own. They therefore aim to relax the assumptions
classical sampling-based planning methods make about what constitutes a model
(e.g., replacing a geometric environment model with sensory experience) and
what constitutes a state (e.g., enabling search and planning directly over
images).

###  2.5 Refining Memory Contents via Forming and Executing Plans

We iteratively form and execute $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$,
and whenever execution is successful, we insert the resulting new trajectories
back into $\mathcal{M}$. We note that these new trajectories are not exactly
the same as $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$, because
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ contains approximate mismatches
between the endpoints of its stitched trajectory segments due to nearest
neighbor retrieval. Forming and executing plans this way creates the following
perception-action loop: i) $\mathcal{M}$ with refined contents is used to
train a more accurate $Q(s_{t},a,s_{g})$, ii) a more accurate
$Q(s_{t},a,s_{g})$ creates a more accurate distance metric $d_{\phi}$, iii) a
better $d_{\phi}$ generates better
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$, iv) better
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ result in higher frequencies of
successful execution to further refine $\mathcal{M}$ (see the supplementary
for an algorithmic description).

##  3 Related work

Self-supervised goal reaching: Our approach is closely related to goal-
reaching methods that combine learning-based distance-regression with graph
search, particularly Semi-parametric Topological Memory (SPTM) [14] and Search
on the Replay Buffer (SoRB) [12], which we compare to in our experiments. The
key difference of our approach is that when setting the edges of the planning
graph, it retrieves transitions that actually happened rather than relying on
learned distance regression. This brings two main benefits. First is
robustness. Local reachability estimates are susceptible to overestimation
when evaluated between pairs of states that are far apart or unreachable. This
is because such states rarely occur together and are therefore out of
distribution for the distance regression model. This creates ‘hallucinated’
shortcuts in the planning graph that corrupt shortest path queries [12, 13].
To address this, [14] employs temporally consistent localization and adaptive
waypoint selection, while [12] employs distributional Q-learning and an
ensemble of Q-functions. In our approach, eq.1 naturally addresses this
problem, since it requires an actual short trajectory in the dataset
approximately connecting two states before marking them as close. The second
benefit of our approach is that _it can optimize general reward functions_.
This is because it decouples the reachability metric $len(\tau)$ (used in
nearest neighbor queries and as a threshold to create edges) from the
downstream task reward $\mathcal{R}(\tau)$ (used to set edge distances),
unlike previous work.
Image-Based Navigation: [26, 27, 28] present learning-based navigation systems
that incrementally build roadmaps through online operation. Our approach has
two main differences: i) it builds a roadmap entirely using raw offline data,
therefore allowing applications like multi-robot learning without additional
loop-closure mechanisms to fuse graphs from multiple agents, ii) our approach
can optimize general reward functions, therefore it is not limited to
navigation.
Robot Motion Planning: A common approach to motion planning is to first run a
sampling-based planning algorithm [29, 25], and then refine the result through
trajectory optimization [30, 31, 32] to satisfy constraints [33, 34, 35]. An
important bottleneck is that sampling-based planning algorithms require a
precomputed map of the environment, and our approach extends such algorithms
in a way that relaxes this requirement by replacing a precomputed map with raw
exploration experience.
SLAM and Geometric Maps: SLAM based methods [36] can autonomously construct
high-fidelity geometric maps [37, 38], therefore alleviating the bottleneck of
precomputing environment maps. The downside of such approaches is that they
can abstract away useful physical and semantic affordances. For example, a
purely geometric map cannot plan a path through a traversable field of tall-
grass, while our approach can learn such affordances as long as they are
represented in past experiences.

##  4 Experiments333All experiments have a corresponding section in the
supplementary providing further implementation details.

Figure 3:  A comparison between perceptual distances $d_{\phi}$ and other
suitable metrics from Sec.2.2. While all of these metrics are reasonably
monotonic with physical reachability (i.e., goal distance), only perceptual
distances $d_{\phi}$ do not saturate when evaluated locally (i.e., for close
by goals). In addition, the ratio between the variance of $d_{\phi}$ and the
slope of its mean is much smaller compared to other sensible metrics (i.e.,
$d_{\phi}$ has a high signal-to-noise ratio). This means that perceptual
distances can implement a more accurate nearest-neighbor criterion for
perceptual experience retrieval and trajectory stitching, compared to the
other metrics.

Setup: Our experiments are performed in ViZDoom [39], Habitat [40], and the
Maze2D benchmark [41]. The VizDoom environment consists of a clover shaped
maze. States solely consist of four images $I_{North/East/South/West}$ that
form a panorama (i.e., $4\times 3\times 160\times 120$ dimensions), and
actions move the agent North/South/East/West by a fixed distance $\Delta$. The
maze contains many long-thin column-like obstructions (shown as dots in
visualizations). Habitat experiments contain demonstrations on two large-scale
scans of real-world apartments: i) Roxboro, with a total area of $~{}62$ m2,
and ii) Annawan, which has a total-area of $~{}75m2$. States consist of a
single 150 FOV image (i.e., $3\times 256\times 256$ dimensions). There are 3
actions:
$\\{turn\\_left\\_30\\_deg,turn\\_right\\_30\\_deg,move\\_forward\\_\Delta\\}$.
Maze2D is a continuous control task, where states consist of the 2D position
and velocity of a point mass, and actions correspond to 2D accelerations. In
all environments, an offline training dataset is collected by a uniform random
walk exploring the environment. For VizDoom and Habitat, this offline training
dataset consists of only 300k and 150k timesteps respectively, while for
Maze2D there are 1e6 timesteps. Supplementary material contains further
details.

###  4.1 Experiments in Vizdoom

Validating Perceptual Representations: Fig.3 shows that
$d_{\phi}(s_{t},s_{g})$ obtained from our model captures a suitable notion of
local reachability. Fig.5 in turn shows that retrieving nearest neighbor
states $\mathcal{N}_{d_{p}}(s_{t})$ from $\mathcal{M}$ using $d_{\phi}$ (i.e.,
NN retrieval) returns physically close states.

Figure 4: Comparisons of our local policy $\pi_{\mathcal{M}}$ and global
policy $\pi_{\mathcal{M}^{*}}$ with SPTM and SoRB. $\pi_{\mathcal{M}}$
performs well because it avoids getting stuck (as such events are filtered by
eq.1), while $\pi_{\mathcal{M}^{*}}$ performs well because it builds robust
roadmaps without hallucinated shortcuts; therefore avoiding the main failure
modes of the baselines. Figure 5: At the core of PALMER is a process called
perceptual experience retrieval (PER). Given a query pair of current-goal
states, PER searches the replay buffer to retrieve the highest scoring
trajectory $\tau_{\mathcal{M}(s_{t},s_{g})}$ whose first and last states are
close to the query pair according to the perceptual distance $d_{\phi}$. Left,
Middle: Visualizations of $\tau_{\mathcal{M}(s_{t},s_{g})}$ retrieved using
PER and nearest neighbor states $\mathcal{N}_{d_{p}}(s_{t})$ retrieved using
$d_{\phi}$. Right: Setting edges of a roadmap using
$len(\tau_{\mathcal{M}(s_{t},s_{g})})$, compared with distance estimates used
in SORB and DDL [20]. We found that distance estimates from baselines are
prone to setting false edges that cross map boundaries.

Validating Perceptual Experience Retrieval (PER): Fig.5 shows visualizations
of trajectories retrieved with PER. We implement a retrieval policy
$\pi_{\mathcal{M}}$ that computes $\tau_{\mathcal{M}(s_{t},s_{g})}$ through
eq.1 at each timestep $t$ and executes $argmax_{a}\
Q(s_{t},a,\tau_{\mathcal{M}(s_{t},s_{g}),s,1})$, therefore forming a model
predictive control (MPC) loop. We evaluate $\pi_{\mathcal{M}}$ in an image-
based navigation task where start/goal images are sampled randomly to have an
euclidean distance $n\times\Delta$ in between, and a trial is considered
successful if the agent can get within $\Delta$ proximity of the goal position
within $4\times n$ time-steps. We use the local policies from SORB [12] and
SPTM [14] as baselines. Fig.4 shows the results. The main mode of failure for
both SPTM and SORB local policies is that they get stuck in column-like
structures. $\pi_{\mathcal{M}}$ avoids this, since eq.1 retrieves collision
free $\tau_{\mathcal{M}(s_{t},s_{g})}$.

Robust Distances: PER also helps avoid hallucinations in local distance
regression. Fig.5 illustrates this point by setting edges between sampled
states by thresholding $len(\tau_{\mathcal{M}(s_{t},s_{g})})$, where methods
of [12, 20] are used as baselines. It can be seen that edges set by
$len(\tau_{\mathcal{M}(s_{c},s_{g})})$ are more robust.

Figure 6: We repurpose conventional sampling-based planning algorithms as
memory search mechanisms, by altering their graph building subroutines so that
whenever an edge is created a trajectory $\tau_{\mathcal{M}(s_{t},s_{g})}$ is
retrieved through PER and stored in that edge. We visualize the resulting
planning graphs produced by our proposed algorithms R-PRM, R-RRT, R-RRT*.

Proposed Planning Algorithms: Fig.6 shows visualizations of planning graphs
and $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ produced by R-PRM, R-RRT, and
R-RRT*. It can be seen that R-PRM doesn’t contain any hallucinated edges,
while R-RRT and R-RRT* maintain the visual characteristics of their classical
counterparts (i.e., R-RRT has jagged branches with uniform coverage, while
R-RRT* has straight branches shooting out from the root). We implement an MPC
policy $\pi_{\mathcal{M}^{\text{*}}}$ that replans at each timestep $t$ using
Algorithm 2 to return $\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g})}$, and
executes $argmax_{a}\
Q(s_{t},a,\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,1})$. We again use SORB
[12] and SPTM [14] as baselines.555For a comparison without confounders, we
train SoRB with DDQN [42] rather than distributional Q-learning [43], and we
do not employ temporally consistent localization for SPTM, as such fixes are
equally applicable to our method and orthogonal to the discussion. The
supplementary provides further elaboration. Fig.4 shows the results. In
addition to the local policy getting stuck, a new mode of failure for both
baselines is that false distance estimates throw-off graph search by setting
hallucinated shortcuts. A new baseline is $\pi_{mpc}$, which extends the SPTM
local policy by using $p_{fwd}$ and $p_{t}$ from Sec.2.2 to implement an MPC
loop with n-step look-ahead. $\pi_{mpc}$ avoids getting stuck in columns
thanks to n-step lookahead, but still isn’t sufficient for global navigation
as the accuracy of simulated rollouts from $p_{fwd}$ decreases with the number
of timesteps.

Figure 7: Memory Refinement: In PALMER, a policy has three groups of
parameters: $Q(s_{t},a_{t},s_{g})$, $f_{\phi}$, and the contents of
$\mathcal{M}$. Iteratively forming plans through PER and executing them
creates a feedback loop between these components, where: i) actions inform
perception during the training of $f_{\phi}$, ii) perception facilitates
actions through the formation plans, and iii) memory serves as the medium for
this reciprocal interaction. As a result, trajectories produced by explicit
planning are gradually internalized as implicit behavior encoded in the model
parameters. This leads to: Q-values propagating further into distant goals
(Left), memory contents getting closer to optimal (Middle), and performances
of local policies showing significant improvement (Right).

Refining Memory Contents: We refine the contents of $\mathcal{M}$ by
iteratively generating and executing
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$. We then retrain all model
components only on the resulting new data that is equal in size to the initial
unrefined $\mathcal{M}$. Fig.7 shows the results. When $\pi_{\mathcal{M}}$,
and $argmax_{a}Q(a_{t},a,s_{g})$ are used as policies, their success ratio
increases significantly if they are trained on the optimized $\mathcal{M}$.
Q-value estimates trained on the optimized $\mathcal{M}$ also propagate better
to goals further away. The scaling of $len(\tau_{\mathcal{M}(s_{c},s_{g})})$
with goal-distance changes from an exponential trend to an approximately
linear one, due to the inclusion of transitions from successfully executed
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$. These results highlight that
refining memory contents improves the quality of future plans.

###  4.2 Experiments in Habitat

Figure 8: We evaluate our R-PRM based policy $\pi_{\mathcal{M}^{*}}$ in the
Habitat simulator for image-based navigation. Top Left: Success ratios in
training and test apartments. Top Right: Number of timesteps until reaching
the goal. ("Habitat seen" refers to the training apartment Roxbox, while
"habitat unseen" refers to the test apartment Annawan. Bottom: We found that
training the perception model $f_{\phi}$ on a single apartment generalizes
sufficiently well to allow perceptual experience retrieval and trajectory
stitching in any unseen apartment.

As shown in Fig.8, we find that our method allows image-based navigation in
this new domain with significantly different visuals and layouts (i.e., real-
world apartments), action space (i.e., turn-left, turn-right, go-forward), and
state space (i.e., single $256\times 256$ RGB images with 150 FOV). Perhaps
more surprisingly, we find that training $f_{\phi}$ only on exploration data
from a single apartment generalizes substantially well to any unseen
apartment, which directly allows perceptual experience retrieval and
trajectory stitching when provided with a corresponding replay buffer. For a
quantitative evaluation, we randomly pick two apartments, named Roxbox and
Annawan. In both apartments, we collect an exploration dataset using a uniform
random walk sequence of only 150k timesteps. We train the model components
solely on data from Roxbox. We then use them to implement our
$\pi_{\mathcal{M}^{*}}$ policy from Sec.4.1, which we then evaluate on both
apartments. For $n\in\\{8,16,24,32,36,44\\}$, we randomly sample $100$ pairs
of start and goal-states in a way that the geodesic distance between them lies
within $n\times\Delta$ and $(n+8)\times\Delta$ through rejection sampling. A
policy is considered successful if it can get within $2\times\Delta$ proximity
of the goal-state. We do not plot the SPTM and SORB baselines, because we
found that the models $\pi_{inv}(a|s_{t},s_{g})$ and $argmax_{a}\
Q(s_{t},a,s_{g})$ that they use as local navigation policies achieved almost
zero percent success rate in reaching local goals beyond $\sim 2\times\Delta$
distance. We empirically observed that most of the time these policies get
stuck in repetitive rotational motions without moving forward. This is most
likely due to the difficulty of offline RL training with hindsight relabelling
over random-walk data obtained with a much more challenging non-cartesian
action space
$\\{turn\\_left\\_30\\_deg,turn\\_right\\_30\\_deg,move\\_forward\\_\Delta\\}$.

###  4.3 Experiments in Maze2D

| SAC | SAC-off | BEAR | AWR | BCQ | CQL | IQL | Diffuser | PALMER
---|---|---|---|---|---|---|---|---|---
maze2d-umaze | 110.4 | 145.6 | 28.6 | 25.2 | 41.5 | 31.7 | 89.6 | 182.1 | 131.76
maze2d-medium | 69.5 | 82.0 | 89.8 | 33.2 | 35.0 | 26.4 | 105.2 | 332.9 | 416.28
maze2d-large | 14.1 | 1.5 | 19.0 | 70.1 | 23.2 | 40 | 159.9 | 328.1 | 361

Table 1: Total rewards on the Maze2D benchmark, which is a continuous control
task that requires long-horizon planning. Our R-PRM based
$\pi_{\mathcal{M}^{*}}$ policy achieves comparatively strong performance.

To test our method on a continuous control task, we perform additional
experiments on the Maze2D benchmark. As shown in Table.1, we find that the
same $\pi_{\mathcal{M}^{*}}$ policy from sections 4.1 and 4.2 achieves strong
performance, and can solve mazes of all three complexities.

##  5 Discussion and Future Directions

Is PALMER less expressive than standard deep Q-learning: Two important
premises of deep Q-learning [44, 34] are: i) minimizing Bellman error through
temporal-difference (TD) updates can restitch observed transitions in new
optimal ways [41, 45], ii) a neural network can learn to extrapolate Q-values
to unobserved but close-by states in high-dimensional spaces (e.g. images)
[46]. Both arguments are equally valid for our approach, since it can: i)
restitch transitions at arbitrary resolutions (i.e., anywhere from one-step
transitions to multi-step trajectories) by virtue of sampling-based planning,
ii) group together close-by states through $d_{\phi}$. Therefore, PALMER is an
RL algorithm that: i) optimizes Bellman error through sampling-based optimal
planning rather than gradient-based TD-updates [46], ii) performs
extrapolation between states using a perceptual-backbone $f_{\phi}$ rather
than a deep Q-network, and iii) replaces the greedy-policy $argmax_{a}\
Q(s_{t},a,s_{g})$ and value estimate $max_{a}\ Q(s_{t},a,s_{g})$ with
$argmax_{a}\ Q(s_{t},a,\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,1})$ and
$\mathcal{R}(\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})})$ respectively. The
key benefits of these alterations come into play when $s_{t}$ and $s_{g}$ are
far apart, and these benefits are: i) the PER mechanism in eq.1 that prevents
hallucinations in $Q(s_{t},a,s_{g})$, ii) global propagation of value
estimates by virtue of employing sampling-based planning methods, which are
known to be particularly proficient at searching high-dimensional state spaces
across long-horizons [35, 29].
Combining PALMER with standard deep Q-learning: Our approach can also be
flexibly combined with any traditional Q-learning method [46, 47, 48], by
using our proposed planning algorithms (Sec.2.4) as experience replay methods
[49]. This alternative approach stitches together
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ during training, and perform
backwards TD-updates over this trajectory starting from
$s_{g}=\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g}),s,-1}$ and ending at
$s_{c}=\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g}),s,0}$. As suggested by Fig.7,
this can allow value estimates $Q(s_{t},a,s_{g})$ to propagate more globally.
Our proof-of-concept experiments identify this as a promising direction, and
we leave a further extensive evaluation to future work. Connections to
contingency learning: Contingency learning refers to the acquisition of
knowledge of statistical correlations between percepts [50, 3, 51]. Following
this definition, PALMER can be interpreted as a contingency learning
framework, as the latent distance metric $d_{\phi}$ captures statistically how
likely two states are to be observed in close temporal proximity. The
knowledge of these statistical contingencies between states is then used for
long-horizon decision making through the proposed perceptual experience
retrieval and planning mechanisms.

##  6 Conclusion and Limitations

We presented PALMER, a long-horizon planning method that combines learning-
based perceptual representations with classical sampling-based planning
algorithms. Given a goal state $s_{g}$ and reward function $\mathcal{R}$, our
method searches the contents of an offline replay-buffer $\mathcal{M}$ to
stitch together a sequence of transitions
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}=\\{s_{1},a_{1},s_{2},...\\}$ that
reaches $s_{g}$ while maximizing $\mathcal{R}$. This results in an
experiential framework for long-horizon planning that is significantly more
robust and sample efficient compared to baselines.

Our experiments show that PALMER can successfully solve long-horizon planning
tasks from continuous high-dimensional inputs. In particular, we have shown
that given an offline dataset of only 150k transitions (i.e., compared to
sample complexities around the orders of magnitude 1e6-1e7 common in RL)
obtained from an entirely uniform random-walk (i.e., which is significantly
less structured compared to on-policy rollouts), it allows image-based
navigation between any two points in large-scale scans of real-world
apartments.

We believe that our memory-based planning perspective highlights a number of
interesting questions for future research. First, which transitions should be
kept in the replay buffer $\mathcal{M}$, and which ones should be discarded?
$\mathcal{M}$ cannot be infinitely expanded after deployment, and it is
critical to distill away redundancies between stored experiences. Second, when
the environment undergoes a change, which transitions in the replay buffer
remain valid and can still be used for planning, and which ones become
invalid? A mechanism that can answer this question can allow quick and sample-
efficient adaptation to environmental changes. Third, how can we extend
$f_{\phi}$ to allow more abstract associations and functional equivariances
between states? This can improve generalization by defining a more flexible
notion of experience retrieval that can recycle past behavior in new contexts
and for new tasks. We leave these questions to future work.

## References

  * [1] S. E. Palmer, _Vision science: Photons to phenomenology_. MIT press, 1999.
  * [2] J. J. Gibson, _The ecological approach to visual perception: classic edition_. Psychology Press, 2014.
  * [3] J. K. O’regan and A. Noë, “A sensorimotor account of vision and visual consciousness,” _Behavioral and brain sciences_ , vol. 24, no. 5, pp. 939–973, 2001.
  * [4] J. D. Co-Reyes, S. Sanjeev, G. Berseth, A. Gupta, and S. Levine, “Ecological reinforcement learning,” _arXiv preprint arXiv:2006.12478_ , 2020.
  * [5] D. Silver, S. Singh, D. Precup, and R. S. Sutton, “Reward is enough,” _Artificial Intelligence_ , vol. 299, p. 103535, 2021.
  * [6] E. L. Thorndike, “Animal intelligence: An experimental study of the associative processes in animals.” _The Psychological Review: Monograph Supplements_ , vol. 2, no. 4, p. i, 1898.
  * [7] ——, “The law of effect,” _The American journal of psychology_ , vol. 39, no. 1/4, pp. 212–222, 1927.
  * [8] D. T. Campbell, “Perception as substitute trial and error.” _Psychological review_ , vol. 63, no. 5, p. 330, 1956.
  * [9] R. J. Herrnstein, “On the law of effect,” _Journal of the experimental analysis of behavior_ , vol. 13, no. 2, pp. 243–266, 1970.
  * [10] S. D. Whitehead and D. H. Ballard, “Learning to perceive and act by trial and error,” _Machine Learning_ , vol. 7, no. 1, pp. 45–83, 1991.
  * [11] D. Bertsekas, _Dynamic programming and optimal control: Volume I_. Athena scientific, 2012, vol. 1.
  * [12] B. Eysenbach, R. R. Salakhutdinov, and S. Levine, “Search on the replay buffer: Bridging planning and reinforcement learning,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [13] S. Emmons, A. Jain, M. Laskin, T. Kurutach, P. Abbeel, and D. Pathak, “Sparse graphical memory for robust planning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 5251–5262, 2020.
  * [14] N. Savinov, A. Dosovitskiy, and V. Koltun, “Semi-parametric topological memory for navigation,” _arXiv preprint arXiv:1803.00653_ , 2018.
  * [15] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. Pieter Abbeel, and W. Zaremba, “Hindsight experience replay,” _Advances in neural information processing systems_ , vol. 30, 2017\.
  * [16] L. P. Kaelbling, “Learning to achieve goals,” in _IJCAI_ , vol. 2. Citeseer, 1993, pp. 1094–8.
  * [17] T. Schaul, D. Horgan, K. Gregor, and D. Silver, “Universal value function approximators,” in _International conference on machine learning_. PMLR, 2015, pp. 1312–1320.
  * [18] P. Agrawal, A. V. Nair, P. Abbeel, J. Malik, and S. Levine, “Learning to poke by poking: Experiential learning of intuitive physics,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [19] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, “Curiosity-driven exploration by self-supervised prediction,” in _International conference on machine learning_. PMLR, 2017, pp. 2778–2787.
  * [20] K. Hartikainen, X. Geng, T. Haarnoja, and S. Levine, “Dynamical distance learning for semi-supervised and unsupervised skill discovery,” _arXiv preprint arXiv:1907.08225_ , 2019.
  * [21] S. Chopra, R. Hadsell, and Y. LeCun, “Learning a similarity metric discriminatively, with application to face verification,” in _2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)_ , vol. 1. IEEE, 2005, pp. 539–546.
  * [22] S. Shalev-Shwartz and S. Ben-David, _Understanding machine learning: From theory to algorithms_. Cambridge university press, 2014.
  * [23] S. M. LaValle _et al._ , “Rapidly-exploring random trees: A new tool for path planning.”
  * [24] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [25] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The international journal of robotics research_ , vol. 30, no. 7, pp. 846–894, 2011.
  * [26] D. Shah, B. Eysenbach, N. Rhinehart, and S. Levine, “Recon: Rapid exploration for open-world navigation with latent goal models,” _arXiv preprint arXiv:2104.05859_ , 2021.
  * [27] D. Shah and S. Levine, “Viking: Vision-based kilometer-scale navigation with geographic hints,” _arXiv preprint arXiv:2202.11271_ , 2022.
  * [28] X. Meng, N. Ratliff, Y. Xiang, and D. Fox, “Scaling local control to large-scale topological navigation,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 672–678.
  * [29] S. M. LaValle, _Planning algorithms_. Cambridge university press, 2006.
  * [30] J. T. Betts, “Survey of numerical methods for trajectory optimization,” _Journal of guidance, control, and dynamics_ , vol. 21, no. 2, pp. 193–207, 1998.
  * [31] ——, _Practical methods for optimal control and estimation using nonlinear programming_. SIAM, 2010.
  * [32] D. E. Kirk, _Optimal control theory: an introduction_. Courier Corporation, 2004.
  * [33] R. Tedrake, _Underactuated Robotics_ , 2022. [Online]. Available: http://underactuated.mit.edu
  * [34] P. Abbeel, _Advanced Robotics_ , 2019. [Online]. Available: https://people.eecs.berkeley.edu/~pabbeel/cs287-fa19/
  * [35] H. Choset, K. M. Lynch, S. Hutchinson, G. A. Kantor, and W. Burgard, _Principles of robot motion: theory, algorithms, and implementations_ , 2005\.
  * [36] S. Thrun, “Probabilistic robotics,” _Communications of the ACM_ , vol. 45, no. 3, pp. 52–57, 2002.
  * [37] M. Bujanca, P. Gafton, S. Saeedi, A. Nisbet, B. Bodin, M. F. O’Boyle, A. J. Davison, P. H. Kelly, G. Riley, B. Lennox _et al._ , “Slambench 3.0: Systematic automated reproducible evaluation of slam systems for robot vision challenges and scene understanding,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 6351–6358.
  * [38] G. Grisetti, R. Kümmerle, C. Stachniss, and W. Burgard, “A tutorial on graph-based slam,” _IEEE Intelligent Transportation Systems Magazine_ , vol. 2, no. 4, pp. 31–43, 2010.
  * [39] M. Kempka, M. Wydmuch, G. Runc, J. Toczek, and W. Jaśkowski, “Vizdoom: A doom-based ai research platform for visual reinforcement learning,” in _2016 IEEE conference on computational intelligence and games (CIG)_. IEEE, 2016, pp. 1–8.
  * [40] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik _et al._ , “Habitat: A platform for embodied ai research,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 9339–9347.
  * [41] J. Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine, “D4rl: Datasets for deep data-driven reinforcement learning,” 2020.
  * [42] H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 30, no. 1, 2016.
  * [43] M. G. Bellemare, W. Dabney, and R. Munos, “A distributional perspective on reinforcement learning,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 449–458.
  * [44] S. Levine, _Deep Reinforcement Learning_ , 2022. [Online]. Available: http://rail.eecs.berkeley.edu/deeprlcourse/
  * [45] Y. Chebotar, K. Hausman, Y. Lu, T. Xiao, D. Kalashnikov, J. Varley, A. Irpan, B. Eysenbach, R. Julian, C. Finn _et al._ , “Actionable models: Unsupervised offline reinforcement learning of robotic skills,” _arXiv preprint arXiv:2104.07749_ , 2021.
  * [46] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [47] M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver, “Rainbow: Combining improvements in deep reinforcement learning,” in _Thirty-second AAAI conference on artificial intelligence_ , 2018.
  * [48] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel _et al._ , “Soft actor-critic algorithms and applications,” _arXiv preprint arXiv:1812.05905_ , 2018.
  * [49] T. Schaul, J. Quan, I. Antonoglou, and D. Silver, “Prioritized experience replay,” _arXiv preprint arXiv:1511.05952_ , 2015.
  * [50] B. F. Skinner, _Contingencies of reinforcement: A theoretical analysis_. BF Skinner Foundation, 2014, vol. 3.
  * [51] A. Noë, A. Noë _et al._ , _Action in perception_ , 2004.
  * [52] A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune, “First return, then explore,” _Nature_ , vol. 590, no. 7847, pp. 580–586, 2021\.
  * [53] S. Tian, S. Nair, F. Ebert, S. Dasari, B. Eysenbach, C. Finn, and S. Levine, “Model-based visual planning with self-supervised functional distances,” _arXiv preprint arXiv:2012.15373_ , 2020.
  * [54] A. Van den Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _arXiv e-prints_ , pp. arXiv–1807, 2018\.
  * [55] R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,” _Artificial intelligence_ , vol. 112, no. 1-2, pp. 181–211, 1999.
  * [56] G. Konidaris and A. Barto, “Skill discovery in continuous reinforcement learning domains using skill chaining,” _Advances in neural information processing systems_ , vol. 22, 2009.
  * [57] R. Tedrake, I. R. Manchester, M. Tobenkin, and J. W. Roberts, “Lqr-trees: Feedback motion planning via sums-of-squares verification,” _The International Journal of Robotics Research_ , vol. 29, no. 8, pp. 1038–1052, 2010\.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

## Supplementary Material

This document presents additional implementation details, visualizations, and
conceptual discussions that were excluded or briefed due to space limitations
in the main paper. The organization mirrors the sections from the main paper
(with the exact same order and numbering), and the exposition generally
maintains a question-answer format. It aims to provide significantly more
details, at a degree of clarity sufficient for re-implementation. As such, we
recommend referring to this document whenever any section in the main paper
can benefit from further elaboration. The supplementary material consists of:

  * •

vizdoom_nav — navigation videos in VizDoom.

  * •

habitat_roxbox_nav — navigation videos in the training apartment Roxbox in
Habitat.

  * •

habitat_annawan_nav — navigation videos in the test apartment Annawan in
Habitat.

  * •

maze2d_experiments — goal reaching videos in Maze2D.

  * •

planning_vis — videos visualizing the execution of R-RRT and R-RRT*.

  * •

code — source code for PALMER.

### Table of Contents

1\. Introduction

  * •

Why learn a latent distance metric for nearest neighbor retrieval?

  * •

What does stitching transitions together mean?

2\. Perception-Action Loop with Memory Reorganization

2.1. Perceptual Representations that Capture Local Reachability

  * •

What does local reachability mean?

2.2. Representation Learning via Reinforcement Learning

  * •

How are the model components trained, and what are their exact inputs and
outputs?

  * •

What do the terms in the contrastive loss-function $L_{Q}$ mean?

2.3. Perceptual Experience Retrieval (PER)

  * •

How do we solve the optimization problem in equation 1 from the main paper?

  * •

What do the retrieved trajectories $\tau_{\mathcal{M}(s_{c},s_{g})}$ look
like?

2.4. Long-Horizon Planning Through Stitching Trajectory Segments

  * •

How does R-PRM work in detail?

  * •

How does R-RRT work in detail?

  * •

How does R-RRT* work in detail?

  * •

What does optimizing the Bellman error on the roadmap mean?

  * •

What does restitching transitions at arbitrary resolution mean?

2.5. Refining Memory Contents via Forming and Executing Plans

  * •

What does optimizing memory contents mean?

  * •

How does the perception-action loop in PALMER work in detail?

3\. Related Work

  * •

What is the main reason why memory-based reasoning over actually observed
transitions is necessary? Why are methods like SPTM or SoRB that solely rely
on learning-based distance estimates are inherently prone to false
predictions?

  * •

What are the details for our implementations of SoRB and SPTM?

4\. Experiments

Setup

  * •

What are the details for the experimental setup in VizDoom?

Validating Perceptual Experience Retrieval (PER)

  * •

What is the exact evaluation process that produced Fig.4 in the main paper?

Robust Distances

  * •

What is the exact evaluation process for the right panel of Fig.5 in the main
paper?

Proposed Planning Algorithms

  * •

Why does the policy $\pi_{\mathcal{M}^{*}}$ use R-PRM for planning?

  * •

What are the details for the $\pi_{mpc}$ baseline?

Experiments in Habitat

  * •

What are the details for the experimental setup in Habitat?

  * •

Why does the agent occasionally take random-looking actions in the habitat
navigation trials?

5\. Discussion and Future Directions

  * •

How is PALMER related to the "Options Framework (Sutton et al.)" and "Skill-
Chaining (Konidaris et al.)"?

  * •

How is PALMER related to "LQR-Trees (Tedrake et al.)?

### 1 Introduction

Why learn a latent distance metric for nearest neighbor retrieval: In a low-
dimensional state space such as 3D positions, L2 distance (i.e., euclidean
distance) directly correlates with _local_ physical-reachability (i.e., we
emphasize local, because euclidian distances still do not match geodesic
distances globally). Therefore in such state-spaces, grouping together two
nearby states and treating them as the same single state for downstream global
planning should still result in a feasible planned trajectory. By feasible, we
mean that the gaps and approximations introduced by state grouping are
functionally inconsequential and can be handled reasonably well by a local
policy tracking the global planned trajectory. This property doesn’t hold in
high-dimensional state spaces such as images, since the L2 distance doesn’t
correlate with physical reachability. The main purpose of $f_{\phi}$ is to
project such high-dimensional spaces into a low-dimensional representation
space where this property holds, so that nearby states can be fused together
to make sampling-based planning computationally tractable.

Figure 9: Visualization of stitching together trajectories. If an agent has
previous experience of separately going through segments $(A,B)$ and $(C,D)$,
it should be able to go from $s_{c}$ to $s_{g}$ through the segments $(A,D)$.

What does stitching transitions together mean: As shown in Fig9, if there are
two separate sequences of transitions in an offline memory buffer that
traverse segments $(A,B)$ and $(C,D)$, an agent should be capable of going
from $s_{c}$ to $s_{g}$ through the segments $(A,D)$ event if such a direct
path of transitions was never actually observed. Traditional deep Q-learning
methods achieve this by combining and propagating value estimates through TD-
updates (i.e., $argmax_{a}Q(s_{1},a,s_{g})$ points to segment $D$ after TD
updates over the path $(C,D)$, therefore the argmax policy would follow the
path $(A,D)$ when going from $s_{c}$ to $s_{g}$. [41] provides a further
discussion). In our approach, this is achieved by setting edge distances for
$(A,B,C,D)$ in a planning graph through perceptual experience retrieval, and
then performing a shortest path computation to retrieve the path $(A,D)$.

### 2 Perception-Action Loop with Memory Reorganization

### 2.1 Perceptual Representations that Capture Local Reachability

What does local reachability mean: At a high-level (and for the special case
of image-based navigation) what the term ‘local reachability’ intends to
convey is that if two images $I_{1}$ and $I_{2}$ are from physically close
positions, $d_{\phi}=|f_{\phi}(I_{1})-f_{\phi}(I_{2})|$ should be small. This
in turn provides a metric for grouping together states that is better than the
L2 distance in image space, which has no correlation with physical
reachability. Such a metric is necessary to make search and sampling-based
planning planning over the memory buffer computationally tractable. This
learned metric $d_{\phi}$ serves the exact same purpose as the hand-crafted
image compression criterion employed in [52] to initialize cells from states.

### 2.2 Representation Learning via Reinforcement Learning

Figure 10: Visualization of the model architecture, reproduced here for ease
of reference.

How are the model components trained, and what are their exact inputs and
outputs: More detailed descriptions for all model components are given below
(Fig.10 presents a visualization):

  * •

The architecture and training of $Q(s_{t},a_{t},s_{g})$ is completely
decoupled from the other components. It consists of cascaded convolutional and
fully-connected layers with batch normalization and ReLU activations between
each layer. It takes as input the concatenated images for current and goal
states (i.e., shape $B\times C\times H\times W$), and outputs a vector of
Q-values for each action (i.e., shape $B\times num\\_actions$). It is trained
through offline DDQN [42] with hindsight goal-relabelling [15]. We first
sample $t\sim Uniform(0,dataset\\_size)$ and $T\sim Geom(p)$, and then
retrieve from the replay buffer a transition and a goal state as
$(s_{t},a_{t},s_{t+1},s_{g}:=s_{t+T})$. We then minimize the TD error $[\
Q_{\theta}(s_{t},a_{t},s_{g})-(\mathbbm{1}_{s_{t+1}=s_{g}}+\gamma\mathbbm{1}_{s_{t+1}\neq
s_{g}}\ max_{a}\ Q_{\theta^{-}}(s_{t+1},a,s_{g}))\ ]^{2}$, as in [53].

  * •

The perceptual backbone $f_{\phi}(s)$ uses a standard Resnet-18 architecture.
It takes as input the images for a given state (i.e., $B\times C\times H\times
W$), and outputs a low-dimensional representation vector $z=f_{\phi}(s)$
(i.e., shape $B\times D$). All other components take as input these low-
dimensional representations, rather than operating over images.

  * •

$p_{fwd}(z^{\prime}_{t+1}\ |\ z_{t},a_{t})$, $\pi_{inv}(a^{\prime}_{t}\ |\
z_{t},z_{g})$, and $p_{t}(T^{\prime}\ |\ z_{t},z_{g})$ all consist of fully-
connected layers with ReLU activations. To train them, we first sample $t\sim
Uniform(0,dataset\\_size)$. We then sample $T$ according to $T\sim
Uniform(0,T_{max})$ or $T\sim Uniform(T_{max},dataset\\_size-t)$, half the
time from the former distribution, half the time from the latter. We retrieve
from the replay buffer a transition and a goal state as
$(s_{t},a_{t},s_{t+1},s_{g}:=s_{t+T})$, and project them into low dimensional
representations $(z_{t},a_{t},z_{t+1},z_{g})$ using $f_{\phi}$. These are
concatenated and passed to models $p_{fwd}(z^{\prime}_{t+1}\ |\
z_{t},a_{t}),\pi_{inv}(a^{\prime}_{t}\ |\ z_{t},z_{g}),p_{t}(T^{\prime}\ |\
z_{t},z_{g})$ in a way compatible with their arguments. $p_{fwd}$ outputs the
mean for the predicted next state distribution (i.e., shape $B\times D$), and
is trained using the MSE loss $L_{fwd}$ with $z_{t+1}$ as the target.
$\pi_{inv}$ outputs a vector of probabilities over actions (i.e., shape
$B\times num\\_actions$), and is trained with the cross-entropy loss $L_{inv}$
with $a_{t}$ as the target. $p_{t}$ also outputs a discrete probability
distribution over $[0,T_{max}]$ that predicts the distribution of time-steps
to reach the goal, where the last bin $T_{max}$ serves as a catch-all for all
values above it. It is trained using the cross entropy loss $L_{T}$, with $T$
as the target. As mentioned in the main paper, all components $f_{\phi}$,
$p_{fwd}(z^{\prime}_{t+1}\ |\ z_{t},a_{t})$, $\pi_{inv}(a^{\prime}_{t}\ |\
z_{t},z_{g})$, $p_{t}(T^{\prime}\ |\ z_{t},z_{g})$ are trained jointly, with
an additional loss function $L_{Q}$ that regularizes $f_{\phi}$.

What do the terms in the contrastive loss-function $L_{Q}$ mean: The loss
function $L_{Q}(s_{t},s_{g})=l_{hinge}(d_{\phi}(s_{t},s_{g})-d_{p})\
\mathbbm{1}_{d_{Q}(s_{t},s_{g})\leq
c_{Q}}+l_{hinge}(d_{p}-d_{\phi}(s_{t},s_{g}))\
\mathbbm{1}_{d_{Q}(s_{t},s_{g})\geq c_{Q}}$ consists of two penalty terms
$l_{hinge}(d_{\phi}(s_{t},s_{g})-d_{p})$ (i.e., only active when $d_{\phi}\geq
d_{p}$) and $l_{hinge}(d_{p}-d_{\phi}(s_{t},s_{g}))$ (i.e., only active when
$d_{\phi}\leq d_{p}$). These penalty terms are gated through two complementary
indicator functions $\mathbbm{1}_{d_{Q}(s_{t},s_{g})\leq c_{Q}}$ and
$\mathbbm{1}_{d_{Q}(s_{t},s_{g})\geq c_{Q}}$. This essentially means that for
$L_{Q}$ to be zero, $d_{\phi}\leq d_{p}$ should hold (i.e., perceptual
representations are close) if and only if $d_{Q}(s_{t},s_{g})\leq c_{Q}$ holds
(i.e., states are physically close). The reason for employing such a
conservative switching mechanism with a hinge loss in $L_{Q}$ (i.e., rather
than a continuous penalty term as in [21, 54]) is because Q-value estimates
are quite inaccurate (especially when $s_{c}$ and $s_{g}$ are far apart), and
their exact value is generally unreliable (i.e., they can indicate whether
two-states are close sufficiently well, but cannot robustly answer how close
they are). To pick the hyperparameter $c_{Q}$, we compute the average Q-value
between states in the replay buffer that were observed to be within one-step
proximity, and use a fraction of this value to as a conservative estimate.
While conceptually the choice for the hyperparameter $d_{p}$ is arbitrary, we
heuristically pick it by examining the average $d_{\phi}$ distance between
subsequent states in the replay buffer, obtained from a preliminary $f_{\phi}$
backbone trained without $L_{Q}$.

### 2.3 Perceptual Experience Retrieval (PER)

How do we solve the optimization problem in equation 1 from the main paper:
Our experiments use $-\mathcal{R(\tau)}=len(\tau)$. We first compute the
perceptual representations $z$ for all states in the replay buffer, and stack
them into a tensor block of shape $(dataset\\_size,D)$. Given $s_{c}$ and
$s_{g}$, we search this tensor with vectorized masking operations to retrieve
a set of neighboring states $N(s_{c},d_{p})$ and $N(s_{g},d_{p})$ (i.e., sets
of states within a perceptual distance threshold $d_{p}$ of $s_{c}$ and
$s_{g}$), to address cons.4. We sort the resulting pairs of states
$(s_{i},s_{j})\in N(s_{c},d_{p})\times N(s_{g},d_{p})$ in terms of $j-i$, and
filter these pairs using cons.5. We then pick the first (i.e., closest) pair,
and return all the states with indices between $i,j$ from the replay buffer as
the resulting trajectory $\tau_{\mathcal{M}(s_{c},s_{g})}$. The important
thing to emphasize about all of these operations is that they can be trivially
vectorized, and therefore the optimization problem in eq.3-5 can be solved in
less time than a forward pass of $f_{\phi}$.

Figure 11: Visualization of retrieved trajectories, with different perceptual
distance threshold. Query states $s_{c}$ and $s_{g}$ are represented as white
squares with a cross in the center, while the start and end points of the
retrieved trajectory $\tau_{\mathcal{M}(s_{c},s_{g})}$ are denoted with a
black square and a yellow square with a diagonal dash respectively.

What do the retrieved trajectories $\tau_{\mathcal{M}(s_{c},s_{g})}$ look
like: As the perceptual distance threshold for $d_{\phi}$ increases, the
physical radii spanned by the nearest neighbor sets $N(s_{c},d_{p})$ and
$N(s_{g},d_{p})$ increase, as shown in Fig.11. As a result, constraint 4 in
the PER equation gets looser, more trajectories satisfy constraints 4 and 5
(because their start and end points are allowed to deviate further from the
query pair $s_{c},s_{g}$), and therefore the optimization in equation 3
returns a shorter trajectory $\tau_{\mathcal{M}(s_{c},s_{g})}$.

### 2.4 Long-Horizon Planning Through Stitching Trajectory Segments

Algorithm 3 Classic PRM (Roadmap Construction)

1:$V\leftarrow\\{SampleFree_{i}\\}_{i=1,...,num\\_vertices};\>E\leftarrow\emptyset$
$\triangleright$ Initialize vertices and edges

2:for each $s_{i}\in V$ do

3: $U\leftarrow Near(V,s_{i},r)\setminus\\{s_{i}\\}$

4: for each $s_{j}\in U$ do $\triangleright$ Draw lines as edges

5: if $CollisionFree(s_{i},s_{j})$ then $E\leftarrow
E\cup\\{(s_{i},s_{j}),(s_{j},s_{i})\\}$ return $G=(V,E)$

Algorithm 4 Classic PRM (Shortest-Path Queries Over the Roadmap)

1:Input: $s_{c},s_{g},G=(V,E),\mathcal{R}(\tau),f_{\phi},\mathcal{M}$

2:for each $s_{i}\in V$ do $\triangleright$ Insert $s_{c}$ and $s_{g}$ into
the PRM graph

3: if $CollisionFree(s_{c},s_{i})$ then

4: $E\leftarrow E\cup\\{(s_{c},s_{i}),(s_{i},s_{c})\\}$

5: if $CollisionFree(s_{i},s_{g})$ then

6: $E\leftarrow E\cup\\{(s_{i},s_{g}),(s_{g},s_{i})\\}$ return
$\\{s_{j}\\}\leftarrow ShortestPath(s_{c},s_{g},G)$ $\triangleright$ Shortest
path through graph search

Algorithm 5 R-PRM (Roadmap Construction)

1:Input: $f_{\phi},\mathcal{M}$

2:$V\leftarrow\\{SampleFree_{i}\\}_{i=1,...,num\\_vertices};\>E\leftarrow\emptyset$
$\triangleright$ Initialize vertices and edges

3:for each $s_{i}\in V$ do

4: $U\leftarrow Near(V,s_{i},r)\setminus\\{s_{i}\\}$

5: for each $s_{j}\in U$ do $\triangleright$ Place PER trajectories in edges

6: $E\leftarrow
E\cup\\{(s_{i},s_{j}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{i},s_{j})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{i},s_{j})})\\}$ return $G=(V,E)$

Algorithm 6 R-PRM (Trajectory Restitching Given the Constructed Roadmap)

1:Input: $s_{c},s_{g},G=(V,E),\mathcal{R}(\tau),f_{\phi},\mathcal{M}$

2:for each $s_{i}\in V$ do $\triangleright$ Insert $s_{c}$ and $s_{g}$ into
the PRM graph

3: if $len(\tau_{\mathcal{M}(s_{c},s_{i})})\leq r$ then $\triangleright$ Place
PER trajectories in edges

4: $E\leftarrow
E\cup\\{(s_{c},s_{i}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{c},s_{i})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{c},s_{i})})\\}$

5: if $len(\tau_{\mathcal{M}(s_{i},s_{g})})\leq r$ then

6: $E\leftarrow
E\cup\\{(s_{i},s_{g}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{i},s_{g})},\
d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{i},s_{g})})\\}$

7:$\tau_{stitched}\leftarrow\emptyset$

8:$\\{s_{j}\\}\leftarrow ShortestPath(s_{c},s_{g},G,\mathcal{R}(\tau))$
$\triangleright$ Trajectory stitching by dynamic programming

9:for $0<i<|\\{s_{j}\\}|$ do $\triangleright$ Concatenate PER trajectories
along the shortest path

10:
$\tau_{stitched}\leftarrow\tau_{stitched}\circ\tau_{\mathcal{M}(s_{i-1},s_{i})}$
return $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}=\tau_{stitched}$

How does R-PRM work in detail: Alg.3, 4 give step-by-step descriptions for the
classical PRM algorithm (adapted from [25]), while Alg.5, 6 describe our new
definitions for R-PRM. It can be seen that there are two main differences:

  * •

In R-PRM, whenever an edge is created, a trajectory
$\tau_{\mathcal{M}(s_{c},s_{i})}$ is retrieved through perceptual experience
retrieval and stored in a field $\tau_{edge}$, while its reward
$-\mathcal{R}(\tau_{\mathcal{M}(s_{c},s_{i})})$ is stored in a different field
$d_{edge}$.

  * •

In PRM the length and cost of a line segment are the same (i.e., euclidian
distance), whereas in R-PRM the length of a trajectory
$len(\tau_{\mathcal{M}(s_{c},s_{i})})$ and its reward
$-\mathcal{R}(\tau_{\mathcal{M}(s_{c},s_{i})})$ are decoupled. This means that
a shortest path query in R-PRM returns a sequence of nodes and edges that
optimize the reward function $\mathcal{R}$. An additional step in R-PRM is
that at the end of the shortest-path query, all trajectories
$\tau_{edge}=\tau_{\mathcal{M}(s_{i-1},s_{i})}$ stored in the returned edges
are concatenated into a single trajectory
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}=\tau_{stitched}$.

Algorithm 7 Classic RRT

1:$V\leftarrow\\{s_{init}\\};\>E\leftarrow\emptyset$ $\triangleright$
Initialize vertices and edges

2:for $i=1,...,n$ do

3: $s_{rand}\leftarrow SampleFree_{i}$ $\triangleright$ Sample random vertex

4: $s_{nearest}\leftarrow Nearest(V,s_{rand})$ $\triangleright$ Find the
nearest vertex in V

5: $s_{new}\leftarrow Steer(s_{nearest},s_{rand},r)$ $\triangleright$ Draw a
line segment of length $r$

6: if $CollisionFree(s_{nearest},s_{new})$ then

7: $V\leftarrow V\cup\\{s_{new}\\}\ ;\ E\leftarrow
E\cup\\{(s_{nearest},s_{new}),(s_{new},s_{nearest})\\}$ return $G=(V,E)$

Algorithm 8 R-RRT

1:$V\leftarrow\\{s_{init}\\};\>E\leftarrow\emptyset$ $\triangleright$
Initialize vertices and edges

2:for $i=1,...,n$ do

3: $s_{rand}\leftarrow SampleFree_{i}$ $\triangleright$ Sample random vertex

4: $s_{nearest}\leftarrow Nearest(V,s_{rand})$ $\triangleright$ Find the
nearest vertex in V

5: $s_{new}\leftarrow\tau_{\mathcal{M}(s_{nearest},s_{rand}),r}$
$\triangleright$ Get the $r$ ’th state in
$\tau_{\mathcal{M}(s_{nearest},s_{rand})}$

6: if $len(\tau_{\mathcal{M}(s_{nearest},s_{new})})\leq r$ then

7: $V\leftarrow V\cup\\{s_{new}\\}$

8: $E\leftarrow
E\cup\\{(s_{nearest},s_{new}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{nearest},s_{new})},$

9:$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\>d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{nearest},s_{new})})\\}$
return $G=(V,E)$

How does R-RRT work in detail: Alg.7 gives a step-by-step description for the
classical RRT algorithm (adapted from [25]), while Alg.8 describes our new
definition for R-RRT. In addition to the two previous differences between PRM
and R-PRM, there is one additional difference between RRT and R-RRT. In RRT,
there is a steering sub-routine that draws a line segment of length $r$
starting from $s_{nearest}$ and extending towards $s_{rand}$, to create a new
vertex $s_{new}$. In R-RRT, this is replaced by retrieving a trajectory
$\tau_{\mathcal{M}(s_{nearest},s_{rand})}$ starting from $s_{nearest}$ and
ending at $s_{rand}$, and its $r$ ’th state is used to create the new vertex
$s_{new}$.

Algorithm 9 Classic RRT*

1:$V\leftarrow\\{s_{init}\\};\>E\leftarrow\emptyset$ $\triangleright$
Initialize vertices and edges

2:for $i=1,...,n$ do

3: $s_{rand}\leftarrow SampleFree_{i}$ $\triangleright$ Sample random vertex

4: $s_{nearest}\leftarrow Nearest(V,s_{rand})$ $\triangleright$ Find the
nearest vertex in V

5: $s_{new}\leftarrow Steer(s_{nearest},s_{rand},r)$ $\triangleright$ Draw a
line segment of length $r$

6: if $CollisionFree(s_{nearest},s_{new})$ then

7: $S_{near}\leftarrow Near(V,s_{new},r)$

8: $V\leftarrow V\cup\\{s_{new}\\}$

9: $s_{min}\leftarrow s_{nearest}$

10: $c_{min}\leftarrow Cost(s_{nearest})+Cost(Line(s_{nearest},s_{new}))$

11: for each $s_{near}\in X_{near}$ do $\triangleright$ Connect along a
minimum-cost path

12: $c_{near}\leftarrow Cost(s_{near})+Cost(Line(s_{near},s_{new}))$

13: if $CollisionFree(s_{near},s_{new})$ and $c_{near}\leq c_{min}$ then

14: $s_{min}\leftarrow s_{near}\ ;\ c_{min}\leftarrow c_{near}$

15: $E\leftarrow E\cup\\{(s_{min},s_{new})\\}$

16: for each $s_{near}\in X_{near}$ do $\triangleright$ Rewire the tree

17: $c_{near,new}\leftarrow Cost(s_{new})+Cost(Line(s_{new},s_{near}))$

18: if $CollisionFree(s_{new},s_{near})$ and $c_{near,new}\leq c_{near}$ then

19: $s_{parent}\leftarrow Parent(s_{near})$

20:
$E\leftarrow(E\textbackslash\\{(s_{parent},s_{near})\\}\cup\\{s_{new},s_{near}\\})$
return $G=(V,E)$

Algorithm 10 R-RRT*

1:$V\leftarrow\\{s_{init}\\};\>E\leftarrow\emptyset$ $\triangleright$
Initialize vertices and edges

2:for $i=1,...,n$ do

3: $s_{rand}\leftarrow SampleFree_{i}$ $\triangleright$ Sample random vertex

4: $s_{nearest}\leftarrow Nearest(V,s_{rand})$ $\triangleright$ Find the
nearest vertex in V

5: $s_{new}\leftarrow\tau_{\mathcal{M}(s_{nearest},s_{rand}),r}$
$\triangleright$ Get the $r$ ’th state in
$\tau_{\mathcal{M}(s_{nearest},s_{rand})}$

6: if $len(\tau_{\mathcal{M}(s_{nearest},s_{new})})\leq r$ then

7: $S_{near}\leftarrow Near(V,s_{new},r)$

8: $V\leftarrow V\cup\\{s_{new}\\}$

9: $s_{min}\leftarrow s_{nearest}$

10: $c_{min}\leftarrow
Cost(s_{nearest})+-\mathcal{R}(\tau_{\mathcal{M}(s_{nearest},s_{new})})$

11: for each $s_{near}\in X_{near}$ do $\triangleright$ Connect along a
minimum-cost path

12: $c_{near}\leftarrow
Cost(s_{near})+-\mathcal{R}(\tau_{\mathcal{M}(s_{near},s_{new})})$

13: if $len(\tau_{\mathcal{M}(s_{near},s_{new})})\leq r$ and $c_{near}\leq
c_{min}$ then

14: $s_{min}\leftarrow s_{near}\ ;\ c_{min}\leftarrow c_{near}$

15: $E\leftarrow
E\cup\\{(s_{min},s_{new}):\>\tau_{edge}=\tau_{\mathcal{M}(s_{min},s_{new})},d_{edge}=-\mathcal{R}(\tau_{\mathcal{M}(s_{min},s_{new})})\\}$

16: for each $s_{near}\in X_{near}$ do $\triangleright$ Rewire the tree

17: $c_{near,new}\leftarrow
Cost(s_{new})+-\mathcal{R}(\tau_{\mathcal{M}(s_{new},s_{near})})$

18: if $len(\tau_{\mathcal{M}(s_{new},s_{near})})\leq r$ and $c_{near,new}\leq
c_{near}$ then

19: $s_{parent}\leftarrow Parent(s_{near})$

20:
$E\leftarrow(E\textbackslash\\{(s_{parent},s_{near})\\}\cup\\{s_{new},s_{near}\\})$
return $G=(V,E)$

How does R-RRT* work in detail: Alg.9 gives a step-by-step description for the
classical RRT* algorithm (adapted from [25]), while Alg.10 describes our new
definition for R-RRT*. R-RRT* almost exactly maintains the tree rewiring
machinery employed in RRT*, the only difference being that the line costs
(i.e., euclidian distance) are replaced with
$-\mathcal{R}(\tau_{\mathcal{M}(s_{i},s_{j})})$ (i.e., in addition to the
previous three differences from R-PRM and R-RRT).

What does optimizing the Bellman error on the roadmap mean: Dynamic
programming based graph-search algorithms like Dijkstra or (discrete) value-
iteration generally employ a cost caching mechanism to iteratively update
cost-to-come values, and these updates reduce Bellman error (i.e., the
difference between the cost-to-come values before and after the update) during
forward-search [29]. R-PRM uses Dijkstra for shortest-path search, while
R-RRT* employs the same dynamic programming based tree-rewiring mechanism as
the original RRT*, therefore both algorithms are optimizing the Bellman error
between the vertices of their graphs through dynamic programming.

What does restitching transitions at arbitrary resolution mean: The
retrospective-planning algorithms R-PRM, R-RRT, R-RRT* are sampling based.
This means that if two consequent states $s_{t}$ and $s_{t+1}$ are retrieved
during their $SampleFree_{i}$ routines, then these algorithms will set an edge
using $\tau_{\mathcal{M}(s_{t},s_{t+1})}$, which is simply the single
transition $(s_{t},a_{t},s_{t+1})$. Therefore, given enough samples, these
algorithms can restitch trajectories down to the level of individual
transitions.

### 2.5 Refining Memory Contents via Forming and Executing Plans

What does optimizing memory contents mean: A replay buffer $\mathcal{M}$ is a
collection of trajectories. Optimizing its contents means adding trajectories
to $\mathcal{M}$ that achieve higher total reward.

Algorithm 11 PALMER: Perception-Action Loop with Memory Retrieval

1:Input: $\mathcal{R}(\tau)$

2:$f_{\phi}.init()$, $Q.init()$, $\mathcal{M}\leftarrow\emptyset$
$\triangleright$ Initialize policy parameters

3:while $t\leq max\\_timestep$ do

4: while $i\ \leq\ num\\_exploration\\_steps$ do $\triangleright$ Exploration

5: i) Using [any suitable method]: explore the environment

6: to obtain an exploration trajectory $\tau_{new}$

7: ii) Using [$\tau_{new}$]: update $\mathcal{M}$ $\triangleright$ Memory
expansion

8: while $i\ \leq\ num\\_updates$ do

9: Using [$\mathcal{M}$]: update $Q(s_{t},a_{t},s_{g})$ $\triangleright$ Train
value function

10: Using [$\mathcal{M}$ and $Q(s_{t},a_{t},s_{g})$]: update
$f_{\phi}(s_{t},s_{g})$ $\triangleright$ Train perception model

11: while $i\ \leq\ num\\_exploitation\\_steps$ do $\triangleright$
Exploitation

12: i) Using [$\mathcal{M}$]: sample a random goal $s_{g}\sim\mathcal{M}$

13: ii) Using [$f_{\phi}(s_{c},s_{g})$ and $\mathcal{R}(\tau)$]: generate
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$

14: iii) Using [any suitable method]: execute
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$

15: to obtain a real trajectory $\tau_{real}$

16: iv) Using [$\tau_{real}$]: update $\mathcal{M}$ $\triangleright$ Memory
optimization

How does the perception-action loop in PALMER work in detail: Alg.11 gives a
step-by-step description of the overall perception-action loop implemented in
PALMER. What PALMER does is essentially bridging any auxiliary exploration
method with any auxiliary exploitation method, by reorganizing exploration
experience in $\mathcal{M}$ into $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$
that can be used for exploitation. The particular way in which the
trajectories $\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ can be executed for
exploitation has a great deal of flexibility, for example: all actions in
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ can be executed sequentially in
an open-loop manner, the first actions of
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ generated at each timestep can be
executed in a model predictive control (MPC) manner, states in
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ can be tracked by an auxiliary
local feedback controller, or the entirety of
$\tau_{\mathcal{M}^{\text{*}}(s_{c},s_{g})}$ can be used to initialize a
separate trajectory optimization method.

### 3 Related Work

What is the main reason why memory-based reasoning over actually-observed
transitions is necessary? Why are methods like SPTM or SoRB that solely rely
on learning-based distance estimates are inherently prone to false
predictions: By definition, states that are far apart from each other in-terms
of physical reachability are rarely observed together in an experiential
learning framework (e.g., within the same RL episode, or within close by time-
steps during random exploration). Therefore, for any learning-based prediction
model that is conditioned on current-goal state pairs (e.g.,
$Q(s_{t},a,s_{g}),\ \pi_{inv}(a^{\prime}|s_{t},s_{g}),\
p_{t}(T^{\prime}|s_{t},s_{g})$), if it is trained solely on the observed
distribution of experiential data, far apart states will be out of
distribution (i.e., they have a low probability of being sampled from the
experiential data distribution, therefore they are underrepresented in the
replay buffer). This means that predictions for such far apart states will
inevitably be inaccurate, unless a hard-negative sampling mechanism is
implemented to explicitly push their reachability-estimates lower. The problem
with this is that there is no inherent signal solely contained in perceptual
input (e.g., images) that can guide the resampling process in a way that is
generally applicable to all tasks.

For example, [53] employs a hard-negative sampling mechanism for a
manipulation task using joint pose labels for guidance, but such a mechanism
has two bottlenecks: i) it is specific to their particular manipulation task,
ii) it assumes auxiliary labels. Similarly, the temporally consistent
localization mechanism used in SPTM is essentially a heuristic fix specific to
navigation. For the case of SoRB, there is no inherent mechanism in
distributional RL that addresses this out-of-distribution issue either. While
employing an ensemble of Q-functions could potentially capture the epistemic
uncertainty for out-of-distribution pairs to directly address this problem, we
used an ensemble of Q-functions in our implementation of SoRB and empirically
observed that it was insufficient. A similar conclusion can be drawn from the
Fig.8 of the original SoRB paper [12], as the bulk of the performance increase
appears to be due to distributional RL, and ensembles only provide a moderate
benefit.

All of these considerations highlight the importance of memory as a
robustification mechanism. To summarize the discussions from above, there are
two main reasons that cause false reachability predictions: i) there is no
robust and general signal solely contained in the isolated instances of
perceptual input $(s_{c},s_{g})$ (i.e., without the trajectory of states in
between that connect them) that can identify whether two states are physically
far apart, ii) both physically close and far apart states can occur with a
long temporal distance in between. Therefore, an agent needs to rely on
memory: in order to identify whether two states are close or not, it should
try to remember if it ever actually observed those two states close-by in a
segment of past experience.

What are the details for our implementations of SoRB and SPTM: Tha main
difference of our SPTM implementation is that it doesn’t employ temporally
consistent localization and adaptive waypoint selection. The main differences
of our SoRB implementation are: i) we use an ensemble of Q-functions, but they
are trained with DDQN rather than distributional RL, ii) we train the
Q-function on offlline random-walk data, rather than an online episodic
training setup with resets and a reward oracle as employed in the original
paper. We acknowledge and emphasize that for SoRB, these differences are the
most likely reason for the lower performance level we observed in our
evaluations compared to the original paper, as they inevitably reduce the
accuracy of Q-values. We however note that our method also employs the same
Q-values, and generally these implementation differences in the baselines were
chosen to facilitate a clear understanding of our approach without
confounders, because: i) they do not directly address the root cause of the
false prediction problem (as discussed above), ii) one of the main benefits of
our method is that it operates over arbitrary offline data without any resets
or reward oracles (and it uses DDQN to train the related Q-function).

### 4 Experiments

### Setup

Figure 12: Visualization of the map used in VizDoom experiments. Further video
visuals of image-based navigation can be found in the folder vizdoom_nav
provided in the supplementary alongside this document.

What are the details for the experimental setup in VizDoom: As shown in
Fig.12, states solely consist of four images $I_{North/East/South/West}$ that
form a panorama (i.e., $4\times 3\times 160\times 120$ dimensions), and
actions move the agent North/South/East/West by a fixed distance $\Delta$. The
geodesic distances scale approximately by a factor of $\times 3$ compared to
euclidian distances (e.g., If a goal has an euclidian distance of $14\Delta$,
it takes approximately $42$ timesteps for an optimal policy to reach it). The
map contains many long-thin column-like obstructions (e.g., torches, pillars,
trees), as we found that image-based navigation policies are prone to getting
stuck in such obstacles. These obstacles have dynamically changing appearances
(e.g., flickering flames on torches, glowing lights on pillars), and can
completely block the field of view of the agent after a collision (as shown in
$I_{East}$ in Fig.12). The replay buffer $\mathcal{M}$ consists of 300k images
obtained from a uniform random walk exploring the map in a single continuous
sequence of actions, without resets and rewards.

### Validating Perceptual Experience Retrieval (PER)

What is the exact evaluation process that produced Fig.4 in the main paper:
For every integer value $n\in[0,14]$, we randomly sample $1000$ pairs of start
and goal-states in a way that the euclidian distance between them lies within
$n\times\Delta$ and $(n+1)\times\Delta$ through rejection sampling, and a
policy is considered successful if it can get within $\Delta$ proximity of the
goal-state.

### Robust Distances

What is the exact evaluation process for the right panel of Fig.5 in the main
paper: To produce the roadmap visualizaitons, we randomly sample 250 states
from the replay buffer and set the edges between them by thresholding the
distance estimates from all methods. Thresholds were calibrated individually
and by hand for each baseline, by picking the threshold with the lowest number
of false edges until a further reduction in the threshold resulted in
splitting the roadmap into a large number of isolated subgraphs (i.e.,
therefore making it impossible to use it for global planning).

### Proposed Planning Algorithms

Why does the policy $\pi_{\mathcal{M}^{*}}$ use R-PRM for planning: PRM and
R-PRM are multi-query methods [25], meaning that the full roadmap only needs
to be constructed once. For any query pair of current-goal states
$(s_{c},s_{g})$, the same roadmap can be reutilized by inserting
$(s_{c},s_{g})$ in the roadmap and performing a shortest path query. In
contrast, RRT and RRT* require recreating a full roadmap for every new query
pair. Since $\pi_{\mathcal{M}^{*}}$ replans at each timestep with a different
current state $s_{t}$, PRM based approaches are computationally much cheaper.
We also note that planning graphs for all methods in this experiment contain
$500$ vertices.

What are the details for the $\pi_{mpc}$ baseline: The $\pi_{mpc}$ policy uses
the $p_{fwd}$ model to obtain simulated rollouts, and uses the $p_{t}$ model
to rank those rollouts in terms of how close they get to the goal. This allows
an MPC optimization loop that picks and implements the first action from the
most successful simulated rollout. As previously discussed above, the main
bottleneck for SPTM and SoRB is the difficulty of estimating reachability
metrics solely using the two states $s_{c},s_{g}$ without any consideration of
the states in between. Simulated rollouts in $\pi_{mpc}$ naturally address
this problem by generating and evaluating entire trajectories. The main
bottleneck for $\pi_{mpc}$ is that the accuracy of state predictions in
simulated rollouts from $p_{fwd}$ degrade with the rollout length.

### Experiments in Habitat

Figure 13: Visualization of the apartments used in Habitat experiments.
Further video visuals of image-based navigation can be found in the folders
habitat_roxbox_nav and habitat_annawan_nav provided in the supplementary
alongside this document.

What are the details for the experimental setup in Habitat: As shown in
Fig.13, states solely consist of a single 150 FOV image (i.e., $3\times
256\times 256$ dimensions). There are 3 actions:
$\\{turn\\_left\\_30\\_deg,turn\\_right\\_30\\_deg,move\\_forward\\_\Delta\\}$.
We run evaluations on two randomly picked apartments: Roxbox, and Annawan. In
both apartments, we collect a replay buffer $\mathcal{M}$ that consists of
150k images obtained from a uniform random walk exploring the map in a single
continuous sequence of actions, without resets and rewards. We use only the
memory buffer from Roxbox to train the perception model $f_{\phi}$, and use
this same model to do perceptual experience retrieval and trajectory stitching
on replay buffers from both apartments. We have observed that the latent
distances from $f_{\phi}$ generalize well, and can directly allow perceptual
experience retrieval and trajectory stitching without any fine-tuning on the
images from the new test apartment.

Why does the agent occasionally take random-looking actions in the habitat
navigation trials: This is due to a combination of two main factors. First,
our MPC loop replans from scratch at each timestep using Algorithm.6. This
frequent replanning has a destabilizing effect on the control loop, similar to
employing a large derivative action in a PID controller (i.e., a strong
anticipatory term causes frequent switches in the actions). This first factor
is exacerbated by the second main factor: the poor performance of $argmax_{a}\
Q(s_{t},a,s_{g})$. This is most likely due to the difficulty of offline RL
training with hindsight relabelling over random-walk data of only 150k
timesteps obtained with a much more challenging non-cartesian action space
$\\{turn\\_left\\_30\\_deg,turn\\_right\\_30\\_deg,move\\_forward\\_\Delta\\}$.
The restitched trajectories $\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,1})$
produced by R-PRM at each time-step are converted to actions by following
their first state $\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,1}$ using
$argmax_{a}\ Q(s_{t},a,\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,1})$, and
inaccurate Q-values occasionally cause random-looking actions.

There are multiple ways to counter this. The most direct way is to train a
better Q-function. Our current Q-function is trained in a particularly
challenging setting, as: i) it is trained on entirely offline data with
hindsight goal relabelling, ii) this data is collected through uniformly
random actions, and iii) it consists of only 150k environment steps. A second
way is to instead counter the large derivative action by reducing the
replanning rate and introducing a momentum mechanism to the controller. For
example, we can replan through R-PRM only every $n$’th timestep (i.e., hence
reducing the replanning rate), and act according to $argmax_{a}\
Q(s_{t},a,\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,n})$ for the timesteps
inbetween (i.e., hence introducing momentum to the controls). We couldn’t get
this fix to work well, because the Q-values are only accurate up to states
that are $\sim 2\times\Delta$ distance away (hence acting according to
$argmax_{a}\ Q(s_{t},a,\tau_{\mathcal{M}^{\text{*}}(s_{t},s_{g}),s,n})$ isn’t
possible for $n\geq 2$ in our case). We note however that our method can still
navigate from any point to any point in a challenging 3D reconstruction of a
real-world apartment in Habitat using poor Q-value estimates, highlighting the
robustness introduced by memory-based planning.

### 5 Discussion and Future Directions

How is PALMER related to the "Options Framework (Sutton et al.)" and "Skill-
Chaining (Konidaris et al.)": The idea of restitching (i.e., chaining)
transition sequences from a replay buffer has direct connections to the
options framework [55] and skill-chaining [56]. Essentially, PALMER can be
thought of as a framework for converting every possible sequence of
transitions $\tau\in\mathcal{M}$ in memory into an option
$o=\\{\pi_{o},I_{o},\beta_{o}\\}$, where the option policy $\pi_{o}$ is
implemented by simply executing all the actions in $\tau$ in an open-loop
manner, the initiation set is
$I_{o}=\\{s\in\mathcal{S}:d_{\phi}(s,\tau_{s,0})\leq d_{p})\\}$, and the
termination condition is
$\beta_{o}=\\{s\in\mathcal{S}:d_{\phi}(s,\tau_{s,-1})\leq d_{p})\\}$.
Therefore, PALMER can be interpreted as a skill-chaining algorithm that
converts unstructured transitions in a replay buffer into a set of executable
options to be chained.

How is PALMER related to "LQR-Trees (Tedrake et al.)": A central idea in
PALMER is repurposing the edge creation subroutines of sampling-based planning
algorithms so that whenever an edge is created some additional processing is
done to connect the endpoints (i.e., particularly, perceptual experience
retrieval in our case). This approach is directly inspired by the method of
LQR-Trees [57], which instead creates a trajectory stabilizing LQR controller
to connect the endpoints of each edge. This results in a roadmap of local
controllers, rather then a roadmap of memories as in PALMER.


* Szkody et al (2021) Szkody P, Olde Loohuis C, Koplitz B, van Roestel J, Dicenzo B, Ho AYQ, Hillenbrand LA, Bellm EC, Dekany R, Drake AJ, Duev DA, Graham MJ, Kasliwal MM, Mahabal AA, Masci FJ, Neill JD, Riddle R, Rusholme B, Sollerman J, Walters R (2021) Cataclysmic Variables in the Second Year of the Zwicky Transient Facility. AJ 162(3):94, DOI 10.3847/1538-3881/ac0efb, 2107.07051
  * Tapia (1977) Tapia S (1977) Discovery of a magnetic compact star in the AM Herculis / 3U 1809+50 system. ApJL 212:L125–L129, DOI 10.1086/182390
  * Taylor et al (1986) Taylor AR, Seaquist ER, Mattei JA (1986) A radio outburst and jet from the symbiotic star CH Cyg. Nature 319(6048):38–41, DOI 10.1038/319038a0
  * Tomov et al (1998) Tomov T, Munari U, Kolev D, Tomasella L, Rejkuba M (1998) Jets from the galactic supersoft X-ray source RX J0019.8+2156. A&A 333:L67–L69
  * Truemper (1982) Truemper J (1982) The ROSAT mission. Advances in Space Research 2(4):241–249, DOI 10.1016/0273-1177(82)90070-9
  * van Kerkwijk et al (2010) van Kerkwijk MH, Chang P, Justham S (2010) Sub-Chandrasekhar White Dwarf Mergers as the Progenitors of Type Ia Supernovae. ApJL 722(2):L157–L161, DOI 10.1088/2041-8205/722/2/L157, 1006.4391
  * Wagner et al (1998) Wagner RM, Thorstensen JR, Honeycutt RK, Howell SB, Kaitchuck RH, Kreidl TJ, Robertson JW, Sion EM, Starrfield SG (1998) A Photometric and Spectroscopic Study of the Cataclysmic Variable SX Leonis Minoris in Quiescence and Superoutburst. AJ 115(2):787–800, DOI 10.1086/300201
  * Warner (1995) Warner B (1995) The Discovery Of Magnetic Cataclysmic Variable Stars. In: Buckley DAH, Warner B (eds) Magnetic Cataclysmic Variables, Astronomical Society of the Pacific Conference Series, vol 85, p 3
  * Watson et al (1980) Watson MG, Mayo SK, King AR (1980) The optical light curve of the AM HER system 2A 0311-227. MNRAS 192:689–696, DOI 10.1093/mnras/192.4.689
  * Webb and Barret (2005) Webb NA, Barret D (2005) Faint X-ray sources in globular clusters in the XMM-Newton and Chandra era. In: Hameury JM, Lasota JP (eds) The Astrophysics of Cataclysmic Variables and Related Objects, Astronomical Society of the Pacific Conference Series, vol 330, p 41, astro-ph/0411506
  * Webb et al (1999) Webb NA, Naylor T, Ioannou Z, Worraker WJ, Stull J, Allan A, Fried R, James ND, Strange D (1999) A spatially resolved ‘inside-out’ outburst of IP Pegasi. MNRAS 310(2):407–413, DOI 10.1046/j.1365-8711.1999.03002.x, astro-ph/9907148
  * Webb et al (2006) Webb NA, Wheatley PJ, Barret D (2006) XMM-Newton X-ray and optical observations of the globular clusters M 55 and NGC 3201. A&A 445(1):155–165, DOI 10.1051/0004-6361:20053010, astro-ph/0509085
  * Webb et al (2018) Webb NA, Schwope A, Zolotukhin I, Lin D, Rosen SR (2018) Two new magnetic cataclysmic variables discovered in the 3XMM catalogue. A&A 615:A133, DOI 10.1051/0004-6361/201730974, 1804.07089
  * Weisskopf (1999) Weisskopf MC (1999) The Chandra X-Ray Observatory (CXO): An Overview. arXiv e-prints astro-ph/9912097, astro-ph/9912097
  * Wickramasinghe and Ferrario (2010) Wickramasinghe DT, Ferrario L (2010) New insights on the origin of magnetic fields in white dwarfs. In: Werner K, Rauch T (eds) American Institute of Physics Conference Series, American Institute of Physics Conference Series, vol 1273, pp 79–84, DOI 10.1063/1.3527894
  * Wickramasinghe and Wu (1994) Wickramasinghe DT, Wu K (1994) The Period Gap and the AM Herculis Type Systems. ApSS 211(1):61–70, DOI 10.1007/BF00658043
  * Wijnen et al (2015) Wijnen TPG, Zorotovic M, Schreiber MR (2015) White dwarf masses in cataclysmic variables. A&A 577:A143, DOI 10.1051/0004-6361/201323018, 1503.05197
  * Winkler et al (2003) Winkler C, Courvoisier TJL, Di Cocco G, Gehrels N, Giménez A, Grebenev S, Hermsen W, Mas-Hesse JM, Lebrun F, Lund N, Palumbo GGC, Paul J, Roques JP, Schnopper H, Schönfelder V, Sunyaev R, Teegarden B, Ubertini P, Vedrenne G, Dean AJ (2003) The INTEGRAL mission. A&A 411:L1–L6, DOI 10.1051/0004-6361:20031288
  * Wood et al (1989) Wood JH, Horne K, Berriman G, Wade RA (1989) Eclipse Studies of the Dwarf Nova OY Carinae in Quiescence. ApJ 341:974, DOI 10.1086/167557
  * Wood (1992) Wood MA (1992) Constraints on the age and evolution of the Galaxy from the white dwarf luminosity function. ApJ 386:539–561, DOI 10.1086/171038
  * Woosley and Heger (2015) Woosley SE, Heger A (2015) The Remarkable Deaths of 9-11 Solar Mass Stars. ApJ 810:34, DOI 10.1088/0004-637X/810/1/34, 1505.06712
  * Yaron et al (2005) Yaron O, Prialnik D, Shara MM, Kovetz A (2005) An Extended Grid of Nova Models. II. The Parameter Space of Nova Outbursts. ApJ 623(1):398–410, DOI 10.1086/428435, astro-ph/0503143
  * York et al (2000) York DG, Adelman J, Anderson J John E, SDSS Collaboration (2000) The Sloan Digital Sky Survey: Technical Summary. AJ 120(3):1579–1587, DOI 10.1086/301513, astro-ph/0006396
  * Zolotukhin et al (2017) Zolotukhin IY, Bachetti M, Sartore N, Chilingarian IV, Webb NA (2017) The Slowest Spinning X-Ray Pulsar in an Extragalactic Globular Cluster. ApJ 839(2):125, DOI 10.3847/1538-4357/aa689d, 1602.05191