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.


Optimized Decision Trees for Point Location in Polytopic Data Sets - Application to Explicit MPC


A. Fuchs

American Control Conference, Baltimore, USA

Presentation of conference paper :

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 mixedinteger 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.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% No recipe for automatically generating a BibTex entry for (06)Talk
Permanent link