How To Run MPC Faster | Understanding Model Predictive Control, Part 5

In this video, we’ll discuss implementation tips for running MPC faster. We’ll continue using the pancake metaphor from the previous video. Feeding people pancakes is a complex process. You need to prepare the mix, cook the pancakes, and serve them fast before customers run out of patience. Another challenge is that you have limited space in your restaurant to store all these ingredients.

Similarly, MPC is computationally complex. One of the reasons for this is that model predictive control solves an online optimization problem at each time step. An MPC problem is formulated as a QP problem that tries to minimize a quadratic cost function. MPC computations get more complex with the increasing number of states, constraints, the length of the control, and prediction horizons. If an MPC controller is running on a big server for an application with slow dynamics such as in the process industry, then the computational complexity shouldn’t be a big concern. However, let’s say that you want to deploy your MPC algorithm to the ECU of an autonomous vehicle. Then the optimization problem needs to be solved within a small sampling interval in the order of milliseconds. Another challenge is that your embedded hardware has limited memory. The matrices that need to be stored for MPC computations grow rapidly with increasing number of optimization variables, but you need to make sure that you don’t run out of memory.

What are some ways to increase throughput and reduce memory usage? For the pancakes example, if there are ingredients that don’t contribute much to the taste but take a lot of time to prepare, you can remove them from your recipe. This will reduce the prepping and serving time and will make it easier to store all the ingredients in a limited space. Similarly, to reduce the complexity and the computation time of MPC, you can try to apply model order reduction techniques that are used to discard the states that don’t contribute to the dynamics of the system. This will also help reduce the memory footprint of the controller. Other things you can try to deal with throughput and memory are to use a shorter control and prediction horizon, reduce the number of constraints, and use lower-precision operations and data representation for implementing MPC.

You can try these quick tips to implement MPC for applications with a small sample time. But if you need to control systems with an even smaller sample time, then you can try using explicit MPC. The pancake analogy for explicit MPC would be as follows. Instead of mixing the ingredients each time you cook a pancake, you can use a premade pancake mix that will allow you to cook faster. Instead of solving the optimization problem online for the current state, explicit MPC solves it offline for all the states within a given range. For each x value within a given range, explicit MPC precomputes the optimal solution. It turns out that this solution consists of linear functions that are piecewise affine and continuous in x. Any constraint cuts the solution space into regions, and each region maps into a unique optimal solution. Expanding this idea to a two-state system would look like this. After computing the optimal solution offline, all MPC does online is to find the region that the current state lies in and evaluate the linear function to create the current control action. Reducing the iterative optimization process to linear function evaluation greatly simplifies the run-time computations. So, explicit MPC can be deployed for applications with a very small sample time.

Having pre-made mix is great, but if you have a wide variety of flavors, it takes time to find the one you’re looking for. And for each different flavored mix, you’ll need additional space in your limited storage. Similarly, if there are many regions, it may be time consuming to search for the region where the current state lies in.  Also, storing all these regions requires a large memory footprint. There are techniques to reduce the number of regions by merging them together. However, in that case the solution is no longer optimal.

Another method for running MPC faster is to use the suboptimal solution. Back to the pancake analogy: the serving time can change greatly based on how fancy the plate is decorated. Customers who don’t want to wait long can pick the basic pancake option from the menu. Others who are more patient and can wait longer can go with the fancier options. In an MPC problem, the number of iterations to find the optimal solution is totally unpredictable and can change dramatically from one time step to another. In the worst case, the computation time may exceed the controller sample time. However, you want to make sure that a solution is found within the sample time and that there’s even some extra time left for other tasks that need to be executed on the hardware. To deal with this, you can determine a maximum value for the number of optimization iterations. This example demonstrates that it would take 10 iterations to find the optimal solution. However, since the maximum number of iterations is set to 5, when it’s reached, the controller stops the optimization and uses the suboptimal solution from that iteration. Note that this is a suboptimal solution, but it still satisfies all the constraints of the optimization problem. To determine the maximum number of iterations, you can test your algorithm on your hardware and identify the execution time used by each iteration. Assuming that each iteration takes a similar execution time, you can choose the maximum number of iterations such that the total execution time does not exceed the controller sample time.

In summary, to run MPC faster, you can first try these quick tips and see if they work well for your system. For fast applications with a very small sample time, you can use explicit MPC, which reduces the run-time computations greatly by precomputing the optimal solution offline. Another option to increase throughput and also guarantee the worst-case execution time for your MPC controller is to use suboptimal solution.

In the next video, we’ll use an autonomous vehicle steering system example in Simulink to demonstrate how you can design an MPC controller using the MPC Designer app.