Efficient evaluation of piecewise control laws defined over a large number of polyhedra

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.