Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


A Logarithmic-Time Solution to the Point Location Problem for Closed-Form Linear MPC


C.N. Jones, P. Grieder, S. Rakovic

IFAC World Congress, Prague, Czech Republic

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 {\it 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 $\Order{c_{n,\epsilon} n\log{R}}$ for an $n$--dimensional state space and for $R$ regions, where $c_{n,\epsilon}$ is a factor depending on the state dimension and an error tolerance $\epsilon$ \cite{arya98optimal}. For MPC based on quadratic control objectives (e.g. $2$-norm), the approach may or may not be applicable, depending on the specific controller structure. As a result of this work, we demonstrate several orders of magnitude sampling speed improvement over traditional MPC and closed-form MPC schemes.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { JonGri:2005:IFA_2031,
    author={C.N. Jones and P. Grieder and S. Rakovic},
    title={{A Logarithmic-Time Solution to the Point Location Problem
	  for Closed-Form Linear MPC}},
    booktitle={IFAC World Congress},
    address={Prague, Czech Republic},
Permanent link