## 3 Explicit MPC Controller Design
### Online Solution of Explicit MPC Model  
The core of the online solution is to determine the position \(\theta\) in the state partition, according to the state value of the current system. The calculating speed of this part directly affects the real-time performance of the control system. The general online solution is a sequential search. This method determines the position \(\theta\) through traversing each polyhedron, which is shown in Algorithm 1 below. However, if the number of polyhedral regions is large, the traverse takes too much time. In this paper, the efficient binary search tree (BST) method was employed. A binary tree storing polyhedrons and corresponding solutions was constructed offline in advance. ```
1:Input \(CR=\{(F_{i},\ G_{i},\ H_{i},\ K_{i})\}\), \(i=0\), \(1\),..., \(N_{r}\), \(\theta\)
2:Initialize \(i\gets 0\)
3:While \(i\leq N_{r}\)
4:if \(H_{i}\theta\leq K_{i}\) break;
5:\(i\gets i+1\);
6:endwhile
7:if\(i=N_{r}+1\) the problem is unfeasible, otherwise
8:\(U_{*}=F_{i}\theta+G_{i}\)
9:Output:\(U_{*}\)
```  
**Algorithm 1** Sequential search algorithm  
The polyhedral regions are divided into the set \(\{CR_{0},\ CR_{1},\ \ldots,\ CR_{N_{r}}\}\). Each polyhedral region is determined by a limited number of hyperplanes. The total hyperplane set is \(\left\{h_{k}=(a_{k},\ \ b_{k})|a_{k}^{T}\theta=b_{k}\right\}\), \(k=1,\ldots,K_{h}\). \(K_{h}\) is the total number of hyperplanes. The positional relationship between a hyperplane \(h_{k}\) and a polyhedron \(CR_{i}\) can be determined based on signs of \(d_{k}(\theta)\), where \(d_{k}(\theta)=a_{k}^{T}\theta-b_{k}\). The minimum of \(d_{k}(\theta)\) is \(d_{k}^{min}\). The maximum of \(d_{k}(\theta)\) is \(d_{k}^{max}\). If \(d_{k}^{min}\leq 0\) and \(d_{k}^{max}\leq 0\), \(CR_{i}\) is on the negative side of \(h_{k}\). If \(d_{k}^{min}\geq 0\) and \(d_{k}^{max}\geq 0\), \(CR_{i}\) is on the positive side of \(h_{k}\). If \(d_{k}^{min}\cdot d_{k}^{max}<0\), \(CR_{i}\) is on the both sides of \(h_{k}\). The polyhedron regions set on the negative side is \(CR_{h_{k}^{-}}\), and on the positive side is \(CR_{h_{k}^{+}}\) (polyhedrons on both sides belong to \(CR_{h_{k}^{-}}\) and \(CR_{h_{k}^{+}}\) at the same time). \(CR_{h_{k}^{-}}\) and \(CR_{h_{k}^{+}}\) can be further divided with new hyperplanes. The binary search tree is formed by following this rule recursively. The main idea of the BST method is to construct a BST tree, and select the best boundary hyperplane as the partition hyperplane, so that the number of PWA control functions is minimized from the current node of the tree to the child nodes of the next layer. The size of a node represents how many polyhedron regions the node contains, so a method that reduces the size of a node is adapted by solving the problem below:  
\[\text{min}_{k}\text{max}\Big{(}\left|CR_{h_{k}^{-}}\right|,\,\left|CR_{h_{k}^{+} }\right|\Big{)} \tag{34}\]  
where \(\left|CR_{h_{k}^{-}}\right|\) and \(\left|CR_{h_{k}^{+}}\right|\) are the sizes of sets \(CR_{h_{k}^{-}},CR_{h_{k}^{+}}\). The hyperplane \(h_{k}\) corresponding to index \(k\) is selected as the split hyperplane. A node in the binary tree, consists of the polyhedron regions set and the split hyperplane. After the construction of the binary search tree, the binary tree search algorithm is proposed. \(N_{1}\) is the highest node in a binary tree, and the explored node \(N_{e}\) is initialized by \(N_{1}\) firstly. By calculating the distance \(d_{h_{k}}\) between the split hyperplane and \(\theta\), \(N_{e}\) is updated to the child node. Until the size of the explored node \(\left|N_{e}\right|\) is 1, the search process is completed.