PALMER: Perception - Action Loop with Memory for Long-Horizon Planning
Authors: Onur Beker
Mohammad Mohammadi
Amir Zamir
Venue: NeurIPS 2022 Accept (2022)
Keywords: representation learning
memory
planning
reinforcement learning
statistical contingencies

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.

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 priori unknown real-world scenarios, agents should be able to: act from nigh-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 can provide the nec- essary representations to address the others, by modeling statistical contingencies between observations. In this direction, we introduce general-purpose planning algorithm called PALMER that combines classical sampling sampling-based planning algo- rithms with learning- baaneng-based perceptual representations. For training these perceptual representations, we combine Q-learning with contrastive representation learning create latent space where the distance between the embeddings of two states captures how easily optimal policy can traverse between them. For planning with these perceptual representations, we re-purpose classical sampling-base algorithms 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 tight feedback loop between representation learning, memory, reinforcement learning, and sampling-based planning. The end result is experiential framework for long- hongzhorizon planning that is significantly more robust and sample efficient compared to existing methods.
planning
Introduction
Animals and humans operate on high-dimensional stimuli (e.g., vision) to achieve diverse and ever- changing goals necessary for their survival 2 3 Learning through trial-and-eme plays fundamental role in this (6, 7 S [0,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 targeted search strategy. Such mechanisms for recycling past successful behavior accelerate trial-and-error compared to uniformly sampling all possible actions. This is because the same behavior (i.e., sequence of actions) 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-worid environments.
significantly
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, greatly reduces the computational cost of trial-and-error by employing the principle of optimality [11. This principle can be colloquially stated treating new and complex problems recomposition of old and simpler sub-prote sub-problems that were already solved before. Recent work I2 [S] 14 employs this perspective to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Planning
start
goal
Start Goal Pair
Shortest Path
Restitching
Execution
Restitching
Shortest Path
Past Transitions Retrieved Replay-Buffi Buffer
Restitched Trajectory
Execution
Local Reachability
Representation Learning
Planning
Memory
Po
Memory
00% [g
(g(+)
f
Evaluation Improvement
Execution
Exploration
Memory
Mernory Lioaate
Treat
Figure Top: Given a start-goal image pair, PALMER plans a path between them by concatenating endpoints past trajectory segments retrieved from provided replay buffer. This enabled by state embedding function fo 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 the replay buffer. iv) executes these
Q-values for representation learning train fo. iii) uses fe to plan plans, v) evaluates resulting traeectories and inserts them back into the replay buffer to improve its contents.
build hierarchical reinforcement learning (RL) algorithms for goal-reaching tasks. Such methods 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 beamiin-basee local policy. Our paper builds upon this line of work.
Contribution: We describe long- horizon planning method that directly operates high dimensional sensory input observable by an agent on its own (c.g., images from an onboard camera). Our method combines classical sampling-basee based planning algorithms with learning-basee based perceptual representations, to retrieve and recompose previously observed sequences of state transitions in replay buffer. This is enabled by two-step process. First, we learn 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 coal-conditioned Q-values learned through offline hindsight relabelling 11 for contrastive representation learning. Second, we threshold this learned latent distance metric to define neighborhood criterion between states. We then define sampling-bass based planning algorithms that search over the replay buffer [12] to retrieve and stitch together trajectory segments (i.c., 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 depicted F. T. Our approach operates on offline unlabeled data, and can therefore be combined with any exploration method to populate the replay buffer. Our experiments implement image-batt based navigation policy in simulation, using an offline replay buffer populated with uniform random-walk exploration data.
2 Perception-Action Loop with Memory Retrieva!" T
Nomenclature: An enviromment is represented as tuple (S, A. Pewe). where S and A are the state and action spaces, and Peno (s ls|s,, a) the Markovian transition dynamics. A trajectory any sequence of states and actions. 7-1 denote the first, last, and i'th states in respectively. The length of trajectory in terms of timesteps denoted as len(7), and concatenation of two
T is
Most sub-sections have corresponding section in the supplementary for further elaboration.

---

lT
Line
I
T"
Pa(7" (g)
mo (a' (1.
Piel 2e. 92)
(g(S))8g)
Zeii
fa(s))
c 19())
Spor
Sp
Sg+1
Memory
Figure 2: An overview of the functions, inputs, and losses used in our method (see See 2.2 for details), We aim to train a perceptual encoder fo with two properties: i) representations of two states should be close if they were observed to be casily reachable from each other within low number of timesteps, ii) the representation of a state should capture minimal sufficient statistic to inform agent about the actions needed to reach nearby states.
trajectories denoted as Teat T1 o 72. We assume an additive reward function R. T where R(T) = (x.a)er a). We call a finite set of trajectories M = { replay buffer.
2.1 Perceptual Representations that Capture Local Reachability
key component of our framework is a perceptual encoder fs( : S Rd that maps states into a representation space where L2 distance (s. 5n)) == Il.f fsys)) 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 goal-conditioned reward function r8 G, (,41,1118)) 88) = - 11 øé, that returns -1 for all steps before reaching goal. This means goal- conditioned Q-values []6 17 for the optimal policy correspond to negative shortest-path distances (i.e., max, mar a, 5g) V 8y) -len(Tsp)) We can then define a symmetric distance metric between states as do (5: sn) := mar( -V(se> Sn)) -g). se) ). This in turn corresponds to the
two-way consistency criterion proposed in 13 What we want from fs(s) is for de (Sc, Sy) and
do (Sc: 8g) to roughly correlate.
2.2 Representation Learning via Reinforcement Learning
Any perceptual encoder fe whose latent representations satisfy the local reachability property defined in Sec 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-conditiond Q-values for contrastive representation learning.
We propose a model (depicted in 2 that includes the following standard components from (s),). projecting state into latent representation; ii) Pfwa(2/44 2(,a)). at).
the literature: modelling the transition distribution induced by (ene (s'|s, a) over the latent space 2 = fs(.), as discussed in [18 [9]: iii) Tanv (a( 24, =g), defining distribution of actions to reach goal state, : iv) Pt (T" 2t, 2g). modelling the distribution of timesteps necessary to reach goal state, as discussed in [20]: : v) Q(se, de, 8y), Q-value function that provides local reachability estimates between pairs of states, as discussed in 12 16].
as discussed in 18 19 14:
Following [6], we train (stt, aze, $g) over offline replay buffer M, using hindsight relabelling 15 [6] with a reward function r(*r, a, 8t-1, 8g) = - -I, 1,s. After training Q(+r, dr, 8,) in isolation, we freeze its parameters and use it to define a contrastive loss function 21] La as explained below. We then train the remaining components using the same replay buffer M. We randomly
sample transition (st. de, st+1) and time difference T, and set the goal state as sg St+T, in hindsight relabelling. We then minimize the following losses:
Lo(st,8)) = Inange (d,, 8g) dp) I ddo(er.sy)Ee (ninge
1 (200)
where bninge is the hinge loss [22]. This contrastive loss dictates that perceptual representations should be close together (i.e., (St, 8y) S dp holds) if and only two states are close to each other in terms of reachability (i.c., do sn) eq holds). dp and cq are hyperparameters.
3

---

Lr(T,TT), Linv at), and sudd( 21+1) are MSE and cross cassopy losses 19 20 Lr and Line dictate that perceptual representations should capture enough information know when and how an agent can reach from one state to another, while ffdd dictates that they should capture only minimal-suffiiiet statistic for doing so ([99) presents a more elaborate discussion).
2.3 Perceptual Experience Retrieval (PER)
Given a perceptual encoder fe that captures local reachability, we go over all states 8, E M in the replay buffer and compute their projections z; = [s(ss,, which are stored alongside the states themselves. We then employ z; 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 se and radius dp (i.c., the same one used in the contrastive loss LQ in Sec Sec 2.2). retrieving neighboring states amounts to computing the set Net, Na,(50, (s.) = {8n (8: 8n) S dp), which can be achieved by a straightforward 1.2 distance computation and thresholding. The number of neighbors Na, (sx) of a query state s, is an approximate measure of how many times the agent has visited around & which also makes a good visitation-coum that applicable to both discrete and continuous state spaces.
ti) Retrieving Neighboring Trajectories: Given a starting state se and a goal state sy, we can search the replay buffer for the highest reward trajectory segment T that starts from state To in Na, and ends in state T-1 in Na, (8y)- This corresponds to the following optimization problem:
TM(S = arg max R(T)) s.t. TO E (a, T-1 E NN,
TEM
To find TM(ssssy) we first select all state pairs (5), E (Na,(ss) x Na, (sg). We then take all sequences of transitions Tú = {st, ae 8141, St. $5-1. that start from 5;, end at sy, and are below a length threshold in terms of timesteps. We sort them based on R(Tx)), 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 (Se, 8y) (i.e., hence the length threshold on T.y). 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 hong-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 build a planning graph. We instead reimagine them as memory search mechanisms by altering their subroutines so that whenever an edge is created, trajectory is retrieved from the replay buffer through PER (eq 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 Se from the replay buffer M using any distribution (e.g., uniform, based risitation-county
2) Lines and Their Cost: The equivalent of drawing a line segment in our framework is retrieving
a trajectory T .M,) and its length and cost are (en(TM(s....) and -R(TM(s....) respectively.
3) Nearest State and Neighborhood Queries: Given a query point s;, these subroutines return the
closest point or a neighborhood of points within distance, among a set of vertices V {s,}. We preserve these definitions, and only replace the metric from cuclidean distance to len (TT(TM(s
Nearest(V. (V, sg) arg min (en((TM(s....))
s.EV
Near(V, (V r) = {sc E V [en(TM((....)) Sr)
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 7 has such an event, this reflects on R(T)).
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 Ts..s..s..) Algorithms T 2 describe R-PRM as an example, and the supplementary
contains descriptions for R-RRT, R-RKI*

---

Algorithm R-PRM (Roadmap Construction)
1: Input: M
2: V
C.cmppeerreeeyaa...oo........ E
Initialize vertices and edges
3: for each 9; E do
4: U U- J'<Nee (-Near(V,ss
{s.}
5: for each 8j U do
Place PER trajectories in edges
6: t {ss, 8j): Tedge TM(eniss); dedge = - - (TMM(en)))))
return G (V,
Algorithm R-PRM (Trajectory Restitching Given the Constructed Roadmap)
1: Input: Sc, Sg. G = EV, R(F)
2: for each 8, V do
Insert Se and 8, into the PRM graph D. Place PER trajectories in edges
3: if illn(TM(e..ee)) S then
4:
E+ E
[Sec 8:) Tedge = TM(s dedge = R(TM(s.)))))
5: if (f S then
6:
E EU (si, 8y) Tedge TM(sniggs dedge R(TM(e)))))
7: Tatitched t 1
8: } f ShortestPath(s,. 8g. G, C(T))
Trajectory stitching by dynamic programming b. Concatenate PER trajectories along the shortest path
9: for <i<<< { do
10:
Tstätehed t- Tatitched (M((s-11.s))
return (M) = Tstitched
We note two things about our proposed planning algorithms. First, they optimize any general reward function R. As the number of sampled vertices increases, RR(xM"(*e.ep) (*..sg) 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-bant bbased 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 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 state (c.g., enabling search and planning directly over images).
2.5 Refining Memory Contents via Forming and Executing Plans
We iteratively form and execute (s..s... and whenever execution successful, we insert the resulting new trajectories back into M. We note that these new trajectories are not exactly the same as TM..s).)))) because (M"(e..e.) contains approximate mismatches between the endpoints of its stitched trajectory segments due nearest neighbor retrieval. Forming and executing plans this way creates the following perception-action loop: M with refined contents used to train a more accurate Qs+,, a, 8g). ii) a more accurate Q(se, 8y) creates more accurate distance metric dg iii) a better do generates better (*.,...),)> iv) better (*.ss).),,) result in higher frequencies of successful execution to further refine M (see the supplementary for an algorithmic description).
3 Related work
Self-super goal reaching: Our approach is closely related to goal-reaching methods that combine learning-bass based iistance-regressee with graph search, particularly Semi- cami-paraettric Topological Memory (SPTM) [14] and Search on the Replay Buffer (SoRB) [12], which we compare to in our experiments. The key difference our approach that when setting the edges of the planning graph, it retrieves transitions that actually huppened rather than relying on learned distance regression. This brings two main benefits. First robustness. Local reachability estimates are susceptible to overestimation when evaluated between pairs of states that are far apart or unreachable. This
5

---

Local Metrics
Latent Distance
mixe C 5p)
Values
FIMO My S2
Time Predictions
Mppp 15,,5,] Mi 1 (os
Time Prediction Entrapy
Action Entropy
Goal Distance (n
Goal Distance in
Goal Distance (n x ?
Gool Distance In x to
Goal Distance (n
Latent Distance
Q-Values
Time Predictions
Time Prediction Entropy
Action Entropy
Global Metrics
Uied S..e 1 ::
200000 000006000
S02E250
0000000
Goal Distance X)
Goal Distance x
Goal Dissance Ik x 41
Goal Distance A]
Gool Distance
While all of these metrics are reasonably monotonie with physical reachability (i.c.. goal distance), only percoptual distances de do not saturate when evaluated locally (i.c., for close by goals). In addition, the ratio between the variance of dæ and the slope of its mean is much smaller compared to other sensible metrics (i.e., dø has a high signal-to-noise ratio). This means that perceptual distances can implement more accurate nearest-neighhor criterion for perceptual experience retrieval and trajectory stitching, compared to the other metrics.
Figure 3: A comparison between perceptual distances dø and other suitable metries from See 2.2
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 [2] [3]. To address this, [14] employs temporally consistent localization and adaptive waypoint selection, while [12] employs distributional Q-learning and ensemble of Q-functions. In our approach, eq 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 (T)(T) (used in nearest neighbor queries and threshold create edges) from the downstream task reward R(T) (used to set edge distances), unlike previous work.
Smage-Basedd 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 not limited to navigation.
Robot Motion Planning: A common approach to motion planning is to first run a sampling-base
planning algorithm [5), and then refine the result through trajectory optimization (30 32 to
satisfy constraints 33 34 35 An important bottleneck is that sampling- baased planning algorithms
require a precomputed map of the environment, and our approach extends such algorithms in a way that relaxes this requirement by replacing 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, purely geometric map cannot plan path through traversable field of tall-grass, while our approach can learn such affordances as long as they are represented in past experiences.
4
Experiments 2
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 North/East Saett//Eas///aae East//Suth///////// //oSth/Wee eest that form panorama (i.e., 4 x 3 x 160 x 1 120 dimensions), and actions move the agent North/South//ast/Wea by a fixed distance A. The maze contains many long-thin column- like obstructions (shown as dots in visualizations). Habitat experiments contain demonstrations on two large-scale scans of weal-world apartments: i) Roxboro, with a total area of 62 m2, and ii) Annawan, which has total-area of 75m2. States consist of a single 150 FOV image (i.e., 3 256 256 searn_leeft30_ddde
burn_turnitr right 1aggtt330____ 3_030dee,. move_forwar Maze2D is a continuous control task, where states consist of the 2D position and velocity of 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 le6 timesteps. Supplementary material contains further details.
dimensions). There are 3 actions:
A..
All experiments have a corresponding section in the supplementary providing further implementation details.

---

Local Policy
Global Policy
0.6
6.3
6
Success Ratio
Success Ratio
SPTM (local) SahB (local)
ScRB tolobali
SPTM (giobal)
0.4
Rur Olocal ours)
Rrer (globel)
(grobal- ours)
Goal Distance (n X 4)
Goal Distance (T. X 4)
Figure 4: Comparisons of our local policy TM and global policy TTM with SPTM and SoRB. T. performs well hecause it avoids getting stuck (as such events are filtered by eq while TMee performs well because it builds robust roadmaps without hallucinated shortcuts; therefore avoiding the main failure modes of the baselines.
dg s 1.0
de $.5
dg 2.5
dg S $1.0
dg S 1.5
de
Samples
NN Retrieval
(5,55)
Physical Distance 5d
Physical Distance 10A
DDL Distance
SoRB Distance
Figure 5: At the core of PALMER is a process called perceptual experience retrieval (PER). Given a query pair of current-gon -oal states, PER searches the replay buffer to retrieve the highest scoring trajectory (,) whose first and last states close to the query pair according to the perceptual distance dg. Left, Middle: Visualizations of T)(().)),) retrieved using PER and nearest neighbor states NN, (8+) retrieved using dg. Right: Setting edges of a roadmap using len (TM((M)s.ss))) )) compared with distance estimates used in SORB and DDL (20). We found that distance estimates from baselines are prone setting false edges that cross map boundaries.
4.1 Experiments in Vizdoom
Validating Perceptual Representations: Fig shows that (s Sg) obtained from our model captures a suitable notion of local reachability. Fig in turn shows that retrieving nearest neighbor states Na,(ss) from M using dø (i.e., NN retrieval) returns physically close states.
Validating Perceptual Experience Retrieval (PER): Fig 5 shows visualizations of trajectories re- trieved with PER. We implement retrieval policy TM that computes TM(e..e,) through eq T at each timestep and executes argmaza ((s,, a, TMii....) therefore forming model predictive control (MPC) loop. We evaluate TM in an image-based navigation task where start/goal images sampled randomly to have an euclidean distance
A in between, and a trial is considered successful if the agent can get within A proximity of the goal position within 4 x n time-steps. We use the local policies from SORB [12) and SPTM [14] 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. RM avoids this, since eq I
retrieves collision free TM(s..s))
Robust Distances: PER also helps avoid hallucinations in local distance regression. Fig illustrats this point by setting edges between sampled states by thresholding len (en(TM(s.,s,)). where methods of
20 are used as baselines. It can be seen that edges set by (en(TM(ss.s) ) are more robust.
Proposed Planning Algorithms: Fig shows visualizations of planning graphs and (M.((.....) pro- duced by R-PRM, R-RRT, and R-RRT* It can be seen that R-PRM doesn't it 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 TM" that replans at each timestep l using Algorithm 2 to return TM' (s..gg) and executes ar argmaza Q(3,, a, (s..)))).. We again
7

---

Graph
Shartest Path
Restitching
Graph
Shortest Path
Restitching
Graph
Shortest Path Restitching
lterations
Less
More Iterations
R-PRM
R-RRT
R-RRT*
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 TM 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*.
Q-Values
Retrieval Length
Local Policy
max, QG, G. 5g)
maku Ols dgl
rdtricual longth Bofice ecilnn
mas, Obt syl updatts
Success Rabo
S
apAnd
Ty lefte spdeter
Goal Distance x 5)
Goal Distance
A)
Goal Distance (rt A)
Figure 7: Memory Refinement: In PALMER, a policy has three groups of parameters: Q(2;, Qe. 8g), for and the contents of M. Iteratively forming plans through PER and executing them creates feedback loop between these components, where: i) actions inform perception during the training of fe. ii) perception fucilitates actions through the formation plans, and iii) memory serves as the medium for this reciprocal interaction. As result, trajectories produced by explicit planning are gradually internalized as implicit behavior encoded in the model parameters. This leads to: Q- Q-values propagating further into distant goals (Left), memory contents getting closer to optimal (Middle), and performances of local policies showing significant improvement (Right).
use SORB [12 and SPTM [14] as baselines Fig 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 shorteuts. A new baseline is Tmpe, which extends the SPTM local policy by using wd and from See 2.2 to implement an MPC loop with n-step look-ahead. Tmpe 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 Pfwd decreases with the number of timesteps.
Refining Memory Contents: We refine the contents of .M by iteratively generating and executing TM"((e..g)) (#c.sy) We then retrain all model components only on the resulting new data that is equal in size to the initial unrefined M. Fig 7 shows the results. When TMM and argmaz, Q (ax, 0, 8g) are used as policies, their success ratio increases significantly if they are trained on the optimized M. Q-value estimates trained on the optimized M also propagate better to goals further away. The scaling of [en(TM(e..s. )) with goal- changes from an exponential trend to an approximately linear one, due to the inclusion of transitions from successfully executed (s..s))) These results highlight that refining memory contents improves the quality of future plans.
4.2 Experiments in Habitat
As shown in Fig 8 we find that 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, turnrighht, go-forward), and state space (i.e., single 256 x 256 RGB images with 150 FOV). Perhaps more surprisingly, we find that training fo only on exploration data from a single apartment generalizes substantially well 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
For a comparison without confounders, we train SoRB with DDQN 42 rather than distributional Q Q-learning and we do not employ temporally consistent localization for SPTM, as such fixes are equally applicable to method and orthogonal to the discussion. The supplementary provides further elaboration.
45
8

---

Global Policy
Timestep Until Success
1.2
R-PRM (Habital Seen!
1.0
-O- R-PRM (Habitat Unseen)
Success Ratio
len(e)
-
R-PRM (Habitat
R-PRM (Habitat Unseen)
0
16
24
24
44
Goal Distance (n A)
Goal Distance
Samples
Graph
Retrieval
Retrieval
Shortest Path
Restitching
Navigation In Habitat
Unseen Apartments
Feneralizaation to
Execution
Restitching
Shortest
Planning
Figure 8: We evaluate our R-PRM based policy ии* 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: found that training the perception model on a single apartment generalizes sufficiently well to allow perceptual experience retrieval and trajectory stitching in any unseen apartment.
train the model components solely on data from Roxbox. We then use them implement our TM policy from See 4.1 which we then evaluate on both apartments. For n E {8, 16, 24, 32, 36, 44), we randomly sample I00 pairs of start and goal-states in way that the geodesic distance between them lies within A and (n 8) A through rejection sampling. A policy is considered successful if it can get within 2 x A proximity of the goal-state. We do not plot the SPTM and SORB baselines. because we found that the models (an=( navigation policies achieved almost zero percent success rate reaching local goals beyond 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 hindsight relabelling over random-wal walk data obtained with much more challenging non-cartesian action space [turn_left. ft_30 _dgg turn Sarr_right__00 20__33ddeep de__deg, move__ooruee
8g) and argmar, Q(s,, a, sg) that they use as local x A
difficulty of offline RI. training with
4.3 Experiments in Maze2D
SAC
SAC-off
BEAR
AWR
BCQ
COL
IQL
Diffuser
PALMER
maze22-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 Total rewards the Maze2D benchmark, which is continuous control task that requires long-horizon planning. R-PRM based 'TM 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 we find that the same πM policy from sections 4.1 and 4.2 achieves strong performance, and can solve mazes all three complexities.
Discussion and Future Directions
Iy PALMER less expressive than standard deep Q-learning: Two important premises of deep Q- learning 44 34 are: i) minimizing Bellman error through temporal-differene (TD) updates can restitch observed transitions in new optimal ways 41455 45), ii) neural network can learn extrapolate

---

Q-values to unobserved but close-by states in sigh-dimensional spaces (e.g. images) [46.. Both arguments are equally valid for our approach, since it can: i) restitch transitions at arbitrary resolu- tions (i.e., anywhere from one-step transitions to multi-step trajectories) by virtue of campling-based planning. ii) group together close-by states through dg- Therefore, PALMER an RI. algorithm that: i) optimizes Bellman enror through sampling-base bassdd optimal planning rather than gradient-based TD-updates [46], ii) performs extrapolation between states using a perceptual-backke backbbne fo rather than deep Q-network, and iii) replaces the greedy-policy argmaz, Qstt, a, 5g) and value estimate maz, Q(sr, a, $g)) with ar argmara Q(st 0, TM' (9.1)))).)) 1 and R(TM' (a).))) respectively. The key benefits of these alterations come into play when 8, and Sg are far apart, and these benefits are: i) the PER mechanism in eq eq that prevents hallucinations in Q(5t, a, sg). 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 algo- rithms (Sec2..4) experience replay methods 49 This alternative approach stitches together (Moi)))))) during training, and perform backwards TD-updates over this trajectory starting from 8g TM"(ss,, and ending at 8e TM' As suggested by Fig this can al- low value estimates (,),, propagate more globally. Our proof-of-coneppt experiments identify this as a promising direction, and we leave a further extensive evaluation to future work. Connections to contingency learning: Contingency learning refers the acquisition of knowledge of statistical correlations between pereepts [50] [[] Following this definition, PALMER can be interpreted as a contingency learning framework, as the latent distance metric de captures statisti- cally how likely two states are to be observed in close temporal proximity. The knowledge of these statistical contingencies between states then used for Long-horizon decision making through the proposed perceptual experience retrieval and planning mechanisms.
Conclusion and Limitations
We presented PALMER, a long-horizon planning method that combines learning- based perceptual representations with classical campling-basee planning algorithms. Given a goal state sg and reward function R. our method searches the contents of an offline replay-buffer A to stitch together a sequence of transitions (=""*)))))) = {si, d1, ...} that reaches $g while maximizing 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- nigh-dimenssonal 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 lc6-1c7 common in RL) obtained from an entirely uniform random-walk (i.e., which is significantly less structured compared on-policy rollouts), it allows image-based navigation between any two points in large-scale scans of real-worke apartments.
We believe that our memory- -ased planning perspective highlights number of interesting questions for future research. First, which transitions should be kept in the replay buffer M, and which ones should be discarded? M cannot be infinitely expanded after deployment, and it is critical to distill away redundancies between stored experiences. Second, when the environment undergoes 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- efffcinnff adaptation environmental changes. Third, how can we extend fø 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. Gibson, The ecological approach to visual perception: classic edition. 2014.
Psychology Press,
10

---

[3] J. K. O' O'regan and A. Noë, "A sensorimotor account of vision and visual consciousness, Behav- ioral and brain sciences, vol. 24, no. 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, Singh, D. Precup, and S. Sutton, "Reward is enough." Artificial Intelligence, vol. 299, p. 103535, 2021.
[6] E. L. Thordike, "Animal intelligence: An experimental study of the associative processes in animals." The Psychological Review: Monograph Supplements, vol. 2, no. 4, p. 1898.
[7]
"The law of effect," The American journnll 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, 330, 1956.
[9] R. J. Hermsttein, "On the law 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. I.
[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 perameera topological memory for naviga- tion," arXiv preprint 1rXiv:1803.000 00653, 2018.
[15] M. Andrychowicz. F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. To- bin, 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. 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 intuitive physics," Advances in neural information processing systems, vol. 29, 2016.
[19] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, -Curiesity-driven exploration by self- supervised prediction," in International conference on machine learning. PMLR, 2017, pp. 2778-2787.
[20] K. Hartikainen, X. Geng, Haarnoja, and S. Levine, "Dynamical distance learning for semi- supervised and unsupervised skill discovery." arXiv preprint arXiv:1907.08222. 2019.
[21] S. Chopra, R. Hadsell, and Y. LeCun, "Learning 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] Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.

---

[23] S. M. VaVal et al., Seapidly-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 Roboties 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, Eysenbach, N. Rhinehart, and 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 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 Roboties, 2022. [Online]. Available: http:///ndeeracuuutedm..cee.l
[34] P. Abbeel. Advanced Roboties, 2019. [Online]. Available: pabbeee//s2877fa1199
https//ppoole..ee..rokkllyyyy..
[35] H. Choset, K. M. Lynch, S. Hutchinson, G. A. Kantor, and W. Burgard, Principles of robot motion: theory, algorithms,, and implemenntations, 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- slam," IEEE Intelligent Transportation Systems Magazine, vol. 2, no. 4, pp. 31-43, 2010.
[39] M. Kempka, M. Wydmuch, G. Rune, J. Toczek, and W. Jaskowski, "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 artificial intelligence, vol. 30, no. 1, 2016.
[43] M. G. Bellemare, W. Dabney, and R. Munos, "A distributional perspective reinforcement learning." " in International Conference on Machine Learning. PMLR, 2017, pp. 449-458.
[44] S. Levine, Deep Reinforcement Learning, 2022. [Online]. Available: cdu//depprccurre//
12

---

[45] Y. Chebotar, K. Hausman, Y. Lu, T. Xiao, D. Kalashnikov, J. Varley, A. Irpan, B. Eysenbach, R. Julian, C. Finn al., "Actionable models: Unsupervised offline reinforcement learning of robotic skills," arXiv preprint arXiv:2104.077455 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-leve control through deep rein- forcement 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 artificial intelligence, 2018.
[48] T. Haarnoja, A. Zhou, Hartikainen, G. Tucker, S. Ha, Tan, V. Kumar, H. Zhu, Gupta, P. Abbeel et al., "Soft actor-critic algorithms and applicationss arXiv preprint arXiv:/812.05900 2018.
[49] Schaul, J. Quan, I. Antonoglou, and Silver, "Prioritized experience replay." arXiv preprint arXiv:1511.05952, 2015.
[50] B. F. Skinner, Contingencies of reinforcement: A theoretical analysis. 2014, vol. 3.
BF Skinner Foundation,
[51] A. Noë, A. Noë el al., Action in perception, 2004.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "l-skFfiVjGr", "reviewer": "Reviewer_Bn9U", "summary": "This paper proposes a method similar to anytime-sampling methods in planning (e.g. RRT*) but in the RL context, to stitch together trajectories from an experience buffer to solve goal reaching tasks. \n\nThe core idea is to learn representations using general neural function approximators by leveraging the idea that the functional distance between two interactions should be small if they can be achieved through similar actions and attain similar reward/cost values. This is formalized using state value function and L2 function over learn feature embeddings. \n\nThe representation is learn by fitting several sub-modules including an encoder, a trandition dynamics model, action proposal network and a function to retrieve a distribution over timesteps necessary to achieve an interaction. Effectively this gives rise to a policy improvement algorithm that follows a virtuous loop of improve the system to achieve goal by iterating over: 1) learn an accurate Q function, 2) Use this Q function learn better function appx, 3) Use this to better estimate expected reward given start and goal query, 4) this is turns lead to better exploration, repeat. This is the core algorithm and there are parallels drawn to RRT* algorithms which behave in similar ways but by using hand-crafted sub-functions. This reformulation of planning algorithms as a memory retrieval mechanism is interesting and is the core conceptual contribution of this paper. This is then validated on navigation tasks in VizDoom and Habitat. ", "questions": "-  It looks like the state action value function has not been trained in the Habitat environment fully correctly. There are a lot of glitches that happen in the policy rollout. Why is this? \n\n- \"We say two states approximately overlap if dϕ(st, sg) ≤ dp holds, where dp is a hyper-parameter\". How is the hyper param selected? It seems like this would greatly depend on the topology of the environment. The variable would be vastly different for navigation, manipulation or gaming tasks. This also makes me wonder if the algorithm easily generalizes to environments beyond navigation tasks. In principle it should but the exploration and this assumption can make it highly trivial to get good empirical results. Have the authors ran experiments on other tasks like the Mujoco continuous control suite or Atari? Even experiments in these synthetic domains would prove out the empirical generality of this framework and make it a very strong paper. \n\n- Section 2.3 is not clear at all. How is the search done?  \"Given any interaction proposal (sc, sg) as a query, we use the components from Sec.2.2 to retrieve the highest scoring trajectory from M whose first-last states overlap with the query pair according to our approximate-overlap criterion from Sec.2.1.\". More details would be good. \n\n- If the environment is dynamic, how would this approach still work?", "limitations": "- RRT* style of algorithms come with anytime sampling convergence guarantees. What does and dosen't hold in this setting? \n\n- Are there any situations under which the bellman optimality is broken under this policy improvement scheme?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nIn long horizon tasks like navigation under sparse rewards, exploration and policy improvement is challenging. Assuming that the agent explores the state space well enough, the experience stitching approach proposed in this paper is a principled solution to tackle this problem in case of non-linear function approximation based RL and planning. \n\nThe key empirical result is shown in Figure 4 where the success ratio degrades more gracefully than baselines in the long horizon planning setting.\n\nWeakness:\n\nThis method assumes that the exploration problem is \"solved\". One of the advantages of RRT* like algorithms is that they quickly explore large unstructured spaces. However, a trajectory stitching based approach will only work well assuming the space is well explored. Please discuss limitations. \n\nThe paper would also be much more powerful and the parallels to RRT* like algorithms much more grounded if larger environments were considered. I suspect some form of intrinsic motivation or curiosity would be needed to solve this but it is important to know where the current proposed method breaks (e.g. what maze or level complexity would this break on compared to RRT*, assuming knowledge of state space?).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JywFUVs3OP9", "reviewer": "Reviewer_BFRQ", "summary": "In this work, the authors introduce PALMER that combines reinforcement learning and classical planning (particularly sampling-based methods) to achieve robust navigation in visual domains. PALMER maintains a memory buffer. During rollout, given a state-goal pair, the lowest cost trajectory on the graph (w.r.t state-goal query) is found by solving an optimization problem minimizing a similarity metric based on perceptual representations (processed referred to as perceptual memory retrieval, or PMR). A probabilistic roadmap is incrementally constructed with transitions added to the buffer. This is done by following the classical sampling-based motion planning routines but replacing the Euclidean distance metric with one that's based on PMR. Doing so allows for effective use of the memory buffer as a trajectory bank for high-level guidance of long horizon navigation tasks. Simulation results show that PALMER is able to effectively generate goal-reaching trajectories from visual input and exhibit decent generalization capability in the VizDoom and Habitat environments", "questions": "1. The claims in the paper are that PALMER is more robust to false predictions and it learns abstractions that can extend from goal-reaching to general RL problems. However, it is not clear how these two claims are supported by the experiment results. In order to support these two claims, the authors need to show (a) how the number of false predictions correlate to the task success rate in PALMER and comparison methods and (b) how PALMER performs on tasks more complex than visual navigation. \n\n2. The idea of restitching transitions in the memory buffer is relevant to offline RL (A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems ), can the authors comment on the similarities and differences?\n\n3. Out of all the components in PALMER, which is the most time consuming and how does it scale with the dimension of its inputs?\n\n4. The effectiveness of PMR and the constructed roadmap depends on coverage of the transitions in the memory buffer over the task space. Will this hinder exploration at the start of training when the coverage is low?", "limitations": "requiring a graph-based roadmap inherits some of its limitations, including the inefficiency caused by high dimensional state space and closely situated obstacles a cluttered environment. And it's not clear to me how a sampling-based planner can be extended to non-navigation RL tasks with arbitrary reward.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper is well written, and the visualizations are very helpful in explaining the core ideas. \n2. I appreciate the detailed explanations of the key concepts provided in the paper and appendices, again incredibly helpful for understanding the paper.  \n\nWeaknesses\n1. lacks comparison with other planning and RL methods in visual navigation\n2. evaluation in support of the claims would strengthen the paper", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JLacy3LsBP3", "reviewer": "Reviewer_PChv", "summary": "This paper presents a planning method called PALMER that creates a feedback loop between reinforcement learning, representation learning, sampling-based motion planning and a non-parametric memory. The method tackles a specific variant of a planning problem where observations from a prior exploration of the environment are available and the goal is to find optimal paths between any two states in the  same environment. The authors conduct experiments in the ViZDoom and Habitat environments which show some improvements over prior methods.", "questions": "See questions in weaknesses above.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The method is well motivated. The idea of using sampling-based motion planning for this task makes sense. The use neural networks for learning the graph structure required for motion planning from pixel-based observations is clever.\n- The results on ViZDoom environment show a significant performance improvement especially for distant goals. \n\nWeaknesses:\n- The scope of the method is low in my opinion as the method requires access to an exploration of the environment. \n- Since the authors are tackling embodied tasks, there are alternative methods which build a map of the environment and use differentiable planning, for example Gated Path Planning Networks (Lee et al. ICML 2018), Path Planning using Neural A* Search (Yonetani et al. ICML 2021), Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees (Chen et al. ICLR 2020). It is difficult to understand the significance of the proposed approach as compared to this line of work as it is missing in the paper both in related work and as baselines.\n- The results on Habitat environment are only qualitative and are not compared against baselines. More comprehensive experiments in realistic environments would make the submission stronger.\n- The writing clarity can be improved significantly. \n  - Many important experimental details are missing which makes it difficult to assess the significance of the results. It is unclear how the exploration trajectories are obtained in different environments. How many trajectories do you use per environment? How are the trajectories sample, is it a random policy, a trained policy or human trajectories? How are the target images sampled? Are target images always observed in exploration trajectories or can they be novel images?\n  - The text contains several terms which are not clearly defined. For example, what do you mean by \"approximate-overlap criteria (L37, L50), what are \"actually observed transitions\" in L48? Which transitions are observed but not actually observed? The text also contains very long sentences which are difficult to follow (for example L39-42, L42-45). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HrHc_bORTYG", "reviewer": "Reviewer_t3oP", "summary": "This paper’s main contribution is a method for stitching observed trajectories together to create a graph of the state space on which classical planning can be done to reach a given goal from a given starting point. This method then forms the core of an iterative system that can collect experience given such a graph and then improve the graph (and other learned components) given the new experience. Experiments in VizDoom validate some of the underlying assumptions and choices of the method and demonstrate its benefits over existing work.", "questions": "1. How does the proposed method fare as a function of dataset/memory-buffer size? Does performance fall off more quickly or slowly than other methods as the memory buffer shrinks?\n2. How strong and how necessary is the assumption of additive reward over trajectories?\n3. If I understand correctly, d_\\phi[(sc1, sg1), (sc2, sg2)] (from line 74) computes the L2 over concatenated feature vectors, which requires computing a square root over the sum of squared entries. Wouldn’t it be better to compute separate L2 distances over sc1,sc2 and sg1,sg2 respectively and then add those values?\n4. Further, the bold text in lines 76-78 says that d_\\phi cares about similar actions and costs but d_Q appears to measure the max cost of moving in either direction from sc1<->sc2 or from sg1<->sg2, which says nothing about the actions and costs of the trajectories from sc1->sg1 and sc2->sg2. So, this bolded text seems wrong?\n5. How well do SoRB and your method do when using the improvements mentioned in footnote 3? Since it’s possible those improvements would eat into some of the benefits from your method.\n6. Please define what an “update” is in figure 7.\n7. How well does your method perform in more stochastic domains? I don’t see anything in the method to deal with noisy transitions.\n", "limitations": "Yes, the authors have done a sufficient job addressing limitations and potential negative societal impacts of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** The presented work is a natural extension of existing ideas in the literature of goal-conditioned planning but is comprehensive and clearly adds novelty to the existing literature by introducing an alternative state embedding function, supporting arbitrary rewards, and enabling the use of classic planning algorithms on in-memory observations.\n\n**Quality and clarity:** The presentation is of high quality, well-written, and clear, albeit quite dense. My main complaint in this regard is that the authors seem to be quite constrained by the page limit, and this is impacting the readability of parts of the text and definitely of the figure captions. I’d encourage moving an additional paragraph from somewhere into the supplement and clarifying the figure captions (e.g., Fig 3 needs the supplement to be understood at all, which should not be the case).\n\n**Significance:** The contribution appears significant and the evaluation is reasonable but a bit limited in scope (mainly focused on ViZDoom) so it’s unclear what the longer term significance of this work will be.\n\nOverall, the paper is well-written and fairly enjoyable to read (aside from the density and need to refer to the supplement to understand certain sections and figures). The exposition, explanations, and clear connections to existing work are much appreciated. This is a large and somewhat complicated method and I felt each component was explained and justified and connected to the other components. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept