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.

A robust model predictive control algorithm is presented that explicitly handles multiplicative, or parametric, uncertainty in linear discrete models over a finite horizon. The uncertainty in the predicted future states and inputs is bounded by polytopes. The computational cost of running the controller is reduced by calculating matrices offline that provide a means to construct outer approximations to robust constraints to be applied online. The robust algorithm is extended to problems of uncertain models with an allowed probability of violation of constraints. The probabilistic degrees of satisfaction are approximated by one-step ahead sampling, with a greedy solution to the resulting mixed integer problem. An algorithm is given to enlarge a robustly invariant terminal set to exploit the probabilistic constraints. Exponential basis functions are used to create a Robust MPC algorithm for which the predictions are defined over the infinite horizon. The control degrees of freedom are weights that define the bounds on the state and input uncertainty when multiplied by the basis functions. The controller handles multiplicative and additive uncertainty. Robust MPC is applied to the problem of wind turbine control. Rotor speed and tower oscillations are controlled by a low sample rate robust predictive controller. The prediction model has multiplicative and additive uncertainty due to the uncertainty in short-term future wind speeds and in model linearisation. Robust MPC is compared to nominal MPC by means of a high-fidelity numerical simulation of a wind turbine under the two controllers in a wide range of simulated wind conditions.

An adaptive autopilot design for an uninhabited surface vehicle Andy SK Annamalai The work described herein concerns the development of an innovative approach to the design of autopilot for uninhabited surface vehicles. In order to fulfil the requirements of autonomous missions, uninhabited surface vehicles must be able to operate with a minimum of external intervention. Existing strategies are limited by their dependence on a fixed model of the vessel. Thus, any change in plant dynamics has a non-trivial, deleterious effect on performance. This thesis presents an approach based on an adaptive model predictive control that is capable of retaining full functionality even in the face of sudden changes in dynamics. In the first part of this work recent developments in the field of uninhabited surface vehicles and trends in marine control are discussed. Historical developments and different strategies for model predictive control as applicable to surface vehicles are also explored. This thesis also presents innovative work done to improve the hardware on existing Springer uninhabited surface vehicle to serve as an effective test and research platform. Advanced controllers such as a model predictive controller are reliant on the accuracy of the model to accomplish the missions successfully. Hence, different techniques to obtain the model of Springer are investigated. Data obtained from experiments at Roadford Reservoir, United Kingdom are utilised to derive a generalised model of Springer by employing an innovative hybrid modelling technique that incorporates the different forward speeds and variable payload on-board the vehicle. Waypoint line of sight guidance provides the reference trajectory essential to complete missions successfully. The performances of traditional autopilots such as proportional integral and derivative controllers when applied to Springer are analysed. Autopilots based on modern controllers such as linear quadratic Gaussian and its innovative variants are integrated with the navigation and guidance systems on-board Springer. The modified linear quadratic Gaussian is obtained by combining various state estimators based on the Interval Kalman filter and the weighted Interval Kalman filter. Change in system dynamics is a challenge faced by uninhabited surface vehicles that result in erroneous autopilot behaviour. To overcome this challenge different adaptive algorithms are analysed and an innovative, adaptive autopilot based on model predictive control is designed. The acronym ‘aMPC’ is coined to refer to adaptive model predictive control that is obtained by combining the advances made to weighted least squares during this research and is used in conjunction with model predictive control. Successful experimentation is undertaken to validate the performance and autonomous mission capabilities of the adaptive autopilot despite change in system dynamics.

The problem of aircraft conflict detection and resolution (CDR) in uncertainty is addressed in this thesis. The main goal in CDR is to provide safety for the aircraft while minimizing their fuel consumption and flight delays. In reality, a high degree of uncertainty can exist in certain aircraft-aircraft encounters especially in cases where aircraft do not have the capabilities to communicate with each other. Through the use of a probabilistic approach and a multiple model (MM) trajectory information processing framework, this uncertainty can be effectively handled. For conflict detection, a randomized Monte Carlo (MC) algorithm is used to accurately detect conflicts, and, if a conflict is detected, a conflict resolution algorithm is run that utilizes a sequential list Viterbi algorithm. This thesis presents the MM CDR method and a comprehensive MC simulation and performance evaluation study that demonstrates its capabilities and efficiency.

This master’s thesis examines how a small MIMO lighting system can be identified and controlled. Two approaches are examined and compared; the first approach is a dynamic model using state space representation, where the system identification technique is Recursive Least Square, RLS, and the controller is an LQG controller; the second approach is a static model derived from the physical properties of light and a feedback feed-forward controller consisting of a PI controller coupled with a Control Allocation, CA, technique. For the studied system, the CA-PI approach significantly outperforms the LQG-RLS approach, which leads to the conclusion that the system’s static properties are predominant compared to the dynamic properties.

The purpose of this thesis is to evaluate Rapid Control Prototyping which is apart of the Model-Based Design concept that makes it possible to convenientlytest prototype control algorithms directly on the real system. The evaluation ishere done by designing two different controllers, a gain-scheduled P controllerand a linear Model Predictive Controller (mpc), for the lowering of the forks of aforklift.The two controllers are first tested in a simulation environment. The thesis con-tains two different simulation models: one physical where only minor parameteradjustments are done and one estimated black-box model. After evaluating thecontrollers in a simulation environment they are tested on a real forklift with areal-time target machine.The designed controllers have different strengths and weaknesses as one is non-linear and single variable, the P controller, and the other linear and multivariable,thempc. The P controller has a smooth movement in all situations without be-ing slow, unlike thempc. The disadvantage of the P controller compared to thempcis that there is no guarantee that the P controller will keep the speed limit,whereas thempcapproach gives such a guarantee.The better performance of the P controller outweighs the speed limit guaranteeand thus a conclusion is drawn that the nonlinearities of the system has a largereffect than the multivariable aspect. Also, another conclusion drawn is that work-ing with Model-Based Design and Rapid Control Prototyping makes it possibleto test many different ideas on a real forklift without spending a lot of time onimplementation. / Syftet med detta examensarbete är att utvärdera Rapid Control Prototyping vil-ket är en del av modellbaserad utveckling som gör det möjligt att enkelt testamodeller av styralgoritmer direkt på det riktiga systemet. Utvärderingen är gjordgenom att testa två olika regulatorer, en P-regulator med parameterstyrning ochen linjär modelbaserad prediktionsregulator (mpc), för sänkningen av gafflarnapå en truck.De två regulatorerna testas först i en simuleringsmiljö. I arbetet används två olikasimuleringsmodeller: en fysikalisk där endast mindre parameterjusteringar görsoch en estimerad black-box modell. Efter att regulatorerna utvärderas i simule-ringsmiljön testas de även på en riktig truck med hjälp av automatisk kodgenere-ring och exekvering på en dedikerad hårdvaruplattform.De konstruerade regulatorerna har olika för- och nackdelar eftersom en är olinjäroch envariabel, P-regulatorn, och en är linjär men flervariabel,mpc:n. P-regulatornhar en mjuk rörelse i alla lägen utan att bli för långsam, till skillnad frånmpc:n.Nackdelen med P-regulatorn, jämfört medmpc:n är att det inte finns någon ga-ranti för att P-regulatorn håller hastighetsbegränsningen sommpc:n gör.P-regulatorns bättre prestanda överväger garantin om att hålla hastighetsbegräns-ningen och därför dras slutsatsen att olinjäriteterna i systemet överväger effekter-na av det faktum att det också är flervariabelt. En annan slutsats är att modell-baserad utveckling och Rapid Control Prototyping gör det möjligt att testa fleraolika idéer på en riktig gaffeltruck utan att spendera för mycket tid på implemen-tationen.

The Linear Quadratic Regulator (LQR) is an optimal control approach which aims to drive states of a linear system to its origin through the minimization of a quadratic cost functional. Such an approach has been widely successful for both theoretical and practical applications. However, when such controllers are subject to uncertainties, optimal closed-loop performance cannot be obtained since robustness properties are no longer guaranteed. Guaranteed Cost Controllers (GCC) presents robust asymptotic stability and provides a guaranteed upper bound to a quadratic cost function. Such method addresses the lack of performance guarantees of the LQR. Meanwhile, Model Predictive Control (MPC) is a class of optimization-based control algorithms that use an explicit model of the controlled system to predict its future states. The MPC can be as a generalization of the LQR for constrained linear systems. Therefore, it equally suffers from a lack of robustness guarantees when the system is subject to uncertainties. Robust MPC (RMPC) approaches were proposed to address MPCs poor closed-loop performance subject to uncertainties. Its objective is to obtain a control input sequence that simultaneously minimizes a cost function and guarantees the feasibility of system states and control inputs, for a system subject to the worst-case disturbance within an uncertainty set. Autonomous vehicles have gained increasing interest from both the industry and research communities in recent years. An essential aspect in the design of automotive control systems is to ensure the controller is stable and has acceptable performance within the entire operational envelope which it is designed to operate. In the case of autonomous vehicles, where there is no human driver as a fallback, it is of utmost importance to ensure the safe operations of the control system and its capability to avoid saturating the handling limits of the vehicle. In this thesis, we propose Guaranteed Cost Controller approaches for both unconstrained and constrained linear systems subject to multiplicative structured norm-bounded uncertainties and present the application of such a controller to the lateral control problem of autonomous vehicles up to the tire saturation limits. / O Regulador Quadrático Linear (Linear Quadratic Regulator, LQR) é uma abordagem de controle ótimo que visa conduzir estados de um sistema linear à sua origem através da minimização de um custo funcional quadrático. Tal abordagem tem sido amplamente bem sucedida para aplicações teóricas e práticas. No entanto, não é possível obter o desempenho ótimo de malha fechada quando esses controladores são sujeitos a incertezas no sistema em decorrência de suas propriedades de robustez não serem garantidas. Controladores de Custo Garantido (Guaranteed Cost Control, GCC) visam abordar a falta de garantia de desempenho do LQR, neste caso. Esses controladores apresentam estabilidade assintótica robusta e fornecem um custo garantido de pior caso para uma função de custo quadrático. O Controle Preditivo de Modelo (Model Predictive Control, MPC) é uma classe de algoritmos de controle baseados em otimização que usa um modelo explícito do sistema controlado para prever seus estados futuros. Uma possível interpretação do MPC é uma generalização do LQR para sistemas lineares com restrições de estado e entrada de controle. Portanto, essa abordagem sofre igualmente da falta de garantias de robustez quando o sistema é sujeito a incertezas. As abordagens de MPC Robustas (Robust MPC, RMPC) foram propostas para abordar o desempenho de malha fechada do MPC sujeito a incertezas no sistema. Seu objetivo é obter uma sequência de entrada de controle que minimize simultaneamente uma função de custo e garanta que os estados do sistema e as entradas de controle estão contidos dentro das restrições para um sistema sujeito à pior das perturbações dentro de um conjunto admissível de incertezas. Pesquisas voltadas para veículos autônomos ganharam crescente interesse nos últimos anos, tanto da indústria automobilística quanto da comunidade acadêmica. Um aspecto essencial no projeto de sistemas de controle automotivo é a garantia de estabilidade e desempenho do controlador dentro de todo o envelope operacional ao qual ele foi projetado para operar. No caso de veículos autônomos, onde não há motoristas humanos para lidar com casos de falha do sistema, é de suma importância assegurar as operações seguras do sistema de controle e sua capacidade de evitar a saturação dos limites de manuseio do veículo. Nesta tese, propomos abordagens GCC para sistemas lineares restritos e irrestritos, sujeitos a incertezas estruturadas contidas por norma e apresentamos a aplicação de tais controladores ao problema de controle lateral de veículos autônomos até os limites de saturação dos pneus.

Garantir le confort thermique des bâtiments est directement lié à la consommation d'énergie. Dans les zones tropicales, les systèmes de refroidissement représentent l'un des postes les plus gourmands en énergie. Afin de réduire la consommation d'énergie mondiale, il est primordial d'améliorer l'efficacité de ces systèmes ou bien de développer de nouvelles méthodes de production de froid. Une installation de refroidissement solaire basé sur le cycle à absorption est une alternative pour réduire les émissions de gaz à effet de serre et la consommation d'électricité. Contrairement aux systèmes classiques de refroidissement à compression mécanique, la production de froid par absorption est un système complexe composé de plusieurs composants comme des panneaux solaires, un ballon de stockage, une tour de refroidissement et une machine à absorption. Outre le dimensionnement des composants, ce système complexe nécessite des actions de contrôle pour être efficace parce que la coordination entre le stockage d'eau chaude, la production et la consommation du froid est nécessaire. Le but de cette thèse est de proposer une structure producteur-consommateur d'énergie basée sur la commande prédictive (MPC). Le système de refroidissement par absorption solaire est considéré comme faisant partie de ce système de production-consommation d'énergie, le système de stockage d'eau chaude est le producteur et la machine à absorption qui distribue de l'eau froide au bâtiment est l'un des consommateurs. Pour que la structure de commande soit modulaire, la coordination entre les sous-systèmes est réalisée en utilisant une approche de partitionnement où des contrôleurs prédictifs locaux sont conçus pour chacun des sous-systèmes. Les contrôleurs des consommateurs calculent un ensemble de profils de demande d'énergie. Ces profils sont ensuite envoyés au contrôleur du producteur qui sélectionne le profil qui minimise le coût global. Dans une première partie, l'approche proposée est testée sur un modèle linéaire simplifié composé d'un producteur et plusieurs consommateurs. Dans une deuxième partie, un cas plus complexe est étudié. Un modèle simplifié d'un système de refroidissement à absorption est évaluée en utilisant l'outil de simulation TRNSYS. Le modèle de production n'est plus linéaire, il est décrit par un modèle non linéaire hybride qui augmente la complexité du problème d'optimisation. Les résultats des simulations montrent que la sous-optimalité induite par la méthode est faible. De plus, la performance de l'approche atteint les objectifs de commande tout en respectant les contraintes. / To guarantee thermal comfort in buildings is directly related to energy consumption. In tropical climates, cooling systems for buildings represent one of the largest energy consumers. Therefore, as energy consumption is a major concern around the world, it is important to improve the systems efficiency or seeking new methods of cooling production. A solar cooling installation based on the absorption cycle is an alternative to mitigate greenhouse gas emissions and electricity consumption. In contrast to conventional vapor-compression based cooling systems, the absorption cooling production involves a complex system composed of several components as collector panel, storage tank, cooling tower and absorption chiller. Besides the sizing of the components, this complex system requires control actions to be efficient as a coordination between hot water storage, cooling water production and consumption is necessary. The aim of this research is to propose a management approach for a production-consumption energy system based on Model Predictive Control (MPC). The solar absorption cooling system is seen as part of this production-consumption energy system where the hot water storage system is the producer and the chiller-building system is one of the consumers. In order to provide modularity to the control structure, the coordination between the subsystems is achieved by using a partitioning approach where local predictive controllers are developed for each of the subsystems. The consumer controllers compute a set of energy demand profiles sent to the producer controller which selects the profile that better minimize the global optimization cost. In a first part, the proposed approach is tested on a simplified linear model composed of one producer and several consumers. In a second part, a more complex case is studied. A simplified model of an absorption cooling system is evaluated using the simulation tool TRNSYS. The producer model is no longer linear, instead it is described by a nonlinear hybrid model which increases the complexity of the optimization problem. The simulations results show that the suboptimality induced by the method is low and the control strategy fulfills the objectives and constraints while giving good performances.

Critical automated maneuvers for ships typically require a redundant set of thrusters. The motion control system hierarchy is commonly separated into several layers using a high-level motion controller and a thruster allocation (TA) algorithm. This allows for a modular design of the software where the high-level controller can be designed without comprehensive information on the thrusters, while detailed issues such as input saturation and rate limits are handled by the TA. However, for a certain set of thruster configurations this decoupling may result in poor control performance due to the limited knowledge in the high-level controller about the physical limitations of the ship and the behavior of the TA. This thesis investigates different approaches of improving the control performance, using nonlinear Model Predictive Control (MPC) as a foundation for the developed motion controllers due to its optimized solution and capability of satisfying constraints. First, a decoupled system is implemented and results are provided for two simple motion tasks showing problems related to the decoupling. Thereafter, two different approaches are taken to remedy the observed drawbacks. A nonlinear MPC controller is developed combining the motion controller and thruster allocation resulting in a more robust control system. Then, in order to keep the control system modularized, an investigation of possible ways to augment the decoupled system so as to achieve similar performance as the combined system is carried out. One proposed solution is a nonlinear MPC controller with time-varying constraints accounting for the current limitations of the thruster system. However, this did not always improve the control performance since the behavior of the TA still is unknown to the MPC controller.