Probabilistic Planning with Sequential Monte Carlo methods

Alexandre Piché, Valentin Thomas, Cyril Ibrahim, Yoshua Bengio, Chris PalICLR 2019 · OpenReview

Introduction

Robot planning is traditionally viewed as a search for a single optimal path. However, this paper re-imagines planning as a probabilistic inference problem over a distribution of "optimal" future trajectories. By applying Sequential Monte Carlo (SMC) methods, the authors develop a planning algorithm capable of handling continuous actions and multimodal strategies. This approach outperforms standard model-free and model-based baselines on complex control tasks like those in the MuJoCo simulator.

The Planning Trilemma

Planning involves using a world model to predict the consequences of actions and select the best path forward. Traditional planning algorithms often face a "trilemma" of limitations:

  1. Discreteness: Methods like Monte Carlo Tree Search (MCTS) excel in discrete domains (like chess or Go) but struggle with the infinite, continuous action spaces typical in robotics.
  2. Unimodality: Popular continuous methods like the Cross Entropy Method (CEM) assume the best future actions follow a single Gaussian distribution. They cannot represent two equally viable but distinct paths (e.g., navigating left versus right around an obstacle).
  3. Linearity: Classical controllers like iLQR assume the world is locally linear and Gaussian, which frequently fails in highly non-linear environments.

The authors seek a general framework that leverages deep learning to model complex dynamics while maintaining the flexibility to represent arbitrary, multimodal distributions over future actions.

Methods: Control as Inference

The authors frame planning through the lens of "Control as Inference." They treat the agent's "optimality" as an observed variable within a Hidden Markov Model (HMM). In this view, finding the best plan is equivalent to estimating the posterior distribution of trajectories, conditioned on the assumption that the agent is acting optimally.

Graphical model of Control as Inference

To solve this inference problem, they introduce Sequential Monte Carlo Planning (SMCP), which consists of several key components:

  • Sequential Importance Resampling (SIR): Instead of sampling an entire trajectory at once, the algorithm builds it step-by-step using a set of "particles" to represent potential futures.
  • The Proposal Distribution: A learned policy—specifically from Soft Actor-Critic (SAC)—is used to suggest actions. This combines the intuitive strengths of model-free learning with the look-ahead capabilities of model-based planning.
  • Weighting and Resampling: Particles are weighted based on a "maximum entropy advantage function." At each step, low-reward particles are discarded, and high-reward particles are cloned. This focuses computational resources on the most promising regions of the state space.
  • Value Function as a "Backward Message": A crucial theoretical insight is that the "backward message" in their HMM framework is mathematically equivalent to the soft value function used in Maximum Entropy Reinforcement Learning.

Experiments and Key Results

The algorithm was evaluated on two main setups to test both its theoretical properties and its practical performance.

1. Multimodality in a Toy 2D Point Mass

A simple environment was designed where an agent must reach a goal while avoiding a central wall. This specifically tested if the algorithm could maintain a multimodal distribution (tracking viable paths both above and below the wall).

Multimodal trajectory tracking in a 2D point mass environment

SMCP successfully tracked both optimal paths around the wall. In contrast, CEM (the standard baseline) collapsed to a single path, and Sequential Importance Sampling (SIS) without resampling failed to explore effectively. The paper highlights that resampling is essential; without it, the algorithm suffers from "weight impoverishment," wasting computational effort on unlikely trajectories.

2. Performance on MuJoCo Benchmarks

The authors also tested SMCP on the standard continuous control benchmarks: HalfCheetah-v2, Hopper-v2, and Walker2d-v2. They used unmodified environments with noisy, state-dependent reward functions.

  • Sample Efficiency: SMCP learned significantly faster than the model-free SAC baseline. By using the world model to "hallucinate" futures, the agent required fewer real-world interactions to achieve high performance.
  • Asymptotic Performance: SMCP achieved higher final scores than other planning methods like CEM and Random Shooting. The results were statistically significant ($p < 0.05$) for the HalfCheetah and Walker2d environments.

Limitations and Future Work

While powerful, treating planning as density estimation comes with trade-offs:

  • Computational Overhead: SMC requires running a forward pass of the policy, value function, and world model for every particle at every planning step, making it computationally expensive compared to simple model-free execution.
  • Model Sensitivity: Like all model-based methods, SMCP is vulnerable to "model exploitation," where the planner finds a trajectory that looks highly rewarding in a flawed model but fails in the real environment.
  • Advanced SMC: The authors suggest that more sophisticated sampling techniques, such as Particle Gibbs or Ancestor Sampling, could further reduce the variance of the estimates and improve planning in even higher-dimensional spaces.

Summary updated

Abstract

In this work, we propose a novel formulation of planning which views it as a probabilistic inference problem over future optimal trajectories. This enables us to use sampling methods, and thus, tackle planning in continuous domains using a fixed computational budget. We design a new algorithm, Sequential Monte Carlo Planning, by leveraging classical methods in Sequential Monte Carlo and Bayesian smoothing in the context of control as inference. Furthermore, we show that Sequential Monte Carlo Planning can capture multimodal policies and can quickly learn continuous control tasks.
BibTeX
@inproceedings{piche2019probabilistic,
  author = {Alexandre Piché and Valentin Thomas and Cyril Ibrahim and Yoshua Bengio and Chris Pal},
  title = {{Probabilistic Planning with Sequential Monte Carlo methods}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=rGMBOz1Irxc},
}
Figure