A Logarithmic-Time Solution to the Point Location Problem for Closed-Form Linear MPC
Abstract
Closed-form Model Predictive Control (MPC) results in a polytopic subdivision of the set of feasible states, where each region is associated to 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 infty-norm), we here 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.
