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.


Efficient Evaluation of Piecewise Control Laws defined over a Large Number of Polyhedra


F.J. Christophersen, M. Kvasnica, C.N. Jones, M. Morari

European Control Conference (ECC), Kos, Greece

We consider the class of piecewise state feedback control laws applied to discrete-time systems, motivated by recent work on the computation of closed-form MPC controllers. The on-line evaluation of such a control law requires the determination of the state space region in which the measured state lies, in order to decide which `piece' of the piecewise control law to apply. This procedure is called the point location problem, and the rate at which it can be solved determines the minimal sampling time of the system. In this paper we present a novel and computationally efficient search tree algorithm utilizing the concept of bounding boxes and interval trees that significantly improves this point-location search for piecewise control laws defined over a large number of (possibly overlapping) polyhedra. Furthermore, the required off-line preprocessing is low and so the approach can be applied to very complex controllers. The algorithm is compared with existing methods in the literature and its effectiveness is demonstrated for large examples.


Type of Publication:


M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
  author       = {F. J. Christophersen and M. Kvasnica and C. N. Jones
                  and M. Morari},
  title	       = {{Efficient Evaluation of Piecewise Control Laws
                  defined over a Large Number of Polyhedra}},
  year	       = 2007,
  booktitle    = {Proc.~of the European Control Conference},
  address      = {Kos, Greece},
  month	       = jul,
Permanent link