PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-supervised Deep Reinforcement Learning with Generalized Computation Graphs for Robot Navigation

Gregory Kahn, Adam Villaflor, Bosen Ding, Pieter Abbeel, Sergey Levine

arXiv:1709.10489v3cs.LGcs.AIcs.RO

TL;DR

Robot navigation needs methods that learn from interaction without the computational burden and assumptions of mapping-based systems, yet conventional learning methods are sample-intensive. The paper introduces a generalized computation graph spanning model-free and model-based reinforcement learning, then applies it to raw-image navigation. The resulting approach outperformed Q-learning baselines in simulation and learned to navigate significant portions of a complex indoor environment after four hours of autonomous real-world training.

  • Problem

    Robot navigation requires learning complex policies from few samples because mapping methods impose assumptions and computational costs while learning-based methods are sample-intensive.

  • Method

    The paper introduces a generalized computation graph that subsumes model-free and model-based reinforcement learning and instantiates hybrid algorithms for navigation.

  • Results

    The approach outperformed prior Q-learning methods in simulation and navigated significant portions of a complex indoor environment from raw camera images after 4 hours of training.

  • Takeaways & Limitations

    Self-supervised reinforcement learning can produce successful real-world indoor navigation policies using raw monocular images and minimal human interaction.

  • Takeaways & Limitations

    The real-world evaluation used a self-contained, finite indoor environment, leaving large outdoor environments with dynamic obstacles as a challenge.

Abstract

from arXiv · show

Enabling robots to autonomously navigate complex environments is essential for real-world deployment. Prior methods approach this problem by having the robot maintain an internal map of the world, and then use a localization and planning method to navigate through the internal map. However, these approaches often include a variety of assumptions, are computationally intensive, and do not learn from failures. In contrast, learning-based methods improve as the robot acts in the environment, but are difficult to deploy in the real-world due to their high sample complexity. To address the need to learn complex policies with few samples, we propose a generalized computation graph that subsumes value-based model-free methods and model-based methods, with specific instantiations interpolating between model-free and model-based. We then instantiate this graph to form a navigation model that learns from raw images and is sample efficient. Our simulated car experiments explore the design decisions of our navigation model, and show our approach outperforms single-step and $N$-step double Q-learning. We also evaluate our approach on a real-world RC car and show it can learn to navigate through a complex indoor environment with a few hours of fully autonomous, self-supervised training. Videos of the experiments and code can be found at github.com/gkahn13/gcg

I. INTRODUCTION

Robot navigation must handle complex, unstructured environments without relying on costly assumptions, while learning-based methods offer adaptation and learning from failures but remain difficult to train efficiently. This paper bridges model-free and model-based reinforcement learning with a generalized computation graph and evaluates hybrid navigation policies in simulation and on a real RC car.

  • Mapping-based navigation can impose computational overhead and assumptions such as static environments or no transparent objects.
  • Learning-based navigation can adapt to environmental statistics and use failures as training data through reinforcement learning.
  • The paper introduces a generalized computation graph that subsumes value-based model-free and model-based methods, enabling hybrid navigation algorithms.
  • In simulation and real-world evaluation, the approach learned better policies than state-of-the-art reinforcement learning methods and navigated indoors from raw monocular images.
  • Model-free methods are typically less sample-efficient, whereas model-based methods struggle with high-bandwidth cameras and complex environments.

III. PRELIMINARIES

The paper formulates collision avoidance as reinforcement learning and reviews value-based model-free methods, including Q-learning and multi-step returns. These methods estimate future rewards from state-action values and trade sample efficiency against on-policy constraints.

  • Collision avoidance is formulated as reinforcement learning in which robots receive rewards for collision-free navigation.
  • Reinforcement learning learns a policy that selects actions to maximize the expected discounted sum of rewards under environment transitions.
  • Value-based model-free algorithms learn state-action Q-functions, then select actions with the highest estimated value.
  • Q-learning minimizes Bellman error using a bootstrap term and can operate off-policy because the behavior policy may be arbitrary.
  • N-step returns can improve sample efficiency, but they make Q-learning on-policy by incorporating multi-step rewards before bootstrapping.

B. Model-based reinforcement learning

Model-based reinforcement learning learns transition dynamics and selects actions by planning over predicted future states, offering sample efficiency and stability through supervised model learning. However, planning and model accuracy create practical tradeoffs, especially for high-dimensional image-based navigation.

  • Model-based methods learn a parameterized transition model that predicts the next state from the current state and action.
  • Action selection solves a finite-horizon control problem over a planned action sequence, with a known reward function.
  • Model predictive control repeatedly plans, executes only the first action, and replans at every time step.
  • Model-based methods update transition parameters by maximizing the likelihood of stored state transitions.
  • All three evaluated metrics—sample efficiency, stability, and final performance—suffer in high-dimensional state spaces such as raw images.
  • They can be sample-efficient and stable, but final performance may be poor because transition-model accuracy is only a surrogate objective.
  • The paper therefore combines model-free and model-based components to seek sample-efficient, stable, and high-performing navigation policies.

IV. A GENERALIZED COMPUTATION GRAPH FOR REINFORCEMENT LEARNING

The generalized computation graph unifies model-free value-function and model-based reinforcement learning by predicting multi-step outputs, comparing them with labels, and optimizing the resulting error. Different policy-evaluation functions and training instantiations recover standard algorithms within this framework.

  • The framework subsumes both value-based model-free methods and model-based algorithms through a shared graph, error function, and policy-evaluation function.The authors present it as a basis for sample-efficient, stable, and high-performing navigation policies.
  • N-step Q-learning is recovered with reward and future-value outputs, model horizon H = 1, N-step returns, and a Bellman-error objective.
  • Standard model-based learning is recovered by predicting the next state, using H = 1 for the model and label horizons, and minimizing prediction error.
  • The graph takes a current state and H-action sequence, predicts H outputs plus a terminal output, and compares them with N labels to form an optimization error.Solid lines represent computations involving model parameters θ, while dashed lines represent signal flow.
  • Algorithm 1 repeatedly observes a state, executes the first action of an action sequence, stores received labels, and updates the graph on the accumulated dataset.
  • Policy extraction selects the H-action sequence maximizing the generalized policy-evaluation function J(st, A^H_t).For N-step Q-learning, J uses predicted reward and future value; for model-based learning, it evaluates predicted dynamics recursively.

V. LEARNING NAVIGATION POLICIES WITH SELF-SUPERVISION

The navigation instantiation uses a recurrent neural network to predict rewards or collision probabilities from images and action sequences. Its design choices control the balance between model-free and model-based learning, policy evaluation, and training stability.

  • The navigation model is parameterized as a deep recurrent neural network to process high-dimensional images and sequential data.Past grayscale images initialize the recurrent unit, which then processes actions and hidden states across the model horizon.
  • The model can predict rewards and future value-to-go, where reward is vehicle speed and value approximates distance traveled before collision.This value representation directly encodes the navigation objective but does not use prior navigation knowledge.
  • Collision-probability outputs predict collision likelihood at each timestep and a best-case future likelihood, potentially providing a faster-learned binary signal.
  • The policy-evaluation function converts predicted outputs into collision-free navigation preferences, including maximizing expected travel or selecting actions least likely to cause collisions.Action selection solves a finite-horizon planning problem; experiments use random shooting over K sampled action sequences.
  • The model horizon H determines the model-free/model-based balance: H = 1 is fully model-free, a full-episode horizon is fully model-based, and intermediate values are hybrid.
  • Choosing a label horizon N > H can increase learning speed but makes training on-policy, whereas increasing H improves model-basedness while exponentially expanding policy-search complexity.Bootstrapping provides another way to learn about future outcomes without increasing the model horizon.

VI. EXPERIMENTS

The experiments evaluate navigation-graph design choices, comparisons with prior methods, and whether the approach can learn navigation on a real robot. The evaluation includes simulated and real-world settings, with videos and code provided online.

  • The experiments assess how navigation computation-graph design choices affect performance, how the approach compares with prior methods, and whether it succeeds on a real robot.
  • The authors provide experiment videos and code at github.com/gkahn13/gcg.

A. Simulation results

Simulation experiments use a continuously learning RC car in a cluttered indoor environment and evaluate design choices for sample efficiency, stability, and final performance.

  • The simulated RC car navigates a cluttered indoor environment using 64×36 grayscale camera images and a single steering-angle action at fixed speed.Actions are selected every dt = 0.25 seconds while the car travels at 2m/s.
  • 1 hour of simulator time produces 14,400 datapoints for the continuous-learning experiments.
  • Episodes continue from the previous endpoint until collision or 1000 meters traveled, with a hard-coded backup maneuver after collisions.
  • The simulation evaluates four navigation-graph design decisions—model output, loss function, model horizon, and bootstrapping—for sample efficiency, stability, and final performance.

1) Model outputs and loss function:

The experiments compare value versus collision-probability outputs and regression versus classification losses, showing that discrete collision prediction and cross-entropy training improve learning outcomes. Horizon effects differ by output type: longer horizons help value models but not collision-probability models.

  • Model outputs: Collision probabilities produce more sample-efficient and higher-performing policies than predicted values under the same mean squared error loss.The collision model receives separate supervision for collision timing, whereas the value model has one loss on the summed outputs.
  • Loss function: Cross-entropy training is significantly better than mean squared error training in both sample efficiency and final performance.
  • Interpretation: Predicting discrete future events can yield faster and more stable learning than predicting continuous sums of discounted rewards.The paper presents this as a finding demonstrated in robot navigation.
  • Model horizon: For value outputs, the long horizon H = 16 is more stable and produces a higher-performing final policy than the short horizon H = 1.The short-horizon model initially learns at the same speed but peaks early and then declines.
  • Model horizon: For collision-probability outputs, short and long horizons show no noticeable performance difference.The bounded 0-to-1 probabilities may reduce bootstrapping bias.

3) Bootstrapping:

Bootstrapping affects value and collision-probability models differently: removing it prevents value models from learning but has little effect on collision prediction. The selected navigation design uses collision probabilities, classification, a long horizon, and no bootstrapping, and outperforms prior simulated-navigation methods while also supporting real-world learning.

  • Bootstrapping effects: Without bootstrapping, value-output models fail to learn, whereas collision-probability models remain comparatively effective.
  • Bootstrapping effects: With bootstrapping, value-output models perform worse than collision-probability models but still benefit from bootstrapping.
  • Bootstrapping effects: Collision-prediction models are not strongly affected by whether bootstrapping is used.The results suggest that avoiding bootstrapping can be advantageous when the task is solvable within H steps.
  • Selected design: The chosen navigation instantiation outputs collision probabilities, uses classification, adopts H = 16, and omits bootstrapping.
  • Prior-work comparison: 50% better than the closest prior method, our approach learns a more stable final policy than double Q-learning and N-step double Q-learning in the simulated cluttered hallway.The comparison excludes model-based approaches because of state-knowledge or image-prediction requirements.

B. Real-world results

The approach learned a navigation policy on a real RC car in a challenging indoor environment using raw monocular images and four hours of fully self-supervised training. The system operated autonomously with asynchronous onboard inference and offboard training, while outperforming comparison policies in simulated evaluation and navigating substantial real-world distances.

  • Real-world setup: At 1.2m/s, the RC car navigated tight turns, changing illumination, and glass walls on Cory Hall’s fifth floor.The indoor environment was selected as a challenging real-world navigation setting.
  • Real-world setup: The fully autonomous system gathered data onboard, trained models offboard, and automatically detected collisions and backed up after impacts.Only recovering the car after it flipped required human intervention, occurring approximately every 30 minutes.
  • Learning outcome: After 4 hours of self-supervised training from raw camera images and no prior knowledge, the car navigated significant portions of the environment.The best trajectory covered 197m, nearly two loops or eight hallway lengths, although occasional early or late turns remained.
  • Simulation comparison: 17× farther than random and 7× farther than double Q-learning, our approach produced smoother driving than double Q-learning under the same gathered-data distribution.Double Q-learning exhibited bang-bang steering, with steering angles always at their limits.
  • Overall conclusion: The study concludes that the approach supports sample-efficient, stable, self-supervised navigation with minimal human interaction and monocular images.The broader evaluation combines simulated comparisons with the four-hour real-world RC-car result.

APPENDIX

Additional simulations compare the navigation approach with Q-learning variants across hallway complexity and reset conditions. The approach is especially stable and effective in cluttered environments and during continuous learning.

  • Comparisons with prior work: The appendix compares the approach with double Q-learning, 10-step double Q-learning, and multi-action Q-learning in empty and cluttered hallways.Each environment was tested both with episode resets and with continuous action without resets.
  • Comparisons with prior work: In empty hallways with resets, 5-step double Q-learning learned a similar policy more quickly despite the approach’s strong final performance.This comparison shows that the approach is not uniformly fastest across all settings.
  • Comparisons with prior work: During continuous learning, double Q-learning approaches were unstable, whereas multi-action Q-learning and the proposed approach were more stable.Removing resets changes the relative stability of the methods.
  • Comparisons with prior work: In complex cluttered environments, the approach was the most stable and learned the best-performing final policy.This result holds for both cluttered-hallway evaluation conditions shown in the appendix.
  • Design decisions: The appendix also evaluates output type, horizon, bootstrapping, loss, monotonic outputs, replay strategy, and episode-termination label handling.These experiments analyze design choices in the navigation computation graph under cluttered-hallway conditions without resets.

D3 Bootstrapping

The design-decision experiments compare model outputs, horizons, bootstrapping, losses, output constraints, replay, and terminal-label handling. Collision probabilities, cross-entropy training, and avoiding bootstrapping were favored for the chosen approach, while effects depended on the algorithm family.

  • D1 Model output: Collision-probability outputs performed better than expected-return outputs when the other design decisions were chosen appropriately.The comparison contrasts rows D-G with rows A-C in the cluttered hallway without resets.
  • D2 Model horizon: For multi-action Q-learning, increasing the horizon from H = 5 to H = 16 had no apparent effect, while longer horizons increased training cost roughly as O(H^2).For collision-probability outputs, H = 16 was better than H = 12, although longer horizons were not investigated.
  • D3 Bootstrapping: Removing bootstrapping significantly harmed multi-action Q-learning performance but benefited the proposed approach.The result indicates that the preferred bootstrapping choice depends on the algorithm design.
  • D4 Loss function: Cross-entropy loss was significantly better than mean squared error for the evaluated collision-probability models.The comparison uses rows F-G for cross entropy and rows D-E for mean squared error.
  • D6 Experience replay: Prioritized replay, with collision-ending experiences forming 50% of each minibatch, did not improve performance over uniform replay.Terminal samples were deliberately overrepresented in the prioritized-replay condition.
Loading 1709.10489v3…