A major challenge in the transportation industry is how to reduce the emissions of greenhouse gases. One way of achieving this in vehicles is to drive more fuel-efficiently. One recently developed technique that has been successful in reducing the fuel consumption is the look-ahead cruise controller, which utilizes future conditions such as road topography. In this this thesis, similar methods are used in order to reduce the fuel consumption of heavy-duty vehicles driving in environments where the required and desired velocity vary. The main focus is on vehicles in urban driving, which must alter their velocity due to, for instance, changing legal speed restrictions and the presence of intersections. The driving missions of such vehicles are here formulated as optimal control problems. In order to restrict the vehicle to drive in a way that does not deviate too much from a normal way of driving, constraints on the velocity are imposed based on statistics from real truck operation. In a first approach, the vehicle model is based on forces and the cost function involves the consumed energy. This problem is solved both offline using Pontryagin's maximum principle and online using a model predictive controller with a quadratic program formulation. Simulations show that 7 % energy can be saved without increasing the trip time nor deviating from a normal way of driving. In a second approach, the vehicle model is extended to include an engine and a gearbox with the objective of minimizing the fuel consumption. A fuel map for the engine and a polynomial function for the gearbox losses are extracted from experimental data and used in the model. This problem is solved using dynamic programming taking into consideration gear changes, coasting with gear and coasting in neutral. Simulations show that by allowing the use of coasting in neutral gear, 13 % fuel can be saved without increasing the trip time or deviating from a normal way of driving. Finally, an implementation of a rule-based controller into an advanced vehicle model in highway driving is performed. The controller identifies sections of downhills where fuel can be saved by coasting in neutral gear. / En stor utmaning för transportsektorn är hur utsläppen av växthusgaser ska minskas. Detta kan åstadkommas i fordon genom att köra bränslesnålare. En nyligen utvecklad teknik som har varit framgångsrik i att minska bränsleförbrukningen är framförhållningsreglering, som använder framtida förhållanden så som vägtopografi. I denna avhandling används liknande metoder för att minska bränsleförbrukningen i tunga fordon som kör i miljöer där önskad och tvingad hastighet varierar. Fokus ligger framförallt på fordon i stadskörning, där hastigheten måste varieras beroende på bland annat hastighetsbegränsningar och korsningar. Denna typ av körning formuleras här som optimala reglerproblem. För att hindra fordonet från att avvika för mycket från ett normalt körbeteende sätts begränsningar på tillåten hastighet baserat på statistik från verklig körning. Problemet angrips först genom att använda en fordonsmodell baserad på krafter och en kriteriefunktion innehållande energiförbrukning. Problemet löses både offline med Pontryagin's maximum princip och online med modellprediktiv reglering baserad på kvadratisk programmering. Simuleringar visar att 7 % energi kan sparas utan att öka körtiden eller avvika från ett normalt körbeteende. Problemet angrips sedan genom att utöka fordonsmodellen till att också innehålla motor och växellåda med målet att minimera bränsleförbrukningen. Specifik bränsleförbrukning och en polynomisk approximation av förlusterna i växellådan är extraherade från experiment och används i simuleringarna. Problemet löses genom dynamisk programmering som tar hänsyn till växling, släpning och frirullning. Simuleringar visar att 13 % bränsle kan sparas utan att öka körtid eller avvika från normalt körbeteende genom att tillåta frirullning. Slutligen görs en implementering av en regelbaserad regulator på en avancerad fordonsmodell för ett fordon i motorvägskörning. Regulatorn identifierar sektioner med nedförsbackar där bränsle kan sparas genom frirulllning. / <p>QC 20171011</p>

This work proposes a series of driver assistance technologies that enable blind persons to safely and independently operate an automobile on standard public roads. Such technology could additionally benefit sighted drivers by augmenting vision with suggestive cues during normal and low-visibility driving conditions. This work presents a non-visual human-computer interface system with passive and adaptive controlling software to realize this type of driver assistance technology. The research and development behind this work was made possible through the Blind Driver Challenge® initiative taken by the National Federation of the Blind. The instructional technologies proposed in this work enable blind drivers to operate an automobile through the provision of steering wheel angle and speed cues to the driver in a non-visual method. This paradigm imposes four principal functionality requirements: Perception, Motion Planning, Reference Transformations, and Communication. The Reference Transformation and Communication requirements are the focus of this work and convert motion planning trajectories into a series of non-visual stimuli that can be communicated to the human driver. This work proposes two separate algorithms to perform the necessary reference transformations described above. The first algorithm, called the Passive Non-Visual Interface Driver, converts the planned trajectory data into a form that can be understood and reliably interacted with by the blind driver. This passive algorithm performs the transformations through a method that is independent of the driver. The second algorithm, called the Adaptive Non-Visual Interface Driver, performs similar trajectory data conversions through methods that adapt to each particular driver. This algorithm uses Model Predictive Control supplemented with Artificial Neural Network driver models to generate non-visual stimuli that are predicted to induce optimal performance from the driver. The driver models are trained online and in real-time with a rapid training approach to continually adapt to changes in the driver's dynamics over time. The communication of calculated non-visual stimuli is subsequently performed through a Non-Visual Interface System proposed by this work. This system is comprised of two non-visual human computer interfaces that communicate driving information through haptic stimuli. The DriveGrip interface is pair of vibro-tactile gloves that communicate steering information through the driver's hands and fingers. The SpeedStrip interface is a vibro-tactile cushion fitted on the driver's seat that communicates speed information through the driver's legs and back. The two interfaces work simultaneously to provide a continuous stream of directions to the driver as he or she navigates the vehicle. / Ph. D.

This dissertation focuses on constrained control of two applications: helicopter and ocean current turbines (OCT). A major contribution in the helicopter application is a novel model predictive control (MPC) framework for helicopter shipboard operations in high demanding sea-based conditions. A complex helicopter-ship dynamics interface has been developed as a system of implicit nonlinear ordinary differential equations to capture essential characteristics of the nonlinear helicopter dynamics, the ship dynamics, and the ship airwake interactions. Various airwake models such as Control Equivalent Turbulence Inputs (CETI) model and Computation Fluid Dynamics (CFD) data of the airwake are incorporated in the interface to describe a realistic model of the shipborne helicopter. The feasibility of the MPC design is investigated using two case studies: automatic deck landing during the ship quiescent period in sea state 5, and lateral reposition toward the ship in different wind-over-deck conditions. To improve the overall MPC performance, an updating scheme for the internal model of the MPC is proposed using linearization around operating points. A mixed-integer MPC algorithm is also developed for helicopter precision landing on moving decks. The performance of this control structure is evaluated via numerical simulations of the automatic deck landing in adverse conditions such as landing on up-stroke, and down-stroke moving decks with high energy indices. Kino-dynamic motion planning for coordinated maneuvers to satisfy the helicopter-ship rendezvous conditions is implemented via mixed integer quadratic programming. In the OCT application, the major contribution is that a new idea is leveraged from helicopter blade control by introducing cyclic blade pitch control in OCT. A minimum energy, constrained control method, namely Output Variance Constrained (OVC) control is studied for OCT flight control in the presence of external disturbances. The minimum achievable output variance bounds are also computed and a parametric study of design parameters is conducted to evaluate their influence on the OVC performance. The performance of the OVC control method is evaluated both on the linear and nonlinear OCT models. Furthermore, control design for the OCT with sensor failures is also examined. Lastly, the MPC strategy is also investigated to improve the OCT flight control performance in simultaneous satisfaction of multiple constraints and to avoid blade stall. / Ph. D.

Advanced Driver Assistance Systems (ADAS) and Autonomous Ground Vehicles (AGV) have the potential to increase road transportation safety, environmental gains, and passenger comfort. The advent of Electric Vehicles has also facilitated greater flexibility in powertrain architectures and control capabilities. Path Tracking controllers that provide steering input are used to execute lateral maneuvers or model the response of a vehicle during cornering. Direct Yaw Control using Torque Vectoring has the potential to improve vehicle's transient cornering stability and modify its steady state handling characteristics during lateral maneuvers. In the first part of this thesis, the transient dynamics of an existing baseline Path Tracking controller is improved using a transient Torque Vectoring algorithm. The existing baseline Path Tracking controller is evaluated, using a linearized system, for a range of vehicle and controller parameters. The effect of implementing transient Torque Vectoring along with the baseline Path Tracking controller is then studied for the same parameter range. The linear analysis shows, in both time and frequency domain, that the transient Torque Vectoring improves vehicle response and stability during cornering. A Torque Vectoring controller is developed in Linear Adaptive Model Predictive Control framework and it's performance is verified in simulation using Simulink and CarSim. The second part of the thesis analyzes the tradeoff enabled by steady state Torque Vectoring between improved limit handling capability through optimal tire force allocation and drivability demonstrated by understeer gradient. Optimal tire force allocation prescribes equal usage in all four tires during maneuvers. This is enabled using steering and Torque Vectoring. An analytical proof is presented which demonstrates that implementation of this optimal tire force allocation results in neutralsteering handling characteristics for the vehicle. The optimal tire force allocation strategy is formulated as a minimax optimization problem. A two-track vehicle model is simulated for this strategy, and it verified the analytical proof by displaying neutralsteering behavior. / Master of Science / Advanced Driver Assistance Systems (ADAS) and Autonomous Ground Vehicles (AGVs) have the potential to increase road transportation safety, environmental gains, passenger comfort and passenger productivity. The advent of Electric Vehicles (EVs) has also facilitated greater flexibility in powertrain configurations and capabilities that facilitate the implementation of Torque Vectoring (TV), which is a method of applying differential torques to laterally opposite wheels to enhance the cornering performance of ground vehicles. Path Tracking (PT) controllers that provide steering input to the vehicles are traditionally used for lateral control in AGVs and ADAS features. The goal of this thesis is to develop Torque Vectoring algorithms to improve a vehicle's stability and shape its steady state behaviour through a corner during low lateral acceleration maneuvers. An existing baseline Path Tracking controller is selected and evaluated. The effect of implementing Torque Vectoring along with this Path Tracking controller is studied and it is found to improve the stability of the vehicle during cornering. This is verified in simulation by designing and implementing the Torque Vectoring algorithm. Finally, a Torque Vectoring strategy is proposed to manage the handling of the vehicle during low acceleration cornering.

[ES] La gran mayoría de procesos del mundo real tienen incertidumbres inherentes, las cuales, al ser consideradas en el proceso de modelado, se puede obtener una representación que describa con la mayor precisión posible el comportamiento del proceso real. En la mayoría de casos prácticos, se considera que éstas tienen un comportamiento estocástico y sus descripciones como distribuciones de probabilidades son conocidas. Las estrategias de MPC estocástico están desarrolladas para el control de procesos con incertidumbres de naturaleza estocástica, donde el conocimiento de las propiedades estadísticas de las incertidumbres es aprovechado al incluirlo en el planteamiento de un problema de control óptimo (OCP). En éste, y contrario a otros esquemas de MPC, las restricciones duras son relajadas al reformularlas como restricciones de tipo probabilísticas con el fin de reducir el conservadurismo. Esto es, se permiten las violaciones de las restricciones duras originales, pero tales violaciones no deben exceder un nivel de riesgo permitido. La no-convexidad de tales restricciones probabilísticas hacen que el problema de optimización sea prohibitivo, por lo que la mayoría de las estrategias de MPC estocástico en la literatura se diferencian en la forma en que abordan tales restricciones y las incertidumbres, para volver el problema computacionalmente manejable. Por un lado, están las estrategias deterministas que, fuera de línea, convierten las restricciones probabilísticas en unas nuevas de tipo deterministas, usando la propagación de las incertidumbres a lo largo del horizonte de predicción para ajustar las restricciones duras originales. Por otra parte, las estrategias basadas en escenarios usan la información de las incertidumbres para, en cada instante de muestreo, generar de forma aleatoria un conjunto de posibles evoluciones de éstas a lo largo del horizonte de predicción. De esta manera, convierten las restricciones probabilísticas en un conjunto de restricciones deterministas que deben cumplirse para todos los escenarios generados. Estas estrategias se destacan por su capacidad de incluir en tiempo real información actualizada de las incertidumbres. No obstante, esta ventaja genera inconvenientes como su gasto computacional, el cual aumenta conforme lo hace el número de escenarios y; por otra parte, el efecto no deseado en el problema de optimización, causado por los escenarios con baja probabilidad de ocurrencia, cuando se usa un conjunto de escenarios pequeño. Los retos mencionados anteriormente orientaron esta tesis hacia los enfoques de MPC estocástico basado en escenarios, produciendo tres contribuciones principales. La primera consiste en un estudio comparativo de un algoritmo del grupo determinista con otro del grupo basado en escenarios; se hace un especial énfasis en cómo cada uno de estos aborda las incertidumbres, transforma las restricciones probabilísticas y en la estructura de su OCP, además de señalar sus aspectos más destacados y desafíos. La segunda contribución es una nueva propuesta de algoritmo MPC, el cual se basa en escenarios condicionales, diseñado para sistemas lineales con incertidumbres correlacionadas. Este esquema aprovecha la existencia de tal correlación para convertir un conjunto de escenarios inicial de gran tamaño en un conjunto de escenarios más pequeño con sus probabilidades de ocurrencia, el cual conserva las características del conjunto inicial. El conjunto reducido es usado en un OCP en el que las predicciones de los estados y entradas del sistema son penalizadas de acuerdo con las probabilidades de los escenarios que las componen, dando menor importancia a los escenarios con menores probabilidades de ocurrencia. La tercera contribución consiste en un procedimiento para la implementación del nuevo algoritmo MPC como gestor de la energía en una microrred en la que las previsiones de las energías renovables y las cargas están correlacionadas. / [CA] La gran majoria de processos del món real tenen incerteses inherents, les quals, en ser considerades en el procés de modelatge, es pot obtenir una representació que descriga amb la major precisió possible el comportament del procés real. En la majoria de casos pràctics, es considera que aquestes tenen un comportament estocàstic i les seues descripcions com a distribucions de probabilitats són conegudes. Les estratègies de MPC estocàstic estan desenvolupades per al control de processos amb incerteses de naturalesa estocàstica, on el coneixement de les propietats estadístiques de les incerteses és aprofitat en incloure'l en el plantejament d'un problema de control òptim (OCP). En aquest, i contrari a altres esquemes de MPC, les restriccions dures són relaxades en reformulades com a restriccions de tipus probabilístiques amb la finalitat de reduir el conservadorisme. Això és, es permeten les violacions de les restriccions dures originals, però tals violacions no han d'excedir un nivell de risc permès. La no-convexitat de tals restriccions probabilístiques fan que el problema d'optimització siga computacionalment immanejable, per la qual cosa la majoria de les estratègies de MPC estocàstic en la literatura es diferencien en la forma en què aborden tals restriccions i les incerteses, per a tornar el problema computacionalment manejable. D'una banda, estan les estratègies deterministes que, fora de línia, converteixen les restriccions probabilístiques en unes noves de tipus deterministes, usant la propagació de les incerteses al llarg de l'horitzó de predicció per a ajustar les restriccions dures originals. D'altra banda, les estratègies basades en escenaris usen la informació de les incerteses per a, en cada instant de mostreig, generar de manera aleatòria un conjunt de possibles evolucions d'aquestes al llarg de l'horitzó de predicció. D'aquesta manera, converteixen les restriccions probabilístiques en un conjunt de restriccions deterministes que s'han de complir per a tots els escenaris generats. Aquestes estratègies es destaquen per la seua capacitat d'incloure en temps real informació actualitzada de les incerteses. No obstant això, aquest avantatge genera inconvenients com la seua despesa computacional, el qual augmenta conforme ho fa el nombre d'escenaris i; d'altra banda, l'efecte no desitjat en el problema d'optimització, causat pels escenaris amb baixa probabilitat d'ocurrència, quan s'usa un conjunt d'escenaris xicotet. Els reptes esmentats anteriorment van orientar aquesta tesi cap als enfocaments de MPC estocàstic basat en escenaris, produint tres contribucions principals. La primera consisteix en un estudi comparatiu d'un algorisme del grup determinista amb un altre del grup basat en escenaris; on es fa un especial èmfasi en com cadascun d'aquests aborda les incerteses, transforma les restriccions probabilístiques i en l'estructura del seu problema d'optimització, a més d'assenyalar els seus aspectes més destacats i desafiaments. La segona contribució és una nova proposta d'algorisme MPC, el qual es basa en escenaris condicionals, dissenyat per a sistemes lineals amb incerteses correlacionades. Aquest esquema aprofita l'existència de tal correlació per a convertir un conjunt d'escenaris inicial de gran grandària en un conjunt d'escenaris més xicotet amb les seues probabilitats d'ocurrència, el qual conserva les característiques del conjunt inicial. El conjunt reduït és usat en un OCP en el qual les prediccions dels estats i entrades del sistema són penalitzades d'acord amb les probabilitats dels escenaris que les componen, donant menor importància als escenaris amb menors probabilitats d'ocurrència. La tercera contribució consisteix en un procediment per a la implementació del nou algorisme MPC com a gestor de l'energia en una microxarxa en la qual les previsions de les energies renovables i les càrregues estan correlacionades. / [EN] The vast majority of real-world processes have inherent uncertainties, which, when considered in the modelling process, can provide a representation that most accurately describes the behaviour of the real process. In most practical cases, these are considered to have stochastic behaviour and their descriptions as probability distributions are known. Stochastic model predictive control algorithms are developed to control processes with uncertainties of a stochastic nature, where the knowledge of the statistical properties of the uncertainties is exploited by including it in the optimal control problem (OCP) statement. Contrary to other model predictive control (MPC) schemes, hard constraints are relaxed by reformulating them as probabilistic constraints to reduce conservatism. That is, violations of the original hard constraints are allowed, but such violations must not exceed a permitted level of risk. The non-convexity of such probabilistic constraints renders the optimisation problem computationally unmanageable, thus most stochastic MPC strategies in the literature differ in how they deal with such constraints and uncertainties to turn the problem computationally tractable. On the one hand, there are deterministic strategies that, offline, convert probabilistic constraints into new deterministic ones, using the propagation of uncertainties along the prediction horizon to tighten the original hard constraints. Scenario-based approaches, on the other hand, use the uncertainty information to randomly generate, at each sampling instant, a set of possible evolutions of uncertainties over the prediction horizon. In this fashion, they convert the probabilistic constraints into a set of deterministic constraints that must be fulfilled for all the scenarios generated. These strategies stand out for their ability to include real-time updated uncertainty information. However, this advantage comes with inconveniences such as computational effort, which grows as the number of scenarios does, and the undesired effect on the optimisation problem caused by scenarios with a low probability of occurrence when a small set of scenarios is used. The aforementioned challenges steered this thesis toward stochastic scenario-based MPC approaches, and yielded three main contributions. The first one consists of a comparative study of an algorithm from the deterministic group with another one from the scenario-based group, where a special emphasis is made on how each of them deals with uncertainties, transforms the probabilistic constraints and on the structure of the optimisation problem, as well as pointing out their most outstanding aspects and challenges. The second contribution is a new proposal for a MPC algorithm, which is based on conditional scenarios, developed for linear systems with correlated uncertainties. This scheme exploits the existence of such correlation to convert a large initial set of scenarios into a smaller one with their probabilities of occurrence, which preserves the characteristics of the initial set. The reduced set is used in an OCP in which the predictions of the system states and inputs are penalised according to the probabilities of the scenarios that compose them, giving less importance to the scenarios with lower probabilities of occurrence. The third contribution consists of a procedure for the implementation of the new MPC algorithm as an energy manager in a microgrid in which the forecasts of renewables and loads are correlated. / González Querubín, EA. (2024). Scenario-Based Model Predictive Control for Systems with Correlated Uncertainties [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/203887

Incremental Sheet Forming (ISF) is a progressive metal forming process, where the deformation occurs locally around the point of contact between a tool and the metal sheet. The final work-piece is formed cumulatively by the movements of the tool, which is usually attached to a CNC milling machine. The ISF process is dieless in nature and capable of producing different parts of geometries with a universal tool. The tooling cost of ISF can be as low as 5–10% compared to the conventional sheet metal forming processes. On the laboratory scale, the accuracy of the parts created by ISF is between ±1.5 mm and ±3mm. However, in order for ISF to be competitive with a stamping process, an accuracy of below ±1.0 mm and more realistically below ±0.2 mm would be needed. In this work, we first studied the ISF deformation process by a simplified phenomenal linear model and employed a predictive controller to obtain an optimised tool trajectory in the sense of minimising the geometrical deviations between the targeted shape and the shape made by the ISF process. The algorithm is implemented at a rig in Cambridge University and the experimental results demonstrate the ability of the model predictive controller (MPC) strategy. We can achieve the deviation errors around ±0.2 mm for a number of simple geometrical shapes with our controller. The limitations of the underlying linear model for a highly nonlinear problem lead us to study the ISF process by a physics based model. We use the elastoplastic constitutive relation to model the material law and the contact mechanics with Signorini’s type of boundary conditions to model the process, resulting in an infinite dimensional system described by a partial differential equation. We further developed the computational method to solve the proposed mathematical model by using an augmented Lagrangian method in function space and discretising by finite element method. The preliminary results demonstrate the possibility of using this model for optimal controller design.

This thesis deals with chemical plants constituted by parallel batch-continuous production lines with shared resources. For such plants, it is highly desirable to have optimal operation schedules which determine the starting times of the various batch processes and the flow rates of the continuous processes in order to maximize the average plant productivity and to have a continuous production without interruptions. This optimization problem is constrained by the limitation of the resources that are shared by the reactors and by the capacities of the various devices that constitute the plant. Such plants are "hybrid" by nature because they combine both continuous-time dynamics and discrete-event dynamics. The formalism of "Hybrid Automata" is there fore well suited for the design of plant models. The first contribution of this thesis is the development of a hybrid automaton model of the chemical plant in the Matlab-Simulink-Stateflow environment and its use for the design of an optimal periodic schedule that maximises the plant productivity. Using a sensitivity analysis and the concept of Poincaré; map, it is shown that the optimal schedule is a stable limit cycle of the hybrid system that attracts the system trajectories starting in a wide set of initial conditions. The optimal periodic schedule is valid under the assumption that the hybrid model is an exact description of the plant. Under perturbations on the plant parameters, it is shown that two types of problems may arise. The first problem is a drift of the hybrid system trajectory which can either lead to a convergence to a new stable sub-optimal schedule or to a resource conflict. The second problem is a risk of overflow or underflow of the output buffer tank. The second contribution of the thesis is the analysis of feedback control strategies to avoid these problems. For the first problem, a control policy based on a model predictive control (MPC) approach is proposed to avoid resource conflicts. The feedback control is run on - line with the hybrid Simulink-Stateflow simulator used as an internal model. For the solution of the second problem, a classical PI control is used. The goal is not only to avoid over- or under-filling of the tank but also to reduce the amplitude of outflow rate variations as much as possible. A methodological analysis for the PI controller tuning is presented in order to achieve an acceptable trade-off between these conflicting objectives.

The goal of this dissertation is to evaluate the effectiveness of model predictive control (MPC) for a magnetically suspended flywheel energy storage uninterruptible power supply (FlyUPS). The reason this research topic was selected was to determine if an advanced control technique such as MPC could perform better than a classical control approach such as decentralised Proportional-plus-Differential (PD) control. Based on a literature study of the FlyUPS system and the MPC strategies available, two MPC strategies were used to design two possible MPC controllers were designed for the FlyUPS, namely a classical MPC algorithm that incorporates optimisation techniques and the MPC algorithm used in the MATLAB® MPC toolbox™. In order to take the restrictions of the system into consideration, the model used to derive the controllers was reduced to an order of ten according to the Hankel singular value decomposition of the model. Simulation results indicated that the first controller based on a classical MPC algorithm and optimisation techniques was not verified as a viable control strategy to be implemented on the physical FlyUPS system due to difficulties obtaining the desired response. The second controller derived using the MATLAB® MPC toolbox™ was verified to be a viable control strategy for the FlyUPS by delivering good performance in simulation. The verified MPC controller was then implemented on the FlyUPS. This implementation was then analysed in order to validate that the controller operates as expected through a comparison of the simulation and implementation results. Further analysis was then done by comparing the performance of MPC with decentralised PD control in order to determine the advantages and limitations of using MPC on the FlyUPS. The advantages indicated by the evaluation include the simplicity of the design of the controller that follows directly from the specifications of the system and the dynamics of the system, and the good performance of the controller within the parameters of the controller design. The limitations identified during this evaluation include the high computational load that requires a relatively long execution time, and the inability of the MPC controller to adapt to unmodelled system dynamics. Based on this evaluation MPC can be seen as a viable control strategy for the FlyUPS, however more research is needed to optimise the MPC approach to yield significant advantages over other control techniques such as decentralised PD control. / Thesis (MIng (Computer and Electronic Engineering))--North-West University, Potchefstroom Campus, 2013

The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control methods is Model Predictive Control (MPC). In each sampling time, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem, which is known to have a computational complexity which grows exponentially in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel. To estimate the information originally sent, a maximum likelihood problem involving binary variables can be solved. The process of simultaneously estimating the information sent by multiple users is called Multiuser Detection (MUD). In this thesis, the problem to efficiently solve MIQP problems originating from MPC and MUD is addressed. Four different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In numerical experiments, the algorithm is applied to unconstrained MPC problems with a mixture of real valued and binary valued control signals, and the result shows that the performance gain can be significant compared to solving the problem using branch and bound. The preprocessing algorithm has also been applied to the MUD problem, where simulations have shown that the bit error rate can be significantly reduced compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the proposed QP solver and MIQP solver have lower computational complexity compared to corresponding generic solvers. Third, the dual active set QP algorithm is enhanced using ideas from gradient projection methods. The performance of this enhanced algorithm is shown to be comparable with the existing commercial state-of-the-art QP solver \cplex for some random linear MPC problems. Fourth, an algorithm for efficient computation of the search directions in an SDP solver for a proposed alternative SDP relaxation applicable to MPC problems with binary control signals is presented. The SDP relaxation considered has the potential to give a tighter lower bound on the optimal objective function value compared to the QP relaxation that is traditionally used in branch and bound for these problems, and its computational performance is better than the ordinary SDP relaxation for the problem. Furthermore, the tightness of the different relaxations is investigated both theoretically and in numerical experiments. / This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Linköping University's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it.

Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution. / Numeriska algoritmer för att effektivt lösa optimala styrningsproblem är en viktig komponent i avancerade regler- och estimeringsstrategier som exempelvis modellprediktiv reglering (eng. model predictive control (MPC)) och glidande horisont estimering (eng. moving horizon estimation (MHE)). MPC är en reglerstrategi som kan användas för att styra system med flera styrsignaler och/eller utsignaler samt ta hänsyn till exempelvis begränsningar i styrdon. Den grundläggande principen för MPC och MHE är att styrsignalen och de estimerade variablerna kan beräknas genom att lösa ett optimalt styrningsproblem. Detta optimeringsproblem måste lösas inom en kort tidsram varje gång som en styrsignal ska beräknas eller som variabler ska estimeras, och således är det viktigt att det finns effektiva algoritmer för att lösa denna typ av problem. Två vanliga sådana är inrepunkts-metoder (eng. interior-point (IP)) och aktivmängd-metoder (eng. active-set (AS)), där optimeringsproblemet löses genom att lösa ett antal enklare delproblem. Ett av huvudfokusen i denna avhandling är att beräkna lösningen till dessa delproblem på ett tidseffektivt sätt genom att utnyttja strukturen i delproblemen. Lösningen till ett delproblem beräknas genom att lösa ett linjärt ekvationssystem. Detta ekvationssystem kan man exempelvis lösa med generella metoder eller med så kallade Riccatirekursioner som utnyttjar strukturen i problemet. När man använder en AS-metod för att lösa MPC-problemet så görs endast små strukturerade ändringar av ekvationssystemet mellan varje delproblem, vilket inte har utnyttjats tidigare tillsammans med Riccatirekursionen. I denna avhandling presenteras ett sätt att utnyttja detta genom att bara göra små förändringar av Riccatirekursionen för att minska beräkningstiden för att lösa delproblemet. Idag har behovet av  parallella algoritmer för att lösa MPC och MHE problem ökat. Att algoritmerna är parallella innebär att beräkningar kan ske på olika delar av problemet samtidigt med syftet att minska den totala verkliga beräkningstiden för att lösa optimeringsproblemet. I denna avhandling presenteras parallella algoritmer som kan användas i både IP- och AS-metoder. Algoritmerna beräknar lösningen till delproblemen parallellt med ett förutbestämt antal steg, till skillnad från många andra parallella algoritmer där ett okänt (ofta stort) antal steg krävs. De parallella algoritmerna utnyttjar problemstrukturen för att lösa delproblemen effektivt, och en av dem har utvärderats på parallell hårdvara. Linjära MPC problem kan också lösas genom att utnyttja teori från multiparametrisk kvadratisk programmering (eng. multiparametric quadratic programming (mp-QP)) där den optimala lösningen beräknas i förhand och lagras i en tabell, vilket benämns explicit MPC. I detta fall behöver inte MPC problemet lösas varje gång en styrsignal beräknas, utan istället kan den förberäknade optimala styrsignalen slås upp. En nackdel med mp-QP är att det krävs mycket plats i minnet för att spara lösningen. I denna avhandling presenteras en strukturutnyttjande algoritm som kan minska behovet av minne för att spara lösningen, vilket kan öka det praktiska användningsområdet för mp-QP och explicit MPC.