Comparison between IP, SQP, and PANOC optimizers.
Model predictive control can be an excellent control method finding optimal control inputs to a system. At the heart of the control method is an optimizer. In this blog, you can read about three powerful optimization algorithms and how they perform when they control a vehicle in a complex scenario.
Model predictive control (MPC) is the big brother in control theory. One common interpretation is that as long as one has access to good computation power MPC can control very complicated systems optimally. There is a bunch of reports on the world wide web that shows simple simulations of cars driving on roads, using MPC, which might lead one to think that this is a great way to operate self–driving cars.
We set out to find out just how accurate this claim is and the limitations MPC has within this field. At the heart of the MPC algorithm is the optimization problem. It is the job of the optimizer to calculate the best series of control inputs for the car in its given environment. This thesis has, therefore, evaluated three different algorithms. Two of them are Sequential quadratic programming (SQP) and Interior-point (IP) method, which are powerful and very common optimizers for non–linear problems. The third optimizer is the Proximal Averaged Newton-type method for Optimal Control (PANOC), which is a new state of the art optimizer.
The optimizers were tested in a simulation where a road was modeled together with some obstacles. The Collision cone method was used as a collision–avoidance system, and it works by calculating the subset of relative velocities that the car can have, which will lead to a collision. Then the optimizer choose the best velocity that is not within this calculated subspace. The collision cone only works if the obstacle is moving linearly. Thus we developed our non–linear version. This method calculates the predicted collision point, which is shown as a black dot in the figures below and applies the collision cone constraint on an obstacle projected onto it.
All the optimizers managed to drive the track but with different results. In short SQP and IP are not performing very well in terms of computation speed, but SQP converges optimally. PANOC, on the other hand, converges very fast, around 33 ms per optimizer call, and is not as sensitive to disturbance. Unlike the others, PANOC can also be initiated from any arbitrary starting point and still manages to converge well.
What follows is a recommendation of application for the optimizers with this thesis as a foundation for the rating.
IP is recommended for lightly constrained problems. The environment should be a linear and smooth environment. If the solution is located close to or on difficult constraint borders, IP will have a hard time converging to a solution.
SQP is best used in medium to highly constrained environments that are not time–critical. If the algorithm can be given enough computational time, it will improve the quality of the solution and is, therefore, suitable for systems that are unstable or if the need for an optimal solution is high. For mildly constrained environments, the need for a warm start is not that high. The algorithm can be used in non–linear, non-smooth environments, given that it is warm started with a guess close to the solution.
PANOC can be used in time–critical systems due to its superior convergence rate. It will rapidly provide a solution. It can also be used in highly constrained environments and even non-smooth and non–linear ones. It should not be used in said complicated environments if the system is unstable or if the requirements on optimal output are high since it is not reliable. The output should be checked so that it meets the specified requirements. PANOC is a suitable choice when there is no way to warm start the optimizer with a good initial guess since it can converge fast from any initial state.
Why PANOC is superior in terms of computation speed is due to that it is constructed with very cheap operations, and it cleverly combines the proximal operator with a quasi-newton method. These two methods together deliver an algorithm that is both fast and, thanks to the proximal operator, can converge in non-smooth highly non–linear environments. PANOC exhibits a couple of strange behaviors, and the cause of these was not found. It does not converge optimally from time to time, and this behavior does not improve with increased computation time. PANOC is definitely a worthy candidate and will most probably find its way out in the market due to its superior advantage in the field of non–linear non-smooth applications such as embedded MPC controllers for autonomous systems.
In general, the environment that has to be modeled for a car to be able to drive in a realistic setting is to complex for current optimizers. MPC can not be used as a controller on its own. For it to give reliable results, the problem has to be simplified a lot so that more accurate response time and convergence can be guaranteed. One possible solution could be to split the optimization problem into two parts. For example, by having one optimization algorithm focusing on driving in its lane and avoid collisions, while another one determines when it’s possible to perform an overtaking maneuver. This could simplify the environment enough to allow the algorithms to behave more reliably.