EMPC中基于混合树型结构的点定位算法  

A Point Location Algorithm Based on Hybrid Tree Structure in EMPC

作　　者：修晓杰[1] XIU Xiaojie(Schoolof In formation Engineering,Hangehou Dianzi Unicersity,Hangzhou Zhejiang 310018,China)

机构地区：[1]杭州电子科技大学信息工程学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2019年第3期65-72,共8页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：浙江省自然科学基金资助项目(LQY18F030001);浙江省教育资助项目(Y201533711)

摘　　要：针对显式模型预测控制中点定位问题,提出一种基于多维查找树的混合树型结构,树型结构分为"树干"、"树梢"和"叶子"三部分。"树干"部分以轴对准超平面作为划分超平面,使用分段仿射控制率数量作为计算准则;"树梢"部分以边界超平面作为划分超平面,使用二叉搜索树结构,并通过划分阈值,限制二叉搜索树的高度;混合树型结构非叶子节点保存划分超平面信息,叶子节点保存分段仿射控制率信息。实验结果表明:算法能有效减少存储需求,提高在线查找效率,并能很好地协调预处理、在线计算和存储需求之间的关系。This paper presents a method for point location problem in explicit model predictive control,by constructing a hybrid tree structure,i.e.,combining the k-dimensional tree(k-d tree)with the binary search tree(BST).The tree structure can be divided into three parts:"trunk","tree-top"and"leaf".The trunk part uses the axis to align with the hyperplane(HP)as the partition hyperplane,and uses the number of peicewise affine(PWA)control ratio as the calculation criterion;the tree-top part uses the boundary HP to construct a balanced binary search tree;non-leaf nodes preserve partition HPs and leaf nodes preserve PWA control ratio.The new method can be applied to the EMPC of high dimensional problems or of a large number of state partitions.Simulation results show that the new method can reduce memory requirement,improve online searching effectiveness,and achieve a trade-off among the preprocessing,online searching and memory storage.

关 键 词：显式模型预测控制 K-D树 二叉搜索树 混合树型结构 分段仿射控制率 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]