ABSTRACT
Explicit model predictive control (EMPC) moves the online computational burden of linear model predictive control (MPC) to offline computation by using multi-parametric programming which produces control laws defined over a set of polyhedral regions in the state space. The online computation of EMPC is to find the corresponding control law according to a given state, this is called the point location problem. This paper deals with efficient point location in larger polyhedral data sets. The authors propose a hybrid data structure, grid k-d tree (GKDT), which is constructed by the k-dimensional tree (k-d tree), hash table and binary search tree (BST). The main part of GKDT is a multiple branch tree which constructs subtrees by splitting the polyhedral region into several equal grids based on the k-d tree and is traversed by the hash function on each level. GKDT has a high search efficiency, even though it needs much more storage memory. A complexity analysis of the approach in the runtime and storage requirements is provided. Advantages of the method are supported by two examples in the paper.
Acknowledgements
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions that helped improve the manuscript. The authors would also like to thank the Automatic Control Laboratory of ETHZ for providing MPT, a Matlab toolbox for multi-parametric optimisation and computational geometry.
Disclosure statement
No potential conflict of interest was reported by the author(s).