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.     

Using a Two‐Level Structure to Manage the Point Location Problem in Explicit Model Predictive Control

The problem of determining the state region in which the current state point lies is referred to as the point location problem in the explicit model predictive control. In this paper, a two‐level structure to store the state regions is proposed and two efficient methods for solving the point‐location problem are developed; these are the two‐level grid (TLG) method and the grid‐BST method. The TLG method uses a tow‐level hash table. Before building the two‐level structure, the synonymy partitions are merged to reduce the memory storage demand. By setting each parameter in a triplet, the two‐level hash table can reach its optimal state and balance the complexity among the memory storage, reprocessing (offline computation) and the online computation. The grid‐BST method uses hash table as the first‐level structure and builds the binary search tree in the hash grid in which there are many partitions. This two‐level structure reduces reprocessing time significantly especially when the state partitions and the piecewise affine control laws (PWA control laws) are in a large number. Using the hyperplane (HP) as the node (not leaf node) of the tree, the method only stores all the different PWA control laws instead of the state partitions. The two proposed methods overcome the quick complexity growth when the number of polyhedral partitions increases and 2 numerical examples show the advantages of the proposed two methods.     

Guaranteed Feasible Control Allocation using Model Predictive Control

This paper proposes a guaranteed feasible control allocation method based on the model predictive control. Feasible region is considered to guarantee the determination of the desired virtual control signal using the pseudo inverse methodology and is described as a set of constraints of an MPC problem. With linear models and the given constraints, feasible region defines a convex polyhedral in the virtual control space. In order to reduce the computational time, the polyhedral can be approximated by a few axis aligned hypercubes. Employing the MPC with rectangular constraints substantially reduces the computational complexity. In two dimensions, the feasible region can be approximated by a few rectangles of the maximum area using numerical geometry techniques which are considered as the constraints of the MPC problem. Also, an active MPC is defined as the controller to minimize the cost function in the control horizon. Finally, several simulation examples are employed to illustrate the effectiveness of the proposed techniques.     

An off-line robust MPC algorithm for uncertain polytopic discrete-time systems using polyhedral invariant sets

In this paper, an off-line synthesis approach to robust model predictive control (MPC) using polyhedral invariant sets is presented. Most of the computational burdens are moved off-line by computing a sequence of state feedback control laws corresponding to a sequence of polyhedral invariant sets. At each sampling time, the smallest polyhedral invariant set that the currently measured state can be embedded is determined. The corresponding state feedback control law is then implemented to the process. The controller design is illustrated with two examples. Comparisons between the proposed algorithm and an ellipsoidal off-line robust MPC algorithm have been undertaken. The proposed algorithm yields a substantial expansion of the stabilizable region. Therefore, it can achieve less conservative result as compared to an ellipsoidal off-line robust MPC algorithm.     

Novel MPC‐Based Fault Tolerant Tracking Control Against Sensor Faults

The problem of active fault‐tolerant tracking control with control input and system output constraints is studied for a class of discrete‐time systems subject to sensor faults. A time‐varying fault‐tolerant observer is first developed to estimate the real system state from the faulty sensor output and control input signals. Then by using the estimated state at each time step, a model predictive control (MPC)‐based fault‐tolerant tracking control scheme is presented to guarantee the desired tracking performance and the given input and output constraints on the faulty system. In comparison with many existing fault‐tolerant MPC methods, its main contribution is that the proposed state estimator is designed by the simple and online numerical computation to tolerate the possible sensor faults, so that the regular MPC algorithm without fault information can be adopted for the online calculation of fault‐tolerant control signal. The potential recursive infeasibility and computational complexity due to the faults are avoided in the scheme. Additionally, the closed‐loop stability of the post‐fault system is discussed. Simulative results of an electric throttle control system verify the effectiveness of the proposed method.     

Design of explicit model predictive control for constrained linear systems with disturbances

On-line model predictive control approaches require the online solution of an optimization problem. In contrast, the explicit model predictive control moves major part of computation offline. Therefore, eMPC enables one to implement a MPC in real time for wide range of fast systems. The eMPC approach requires the exact system model and results a piecewise affine control law defined on a polyhedral partition in the state space. As an important limitation, disturbances may reduce performance of the explicit model predictive control. This paper presents efficient approach for handling the problem of using eMPC for constrained systems with disturbances. It proposes an approach to improve performance of the closed loop system by designing a suitable state and disturbance estimator. Conditions for observability of the disturbances are considered and it is depicted that applying the disturbance’s estimation leads to rejection of the response error. It is also shown that the proposed approach prevents the reduction of feasible space. Simulation results illustrate the advantages of this approach.     

An improved robust model predictive control for linear parameter‐varying input‐output models

This paper describes a new robust model predictive control (MPC) scheme to control the discrete‐time linear parameter‐varying input‐output models subject to input and output constraints. Closed‐loop asymptotic stability is guaranteed by including a quadratic terminal cost and an ellipsoidal terminal set, which are solved offline, for the underlying online MPC optimization problem. The main attractive feature of the proposed scheme in comparison with previously published results is that all offline computations are now based on the convex optimization problem, which significantly reduces conservatism and computational complexity. Moreover, the proposed scheme can handle a wider class of linear parameter‐varying input‐output models than those considered by previous schemes without increasing the complexity. For an illustration, the predictive control of a continuously stirred tank reactor is provided with the proposed method.     

A logarithmic-time solution to the point location problem for parametric linear programming

The optimiser of a (multi) parametric linear program (pLP) is a piecewise affine function defined over a polyhedral subdivision of the set of feasible states. Once this affine function has been pre-calculated, the optimal solution can be computed for a particular parameter by determining the region that contains it. This is the so-called point location problem. In this paper, we show that this problem can be written as an additively weighted nearest neighbour search that can be solved in time linear in the dimension of the state space and logarithmic in the number of regions.

It is well-known that linear model predictive control (MPC) problems based on linear control objectives (e.g., 1- or ∞-norm) can be posed as pLPs, and on-line calculation of the control law involves the solution to the point location problem. Several orders of magnitude sampling speed improvement are demonstrated over traditional MPC and closed-form MPC schemes using the proposed scheme.     

Model predictive control using reduced order models: Guaranteed stability for constrained linear systems

The problem of controlling a high-dimensional linear system subject to hard input and state constraints using model predictive control is considered. Applying model predictive control to high-dimensional systems typically leads to a prohibitive computational complexity. Therefore, reduced order models are employed in many applications. This introduces an approximation error which may deteriorate the closed loop behavior and may even lead to instability. We propose a novel model predictive control scheme using a reduced order model for prediction in combination with an error bounding system. We employ the explicit time and input dependent bound on the model order reduction error to achieve design conditions for constraint fulfillment, recursive feasibility and asymptotic stability for the closed loop of the model predictive controller when applied to the high-dimensional system. Moreover, for a special choice of design parameters, we establish local optimality of the proposed model predictive control scheme. The proposed MPC approach is assessed via examples demonstrating that a good trade-off between computational efficiency and conservatism can be achieved while guaranteeing constraint satisfaction and asymptotic stability.     

基于多参数规划的显式模型预测系统设计的可行域扩张算法

基于约束线性优化控制问题的多参数二次规划求解方法, 提出设计显式模型预测控制系统的可行域逐步扩张算法. 首先建立一种求取优化控制问题输出不变集的迭代算法. 以该输出不变集作为多参数规划问题中状态区域约束限制的初始条件, 通过反复求解多参数规划问题和不断改变状态区域约束限制, 能够逐步扩大显式模型预测控制系统的无限时间可行区域, 直到可行域不再继续扩大. 算法收敛时设计得到的显式模型预测控制系统在其所有的状态分区上都是无限时间可行的. 通过数值仿真计算, 验证本文提出算法的有效性.     

Economic MPC of nonlinear systems with nonmonotonic Lyapunov functions and its application to HVAC control

This paper proposes a Lyapunov‐based economic model predictive control (MPC) scheme for nonlinear systems with nonmonotonic Lyapunov functions. Relaxed Lyapunov‐based constraints are used in the MPC formulation to improve the economic performance. These constraints will enforce a Lyapunov decrease after every few steps. Recursive feasibility and asymptotical convergence to the steady state can be achieved using Lyapunov‐like stability analysis. The proposed economic MPC can be applied to minimize energy consumption in heating ventilation and air conditioning control of commercial buildings. The Lyapunov‐based constraints in the online MPC problem enable the tracking of the desired set‐point temperature. The performance is demonstrated by a virtual building composed of 2 adjacent zones.     

Globally robust explicit model predictive control of constrained systems exploiting SVM‐based approximation

This paper presents a systematic method to address the reduction of online computational complexity and infeasibility problem of explicit model predictive control for constrained systems under external disturbance. In feasible state space, in order to avoid the expensive database searching procedure, support vector machine‐based approximation is proposed to yield a novel unified explicit optimal control law rather than a piecewise affine one developed by explicit model predictive control. In infeasible state space, through constructing finite maximum control invariant sets around fictitious equilibrium points, a reachable controller is devised to steer the infeasible state asymptotically to the feasible state space without violating the hard constraint. Consequently, global robustness is guaranteed by introducing a minimum robust positively invariant set by means of the tube‐based technique, despite the coexistence of external disturbance and training error. Finally, the performance of the presently proposed control law is evaluated through three groups of numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

Approximate explicit constrained linear model predictive control via orthogonal search tree

Solutions to constrained linear model predictive control problems can be precomputed off-line in an explicit form as a piecewise linear state feedback on a polyhedral partition of the state-space, avoiding real-time optimization. We suggest an algorithm that can determine an approximate explicit piecewise linear state feedback by imposing an orthogonal search tree structure on the partition. This leads to a real-time computational complexity that is logarithmic in the number of regions in the partition, and the algorithm yields guarantees on the suboptimality, asymptotic stability and constraint fulfillment.     

Input‐to‐state stability of min‐max MPC scheme for nonlinear time‐varying delay systems

This paper studies the robustness problem of the min–max model predictive control (MPC) scheme for constrained nonlinear time‐varying delay systems subject to bounded disturbances. The notion of the input‐to‐state stability (ISS) of nonlinear time‐delay systems is introduced. Then by using the Lyapunov–Krasovskii method, a delay‐dependent sufficient condition is derived to guarantee input‐to‐state practical stability (ISpS) of the closed‐loop system by way of nonlinear matrix inequalities (NLMI). In order to lessen the online computational demand, the non‐convex min‐max optimization problem is then converted to a minimization problem with linear matrix inequality (LMI) constraints and a suboptimal MPC algorithm is provided. Finally, an example of a truck‐trailer is used to illustrate the effectiveness of the proposed results. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Model predictive control of constrained LPV systems

This article considers robust model predictive control (MPC) schemes for linear parameter varying (LPV) systems in which the time-varying parameter is assumed to be measured online and exploited for feedback. A closed-loop MPC with a parameter-dependent control law is proposed first. The parameter-dependent control law reduces conservativeness of the existing results with a static control law at the cost of higher computational burden. Furthermore, an MPC scheme with prediction horizon ‘1’ is proposed to deal with the case of asymmetric constraints. Both approaches guarantee recursive feasibility and closed-loop stability if the considered optimisation problem is feasible at the initial time instant.     

Switched model predictive control for performance enhancement

This article presents a switched model predictive control (MPC) algorithm for non-linear discrete time systems where the weights on the state and control variables in the cost function to be minimised depend on the current value of the state. In so doing, with a reduced computational burden one can easily include, in the problem formulation, a number of control specifications, such as the requirement to avoid critical regions in the state space or to reduce as much as possible the use of some actuators in other zones of the state space. The proposed MPC method has stability properties and is applied for control of a thermal system. The reported simulation results witness its favourable characteristics with respect to a standard MPC implementation.     

Distributed Model Predictive Control Method for Optimal Coordination of Signal Splits in Urban Traffic Networks

Coordination and control approaches based on model predictive control (MPC) have been widely investigated for traffic signal control in urban traffic networks. However, due to the complex non‐linear characters of traffic flows and the large scale of traffic networks, a basic challenge faced by these approaches is the high online computational complexity. In this paper, to reduce the computational complexity and improve the applicability of traffic signal control approaches based on MPC in practice, we propose a distributed MPC approach (DCA‐MPC) to coordinate and optimize the signal splits. Instead of describing the dynamics of traffic flow within each link of the traffic network with a simplified linear model, we present an improved nonlinear traffic model. Based on the nonlinear model, an MPC optimization framework for the signal splits control is developed, whereby the interactions between subsystems are accurately modeled by employing two interconnecting constraints. In addition, by designing a novel dual decomposition strategy, a distributed coordination algorithm is proposed. Finally, with a benchmark traffic network, experimental results are given to illustrate the effectiveness of the proposed method.     

A parametric branch and bound approach to suboptimal explicit hybrid MPC

In this article we present a parametric branch and bound algorithm for computation of optimal and suboptimal solutions to parametric mixed-integer quadratic programs and parametric mixed-integer linear programs. The algorithm returns an optimal or suboptimal parametric solution with the level of suboptimality requested by the user. An interesting application of the proposed parametric branch and bound procedure is suboptimal explicit MPC for hybrid systems, where the introduced user-defined suboptimality tolerance reduces the storage requirements and the online computational effort, or even enables the computation of a suboptimal MPC controller in cases where the computation of the optimal MPC controller would be intractable. Moreover, stability of the system in closed loop with the suboptimal controller can be guaranteed a priori.     

Model predictive control for constrained uncertain piecewise linear systems

For constrained piecewise linear (PWL) systems, the possible existing model uncertainty will bring the difficulties to the design approaches of model predictive control (MPC) based on mixed integer programming (MIP). This paper combines the robust method and hybrid method to design the MPC for PWL systems with structured uncertainty. For the proposed approach, as the system model is known at current time, a free control move is optimized to be the current control input. Meanwhile, the MPC controller uses a sequence of feedback control laws as the future control actions, where each feedback control law in the sequence corresponds to each partitions and the arbitrary switching technique is adopted to tackle all the possible switching. Furthermore, to reduce the online computational burden of MPC, the segmented design procedure is suggested by utilizing the characteristics of the proposed approach. Then, an offline design algorithm is proposed, and the reserved degree of freedom can be online used to optimize the control input with lower computational burden.