On the choice of the linear decision functions for point location in polytopic data sets - Application to Explicit MPC

This paper deals with efficient point location in large polytopic data sets, as required for the implementation of Explicit Model Predictive Control laws. The focus is on linear decision functions (LDF) which performs scalar product evaluations and an interval search to return the index set of candidate polytopes possibly containing the query point. We generalize a special LDF which uses the euclidean directions of the state space and the projection of the polytopes bounding boxes onto these directions to identify the candidate polytopes. Our generalized LDF may use any vector of the state space as direction and the projection of any points contained in the polytopes. We prove that there is a finite number of LDFs returning different index sets and show how to find the one returning the lowest worst-case number of candidate polytopes, a number that can be seen as a performance measure. Based on the results from an exhaustive study of low complexity problems, heuristics for the choice of the LDF are derived, involving the mean shift algorithm from pattern recognition. The result of extensive simulations on a larger problem attest the generalized LDF a 40% gain in performance, mainly through adjusted directions, at a small additional storage cost.