Research On Point Location Algorithm In Explicit Model Predictive Control

Explicit model predictive control(EMPC)moves the online computational burden of linear model predictive control(MPC)to offline computation by using multi-parametric quadratic 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,and this is called the point location problem.The performance of it determines the performance of EMPC and its applications.EMPC aims at expanding the application to the new field that MPC is not good at.Although the problem is tractable and practically solvable for many interesting control applications,the online computational effort and memory demands grow fast as the problem size increases,especially with large number of state partitions and high dimensional state space.The problem of point location has become hot research topics in society of explicit model predictive control.Based on multi-parametric quadratic programming theory,polytope theory,piecewise affine theory and computer data structure theory,the point location problem with large number of state partitions and high dimensional state space is investigated.The purpose of the study is to improve the online computing efficiency,reduce the memory demand and preprocessing time,and tradeoff among them.The main results are obtained as follows.1.The paper studies and summarizes the literatures of point location algorithms,and based on that,the hash table algorithm and BST algorithm are improved.The improved hash table algorithm needs relatively fewer memory demands than before,and the improved BST algorithm reduces the preprocessing time obviously.2.Besides searching the partitions one by one,hash table and binary search tree(BST)are used as two efficient solutions in point location.However,the hash table method needs more memory storage,and the process of building the BST becomes extremely complex and needs much preprocessing time.This paper proposes some ideas of constructing the data lookup table and the corresponding improved structure using multi-level hash structure.By setting a threshold,each hash grid has roughly the same number of the piecewise affine control laws.However,the efficiency is low and the memory demand is big by searching directly in the hash grid.The improved algorithm uses BST to construct in each hash grid,which reduces the online computing time significantly and the memory demand especially when the state partitions and the piecewise affine control laws are in a large number.3.This paper presents an approach of constructing a hybrid data structure called constructed k-d tree,which combines the k-dimensional tree(k-d tree)with the binary search tree(BST)for point location in the polyhedral sets.To maintain a ?full‘ and balanced constructed tree the number of affine control laws is used as the basis for choosing the separating hyperplanes(HPs)during the main construction process of the hybrid tree,thus improving offline efficiency by reducing the number of candidate HPs requiring computation.This methodology can be applied to the EMPC of high dimensional problems as the k-d tree(the main body of the hybrid tree)has already been successfully used to solve high dimensional problems in the field of computer science and engineering.The method involves a trade-off between memory storage requirement and online efficiency.4.This paper deals with efficient point location in larger polyhedral data sets and proposes a multiway data structure,grid k-d tree(GKDT),which is constructed by k-dimensional tree(k-d tree),hash table and binary search tree(BST).The main part of the structure is a multiple branch tree which constructs subtrees by splitting the polyhedral region into several equal grids based on k-d tree and traversed by the hash function on each level.GKDT has a high searching efficiency,even though it needs much more storage memory.5.It is a preliminary attempt to apply the EMPC method to 3-DOF helicopter and the study of the validation of the point location algorithm is made in the paper.On the basis of the dynamics principle of 3-DOF helicopter,the characteristic of control system,a control model of 3-DOF helicopter is built and the state partitions and their corresponding PWA control laws are computed by mp-QP.Controller and the corresponding simulation structure for regulation and tracking simulation are designed and the simulations are conducted.Based on the results of simulation,the paper analyses the influence factor of EMPC.The effectiveness of the proposed methods are verified by numerical experiments.Finally,the conclusion and future work are presented.