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

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