A logarithmic-time solution to the point location problem for closed-form linear MPC

Closed-form Model Predictive Control (MPC) results in a polytopic subdivision of the set of feasible states, where each region is associated with an affine control law. Solving the MPC problem on-line then requires determining which region contains the current state measurement. This is the so-called point location problem. For MPC based on linear control objectives (e.g., 1- or α-norm), we show that this problem can be written as an additively weighted nearest neighbour search that can be solved on-line in time linear in the dimension of the state space and logarithmic in the number of regions. We demonstrate several orders of magnitude sampling speed improvement over traditional MPC and closed-form MPC schemes.