Efficient computation of controller partitions in multi-parametric programming

The off-line solution to optimal control problems for linear or piecewise-affine systems with constraints has garnered much attention because the on-line implementation can be realized with a simple look-up table. Specifically, multi-parametric programming techniques can be utilized to compute a piecewise-affine feedback law off-line. Even though the computation is performed off-line, the necessary computation time may easily become excessive for larger problems. This paper identifies the computation of minimal representations of polytopes as a key driver for complexity and presents an efficient method for reducing the associated computation cost. The method utilizes bounding-boxes and ray-shooting to discard redundant hyper-planes efficiently. A case study demonstrates the computational advantages.