Source-linked AI summary
Model Predictive Path Integral Control using Covariance Variable Importance Sampling
Grady Williams, Andrew Aldrich, Evangelos Theodorou
TL;DR
The paper addresses inefficient trajectory sampling in model predictive path-integral control, where uncontrolled dynamics rarely produce useful low-cost behavior. It introduces generalized importance sampling that changes drift and diffusion, uses GPU-parallel rollout sampling, and compares MPPI with MPC-DDP in simulation. The reported experiments show MPPI outperforming DDP on two difficult control tasks while handling nonlinear dynamics and non-smooth obstacle costs.
Problem
Uncontrolled-dynamics sampling typically produces few low-cost trajectories, making real-time model predictive path-integral control difficult, particularly for nonlinear systems.
Method
The paper develops MPPI using generalized importance sampling that changes both sampling mean and variance, with parallel trajectory optimization on a GPU.
Results
MPPI outperforms a state-of-the-art DDP method on two difficult control tasks in simulation.
Takeaways & Limitations
Sampling-based control can account for nonlinear dynamics without derivatives and can use obstacle-hit impulse costs that are difficult for smooth-gradient optimization methods.
Abstract
from arXiv · showhide
In this paper we develop a Model Predictive Path Integral (MPPI) control algorithm based on a generalized importance sampling scheme and perform parallel optimization via sampling using a Graphics Processing Unit (GPU). The proposed generalized importance sampling scheme allows for changes in the drift and diffusion terms of stochastic diffusion processes and plays a significant role in the performance of the model predictive control algorithm. We compare the proposed algorithm in simulation with a model predictive control version of differential dynamic programming.
I. INTRODUCTION
Path integral control transforms stochastic optimal control into trajectory expectations that can be approximated by forward sampling. The paper motivates generalized sampling and derives a framework that addresses inefficient uncontrolled sampling while supporting nonlinear dynamics and non-smooth costs.
- The path integral framework transforms the value function into an expectation over trajectories, enabling Monte Carlo solution through forward stochastic sampling.
- Model predictive path integral control continuously optimizes an open-loop sequence while executing the current best guess, but real-time sampling is difficult for complex dynamics.
- Uncontrolled-dynamics sampling is inefficient because low-cost trajectories are unlikely, especially when nonlinear trajectories become trapped in undesirable state-space regions.
- The proposed generalized importance sampling changes both the mean and variance of the sampling distribution without violating the path-integral derivation.
- The framework assumes affine control and disturbance structure plus a cost-noise relationship requiring the noise matrix and control-cost matrix to have the same rank.
- The path-integral formulation replaces backward PDE solution with forward trajectory sampling, avoiding classical PDE methods that become intractable as state dimension grows.
A. Discrete Approximation
The continuous-time path-integral control equations are converted into discrete-time dynamics using time-step updates and Gaussian noise. This produces a sampling procedure suitable for Monte Carlo approximation of the control.
- The dynamics are discretized by writing the next state as the current state plus a time-step increment.
- The discrete increment combines drift and control over Δt with diffusion driven by a standard normal Gaussian vector.
- The uncontrolled discrete dynamics define the sampling distribution p used to approximate the path-integral expectation.
- The implementable control approximation evaluates the expectation by drawing many trajectory samples and applying a Monte Carlo approximation.
III. GENERALIZED IMPORTANCE SAMPLING
Generalized importance sampling rewrites path-integral control so trajectories can be sampled from dynamics with both nonzero control input and altered variance. The resulting likelihood ratio preserves the derivation while adding a term that penalizes overly aggressive exploration.
- Motivation: Sampling from uncontrolled dynamics is inefficient because low-cost trajectories are unlikely, especially for nonlinear systems that can enter undesirable state-space regions.The framework therefore seeks a sampling distribution more likely to produce low-cost trajectories.
- Motivation: Changing only the sampling mean can be insufficient in low-variance systems because the state space is not explored aggressively.The proposed derivation changes both the initial control input and the exploration variance.
- Importance sampling construction: The generalized scheme uses a distribution q with nonzero control input and changed variance to approximate the original path-integral expectation.The likelihood ratio converts expectations under the uncontrolled distribution p into expectations under q.
- Likelihood-ratio theorem: The theorem gives the likelihood ratio between uncontrolled trajectories p(τ) and controlled trajectories q(τ) with adjusted variance, under invertibility conditions on A_ti and Γ_i.The proof constructs discrete-time trajectory densities and simplifies their ratio through Gaussian transition probabilities and quadratic completion.
- Novelty: Unlike earlier Girsanov-based approaches, the theorem permits changing the variance as well as the mean of the sampling distribution.The likelihood-ratio expression retains the Girsanov terms and adds a quadratic term that penalizes over-aggressive exploration.
B. Likelihood Ratio as Additional Running Cost
The likelihood ratio can be incorporated into path-integral control as an additional running cost, yielding an iterative control update while removing state-independent normalization terms.
- Running-cost reformulation: The likelihood ratio is folded into the cost-to-go as an extra running cost in the path-integral formulation.Because it appears in both numerator and denominator, state-independent terms can be factored out and canceled.
- Running-cost reformulation: After cancellation of the normalization term, only the summation of the quadratic quantities Q_i remains in the relevant likelihood-ratio contribution.The reformulation uses the relationship between the sampling covariance Σ and the control-cost matrix R.
- Control update: Redefining the running cost produces the iterative update law for the control input.The resulting update is obtained after rewriting the state increment and factoring terms independent of the expectation.
C. Special Case
For the experimental special case, the generalized update becomes a rollout-based, reward-weighted average of control perturbations. The likelihood-ratio term adds the original control cost to the sampling cost.
- Special-case assumptions: The experiments use dynamics with A set to √νI and assume that G_c(x_t,t) is square and invertible.These assumptions simplify the matrix expressions used in the generalized update.
- Rollout update: The approximate update averages random control-input variations across K rollouts, weighted by each rollout’s cost-to-go S(τ_i,k).This expression is described as a reward-weighted average of random control variations.
- Likelihood-ratio simplification: For this special case, the likelihood-ratio contribution simplifies through expressions for z−µ, Γ̃^-1, and H^-1.These simplifications are used to derive the modified running cost.
- Cost interpretation: The likelihood ratio introduces the original optimal-control control cost into the sampling cost, which initially contained only state-dependent terms.This is the stated effect of the generalized importance-sampling correction in the special case.
IV. MODEL PREDICTIVE CONTROL ALGORITHM
The MPPI controller repeatedly optimizes and executes control online, requiring rapid convergence and real-time sampling of many trajectories. Tunable exploration variance supports convergence, while GPU parallelization supports large-scale sampling.
- MPPI optimizes a trajectory, executes one control, and re-optimizes using the unexecuted previous trajectory as a warm start.
- The model predictive setting requires rapid convergence because control is executed before trajectory optimization fully converges.
- The generalized importance-sampling term tunes exploration variance to enable faster convergence.
- GPU implementation runs trajectory sampling in parallel to support sampling many trajectories in real time.
V. EXPERIMENTS
The experiments evaluate MPPI on three simulated platforms at 50 Hz, comparing it with MPC-DDP for the race-car and quadrotor tasks. The algorithm is implemented through a sampling-based control loop with GPU-compatible trajectory rollouts.
- MPPI was tested on a cart-pole, a miniature race car, and a quadrotor navigating an obstacle-filled environment.
- MPC-DDP serves as the baseline for the race-car and quadrotor experiments.
- The controller operates at 50 Hz, repeatedly re-optimizing the open-loop control sequence.
- The MPPI algorithm samples K trajectories across N timesteps and updates controls using rollout costs and sampled perturbations.
- After applying the control update, the algorithm shifts the control sequence, initializes the final control, and updates the state from feedback.
A. Cart-Pole
In the cart-pole swing-up experiment, MPPI varies exploration variance and rollout count while controlling the pole over a one-second optimization horizon. Increasing exploration variance accelerates swing-up, whereas natural variance alone fails.
- The cart-pole controller runs for 10 seconds with a one-second optimization horizon, swinging up and balancing the pole.
- Figure 1 reports average running cost as a function of exploration variance ν and rollout count.
- Exploration variance ν was varied from 1 to 1500, and higher variance enabled faster pole swing-up.
- Using only the natural system variance prevented swing-up and produced a cost around 2000.
B. Race Car
The race-car task evaluates MPPI on nonlinear tire–ground dynamics while minimizing track deviation and speed error. MPPI enters turns near the desired speed and slides through them, unlike MPC-DDP, which slows before turns and has higher average cost.
- The race-car objective penalizes elliptical-track deviation and deviation from a forward speed of 7 meters/sec.
- MPPI uses exploration variance set to a constant multiple ν of the system’s natural variance.
- The average-cost comparison varies exploration variance ν from 50 to 300 and rollout count from 10 to 1000, with cost capped at 25.0.
- MPPI enters turns close to 7 m/s and slides through them, while DDP significantly reduces forward velocity before entering turns.
- The DDP behavior results in higher average cost than MPPI in the race-car task.
C. Quadrotor
The quadrotor experiments evaluate MPPI and DDP in nonlinear obstacle-filled forests, where MPPI uses obstacle-aware costs and directly reasons about crashes. The reported comparisons show MPPI taking faster, more direct routes while navigating safely closer to obstacles.
- Task setup: The quadrotor task uses a nonlinear dynamics model with cylindrical obstacles arranged in forests averaging 3, 4, or 5 meters apart.The model includes position, velocity, Euler angles, angular acceleration, and rotor dynamics.
- Task setup: MPPI and DDP use separate cost functions designed to guide the quadrotor through each forest as quickly as possible.
- Results: In the 4m obstacle field, MPPI safely takes a much more direct route than DDP by reasoning about obstacle shape.
- Results: The forest comparison reports navigation time and trajectories for MPPI and DDP in the simulated environment.
- Cost design: MPPI explicitly reasons about crashing and considers only the closest obstacle, whereas MPC-DDP uses a large exponential cost summed over nearby obstacles.The crash indicator causes a rollout to stop when the vehicle hits the ground or an obstacle.
- Results: MPPI can travel faster and closer to obstacles than MPC-DDP because its cost function directly represents crashing.
VI. CONCLUSION
The paper concludes that MPPI outperforms state-of-the-art DDP on two difficult control tasks through derivative-free stochastic trajectory sampling and GPU parallelization. Its generalized likelihood ratio permits exploration-variance tuning, while online variance adjustment remains future work.
- MPPI outperforms a state-of-the-art DDP method on two difficult control tasks without requiring derivatives of the dynamics or costs.
- The method derives a generalized likelihood ratio for discrete-time diffusion processes and uses a GPU to sample thousands of trajectories in real time.
- Tuning exploration variance is critical because the system’s natural variance is typically too low to achieve good performance.
- The experiments change variance only by a constant multiple of the system’s natural variance.
- Automatically adjusting variance online is identified as future work for switching between aggressive and conservative exploration.