Optimal decision trees for point location in polytopic data sets - application to explicit MPC

Explicit Model Predictive Control (EMPC) produces control laws defined over a set of polytopic regions in the state space. In this paper we present a method to create a binary search tree for point location in such polytopic sets, in order to provide a fast lookup of the control law corresponding to a given state. We use hyperplanes as decision criteria that are, contrary to previous works, not constrained to the boundaries of the polytopes. Each hyperplane is the solution of a mixed-integer optimization problem with two objectives: having the same number of polytopes on either side of the hyperplane and minimizing the number of polytopes cut by the hyperplane. Contrary to previous approaches, the method can be applied to polytopic sets where the polytopes are either adjacent with common facets (for classical EMPC) or separated in space (for suboptimal EMPC). There are two benefits using this approach: First, the method optimizes the balance of the tree. If a tree of the theoretically lowest possible depth (i.e. log2 depth) exists, the algorithm will find it, although the time to solve the optimization problem may become prohibitive for large problems. Second, the method provides an efficient evaluation of suboptimal EMPC policies since it allows to maximize the distance of the hyperplane to the closest polytope that is not intersected.