Grid k-d tree approach for point location in polyhedral data sets – application to explicit MPC

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.

KEYWORDS:

• Explicit model predictive control
• point location
• binary search tree
• k-d tree
• grid k-d tree

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

Additional information

Funding

The work is supported by the Natural Science Foundation of Zhejiang Province, China (LQY18F030001).