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

Author(s):C.N. Jones, P. Grieder, S. Rakovic |
Conference/Journal:IFAC World Congress, Prague, Czech Republic |

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 {\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. | Year:2005 |

Type of Publication:(01)Article | |

Supervisor: | |

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}, pages={}, year={2005}, address={Prague, Czech Republic}, month=jul, url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=2031} } | |

Permanent link |