Model Predictive Path Integral

Topics: Model Predictive Control

Introduction

Model Predictive Path Integral (MPPI) is a sampling-based model predictive control algorithm. It is, in a sense, a Monte Carlo MPC, where control inputs are sampled from predefined distributions and are propagated through the dynamics model to generate a large set of candidate trajectories. The algorithm scores the candidate trajectories, ranks them, and updates the distribution of actions by weighting the best trajectories.

MPPI is particularly effective for:

• Nonlinear dynamics, where motion isn’t simple or linear.
• Non-convex objectives, multiple possible paths or goals.
• Real-time decision-making in dynamic environments

Algorithm Structure

The MPPI algorithm starts with a vector/matrix of "nominal" control inputs $u$ and disturbance distribution $\delta u$ (usually Gaussian) for every step in the finite control horizon. For example, if $T=5$ and $u\in\mathbb{R}^2$, then there are $5\times2=10$ control inputs and disturbance distributions.

The algorithm follows the below structured steps:

1. Trajectory generation: sample control inputs from the distributions ($u+\delta u_k$) and propagate them through the system dynamics to obtain a large set of $k$ trajectories. The number of trajectories depends on the computation capabilities, but is usually in the hundreds or thousands. This enables the exploration of several candidate trajectories through stochastic sampling.

2. Cost Computation: evaluate each trajectory based on a predefined cost function

3. Control Update: First, assign a higher weight to the trajectories with lower cost using a softmax function:
   $w_k = e^{-\frac{1}{\lambda} S_k}$
   where $w_k$ and $S_k$ are the weight and cost of trajectory $k$ respectively, and $\lambda$ is a parameter that affects the degree of weighting.

   Then, update the nominal control sequence by computing a weighted average of the sampled control inputs:
   $u \leftarrow u + \frac{\sum_k w_k \, \delta u_k}{\sum_k w_k}$
   The algorithm then employs a receding horizon strategy, meaning that only the first control input of the nominal trajectory is applied to the system, and the whole process repeats for the next timestep.

Pseudocode

References

1. https://www.mathworks.com/help/robotics/ug/local-path-planning-using-model-predictive-path-integral.html
2. https://www.youtube.com/watch?v=19QLyMuQ_BE