summaries: This paper tackles the problem of long horizon visual planning, with the aim of of being able to plan actions to reach distant goals. This is a well studied problem, and like prior work this method considers the setting where the agent is given an offline dataset of interaction, which it learns from to be able to reach new goals (specified by a goal image). The method first does unsupervised representation learning, where it learns a discrete representation of images (using contrastive predictive coding (CPC) with a discrete latent variable using Gumbel Softmax). Using a set of discrete latent variable, it then builds a set of graphs which connects these discrete states based on the collected experience, and derives a planning procedure to find a path in the graph which reaches the goal.  This paper presents a method that combines learning discrete representations together with planning using graph search to solve long horizon tasks from vision. The approach works by generating data via random exploration and trains a representation encoder on this data. This network extracts objects from the observations and passes them through a CNN and shared encoder to generate one-hot encodings; these encodings are concatenated to generate the discrete representation. The encoder is trained via a contrastive learning objective with a similarity matrix that encourages nearby states to share similar encodings, thereby encouraging spatial and temporal abstractions. Next, these representations are combined together with an abstract planner to generate a sequence of waypoints to the goal. This is done by creating a graph of transitions from the collected exploratory data and search within this graph — this is executed for each encoding at a time with the assumption that the task can be solved by moving each object independently of the others. Finally, a low-level controller is used for reaching the waypoints and final goal, this is done via MPC on an action-conditional predictive model that generates future observations given the current state and goal. The approach is tested on two simple planar planning tasks where the agent has to solve k-object arrangement and open a room with a key respectively. This work presents Discrete Object-factorized Representation Planning (DORP), which learns a discrete representation from videos with an enforced temporal consistency. This representation can then be planned over through a sequence of small alterations to the discrete embedding, which are then executed via MPC. DORB is demonstrated to solve long-horizon tasks and learn representations that consider objects and their properties. 
abstractText: Discrete representations have been key in enabling robots to plan at more abstract levels and solve temporally-extended tasks more efficiently for decades. However, they typically require expert specifications. On the other hand, deep reinforcement learning aims to learn to solve tasks end-to-end, but struggles with long-horizon tasks. In this work, we propose Discrete Object-factorized Representation Planning (DORP), which learns temporally-abstracted discrete representations from exploratory video data in an unsupervised fashion via a mutual information maximization objective. DORP plans a sequence of abstract states for a low-level model-predictive controller to follow. In our experiments, we show that DORP robustly solves unseen long-horizon tasks. Interestingly, it discovers independent representations per object and binary properties such as a key-and-door.
references.authors: Pulkit Agrawal Ashvin V Nair Pieter Abbeel Jitendra Malik Sergey Levine
references.title: Learning to poke by poking: Experiential learning of intuitive physics
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ankesh Anand Evan Racah Sherjil Ozair Yoshua Bengio Marc-Alexandre Côté R Devon Hjelm
references.title: Unsupervised state representation learning in atari
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Masataro Asai Alex Fukunaga
references.title: Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary
references.venue: arXiv preprint arXiv:1705.00154,
references.authors: Mohammad Babaeizadeh Chelsea Finn Dumitru Erhan Roy H Campbell Sergey Levine
references.title: Stochastic variational video prediction
references.venue: arXiv preprint arXiv:1710.11252,
references.authors: Ruzena Bajcsy
references.title: Active perception
references.venue: Proceedings of the IEEE,
references.authors: Ruzena Bajcsy Yiannis Aloimonos John K Tsotsos
references.title: Revisiting active perception
references.venue: Autonomous Robots,
references.authors: Christopher P Burgess Loic Matthey Nicholas Watters Rishabh Kabra Irina Higgins Matt Botvinick Alexander Lerchner. Monet
references.title: Unsupervised scene decomposition and representation
references.authors: Maxime Chevalier-Boisvert Lucas Willems Suman Pal
references.title: Minimalistic gridworld environment for openai gym
references.venue: https://github.com/maximecb/gym-minigrid,
references.authors: Frederik Ebert Chelsea Finn Sudeep Dasari Annie Xie Alex Lee Sergey Levine
references.title: Visual foresight: Model-based deep reinforcement learning for vision-based robotic control
references.venue: arXiv preprint arXiv:1812.00568,
references.authors: Ben Eysenbach Russ R Salakhutdinov Sergey Levine
references.title: Search on the replay buffer: Bridging planning and reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Chelsea Finn Ian Goodfellow Sergey Levine
references.title: Unsupervised learning for physical interaction through video prediction
references.venue: In Advances in neural information processing systems,
references.authors: Paul Fitzpatrick
references.title: First contact: an active vision approach to segmentation
references.venue: In Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453),
references.authors: James J Gibson
references.title: The ecological approach to visual perception: classic edition
references.authors: Klaus Greff Raphaël Lopez Kaufman Rishabh Kabra Nick Watters Chris Burgess Daniel Zoran Loic Matthey Matthew Botvinick Alexander Lerchner
references.title: Multi-object representation learning with iterative variational inference
references.authors: Emil Julius Gumbel
references.title: Les valeurs extrêmes des distributions statistiques
references.venue: In Annales de l’institut Henri Poincaré,
references.authors: Danijar Hafner Timothy Lillicrap Ian Fischer Ruben Villegas David Ha Honglak Lee James Davidson
references.title: Learning latent dynamics for planning from pixels
references.venue: In International Conference on Machine Learning,
references.authors: Karol Hausman Dejan Pangercic Zoltán-Csaba Márton Ferenc Bálint-Benczédi Christian Bersch Megha Gupta Gaurav Sukhatme Michael Beetz
references.title: Interactive segmentation of textured and textureless objects
references.venue: In Handling Uncertainty and Networked Structure in Robot Control,
references.authors: Kaiming He Haoqi Fan Yuxin Wu Saining Xie Ross Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Eric Jang Shixiang Gu Ben Poole
references.title: Categorical reparameterization with gumbel-softmax
references.venue: arXiv preprint arXiv:1611.01144,
references.authors: Leslie Pack Kaelbling Tomás Lozano-Pérez
references.title: Hierarchical task and motion planning in the now
references.venue: In 2011 IEEE International Conference on Robotics and Automation,
references.authors: Ken Kansky Tom Silver David A Mély Mohamed Eldawy Miguel Lázaro-Gredilla Xinghua Lou Nimrod Dorfman Szymon Sidor Scott Phoenix Dileep George
references.title: Schema networks: Zero-shot transfer with a generative causal model of intuitive physics
references.venue: arXiv preprint arXiv:1706.04317,
references.authors: Jacqueline Kenney Thomas Buckley Oliver Brock
references.title: Interactive segmentation for manipulation in unstructured environments
references.venue: In 2009 IEEE International Conference on Robotics and Automation,
references.authors: Thomas Kipf Elise van der Pol Max Welling
references.title: Contrastive learning of structured world models
references.venue: arXiv preprint arXiv:1911.12247,
references.authors: Thanard Kurutach Aviv Tamar Ge Yang Stuart J Russell Pieter Abbeel
references.title: Learning plannable representations with causal infogan
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Suha Kwak Minsu Cho Ivan Laptev Jean Ponce Cordelia Schmid
references.title: Unsupervised object discovery and tracking in video collections
references.venue: In Proceedings of the IEEE international conference on computer vision,
references.authors: Michael Laskin Scott Emmons Ajay Jain Thanard Kurutach Pieter Abbeel Deepak Pathak
references.title: Sparse graphical memory for robust planning
references.venue: arXiv preprint arXiv:2003.06417,
references.authors: Kara Liu Thanard Kurutach Christine Tung Pieter Abbeel Aviv Tamar
references.title: Hallucinative topological memory for zero-shot visual planning
references.venue: arXiv preprint arXiv:2002.12336,
references.authors: Corey Lynch Mohi Khansari Ted Xiao Vikash Kumar Jonathan Tompson Sergey Levine Pierre Sermanet
references.title: Learning latent plans from play
references.venue: In Conference on Robot Learning,
references.authors: Xiao Ma Siwei Chen David Hsu Wee Sun Lee
references.title: Contrastive variational model-based reinforcement learning for complex observations
references.venue: arXiv preprint arXiv:2008.02430,
references.authors: Chris J Maddison Andriy Mnih Yee Whye Teh
references.title: The concrete distribution: A continuous relaxation of discrete random variables
references.venue: arXiv preprint arXiv:1611.00712,
references.authors: Mehdi Mirza Andrew Jaegle Jonathan J Hunt Arthur Guez Saran Tunyasuvunakool Alistair Muldal Théophane Weber Peter Karkus Sébastien Racanière Lars Buesing
references.title: Physically embedded planning problems: New challenges for reinforcement learning
references.venue: arXiv preprint arXiv:2009.05524,
references.authors: Suraj Nair Chelsea Finn
references.title: Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation
references.venue: arXiv preprint arXiv:1909.05829,
references.authors: Soroush Nasiriany Vitchyr Pong Steven Lin Sergey Levine
references.title: Planning with goal-conditioned policies
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Andrew Y Ng Daishi Harada Stuart Russell
references.title: Policy invariance under reward transformations: Theory and application to reward shaping
references.venue: In ICML,
references.authors: Masashi Okada Tadahiro Taniguchi
references.title: Dreaming: Model-based reinforcement learning by latent imagination without reconstruction
references.venue: arXiv preprint arXiv:2007.14535,
references.authors: Aaron van den Oord Yazhe Li Oriol Vinyals
references.title: Representation learning with contrastive predictive coding
references.venue: arXiv preprint arXiv:1807.03748,
references.authors: Karl Pertsch Oleh Rybkin Frederik Ebert Chelsea Finn Dinesh Jayaraman Sergey Levine
references.title: Long-horizon visual planning with goal-conditioned hierarchical predictors
references.venue: arXiv preprint arXiv:2006.13205,
references.authors: Ali Razavi Aaron van den Oord Oriol Vinyals
references.title: Generating diverse high-fidelity images with vq-vae-2
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sebastian Risi Kenneth O Stanley
references.title: Deep neuroevolution of recurrent and discrete world models
references.venue: In Proceedings of the Genetic and Evolutionary Computation Conference,
references.authors: Nikolay Savinov Alexey Dosovitskiy Vladlen Koltun
references.title: Semi-parametric topological memory for navigation
references.venue: arXiv preprint arXiv:1803.00653,
references.authors: Aravind Srinivas Michael Laskin Pieter Abbeel
references.title: Curl: Contrastive unsupervised representations for reinforcement learning
references.venue: arXiv preprint arXiv:2004.04136,
references.authors: Siddharth Srivastava Eugene Fang Lorenzo Riano Rohan Chitnis Stuart Russell Pieter Abbeel
references.title: Combined task and motion planning through an extensible planner-independent interface layer
references.venue: IEEE international conference on robotics and automation (ICRA),
references.authors: Karl Stratos Sam Wiseman
references.title: Learning discrete structured representations by adversarially maximizing mutual information
references.venue: arXiv preprint arXiv:2004.03991,
references.authors: Marc Toussaint
references.title: Logic-geometric programming: An optimization-based approach to combined task and motion planning
references.venue: In IJCAI, pp. 1930–1936,
references.authors: Rishi Veerapaneni John D Co-Reyes Michael Chang Michael Janner Chelsea Finn Jiajun Wu Joshua Tenenbaum Sergey Levine
references.title: Entity abstraction in visual model-based reinforcement learning
references.venue: In Conference on Robot Learning,
references.authors: Ning Wang Yibing Song Chao Ma Wengang Zhou Wei Liu Houqiang Li
references.title: Unsupervised deep tracking
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Zi Wang Caelan Reed Garrett Leslie Pack Kaelbling Tomas Lozano-Perez
references.title: Active model learning and diverse action sampling for task and motion planning
references.venue: In International Conference on Intelligent Robots and Systems (IROS),
references.authors: Manuel Watter Jost Springenberg Joschka Boedecker Martin Riedmiller
references.title: Embed to control: A locally linear latent dynamics model for control from raw images
references.venue: In Advances in neural information processing systems,
references.authors: Nicholas Watters Loic Matthey Matko Bosnjak Christopher P Burgess Alexander Lerchner
references.title: Cobra: Data-efficient model-based rl through unsupervised object discovery and curiosity-driven exploration
references.authors: Fanyi Xiao Yong Jae Lee
references.title: Track and segment: An iterative unsupervised approach for video object proposals
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Wilson Yan Ashwin Vangipuram Pieter Abbeel Lerrel Pinto
references.title: Learning predictive representations for deformable objects using contrastive estimation
references.venue: arXiv preprint arXiv:2003.05436,
sections.heading: 1 INTRODUCTION
sections.text: In future, we hope that robots will be able to operate in unstructured environments such as homes and hospitals, and endowed with long-horizon planning ability. Despite successes in deep reinforcement learning (RL) from raw observations, much progress relies on the availability of shaped reward to guide the learning (Ng et al., 1999; Mirza et al., 2020). On the other hand, over past decades, task and motion planning has been shown to solve much longer-horizon goal-directed tasks such as making a cup of coffee from torque control (Kaelbling & Lozano-Pérez, 2011; Srivastava et al., 2014; Toussaint, 2015; Wang et al., 2018). However, these methods often require pre-specified discrete abstract states, task representations and transition models, e.g., whether the robot is holding a cup and what actions (or perturbations) change such an abstract state. In this paper, we aim to learn discrete representations for high-level abstract planning from video interaction data, combined with a learned short-horizon controller.
  Learning discrete representations from unsupervised data for planning is challenging for two reasons. First, the relationship between the optimization objective and the true task objective is not well-defined. Second, optimizing a model with a discrete layer is difficult with standard deep learning techniques. Recent methods approach the first problem using reconstruction or constrastive objectives (Watter et al., 2015; Anand et al., 2019; Ha & Schmidhuber, 2018; Kurutach et al., 2018; Hafner et al., 2019; Srinivas et al., 2020); however, the learned representations are in continuous latent space which is unstructured and difficult to combine with high-level abstract planning. While other methods show promise in learning discrete representations, they have not been applied to temporally-extended RL tasks (Oord et al., 2018; Razavi et al., 2019; Risi & Stanley, 2019; Asai & Fukunaga, 2017; Stratos & Wiseman, 2020).
  In this work, we propose Discrete Object-factorized Representations for Planning (DORP) – a novel framework for visual planning and control by learning discrete representations and a low-level controller. DORP learns discrete representations from images that change slowly overtime, such as whether or not the agent holds a key or which room the agent is in, along with a low-level predictive model for control. These slow features enable the agent to plan at a low frequency in longer-horizon tasks. More specifically, DORP represents an abstract state as a set of one-hot vectors, and optimizes its encoder by maximizing a mutual information lower bound between the current representations to future observations (Oord et al., 2018). In order to train through the discrete layer, we apply the Gumbel-Softmax reparametrization trick (Jang et al., 2016; Maddison et al., 2016). Using abstract states as nodes, we build an approximate feasibility graph based on observed transition data. When provided with new start and goal images, the agent plan the shortest abstract path. Using the next
  abstraction as waypoint, model-predictive control maximizes the objective that is 1 if it reaches the target abstraction and 0 otherwise with a trained video prediction model. Unlike other subgoal planning work (Savinov et al., 2018; Nasiriany et al., 2019; Laskin et al., 2020; Liu et al., 2020), by following abstract waypoints, DORP avoids unneccessary steps to match exact waypoint states.
  In a set of experiments, we demonstrate that DORP learns temporally-consistent and objectfactorized representations suitable for planning. We show that these representations enable DORP to handle unseen long-horizon tasks more successfully compared to the states-of-the-arts in visual planning. Interestingly, we observe that latent representations show object-level factorization such as key-and-door.
sections.heading: 2 PRELIMINARIES
sections.text: We present background material on unsupervised representation learning and discrete optimization that our method builds on, and our problem formulation.
  Contrastive Predictive Coding (CPC) (Oord et al., 2018) learns low-dimensional representations that are most predictive of the future future high-dimensional sequential data. A non-linear encoder qθ : O → Rl, parametrized by θ, encodes the observation ot ∈ O to a latent l-dimensional vector representation zt. Let’s define a similarity score fk(zt, ot+k) = exp(ztψqθ(ot+k)) where ψ is a trainable l-by-l similarity matrix and ot+k is a future observation k steps ahead of ot. Given the query observation ot, we aim to classify the key observations – ot+k as positive and other sample õ from the dataset as negative. Formally, we optimize the loss function LCPC = −Eot,ot+k [ log fk(zt, ot+k)− log ∑ oj∈X fk(zt, oj) ] with respect to θ and ψ. This also corresponds to maximizing a lowerbound of the mutual information between the latent representation zt and the future observation ot+k.
  Gumbel-Softmax (GS) (Jang et al., 2016) is a discrete optimization technique to compute the gradient of through samples from a categorical distribution πi. GS first applies a reparametrization trick to rewrite samples zi as onehot(argmaxj(gj + logπi)) where gj are i.i.d samples from Gumbel(0, 1) (Gumbel, 1935). GS approximates argmax with softmax making the discrete stochastic layer differentiable, i.e., zi = softmax((gi + log πi)/τ). When the temperature parameter τ approaches 0, the samples converge to the true categorical distribution. Empirically, the temperature τ starts high and is annealed closer to 0 by a certain schedule.
sections.heading: 2.1 PROBLEM STATEMENT: GOAL-DIRECTED VISUAL PLANNING AND CONTROL
sections.text: We define an unknown, fully-observable, stochastic dynamical system f which maps input observation ot ∈ O and action at ∈ A to the next observation ot+1. Under this dynamical system, we assume a simple exploration policy πrand which can collect data that characterizes the dynamics of the system. This is known as self-supervised data or play data (Agrawal et al., 2016; Lynch et al., 2020). We consider high-dimensional observation such as images.
  Our goal is to learn discrete abstraction zt ∈ Z given observation ot, an abstract feasibility model, and a low-level local controller. At test time, given start os and goal og observations, we can plan a sequence of abstract states zs, z1, ..., zg where zs and zg are the representation of os and og , and apply the low-level controller to reach these abstract waypoints and finally to og .
sections.heading: 3 DISCRETE OBJECT-FACTORIZED REPRESENTATION FOR PLANNING
sections.text: Our objective is to derive representation properties such as object-factorization and temporalconsistency from an unsupervised learning objective to facilitate long-horizon planning. When object representations are factorized, the agent can escape the need of combinatorial data configurations and can quickly generalize to unseen tasks. Also, the connectivity graph can also be memory-efficiently represented and combined with a more powerful planning algorithm. Another important property for a representation is temporal consistency, meaning any two state observations in the same abstraction should be reachable from one-another by a short sequence of actions. When this property holds in the latent space, a high-level plan can be successfully executed by a low-level controller.
  We propose Discrete Object-factorized Representation for Planning (DORP) to tackle goal-directed visual planning and control problem. DORP learns latent discrete representations, a connectivity graph for abstract planning, and a low-level model-predictive controller. We describe each subcomponent in Section 3.1 - 3.3.
sections.heading: 3.1 DISCRETE REPRESENTATIONS
sections.text: Despite successes in applying its unsupervisedly learned representations for downstream tasks, CPC is not endowed with an inductive bias for its representations to facilitate planning (Oord et al., 2018). Additionally, it is unclear how a discrete representations can be extracted and optimized. Toward this goal, we propose an object-factorized architecture with asymmetric Gumbel softmax for discrete optimization, and a diagonally dominating and diagonally positive similarity matrix to encourage temporal consistency.
  We implement our DORP architecture to encourage object-factorization and capture discrete representations. The extractor passes an anchor observation through a convolutional neural network and outputs a c-channel feature map. Each feature map is inputted to a shared encoder followed by a Gumbel softmax. For a positive and negative pair of images, however, we opt for a continuous embedding by swapping Gumbel softmax for softmax. Empirically, without this asymmetry trick, the optimization tends to converge to a poor local optima. Together these one-hots are flattened into long vectors, and their bilinear product is the similarity score between the query-key pair (see Figure 2).
  We propose an inductive bias in the similarity score function to encourage temporal consistency. Instead of a fully trainable matrix, we parameterize the similarity matrix ψ to be diagonally dominant and diagonally positive (DDDP). This property biases the similarity score to be high when the key embedding z̃t+k is close to the query embedding zt and maximized when z̃t+k = zt. In other words, this incentivizes the representations of positive pairs to share
  weight matrix as eψ0(−σ(ψ1) + αIl×l) where Il×l is an identity matrix, α is a positive constant, σ is a sigmoid function, ψ0 is a trainable scalar, and ψ1 is a trainable l-by-l matrix.
sections.heading: 3.2 ABSTRACT PLANNING
sections.text: A critical component in planning is a connectivity graph that decides whether two discrete representations are connected. One naive solution is to build such a graph from data – all observed representations as nodes and all observed transitions as edges. However as the number of independent entities increases, the amount of data required to generate the nodes and edges in order to cover the state space increases exponentially. To solve this, we propose to reduce the planning problem by exploiting factorization (see Figure 3).
  1. First, embed the current image os and goal og as zs = qθ(os) and zg = qθ(og).
  2. Pick a random one-hot index i s.t. the current state’s one-hot zis differs from the goal’s one-hot zig .
  3. Build a graph based on how this one-hot transits in the data (ignoring all other one-hots). 4. Plan a path zi1, ..., z i g from z i s to z i g . If this does not exists, then we fail the task.
  5. Execute the low-level controller following the next target zik, k = 1, · · · , g, while keeping other zj the same.
  6. If it doesn’t reach zik, remove the edge from the graph and redo the planning in step 4.
  7. If it succeeds, follow the next target until it reaches zig . 8. Repeat step 2 until all the one-hots match. 9. Finally, execute the low-level controller to the goal image og .1
  Our proposed method assumes that each latent one-hot can be manipulated independently to solve the task. This assumption can hold various settings. For example, imagine a task that requires reorganizing furniture in a spacious room, and each objects is represented as a separate one-hot. Here, we can manipulate each object separately, and since there is plenty of empty space in this scenario, we can easily plan around objects to avoid collisions.
  This assumption does not always hold; along the same scenario, when the space is more cluttered, objects are more likely to collide, and the proposed fully-factorized planning may fail even though a solution exists (incomplete). We extend this planning algorithm by building a graph on a random set of one-hot indices at a time in step 2. When can choose this set to contain all the one-
  1An implicit assumption of temporal consistency in the learned discrete representations is required.
  hots the method is equivalent to the full graph search (complete but expensive). Thus, our extended planning method can trade between completeness and efficiency.
sections.heading: 3.3 LOW-LEVEL CONTROL
sections.text: The low-level controller is the key component in order to follow abstract plans and reach the goal. For this reason, the controller must be flexible in achieving multi-objectives. Modelpredictive controller (MPC) achieves this by modeling the dynamics of the world from past data and minimizing with the total predicted cost of horizon T at run-time: a∗t , ..., a ∗ t+T−1 =
  argminat,...,at+T−1 E [∑T i=1 γ tĉt+i ] . The predicted cost is computed by applying a known cost function on the predicted outcome of a T -step action sequence from the current observation ot.
  MPC requires the world model and the costs. For the world model, we implement a stochastic video prediction model (Babaeizadeh et al., 2017). In our framework, we define two cost functions for reaching abstract goals and for reaching the final goal observation. The first cost function is defined to be 1 if the current embedding exactly matches the goal embedding (all the one-hots match) and 0 otherwise: clat(ot, z′) = 1[qθ(ot) == z′]. The second cost function is defined by its L2 loss in the observation space to the goal: cobs(ot, og) = ||ot − og||. This cost is versatile for reaching nearby observations particularly to reach the goal observation once it has reached the goal code.
sections.heading: 4 RELATED WORK
sections.text: Object Discovery Recent work has studied unsupervised object segmentations from visual inputs (Burgess et al., 2019; Greff et al., 2019), and entity-factorized representations and models for predictions (Kipf et al., 2019). However, these studies have not been demonstrated to directly solve the task. In this work, we take a step further to evaluate the representations in downstream tasks. While other work (Veerapaneni et al., 2020; Watters et al., 2019) shows how the MPC agents benefit from object-factorized models, they require shaped rewards for the tasks. In contrast, we consider a longhorizon task in which the agent only receives its reward when it has reached the goal. A large body of work in computer vision has studied unsupervised video object segmentation (Aloimonos et al., 1988; Bajcsy, 1988; Bajcsy et al., 2018; Gibson, 2014; Fitzpatrick, 2003; Hausman et al., 2015; Kenney et al., 2009) and unsupervised object detection (Kwak et al., 2015; Wang et al., 2019; Xiao & Jae Lee, 2016). However, semantic segmentation and object detection might not be the correct representation for the end-task. In this work, we learn representations that are more ready to use for planning without explicit segmentation or detection.
  World models Much previous work has applied generative models of the world to visual control tasks (Watter et al., 2015; Ha & Schmidhuber, 2018; Hafner et al., 2019). Other work (Ma et al., 2020; Okada & Taniguchi, 2020; Yan et al., 2020) leverages a contrastive objective to learn a latent world model. These methods however require dense reward signals for most tasks. Visual foresight methods (Finn et al., 2016; Ebert et al., 2018) demonstrate impressive results on real robots using unshaped reward such as pixel distance to the goal, but it still remains limited to short-horizon object pushing tasks. In our work, we borrow these methods for low-level controllers. Asai & Fukunaga (2017) learn discrete abstraction of the system such as an 8-piece puzzle, but do not consider temporal abstraction. Kansky et al. (2017) demonstrate that discrete object-factorized representations can be used to learn logic-based transitions. In combination with powerful planning, it improves generalization and data efficiency. However, it assumes supervised ground-truth labels for representation learning. In this work, we aim to learn this in an unsupervised manner.
  Hierarchial RL Recent work has tried to approach long-horizon visual planning by breaking down tasks using skills (Lynch et al., 2020; Kipf et al., 2019). Our approach is orthogonal and may deploy such action abstractions as a low-level controller. Other methods propose to plan subgoals and attempt to follow them either in the latent space (Kurutach et al., 2018; Nasiriany et al., 2019; Nair & Finn, 2019) or in the visual space (Savinov et al., 2018; Liu et al., 2020; Eysenbach et al., 2019). However, such methods require labor-intensive engineering to tune the threshold on when to move on to pursue the next subgoal (Savinov et al., 2018; Liu et al., 2020) because the observations or the latent states can never exactly match. Imagine bringing a chair from one office to another. It would be time consuming to match all the positions and orientations of the chair along the way. Rather we should care about rough area the chair has to go through in order to reach the goal. In our work, by learning the discrete codes, our method do not require such threshold as it exactly knows when
  it has reached the target discrete representation. Additionally, it avoids aiming to match a specific waypoint observation. Instead of planning to the goal, Pertsch et al. (2020) predict intermediate images iteratively to construct a subgoal tree. However in order to train such prediction model a long-sequential training data are required. Instead our work can be applied to short-horizon or long-horizon trajectories.
sections.heading: 5 EXPERIMENTS
sections.text: We perform experiments aimed at answering the following questions: (1) Are DORP representations temporally-consistent for high-level planning? (3) Can DORP representations factorize objects that translate or change in appearances over time? (3) How does DORP compare to the visual planning SOTA in solving unseen long-horizon goal-directed tasks?
sections.heading: 5.1 ENVIRONMENTS
sections.text: We evaluate DORP on two main environments – object-rearrangement and key-room. All the observations are provided as color images of size 16× 16× 3. k-object-rearrangement Multiple (k) 2-by-4 blocks of different colors can each be manipulated independently by an agent. The tasks require the agent to manipulate these objects from a start configuration to a goal configuration. In each step, it can manipulate each block by one unit in one of the 4 directions. The agent collects data by randomly interacting with one of the objects at each timestep in a purely exploratory manner, without any goal in mind. In this environment our trajectory has length one that is the configuration is randomly reset after every step.
  key-room Two variations of key-room depend on the number of rooms – key-corridor (6 rooms and a corridor) and key-wall (2 rooms. A key and agent are represented by 1 pixel. A key is placed in a fixed location in a room. If the agent steps on the key a door will be removed allowing the agent to enter a locked room. Each step the agent can move in one of the four directions by 1 unit. The agent collect data by a long random walk – 1500 steps for key-corridor and 1000 steps for key-wall. After each reset the agent will be placed randomly in one of the unlocked rooms. This environment is inspired by MiniGrid (Chevalier-Boisvert et al., 2018).
sections.heading: 5.2 BASELINES
sections.text: We choose the state-of-the-arts visual foresight (VF) (Ebert et al., 2018) implemented using SV2P architecture (Babaeizadeh et al., 2017) as our baseline for two reasons. First, VF only requires selfsupervised data collection and is applicable to unseen tasks – thus aligning with goal-directed visual planning problems. Second, Visual Foresight is a low-level controller of DORP. By sharing the same video model as baseline, we show a direct improvement of abstract planning for temporallyextended tasks. Two optimization variations of VF – VF with random shooting (VF-RS) and VF with cross-entropy method (VF-CEM) – both share the same video prediction model. Their objective is to minimize its L2 distance from the current image to the goal image. While DORP deploys VFRS for its low-level control, VF-CEM comparision are provided for an improved baseline. VF-RS randomizes 1000 trajectories and take the full action sequence that achieves the minimum cost. VF-CEM randomizes 1000 samples per iteration. We pick the top 2% to refit a distribution over sequence and repeat for 3 iterations.
  To understand DORP representation learning improvement, we evaluate DORP when replacing its DDDP similarity matrix by an arbitrary weight (Oord et al., 2018) or an identity matrix (He et al., 2020) which have been used extensively in unsupervised representation learning. To understand the benefits of factorized planning, we replace it with the full graph planning with a maximum limit on the number of steps allowed.
sections.heading: 5.3 QUANTITATIVE RESULTS
sections.text: Temporal consistency We investigate DORP representations by color-coding the discrete embeddings on the configuration map of the environments. For visualization simplicity we choose 1-
  3With the exceptions for 5 objects in which we evaluate VF-RS on 10 tasks, VF-CEM on 11 tasks, and DORP on 23 tasks due to time and compute limits.
  object-rearrangement to visualize the learned code map. In this environment we have a single one-hot code for representing the object. We demonstrate that DORP learns temporally consistent representations in which two states from the same discrete code are connected by a short-horizon controller (see Figure 5(a)). Similarly, we observe the same property in key-wall environment (see Figure 6).
  Object factorization We evaluate the behavior of the one-hot codes by changing one property of the agent at a time such as positions or whether the agent has a key. In Figure 4(c) we observe that by moving one object at a time only at most one one-hot code changes its value k-object-rearrangement. In key-room, we formulate the discrete representation as follows: of the two output one-hot latents, the first is set to a size z0 and the other is set to size 2. Our aim is for one latent one-hot to encode the agent’s abstract state and for the other binary latent to encode the key’s abstract state. In Figure 6, we demonstrate that the learned abstract representations are factorized as desired by observing (1) the larger one-hot changes when the agent moves with no key interactions and (2) the binary one-hot changes when removing and adding the key while maintaining the agent position.
  Weight Ablation We study the effect of the proposed similarity matrix against commonly-used similarity matrices (Oord et al., 2018; He et al., 2020) in unsupervised representation learning. In Figure 5, we demonstrate that DORP is able to exploit more available latent code and therefore helping the latent space to be more temporal consistent.
sections.heading: 5.4 QUANTITATIVE RESULTS
sections.text: Long-horizon planning We test the agent by its ability to solve unseen goal-directed tasks. In k-object-rearrangement, we can study the effect of the increase of the length and complexity of the tasks by increasing the number of objects. In Table 1, we demonstrate that as the number of objects increases DORP is able to succeed in most of the tasks. While other methods’ performances degrade quickly. Note that when faced with 5 objects DORP employs the extended planning version by grouping the 5 one-hots into two groups of 2 and 3 one-hots. By considering more that one object at a time, the agent is able to perform non-myopic planning and achieve 87% success rate. We also evaluate DORP on two variations of key-room. In our evaluations, we find that DORP solves keywall with a single wall and door successfully in 9 of 10 tasks. When using a ground-truth dynamics model in place of an SV2P model, DORP solves Key-Room successfully in 37 of 40 tasks, and Key-Corridor in 33 of 40 tasks.
sections.heading: 6 CONCLUSION AND FUTURE DIRECTIONS
sections.text: In this paper, we propose an unsupervised discrete representation learning method for long term planning, which can extract high level abstract states that are good for planning in an purely unsupervised manner. We demonstrate DORP’s effectiveness over other methods on challenging long horizon tasks. We note that our method generate approximate plans more tractably and hence trades off optimality for efficiency, like other state abstraction works (Savinov et al., 2018; Liu et al., 2020; Eysenbach et al., 2019). Those approximate solutions can be used to initialize a model-free policy which can be later fine-tuned to reach optimality. We leave this as our future work.