Latent Planning via Expansive Tree Search
Authors: Robert Gieselmann
Florian T. Pokorny
Venue: NeurIPS 2022 Accept (2022)

Abstract: Planning enables autonomous agents to solve complex decision-making problems by evaluating predictions of the future. However, classical planning algorithms often become infeasible in real-world settings where state spaces are high-dimensional and transition dynamics unknown. The idea behind latent planning is to simplify the decision-making task by mapping it to a lower-dimensional embedding space. Common latent planning strategies are based on trajectory optimization techniques such as shooting or collocation, which are prone to failure in long-horizon and highly non-convex settings. In this work, we study long-horizon goal-reaching scenarios from visual inputs and formulate latent planning as an explorative tree search. Inspired by classical sampling-based motion planning algorithms, we design a method which iteratively grows and optimizes a tree representation of visited areas of the latent space. To encourage fast exploration, the sampling of new states is biased towards sparsely represented regions within the estimated data support. Our method, called Expansive Latent Space Trees (ELAST), relies on self-supervised training via contrastive learning to obtain (a) a latent state representation and (b) a latent transition density model. We embed ELAST into a model-predictive control scheme and demonstrate significant performance improvements compared to existing baselines given challenging visual control tasks in simulation, including the navigation for a deformable object.

Latent Planning via Expansive Tree Search
Robert Gieselmann
Florian T. Pokorny
KTH Royal Institute Technology
KTH Royal Institute of Technology Stockholm, Sweden fpokorny@kth.se
Stockholm, Sweden robgie@kth.co
Abstract
Planning enables autonomous agents to solve complex decision-making prob- lems by evaluating predictions of the future. However, classical planning al- gorithms often become infeasible in real-world settings where state spaces are high-dimensional and transition dynamics unknown. The idea behind latent plan- ning to simplify the decision maaiin task by mapping it to -iweendieniiinal emhedding space. Common latent planning strategies mization techniques such as shooting or collocation, which are prone to failure long-horizon and highly non-convex settings. In this work, we study hong-horizon goal-reaching scenarios from visual inputs and formulate latent planming as an explorative tree search. Inspired by classical sampling-based motion planning algorithms, we design a method which iteratively grows and optimizes a tree rep- resentation of visited areas of the latent space. To encourage fast exploration, the sampling of new states is biased towards sparsely represented regions within the es- timated data support. Our method, called Expansive Latent Space Trees (ELAST), relies on self-supervised training via contrastive learning to obtain (a) latent state representation and (b) a latent transition density model. We embed ELAST into model-predice control scheme and demonstrate significant performance improvements compared to existing baselines given challenging visual control tasks in simulation, including the navigation for deformable object.
based trajectory opti-
Introduction
To perform challenging control tasks real-world environ- ments, intelligent agents must reason across many temporal steps, often relying on high-dimensional sensor data such as im- ages. Over the past decade, machine learning has significantly improved the state-of tet--heean art in image-based robotics and per- ception 34
Zatart
15] However, existing methods often limited to problems with relatively short time horizons and fail when the target is far in the future. Reinforcement learning (RL), for example, is prone to failure in such scenarios due sparse reward feedback and the resulting complexity of credit assignment (37 [6]. Classical planning algorithms 330, on the other hand, excel solving temporally-extended decision problems, but typically require compact representa- tions, state distance metrics and perfect knowledge transition dynamics.
36
17
Zgoal
Figure 1: Sampling- based latent ploration with ELAST. A tree (blue) iteratively grown optimized while being bound to the estimated latent sup- port region (gray).
Recent work proposes mixture of planning and deep learning methods to enable planning from complex visual observations. divided into planning (a) directly in the observation space
Current approaches can be broadly and (b) in learned latent
44
35
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The first variant usually relies on generative modeling of video sequences to synthesize feasible image paths. The inherently high computational cost of training and deploying such generative models, as well as the burden to make visually accurate predictions, present key limitations of this type of method. Latent planning, on the other hand, maps the control problem to lower-dimensional embedding space in order to reduce the complexity of the search space and facilitate the approximation of the dynamics. Moreover, this bypasses the computational bottleneck of synthesizing high-dimensional observations allowing fast computation of paths even in long-horizon settings.
spaces 14 43
A large number of existing latent planning strategies are based on trajectory optimization tools that originated in the optimal control literature [25]. In particular, gradient-free shooting- -baned strategies
such as the Cross-Entroon
Method (CEM) B or Predi-Pree Path Integral control (MPPI)
557 attracted much attention due to various applications in model-based RI. [14 [39 . Numerical
trajectory optimization through direct collocation (25] was recently used in 43 for planning over
latent spaces. Despite their recent popularity, the aforementioned techniques are known to suffer
from local minima when the optimization landscape is highly non-convex [51 which makes them less suitable for planning in geometrically complex spaces.
In this work, we pursue the intriguing idea of planning in latent spaces and focus on improving existing techniques by formulating planning as a search within the continuous latent state space. We present Expansive LAtent Space Trees (ELAST) which solves high-dimensions an explorative search within the latent data support. Our method differs from existing approaches in that it grows and optimizes a tree representation of previously visited areas, which can be leveraged to improve the efficiency of the exploration. This concept is largely inspired by ungle-query sampling- based planners [30 in the field of robot motion planning, in particular the asymptotically optimal Random Trees (RRT) [31 [31244] and Expansive Space Trees (EST) [18].
goal-reaching tasks through
version of Rapidly-exploriin Motion planners are typically used for navigating robots through geometrically complex environments, analogously our motivation is to introduce similar concepts in latent spaces. should be noted that direct application of these methods to our setting is not possible because state metries, sampling distribution, collision checks and other important quantities are difficult to define for learned embeddings. To overcome these challenges, we self-superrvsed contrastive learning to obtain state representation which locally preserves certain geometric properties that favor planning, and in a second step approximate latent dynamics and state connectivity models from random interaction data. We demonstrate that our learned embedding allows us to effectively use noise-contrastive estimation (NCE) 12 [3
for the approximation of conditional transition densities.
Our main contribution is the presentation of ELAST, a new latent planning algorithm for long-horizon goal-reaching. In the scope of this work, we focus on visual input data represented by sequences of image observations. To the best of our knowledge, we are the first to present explorative tree search in latent spaces without the need of expert data privileged information about the environment. Unlike static map-based approaches [44) [8] [10], our planner is compatible with parameterized settings, e.g. environments which are conditioned on the position of obstacles. Our evaluation on challenging visual control tasks in simulation shows significant performance improvements in downstream task success rate and path quality compared to existing baseline solutions.
2 Related Work
Planning in Images Spaces
A large body of prior works learn video dynamics solve visual
planning tasks g 7777
40 53). Visual Foresight [7], for example, generates predictions of future frames to optimize next-step actions through shooting-based optimization. [53] extends this idea with offline Q-lcarning to obtain improved cost-to-go metrics in long- horizon settings. [40] uses a hierarchical architecture to produce subgoal images for temporally-exteee
59
navigation tasks. The approaches in 8 19 29 learn a distance metric using value-basee reinforcement learning to construct a graphical representation of the observation space. Paths are then generated by solving the shortest path problem on the graph. In similar fashion, 44 uses self-supervised training of a connectivity classifier to construct map of neighboring image states.
(35 builds upon this idea but uses an energy-based model to approximate the traversability between states. The methods presented in 27 (55 use map-free approach which plans visual paths by predicting intermediate frames using generative adversarial network [.]. In this work, we take a fundamentally different approach to

---

visual planning by instead solving the decision- maniin task in a learned embedding space, thereby bypassing the need for computationally demanding generative video models.
Latent Planning and Control The idea of latent planning and control is to use compact repre-
sentations which simplify decision-makinn and dynamics learning. [56] train linear dynamics
model to achieve locally-linear control from images in learned embedding. 33 48 42] investigate
contrastive-predietic coding to learn useful representations for control. [14] uses a reconstruction-
based visual embedding and plans actions using shooting-based trajectory optimization via the
Cross-Entropy Method (CEM) 3] Similary, (39] uses Prreic-Preeictive Path Integral Control
(MPPI) [57 with learned dynamics models for dexterous robot manipulation tasks. 43] recently introduced vollocation-basee trajectory optimization [25] to moddll-based reinforcement learning in latent spaces. The methods in [50] 61 approach visual control tasks via gradient- based planning in a learned embedding space. 41 plans sequences of coarse subgoals by solving the shortest- path problem through direct optimization
the latent manifold. 22 implement an RRT-like [30] sampling-basd baaiigg planner within a learned embedding. The presented method is suitable for robot mo- tion planning from image inputs and relies on the existence of state samplers and collision checking mechanisms. Similarly, (23] presents a task-conditioned sampling-basee -bannd motion planner for efficient exploration in latent spaces but requires access to predefined task space. The line of work in 45 46) combines model-based RL with Monte Carlo Tree Search (MCTS) (5) to improve the capabilities in long-howe oong-horizon decision- making tasks such as playing Atari games from video input. While limited to discrete action spaces, [20] recently extended this idea to continuous action spaces introducing a sampling-basee policy iteration framework.
Similar to the works in [2 and (23], our method is highly inspired by classical sampling-bai based robot motion planners. However, in contrast, do not require expert data, collision oracles, or other privileged information about the environment. ELAST is a single-query approach, meaning that it generates new search tree for each planning query. Unlike map- or graph-based approaches R 19 29 (44, this provides more flexibility by allowing planning beyond static environments, e.g., parameterizing on obstacle configurations Compared to sampling-
approaches such as CEM, MPPI or continuous MCTS, we exploit the properties of our state embedding for keeping track of already visited areas, thereby encouraging fast exploration.
3 Preliminaries
Sampling-based Motion Planning In the motion planning literature, the configuration space is defined as the space of all possible robot configurations, i.c., the specifications that accurately describe the state of a robot system [30]. hampling-based motion planners solve continuous robot motion planning tasks by performing a search that probes the configuration space through sampling 30]. A prominent representative of sampling- based algorithms are Rapidly-exploring Random Trees (RRT) (31) It grows a search tree by iteratively adding new samples drawn from the configuration space. At each step. new state is connected to its nearest neighbor in the tree if the corresponding transition is valid. Instead of sampling directly from the state space, Expansive Space Trees (EST) 18 build search tree by systematically expanding nodes in sparsely represented regions of the configuration space. The work in 24 presents an adaptation of sampling-hase
methods such as RRT which produce asymptotically optimal paths with respect to the number of planner iterations. Classical motion planners operate on well-described configuration spaces, e.g. robot joint space, and assume access collision detection and state samplers. In this work, we bridge the gap between sampling-based motion planning and learning control from visual input.
Estimation Density estimation ubiquitous task in machine learning and statistics. Unnormalized density models, often known as energy-based models, offer flexible pa- rameterizations for instance using expressive neural network architectures. A recent introduction to energy-based model optimization is given in [49] Noise-contrastin estimation (NCE) [12 13] is widely-used training method for energy- based models due to its balance between statistical efficiency and computation. NCE trains a density model by distinguishing between points x from the original data distribution pa and samples drawn from an auxiliary noise distribution pa. The corresponding maximum likelihood objective, shown in Eq. 2 resembles nonlinear logistic regression. NCE simultaneously estimates an unnormalized model Ph and normalization constant b which allows to retrieve normalized density estimates Pm where in pm p (u) + b. Note that E is in practice
3

---

computed as an empirical mean from the training data.
m(u) + =+xe(((-G(u)
with G(u) = Pm - In pm)
(1)
INCE
E pr-pa
[I][m[)]]] +v
[In[1 m(vi]
(2)
y~Pp
To ensure good approximation results, it crucial that the support of Pr contains Pa without deviating too much from it. Moreover, Ps. should be computationally efficient to evaluate for any input. A central problem in NCE is therefore find proper choice for Pn. with respect the unknown data distributions Pa- For detailed derivations, we refer to 12 13
Contrastive Predictive Representations Contrastive representation learning compares among data samples to learn embeddings which map similar data samples close together and dissimilar ones far apart [32]. Contrastive Predictive Coding (CPC) [54] uses this principle to learn latent representations Z for sequential data X. The InfoNCE objective (Eq. 3) derived which attempts to maximally preserve the mutual information between the k-step future observations Z and context representations Yr which pool prior information Zge in the latent space Z. Inspired by NCE, identifies correlated pairs drawn from p(r++* + (Bt)) among uncorrelated ones, given a user-defined similarity f( }+). [54] use ( M1) exp(2 W&3e) which computes similarity by taking the dot product between the latent encodings 2 and their corresponding future linear predictions W yr.
f(ot+k. Vi)
LInFANCE
E X
log
CPC was shown to learn smooth representations useful for control in various different settings 48 33
58 35 We utilize an adaptation of (Sec. 4.1 to recover embeddings that are compatible
with our planning algorithm.
Expansive Latent Space Trees
We study goal-conditioned reaching tasks from visual inputs modeled using Markov Decision Processes (MDPs). The state space S is composed of image sequences = XCxWWX where N denotes the number of frames, the number of channels, W the width and H the height of single frames. Moreover, we define the continuous action space A Rdd and the set of goal states G = S. In addition to single environments, we also consider families of environments conditioned on raw context observations e E C (e.g. images) capturing task-relevant information, e.g. the position of obstacles. Instead of learning a controller directly from images, instead seek a method which solves goal-reaching tasks in a wwwer-dimensoons latent state space Z Rd In this regard, we assume no access to the underlying MDP dynamies, state distance metrics and only provide fixed-size training dataset composed of random environment interactions.
This section presents ELAST, a method for solving the described type of control problems through explorative tree search and local control within 2. A schematic overview of our approach is presented Fig. 2 It consists of state encoder & (Sec. 4.11p p transition density model & (Sec. (4.2) forward dynamics model hy (Sec. 4.3) and a local policy (Sec. 4.4), each modelled using feed- forward neural networks. During execution time, á encodes the current and goal states Sstarts Sgoal S into the latent vectors Estart, Zgoal E Z (Fig. 2 For context-conditioned tasks, we additionally feed a vontert-vector into the network. The planning module (Fig. 2 then builds a search tree within Z that finds a sequence of latent states connecting Astart to Žgoal- To improve the quality of solutions in terms of temporal path length, the search tree is optimized during planning. This is done by rewiring the tree after every expansion using the transition density estimator (Fig. (b). The planner then passes the computed discrete n-step solution path to the MPC controller module (Fig. (bb which queues the corresponding intermediate states to be achieved by
4.1 Geometric Properties of the Encoder
We define an encoder Φ x C-2 which maps states & conditioned on contexts e into latent space Z dd with dz < NXCxWxH. For brevity, we for now focus environments

---

(a) latent encoder + forward dynamics inverse dynamics (local policy)
transition density estimation
strategy
contect image
cantea!
image
Sutrr
Sgw
queue sequence of latent weypoints
Zaan
act using policy
plan
S
St
replan every steps
reached
(d) Sampling-based planning space
Start
Syeal
Zalart
encode and
repeat: expand and
backtrace obtain path
Figure 2: Overview of the different modules of ELAST. (a) training of latent encoder, dynamics and policy, (b) noise-contrastive estimation of transition densities o( [zs c). moxel-predicctive control framework, (d) planning via explorative tree search 2.
without task-specifir context, hence é S-ZZ. As further described in Sec. 4.3 performs nearest-neighhor lookups to sample new nodes and rewire the tree. To enable simple and efficient neighborhood computations, desirable property of é is the preservation of the proximity of temporally subsequent states within Z. This can be achieved by using a global state distance metric to enforce strict correspondence of distances during training. However, it typically requires privileged knowledge of the underlying MDP dynamics to define such a metric and is therefore not possible in setting. Moreover, distances cannot be inferred directly from our training data which was collected by a sub-optimal policy. Instead, we rely on the knowledge of continuity between observations enforee proximity of temporally adjacent states, More specifically, we employ contrastive learning via CPC (Sec. 3 and consider positive pairs (2t+k. Z(++k) where ž4+& denotes the predicted future latent state given the current state 2 and sequence actions attt+k-1 To obtain ž+t we simultaneously train an auto-regressive dynamics model h, x 1x.A-x 4 A similarity based
planner
on the squared Euclidean distance is used, hence f(1++4 s:)
| - A The encoder loss Cg is depicted in Eq. In accordance with the observations in [48] 33 (88 we add MSE loss on the predictions of h (weighted by Ks)) encourage hy be consistent with the latent dynamics.
81) log f(s,
C.
Kn. > (2111+) -
Optimizing á with Eq. we intend to achieve locality of correlated states while shaping dynamics that are predictable by model hy. For context-conditionel tasks, we additionally feed c into the dynamics model, i.e. hy AxAxC and optimize & considering the empirical expectation the loss in Eq. w.r.t. C (full objective in App. A.I.
4.2 Conditional Transition Density
Due to the symmetry of the critic in CPC (Sec. 4.1p. the learned embedding does encode the full causal relationship between states. Subsequent states are organized close together but we lose the information in which direction transitions were experienced, i.e the arrow of time. A model of the state connectivity is yet required for rewiring tree nodes and becomes indispensable for environments with asymmetric dynamics.
recover this knowledge, we approximate the conditional density p(#++1 1| c) of latent transitions 21:+1le using noise-contrastive estimation (NCE) (Sec. 3). More specifically, we employ a parametric model / 2 ZxC to represent the set of log density estimators given by the conditioning the transition source node and environment context We

---

(a) Sumple mode Awount
(h) peneenittndeeeee Saa rsing
neigtbors:
led des to (N)
(d) Rewiring (peneni modc)
(c) Rewring (chidd notes)
Rlwwiiigg done
Figure 4: Tree growth and rewiring mechanism. Repeat: (a) select random node Sexpand (bluc) in the existing tree (b) create node Snew (yellow) from Zexpond using random action and dynamics Hy (c) find of reachable nodes Zneigh (orange) in the neighborhood around Snew (d) change parent of Enew if there exist a node in Zueigh for which knew is reachable and which reduces the cost of reaching Znew (c), (f) alter parent for every nodes in Zneigh if transitioning from &new is possible and reduces traveling cost.
Figure 3: Illustration of positive pairs and noise training the tran- sition density model to via NCF. Gaussian noise distribution p.. in red, start states of transitions in gray points of transitions ze+1 in green.
train v by maximizing the expectation of the NCE objectives JNCE over the empirical distribution of all conditionings for the observed data, hence Ts = 1e [JNcE(c, 24]] A discrete version of this strategy has previously been used in (38 for estimating the context-dependent probability of words in probabilistic language models.
The crux of NCE is find noise distribution Pa. which tightly encloses the support of the unknown target distribution (Sec. 3). in our case p(z++1 c). Our key insight is however that due to the contrastive training of subsequent states encouraged to be mapped close together in 2. Hence, a simple choice for is found by centering a multivariate Gaussian (2z, Σ) at each starting state 2, of transition and setting the value of > empirically given the absolute lengths of all observed latent transitions in the data (Fig, 3).
One motivation of using NCE instead of other density estimation techniques is that it allows the use of powerful neural network function approximators. Furthermore, the discriminative training procedure using Pa. provides examples of outlier points for which the model assigns low density. Extrapolating densities an important feature which helps us to identify unlikely transitions outside the data support.
4.3
Tree Expansion and Optimization
Due to the unboundedness of the Euclidean embedding space, erroneous transitions during the tree expansion might result in the exploration of areas outside the support of the latent distribution. To reduce the number of detrimental transitions, we train powerful dynamics ensemble estimator
H = {h],... .., hm after the encoder training. Moreover, this allows us to evaluate the ensemble's predictive uncertainty (28) and reject highly uncertain predictions during planning.
Given the encoder Φ forward dynamics H, and transition density model vh, all the building blocks that compose planner are introduced. For every new planning query, start by adding Saart to the tree and then alternate between expanding and optimizing the search tree. Fig. filllustrates the mechanisms behind this procedure.
Tree Expansion During the expansion step, we sample node Zexpand from the current tree and generate new state znew from using H₃ and random action a> The newly generated transition is discarded if the density estimated by v is below threshold т, or the predictive uncertainty Var((h).* 1..m) exceeds threshold re. If both tests are passed, we connect "new the tree and continue with the rewiring step.
Rewiring We optimize the search tree by rewiring edges locally around each newly added node if this reduces the traveling distance from the root. Firstly, we find the set of neighboring tree nodes Zneigh within ball of radius Tneigh around Fnew. Next, we select the elements in Zneigh that are reachable from Znew, i.e. the associated transition density 27, For all the remaining nodes, including
Zexpand, we determine the number of steps travel from Astart to Znew. The node associated with the

---

minimum cost becomes the new parent node of znow. For each node in Zneigh, we then make knew the parent node if such transition is likely and it reduces the traveling cost from Atant Essentially, rewiring reduces travel costs from the root by looking for lower cost paths through existing nodes in the tree. Note that similar techniques are used within asympiotically-opiiaa sampling-bas planners, e.g. RRT [24]. The key difference, however, is that our planner operates in a learned state embedding with approximated latent dynamics and connectivity. Further, note that we consider the path cost as the number of steps in time, not the geometric length of the piecewise linear latent path.
motion
The planning stops after Faer expansion steps. Solution paths are then determined by backtracking up the tree. We return the path with the lowest travel cost among the paths that end near Zgoal (inside sphere of radius r rgou)). If there are no such paths, we simply take the one with the smallest remaining Euclidean distance to -gnal-
Node Sampling Biases Uniform sampling of Zexpand leads slow growth of the search tree with respect to the covered space. To encourage the planner to quickly grow into unexplored regions, we need to bias the sampling towards regions of Z that are less represented in the current tree. With probability Pspurse we therefore sample Eexpand using a distribution weighted by the inverse number of reachable neighbors for each node. The random uniform node selection is continued with probability Puniform- We also use Penal to select the node closest Egnal in terms of Euclidean latent distance. We found that this simple heuristic promotes sufficient exploration towards the goal. For more details on sampling biases, see App. A.1.2
4.4 Integration with Model-Predictivy Control
In order use ELAST for goal-reaching control, we integrate into simple Model Predictive Control (MPC) scheme (Fig. (-)) The controller queues the planned sequence of latent states as waypoints and replans after Reeplan interactions. Between planning, the local control policy π ZxZx + A navigates to the next waypoint. For simplicity, we employ a simple one-step [(a+ - π (21, c))1.
policy which is trained using the supervised loss C,- Ez
5 Experiments
In this section, we evaluate the effectiveness of ELAST for solving challenging downstream reaching tasks from visual observations. For that purpose, we use the closed loop control setting described in Sec. [4.4aand measure the performance in terms of average success rate. Moreover, we investigate the impact of different components and hyperparameters of our method on the quality of the computed solutions.
5.1 Experimental Setup
Baselines To put ELAST in relation to existing work, we the following baselines. PlaNer 14] a latent planning algorithm based on shooting-based trajectory optimization via the Cross- Entropy Method (CEM) 3. Hallucinative Topological Memory (HTM), an image-based planning method for context-conditioned reaching tasks. HTM plans paths on map of raw images generated by sampling observations from a Variational Autoencoder (26. To decouple the effect of representation learning and planning. we evaluate several methods that build on our learned CPC embedding. CPC-CEM uses planning via CEM using the Euclidean latent distance towards the goal as cost. Similarly, CPC-Coll. uses trajectory optimization through direct collocation. CPC-GCBC presents behavioral cloning method trained on CPC latent states. Finally, we implemented goal-conditioned behavior cloning policy V-GCBC which is trained directly from images. In addition, we tested an offline version of the method presented [ but did not produce sensible results under our experimental conditions and is therefore not included in the following evaluation (see App. C.5). Detailed information on the hyperparameters and the implementation of the basclines can found in App. C
To test our method for specific environmental characteristics, we designed the toy environments shown in Fig. 5 BlockS, block agent must navigate through an S-shaped corridor representing a long-horizon and a geometrically non-convex setting. BlockAsym introduces asymmetric transition dynamics through unidirectional stream on one side of the workspace. Parameterized environments that depend on the position of obstacles are explored in both BlockParam
Control Tasks
7

---

Table 1: Success rates (%) for test scenarios averaged over three independent training
METHOO
BLUCKS
ASYM
PARAM
ARM
REACH
BUTTON
DRAWER
HAMMER
CABLE
PARAM
MEDIUM
ELAST
99
96
100::00
8-
88
96 2
88 5
81 12
22
95
79: 11
CPC-CEM
2:2:2
9
68 3
64
1.6
1::0
32
0
1.
1:3
CPC-COLL.
15.11
0::
7:5
3:2:2
21 =
312
1:1
441:2
0::
511
CPC-GCBC
20::2
0=
0=0
29
57 2
31#2
20
2
0=0
26
20
PLANET
17+11
0=0
11+00
18+3
0=0
6
+8
HTM
74.33
0=0
1528
28
43
5
45
342
0=0
1943
30
V-GCBC
25
35
13+2
RANDOM
84-22
0+
0+0
1+1
0+0
1=0
4
0+000
3
(a) BlockS
(b) BlockAsym
(a) Reach
(b) Cable
(c) CableParam
(c) BlockParam
(d) PlanarArm
(d) Button
Drawer
(f) Hammer
Figure 5: Planar control environments
Figure 6: Visually-complex robotics tasks
and PlanarArm. Additionally, we evaluated the visually demanding robot control tasks presented in
Fig. These include robot reaching task (Fig. (6)) and static and parameterized version of cable navigation problem (Fig. 66 and c). In addition, we implemented three robot manipulation tasks (Fig. d-ff adapted from the metaworld benchmark (60).
We form states s, by stacking three consecutive RGB frames resolution 64x In parameterized environments, obtain context observations by taking the latent encodings given by convolutional autoencoder that was trained separately on raw context images. For all environments, we evaluate the performance in reaching distant goals &gaal with respect to task-specific maximum allowed number of interactions. We evaluate the success rates of trajectories 100 unseen scenarios for each task. Detailed information about the implementation of the environments and the experimental evaluation can be found in App.
5.2 Experimental Results
How does the performance of ELAST compare other methods? The results of our benchmark evaluation are shown in T Overall, we observe significantly higher average success rate for MPC control with ELAST compared the selected baselines. This as well as for the visually complex manipulation tasks. The ablation comparison with CPC- EPC-CEM, CPC-Coll. and CPC-GCBC supports that not only the choice of representation, but also our planning strategy contributes to the success of ELAST. Fig. 7 iillustrates the exploration behavior in the BlockS environment for ELAST and CPC-CEM explored regions of the latent space with respect to different numbers of sampled states. It can be seen that our method expands faster and connects the goal the tree with less than 7500 generated states. However, CPC-CEM did not explore deep enough to reach the goal, even given much larger number of samples (J=10, H=50, K=000 corresponds to 10 generated states). HTM did not provide robust solutions compared to approach. While the generated images were mostly
for the planar environments
displays the Isomap embeddings [22] of the

---

mommum
Yhnr 500
(b) Thner 5000
(c) Tiner 7500
(3,20, 200)
(10, 20, 500)
[10, 50, 1000)
Figure 7: Exploration behavior of ELAST and CEM illustrated within 2D Isomap embeddings for the BlookS task. The goal (red) and start (green) lic on different ends of the corridor. (a)-(c): ELAST: search tree (blue) and best path (orange) at different iterations narr. (d)-(f): CEM: visited area (blue) and final population (orange) for different (I, H. K) with iterations I. horizon H and K candidates.
visually sound, some remaining image artifacts resulted in shortcuts in the graph, often rendering entire paths infeasible. This result supports our motivation to pursue planning in a dimee-ideensional space avoid the challenge of obtaining accurate -ighddimessooal observations. While our method performed best among all baselines for the Hammer environment, we achieved only 22% success for this task. We attribute this to the difficulty of planning through the narrow passages introduced by the grasping subtask in this environment (see App. D.10). We also found that the agent often failed grasp the object correctly, which might be improved in the future by using more sophisticated RL policies instead of the short-sighted policy и. Visualizations of successful latent paths for all environments can be found in App. D.9
How does our NCE transition density model impact the performance of the planner? To answer this question, we tested ELAST in the BlockS and Cable environments without reject- ing transition during planning. We observed significant drop in performance for both tasks from 96 + 3% to + 4% in Block5-hard, re- spectively from 95 2% to 25 55% in the Cable task. Fig. SA shows the predicted neighboring latent states with respect to node in the unidi- rectional passage in the BlockAsym environment. As shown, transition density model correctly determines state connectivity even under highly asymmetric transition dynamics. Without transi- tion rejection enabled, the performance on this task dropped 73 + 5% result of infeasi- ble shortcut paths against the direction of the stream. The results indicate that generates
(a)
(b)
Figure 8: (a): Predicted neighboring states (green) for node (blue) within the unidirectional passage Block- Asym (projected with Isomap). Obtained by thresholding estimated transition densitics (b): Example of infcasible path from initial state (green) towards goal (red) that occurs when transition rejection is disabled
useful transition density estimates which is indeed crucial for the performance of our method.
Does the rewiring affect the quality of generated paths? The tree rewiring strategy (Sec. 4.3 encourages smooth and near-optimal paths which important to finish the control tasks within the allowed contingent of environment steps. We evaluated ELAST on the BlockS -arrk--rrrrddaa and the Button tasks without optimizing the tree. The success rates decreased drastically from 96 = 3% 40 = 4% in BlockS-han and from 88 + 5% to 50 + 2% in the Button environment. For the remaining successful episodes, we observed an increase of average trajectory length from 36 1 to + 2 and from 38 + to 72 + 5 steps in the BlockS-hard respectively the Button task. Our results confirm the necessity of path rewiring reduce trajectory lengths and thereby improve the success of our method.
Importance of sparse node sampling bias The exploration behavior of ELAST is largely deter- mined by the weighting of the sampling biases. Fig. Dillustrates the computed latent search trees for planning with Peparse = 0.78 and Psparse = 0.0 for the BlockAsym task. As shown, the tree does not reach the goal in the case of Psparse 0.0 which in fact led to a drop in performance to 0% on this task. Similar trends were observed for other environments (App. D.5). Our results suggest that sampling nodes in sparsely populated areas is very effective in speeding up the exploration of the search space.

---

For all experiments, we used Puniform Puniform=0.2 0.2, Poparc=0.785 and P.0m1=0.02, which were found to be sufficient to achieve balance between exploration and goal-directed node selection.
Depending on the difficulty of the environ- ment, the number of planning iterations was chosen between = and 10000. A detailed overview of planning hyperparam- eters is given in App. A..12 Moreover, we provide collection of further ablation experi- ments in [ This include the impact of dynam- ics ensemble (App. D.3) and comparison of using our planning on a fi- VA- latent space instead of the CPC embedding (App. D.I).
(a) Popase 0.0
(b) Poparae =0.78
Figure 9: Impact of parameter Piparso on the tree explo- ration in the BlockAsym environment. Computed paths (or- ange) and search tree (blue) for Thner = 5000, Paeal 0.02 and Punsfoem 1.0-poal - Pipuse (visualized using Isomap)
6 Limitations and Future Work
The type of decision problems studied in this work is based on the assumption that the full state of the environment can be inferred from the information encoded in the image sequences. However, in robot manipulation tasks, partially observable environments are often encountered, e.g., due to visual occlusions or sensor uncertainties. To extend ELAST to partially observable MDPs (POMDPs), one could replace our deterministic encoder and integrate filtering techniques to update a belief over latent states. A similar approach was taken in [14, which uses recurrent neural network architecture integrate knowledge over time. In addition, the investigation of sampling canpling-based based belief space planning methods (c.g. in the context of latent spaces represents an interesting future direction.
In Sec. 4.3 we introduced the node sampling bias in order to quickly explore the latent space. Previous work employed deep generative networks learn state sampling for classical robot motion planning 21]. Similarly, planner efficiency could be improved by incorporating learned sampling heuristics that consider task-specific information to promote the selection of promising nodes. Currently, ELAST performs random sampling of actions during tree expansion, which could be ineffective for control tasks with high-dimensional action spaces. In addition to node selection, method could be improved by using heuristics to select actions.
In the context of this work, focus planning in goal-reaching scenarios with long time horizons. Similar to [4 47 [43, it would be interesting to adapt our method to the RL setting. This would allow applications beyond reaching, e.g., achieving goals that are not defined by a single state. Instead of finding the shortest path to one particular latent state, the planner would need to search for a trajectory.
7 Conclusion
We presented ELAST, a method for solving high-dimensional and long-term goal reaching through planning in latent spaces. Our approach combines ideas from classical sampling-based motion planning and self-supervised contrastive learning, and initiates tree search bounded by the estimated support region of the latent space. The effectiveness of ELAST was demonstrated in challenging and visually complex control environments. We hope that our work will inspire new planning methods that incorporate both motion planning and machine learning concepts.
Acknowledgements
This work partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
10

---

References
[1] Algoryx. Agx dynamics real-time multi-body simulation. agx dynamics/ 2021.
[2] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang. Xin Zhang, Jake Zhao, and Karol Zieba. End to end learning for self-driving cars. CoRR, abs/1604.07316, 2016.
[3] Zdravko I. Botev, Dirk P. Kroese, Reuven Y. Rubinstein, and Pierre L L'Ecuyer. Chapter 3 the cross-entropy method for optimization. In C.R. Rao and Venu Govindaraju, editors, Handbook of Statistics, volume 31 of Handbook of Statisticx, pages 35-59. Elsevier, 2013.
[4] Adam Bry and Nicholas Roy. Rapidly-exploring random belief trees for motion planning under uncertainty. In 2011 IEEE International Conference on Robotics and Automation, pages 723-730, 2011.
[5] Remi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. CG'06, page 72-83, Berlin, Heidelberg, 2006. Springer-Verlag.
[6] Erwin Coumans and Yunfei Bai. Pybullet, python module for physics simulation for games, robotics and machine learning. hattp://pybullet.orgg 2016-2021.
[7] Frederik Ebert, Chelsea Finn, Sudeep Dasari, Annie Xie, Alex Lee, and Sergey Levine. Visual Foresight: Model-B Badel- Deep Reinforcement Learning for Vision-Based Robotic Control. arXiv e-prints, page arXiv:1812.008:: December 2018.
[8] Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems, 2019.
[9] Chelsea Finn, Ian Goodfellow, and Sergey Levine. Unsupervised learning for physical interac- tion through video prediction. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016
[10] Robert Gieselmann and Florian T. Pokorny. Planning-augmentt hierarchical reinforcement learning. IEEE Robotics and Automation Letters, 633):5097-5104, 2021.
[11] Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani. M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[12] Michael Gutmann and Aapo Hyvärinen.
estimation: A new estimation principle for unnormalized statistical models. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pages 297-304, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
[13] Michael U. Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13(1 1):007361. 2012.
[14] Danijar Hafner, Timothy Lillicrap. Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2565-2565. PMIR, 09-15 Jun 2019.
[15] Meera Hahn, Devendra Singh Chaplot, Shubham Tulsiani, Mustafa Mukadam, James M Rehg, and Abhinav Gupta. No rl, no simulation: Learning to navigate without navigating. In Advances in Neural Information Processing Systems, volume 34, pages 26661-26673. Curran Associates, Inc., 2021.

---

[16] Anna Harutyunyan, Will Dabney. Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nicolas Heess, Hado P van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup, and Remi Munos. Hindsight credit assignment. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[17] Ryan Hoque, Daniel Seita, Ashwin Balakrishna, Aditya Ganapathi, Ajay Tanwani, Nawid Jamali, Katsu Yamane, Soshi Iba, and Ken Goldberg. VisuoSpatial Foresight for Multi-Step, Multi-Tann Fabric Manipulation. In Proceedings of Robotics: Science and Systems, Corvalis, Oregon, USA, July 2020.
[18] D. Hsu, J.-C. Latombe, and R. Motwani. Path planning in expansive configuration spaces. In Proceedings of International Conference on Robotics and Automation, volume 3, pages 2719-2726 vol.3, 1997.
[19] Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[20] Thomas Hubert, Julian Schritwieser, Ioannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning in complex action spaces. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 1476-4488 PMLR, 18 24 Jul 2021.
[21] Brian Ichter, James Harrison, and Marco Pavone. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7087-7094 2018.
[22] Brian lchter and Macro Pavone, Robot motion planning in learned latent spaces. IEEE Robotics and Automation Letters, 443):2007-2414, 2019.
[23] Brian Ichter, Pierre Sermanet, and Corey Lynch. Broadly-exploring, local-policy trees for long-horizon task planning. In 5th Annual Conference on Robot Learning, 2021.
[24] Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. CoRR, abs/1 105. 105.1186, 2011.
[25] Matthew Kelly. An introduction trajectory optimization: How do your own direct colloca- tion. SIAM Review, 59(4):849 904, 2017.
[26] Diederik P Kingma and Max Welling. Auto-encoding variational bayes, 2014.
[27] Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart J Russell, and Pieter Abbeel. Learning plannable representations with causal infogan. S. Bengio, H. Wallach, Larochelle, K. Grau- man, N. Cesa-Bianchi and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[28] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable pre- dictive uncertainty estimation using deep ensembles. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Informa- fion Processing Systems, volume 30. Curran Associates, Inc., 2017.
[29] Michael Laskin, Scott Emmons, Ajay Jain, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning. In Advances in Neural Information Processing Systems, 2020.
[30] S. M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, U.K., 2006. Available at http://planning wwapinnng.....uuu... wiuc.edu//
[31] Steven M. Lavalle. Rapidly-exploring random trees: A new tool for path planning. Technical report, 1998.
[32] Phuc H. Le-Khae Graham Healy, and Alan F. Smeaton. Contrastive representation learning: framework and review. IEEE Access, 8: -9993977- 2020.
12

---

[33] Nir Levine, Yinlam Chow, Rui Shu, Ang Li, Mohammad Ghavamzadeh, and Hung Bui. Predic- tion, consisteney, curvature: Representation learning for locally-lineas control. In International Conference Learning Representations, 2020.
[34] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(39):1-40, 2016.
[35] Kara Liu, Thanard Kurutach, Christine Tung, Pieter Abbeel, and Aviv Tamar. Hallucinative topological memory for zero-shot visual planning. In Hal Daumé III and Aarti Singh, edi- tors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6259-6270. PMLR, 13-18 Jul 2020.
[36] Jeffrey Mahler, Matthew Matl, Vishal Satish, Michael Danielezuk, Bill DeRose, Stephen McKinley, and Ken Goldberg. Learning ambidextrous robot grasping policies. Science Robotics, 4(26))caau4984, 2019.
[37] Marvin Minsky. Steps toward artificial intelligence. Proceedings of the IRE, 49(1):8-3,, 1961.
[38] Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilissic language models, 2012.
[39] Anusha Nagabandi, Kurt Konolige, Sergey Levine, and Vikash Kumar. Deep dynamics models for learning dexterous manipulation. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura, editors, Proceedings of the Conference on Robot Learning, volume 100 of Proceedings of Machine Learning Research, pages 1101-1112. PMLR, 30 Oct-01 Nov 2020.
[40] Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long-horizer tasks via visual subgoal generation. In International Conference on Learning Representations, 2020.
[41] Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal- conditioned policies. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[42] Tung D Nguyen, Rui Shu, Tuan Pham, Hung Bui, and Stefano Ermon. Temporal predictive coding for model-based planning in latent space. In Marina Meila and Tong Zhang, editors, Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8130-8139. PMLR, 18-24 Jul 2021.
[43] Oleh Rybkin, Chuning Zhu, Anusha Nagabandi, Kostas Daniiliiss, Igor Mordatch, and Sergey Levine. Model-based reinforcement learning via latent-space collocation. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9190-9201. PMLR, 18-24 Jul 2021.
[44] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. In International Conference Learning Representations, 2018.
[45] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):004-099 dec 2020.
[46] Julian Schrittwieser, Thomas K Hubert, Amol Mandhane, Mohammadamin Barekatain, Ioannis Antonoglou, and David Silver. Online and offline reinforcement learning by planning with learned model. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[47] Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8583-8592. PMLR, 13-18 Jul 2020.
13

---

[48] Rui Shu, Tung Nguyen, Yinlam Chow, Tuan Pham, Khoat Than, Mohammad Ghavamzadeh, Stefano Ermon, and Hung Bui. Predictive coding for locally-lineas control. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8862-8871. PMIR, 13-18 Jul 2020.
[49] Yang Song and Diederik P Kingma. How to train your energy baaryy-baedd models. arXiv preprint arXiv:2101.33286 2021.
[50] Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal planning networks:
Learning generalizable representations for visuomotor control. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4732-4741, PMLR,
10-15 Jul 2018.
[51] Russ Tedrake. Underactuated Robotics. 2022.
[52] Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 29065500):219--2333 2000.
[53] Stephen Tian, Suraj Nair, Frederik Ebert, Sudeep Dasari, Benjamin Eysenbach, Chelsea Finn, and Sergey Levine. Model-based visual planning with self-supervised functional distances. In International Conference on Learning Representations, 2021.
[54] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, abs/1807.00 00744.. 2018.
[55] Angelina Wang, Thanard Kurutach, Kara Liu, Pieter Abbeel, and Aviv Tamar. Learning robotic manipulation through visual planning and acting. In Proceedings of Robotics: Science and Systems, Freiburgim Germany, June 2019.
[56] Manuel Watter, Jost Springenberg, Joschka Boedecker, and Martin Riedmiller. Embed to control: A locally linear latent dynamies model for control from raw images. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[57] Grady Williams, Paul Drews, Brian Goldfain, James M. Rehg, and Evangelos A. Theodorou. Aggressive driving with model predictive path integral control. In 2016 IEEE International Conference Robotics and Automation (ICRA), pages 1433-1440, 2016.
[58] Wilson Yan, Ashwin Vangipuram, Pieter Abbeel, and Lerrel Pinto. Learning predictive repre- sentations for deformable objects using contrastive estimation. CoRR, abs/2003.05436, 2020.
[59] Lin Yen-Chen, Maria Bauza, and Phillip Isola. Experiencee-mbeedded visual foresight. In Conference on Robot Learning, 2019.
[60] Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura, editors, Proceedings of the Conference on Robot Learning, volume 100 of Proceedings of Machine Learning Research, pages 1094-11000 1100. PMLR, 30 Oct-01 Nov 2020.
[61] Tianhe Yu. Gleb Shevehuk, Dorsa Sadigh, and Chelsea Finn. Unsupervised visuomotor control through distributional planning networks. Proceedings of Robotics: Science and Systems, FreiburgimBreisgau, Germany, June 2019.
14

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include a justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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] See section and App. D.T0
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our method describes general planning algorithms for nigh-dimensional data under unknown dynamics. We do not foresee any immediate societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you 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 ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] See supple- mented code repository.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See App. A.1.3
(c) Did you report error bars (e.g., with respect to 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 (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See App. A.1.3
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're '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]
15


Reviews:
[{"review_id": "znfspd3sEM6", "reviewer": "Reviewer_v4DQ", "summary": "This paper proposes a new algorithm for planning and control for long-horizon goal-reaching tasks in high-dimensional spaces (e.g., control from vision). To do so, the proposed approach performs sampling-based planning in a lower-dimensional latent space. This latent space and its associated transition model are learned using contrastive learning. With these two building blocks, the proposed approach recursively plans a sequence of latent states that are tracked using a learned control policy. The approach outperforms existing baselines in a number of simulation experiments.", "questions": "- Computation times: how long does it take for the approach to compute a plan? How does it compare with baselines? What is the computational bottleneck in the proposed approach? How does it depend on the size of the learned latent space representation?\n\n- Comparisons and feedback control: the role of feedback (from replanning with MPC and tracking the plans with the local policy $\\pi$) should be clarified in the comparisons. The following important details are not described in the body of the paper or in the appendix, which hinders reproducibility and interpretability of the results:\n--- Is PlaNet [12] implemented with online replanning and/or local feedback or not? Is a new trajectory computed at each iteration (as in the original paper) or every 3-25 time steps as in the CPC baselines?\n--- Is HTM [29] implemented with the same local policy $\\pi$ as ELAST? Is replanning done as in ELAST for a fair comparison, or not?\n\n- The paper mentions the difficulty of planning through narrow passages in the Hammer environment. Is the corresponding region in the learned latent space also narrow or not necessarily? Indeed, a good learned latent representation for sampling-based planning would assign larger volume to feasible \"narrow\" passages. Does the proposed approach yield this property or not necessarily? Can the authors add the learned latent space for failure cases in the Hammer environment in Appendix D.8?\n\nSuggestions:\n- The discussion in the paragraph: \"Does the rewiring affect the quality of generated paths?\" is not surprising and follows from results in the sampling-based planning literature (rewiring is a standard step). I recommend making this paragraph shorter.\n- The paper and appendix include typos and should be proof-read (e.g., previosuly, exisitng, distriubtion, This baselines applies, etc.).", "limitations": "Yes, the authors state the limitations of the approach (but, importantly, the paper misses a discussion about the computation times). A discussion of failure cases (e.g., only 22% success rate on the Hammer environment) is included.\n\nIf the authors provide a convincing discussion about the computation times for their proposed approach, I will be happy to raise my rating.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes an interesting contribution for long-horizon planning in high-dimensional spaces, as it combines (long-horizon) sampling-based planning techniques from the robotics community with learned representations from the machine learning community to enable planning in a lower-dimensional latent space. The approach is original and clearly presented, and, in general, the paper is well-written.\n\n** Strengths **\n- The learned latent space and density transition model alleviate the need to learn a collision detector, distance metric, and sampling distribution for sampling-based planning.\n- By planning and learning a transition model in a latent space, the approach does not require learning high-dimensional transition models (e.g., video generative models), which can be computationally expensive to train and evaluate.\n\n** Weaknesses **:\n- The paper does not report computation times. As such, it is unclear if the approach runs in real-time and can be applied to real-world robotic problems, or if it only works in simulation. In particular, more details should be provided regarding scalability of the method with respect to the dimension of the latent space, computation times for the MPC controller, etc.", "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": "8XkvdIqpPG9", "reviewer": "Reviewer_ASfb", "summary": "The authors propose ELAST, a method for model-based long-horizon planning in a low-dimensional latent space of partially-observable systems with high-dimensional observations $s_t$ (e.g. images).\nThe method can be separated in three conceptual stages.\n- First, latent encodings $z_t$ are obtained for each observation $s_t$ (see below).\n- Second, a transition model is fit to time-consecutive encodings to capture the system dynamics $p(z_{t+1} | z_t)$ (disregarding context $c$ for brevity here).\n- Finally, the transition model is used for latent space planning towards a latent goal.\nThis is done by expanding a search tree and then using a heuristic to cull expanded nodes based on the transition model's density, such that the tree remains compliant with the learned dynamics (i.e. sampling-based motion planning, inspired by Rapidly-exploring Random Trees (RRT) and Expansive Space Trees (EST)).\nThe low-dimensional latent space lowers the search cost, which allows the authors to use long planning horizons.\nThe search produces waypoints for an MPC controller, which uses a local parametric policy to bridge them.\n\nThe method is validated over 10 different simulated environments with decent complexity and reasonable success rates.\n\nIn terms of model learning, the latent encodings are a byproduct of applying *Contrastive Predictive Coding* (CPC) [1], to estimate the density ratio $p(s_{t+k} | s_t) / p(s_{t + k})$ which implicitly captures the dependence between consecutive observations $s_t$.\nThe objective of CPC is called InfoNCE and is heavily inspired by *noise contrastive estimation* (NCE) [2] and avoids generative modelling of the observations $s_t$ alltogether.\nThe encodings alone are not enough for planning, as a latent transition model is also necessary.\nThe authors estimate the transition's conditional using NCE as well in a second step, based on the latent encodings alone.\nThere is some redundancy in modelling the transition (see my comments below).\n\n**References**\n\n[1] Oord, A.V.D., Li, Y. and Vinyals, O., 2018. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748.\n\n[2] Gutmann, M. and Hyvärinen, A., 2010, March. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the thirteenth international conference on artificial intelligence and statistics (pp. 297-304). JMLR Workshop and Conference Proceedings.\n", "questions": "- Using RRT / EST trees for expansion leads to heuristics, e.g. the rewiring or the heuristic bias towards unexplored regions. Have you considered search that is better aligned with dynamic programming?\n\nAlso see my remarks above.\n", "limitations": "I don't see any major negative social impact. Some of the method's limitations are acknowledged in a dedicated section.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The method seems widely applicable, as little domain knowledge is employed.\n- Planning appears to be efficient, the authors consider long search horizons and up to 7500 tree expansion steps during planning.\n- Using search for control, be it with tree heuristics like here or through optimal dynamic programming, is generally better than local optimization methods that are prone to getting stuck in local minima.\n- The formulation appears novel to me.\n\n**Weaknesses**\n- The paper sets out to address planning for partially-observable systems, specifically where the state-space does not match the observations, which for me implies a Partially-Observable Markov Decision Process (POMDP).\nHowever, the methods are geared towards solving an MDP, as lookahead control (MPC) is used and generative observation modelling is omitted alltogether.\nI found no clarification of this aspect in the main text, and I believe this is a very important point in terms of positioning the method and making its limitations clear.\nFor example, an optimal POMDP controller would need to plan in *belief space*, and account for the effect of future observations on the state estimate [1].\nState estimates should also generally be uncertain, to account for observation noise and modelling errors, and from what I can tell the obtained latent encodings are a deterministic mapping of the observations.\nCould you please comment on how the method fits / differs from the POMDP paradigm? I believe this should be discussed in the manuscript.\n- I can see how observation generation can burden model training, but why is that an issue during deployment for control (sec. 1, paragraph 2)? Assuming that we disregard the POMDP aspect (which is currently the case), control would only require the dynamics and rewards / the goal state.\n- Contrastive estimation to avoid observation generation has been considered in Dreamer [2] before, where through a single objective dynamics are learned in parallel with shaping the latent space (I'm referring to the mutual-information NCE variant, not the ELBO). What is the justification of learning the transition in two stages (first the encodings through CPC, then the dynamics through NCE)?\n- $h_f$ (the forward dynamics model) and $\\psi$ (the transition density) seem redundant, and this redundancy raises questions. E.g. why is the transition density learned in a second stage (see comment about Dreamer above) and why isn't the forward dynamics model trained to capture the transition density already?\n- It is argued that NCE is better for transition estimation because the noise model provides outliers (end of sec. 4.2). But the noise model should be as close to the data distribution as possible for unbiased NCE gradients--can you elaborate?\n- Thresholding based on the transition density when rejecting samples from the search tree does not properly capture the probabilistic mass of the transition (sec. 4.3). Have you considered rejection sampling / importance sampling?\n- The experimental section ablates the planner and shows it is a core requirement for success, but ablations of model learning (encoding, transition) would also be helpful to assess the method. E.g. what would happen if the planning scheme is used with dynamics learned through generative modelling, e.g. PlaNet or Dreamer? Currently one cannot tell if the contrastive modelling is a major factor in terms of success, or generative modelling could work just as well.\n\n**Further Remarks**\n- I believe the choice of the similarity used in CPC should be motivated further, with more details about why it enforces proximity preservation. This is not immediately clear from the ratio estimation of $p(s_{t+k} | s_t) / p(s_{t+k})$ alone.\n- I did not find details about the training of the ensemble $H_f$, this ties into my comment about the redundant transition modelling.\n- Sequences of observations are generally not guaranteed to be Markovian (sec. 4, first sentence).\n\nDespite the above weaknesses, the method appears pragmatic and seems to work on the considered tasks.\nI find that search in a low-dimensional latent state-space is generally a good idea, albeit driven by heuristics.\nThis makes me lean towards a slightly positive assessment.\nHowever, I have reservations about the methodology and the authors' input would be appreciated.\n\n**References**\n\n[1] Bertsekas, D., 2012. Dynamic programming and optimal control: Volume I (Vol. 1). Athena scientific.\n\n[2] Hafner, D., Lillicrap, T., Ba, J. and Norouzi, M., 2019. Dream to control: Learning behaviors by latent imagination. arXiv preprint arXiv:1912.01603.", "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": "7D-8cyUz9Q_", "reviewer": "Reviewer_b7bj", "summary": "This paper presents a method to perform planning in latent space for robotic applications. The latent space is created for visual observations. The planning procedure follows a methodology similar to sampling-based motion planning in robotics: sampling new configurations (here, in latent space), evaluation of the feasibility of transitioning, re-evaluating the connectivity of this new node to existing nodes. The method is demonstrated in several tasks in simulation, including non-rigid object manipulation, a domain outside of what classical sampling-based planners could solve.\n", "questions": "- Why is the state a sequence of images? What are those sequences for the initial and final states (e.g., s_start and s_goal in Fig.2)?\n- What is f in line 197? Please, explain.\n- What is the distance metric for the neighbor search in Rewiring? L2 in latent space?\n- As I understand it, in line L263 there is a “hidden” implicit assumption: the distance from the tree node in latent space to the goal can be computed in Euclidean space. Or in other words, there is a transformation from latent, to a state where the distance to goal state can be computed by Euclidean distance. Is this true? This seems to strongly restrict the application domains for this method. Also, the effect of this trick is not evaluated in the experiments, but I suspect it provides a large boost. Seems to be however strongly against the idea of planning in latent space? Also, the sentence is weirdly written. The appendix explains another use of Euclidean distance in sampling.\n- The experiments are restricted to an MPC setup. Why? As the authors argue, previous approaches could suffer from local minima entrapment. One of the advantages (the main one?) of sampling-based planning techniques such as RRT is that they are able to find a full path to the goal. Why use it in an MPC methodology? Why not evaluate the execution of such a path. Are there issues with it?\n", "limitations": "I indicated some of my doubts about the limitations in the questions. I think some of those could be added to the (currently very brief) discussion of limitations in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Significance: the method has the potential to open new avenues of research in planning. It tries to extend a well-studied solution from robotics (sampling-based planning) into domains where they couldn’t be applied, and also reducing the necessary information by integrating it with learning based methods.\n- Quality: the paper is well written and easy to read. Minor: starting the paper with “Over the past decade, machine learning has significantly improved the state-of-the-art in image-based robotics and perception” but then citing a single paper feels a bit limited. Consider citing several seminal works, or a survey. Also, maybe there is a better citation than Minsky for the limitations of RL (credit assignment in sparse reward setup). Finally, maybe “unexplored” is better word than “undiscovered” in some places of the text? The planner “explores” these areas to check for feasibility. Also, it should be clear what “undiscovered/unexplored” means in this context. Are these areas where the latents are generated before observing images (extrapolation)?\nOne notable lack are theoretical warranties. Sampling-based motion planning is a field where these warranties were carefully studied. I wonder about the effect on completeness of sampling using a sampler based on an ensemble of observed dynamics. This seems to steer search towards observed transitions, which indicates that all paths need to be randomly explored at the beginning? Experiments on this would be necessary.\n- Originality: the main idea (trajectory planning through sampling in the latent space) has been presented before, as the authors review. However, the presented method is original as it does not require a collision checker and can be used for environments with changes that can be parameterized.\n- Clarity: the paper and the concepts are mostly clear. The section about NCE could be improved. For example, the equations are copied from the original NCE paper but the terms are not explained. Some sentences are a bit convoluted, with multiple unclear subordinates (e.g., L151). The use of random trajectories to train is first indirectly introduced in L191; this methodology for training should be explained before, maybe at the beginning of Section 4. In general, the use of demonstrations is not clear. Consider indicating with bold text the best solution in Table 1.\n\nThere is a couple of typos, e.g., l117, l207, l220, caption Fig.4,...", "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": "0sPhLKYuMoo", "reviewer": "Reviewer_6tyY", "summary": "This work presents ELAST, an approach for long-horizon planning through sampling-based motion planning in learned latent spaces. Given a high dimensional observation (images), the approach first learns a latent representation using self-supervised contrastive learning, a latent dynamics model, and a transition density function. This latent space is then searched via expansive space trees to solve motion planning problems from initial states to goal states. Finally, plans are executed via MPC. ELAST allows efficient searching of spaces and long-horizon planning as shown over a number of environments.\n", "questions": "\nSee above in strengths and weaknesses as well\n- What is the computation time?\n- I think an ablation to VAE-based latent spaces with enforced dynamics is missing.\n- How robust is the latent space? It would be good to see N random training seeds in the Appendix shown with isomaps. Similarly this would be informative for VAE-based latent spaces and VAE-based spaces with enforced dynamics.\n- Why does 19c/d form a loop in the isomap?\n", "limitations": "I would appreciate greater discussion of the limitations of ELAST, right now it's focused more on future work and how previous works can be incorporated. A few limitations of at least the current setup I see is it is not clear how robust the approach is to more complex environments (e.g., with more obstacles) and higher dimensional problems (in the true low-level state space or in the controls space). It would also be good to understand how it scales to kinodynamic systems. I feel the computation time may too be a limitation depending on the results.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is generally well written and clear, as are the figures demonstrating the approach. The area of learning latent representations is useful and important. The minimal assumptions and requirements on data for ELAST makes the method generally applicable. Based on the planning results and plots of the latent spaces the latent space learned is generally robust. The MPC replanner seems to be effective for following the trajectories.\n\nIn terms of number of environments and comparisons the experiments section is thorough (though see notes below on complexity of the environments). The detailed ablations in the appendix and ablations in the experiments section are well done.\n\nThe two main weaknesses I see are (1) the complexity of the environments (both in terms robot dimensionality and environment variation) and (2) the novelty compared to prior approaches for latent tree searches.\n\n(1) Each of the environments has relatively low dimensional true, important state spaces, which is an area where these latent space methods perform well. It would be useful to see how it performs in spaces such as an SE(2 or 3) rigid body in a complex environment. Furthermore it would be useful to see how it performs with more complex dynamics, such as a kinodynamic system which may force higher dimensional learned latent spaces (a double integrator for instance). \n\nFinally, as a benefit over prior methods is that it does not require a collision checker (which allows some degree of generalization to new environments) it is imperative the authors demonstrate the approach on more complex obstacle environments, which can be encoded via the context. I’m not sure from the results shown that it would perform well in such cases. In the current implementation, the conditioning on the actual states of parameterization (such as the position of the moved block) does not seem consistent with the rest of the paper: why not condition on the image alone? A 2D environment with significantly more variations and objects than 5c may suffice to show that it can work in such a more complex setting, though scaling to 3d scenes would be more informative. \n\n(2) The novelty compared to prior works using tree-search in latent space is potentially limited. For example, [15] does use a sampler and a learned collision checker as noted, but removing them essentially reduces that algorithm to ELAST. The state sampler is only used to bias the search and make it more efficient, but also state sampling is likely freely available from your training data. It is not clear to me why one wouldn’t use it. The collision checker is used to allow generalization to novel environments, which in ELAST is handled by the context c. It is not clear how powerfully the context can be used to extend to more complex environments and should be shown by this work. \n\nOne major change between 15 and this work is that the latent space is learned in a potentially more robust way through contrastive learning. It would be useful to investigate the effect this has by comparing to VAE-based latent spaces with enforced dynamics.\n\nA few more minor weaknesses:\n- An algorithm box for the tree search and the latent space learning would be appreciated. \n- Adding the network names to the figures in e.g. Fig 3 and 4 would be helpful to quickly see how each fits together.\n\nMinor notes:\n- Line 198: list the inptuts and outputs of h_f.\n- ELAST + RL is an interesting extension\n- Appendix D1 is interesting and would appreciate more detailed\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