Institutionen för systemteknik (ISY)

This letter considers the problem of detecting and tracking objects in a sequence of images. The problem is formulated in a filtering framework, using the output of object-detection algorithms as measurements. An extension to the filtering formulation is proposed that incorporates class information from the previous frame to robustify the classification. Further, the properties of the object-detection algorithm are exploited to quantify the uncertainty of the bounding box detection in each frame. The complete filtering method is evaluated on camera trap images of the four large Swedish carnivores, bear, lynx, wolf, and wolverine. The experiments show that the class tracking formulation leads to a more robust classification.

This paper introduces a disturbance-parametrized (DP) robust lattice-based motion-planning framework for nonlinear systems affected by bounded disturbances. A key idea in this work is to rigorously exploit the available knowledge about the disturbance, starting already offline at the time when a library of DP motion primitives is computed and ending not before the motion has been executed online. Given an up-to-date-estimate of the disturbance, the lattice-based motion planner performs a graph search online, to non-conservatively compute a disturbance aware optimal motion plan with formally motivated margins to obstacles. This is done utilizing the DP motion primitives, around which tubes are generated utilizing a suitably designed robust controller. The sizes of the tubes are dependent on the upper bounds of the disturbance appearing in the error between the actual system trajectory and the DP nominal trajectory, which in turn along with the overall optimality of the plan is dependant on the user-selected resolution of the available disturbance estimates. Increasing the resolution of the disturbance parameter results in smaller sizes of tubes around the motion primitives and can significantly reduce the conservativeness compared to traditional approaches, thus increasing the performance of the computed motion plans. The proposed strategy is implemented on an Euler-Lagrange-based ship model which is affected by a significant wind disturbance and the efficiency of the strategy is validated through a suitable simulation example.

In model-predictive control (MPC), an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. We propose an algorithm for computing which sequence of subproblems an active-set algorithm will solve, for every parameter of interest. These sequences can be used to set worst-case bounds on how many iterations, floating-point operations, and, ultimately, the maximum solution time the active-set algorithm requires to converge. The usefulness of the proposed method is illustrated on a set of QPs originating from MPC problems, by computing the exact worst-case number of iterations primal and dual active-set algorithms require to reach optimality.

We propose a linear programming method that is based on active-set changes and proximal-point iterations. The method solves a sequence of least-distance problems using a warm-started quadratic programming solver that can reuse internal matrix factorizations from the previously solved least-distance problem. We show that the proposed method terminates in a finite number of iterations and that it outperforms state-of-the-art LP solvers in scenarios where an extensive number of small/medium scale LPs need to be solved rapidly, occurring in, for example, multi-parametric programming algorithms. In particular, we show how the proposed method can accelerate operations such as redundancy removal, computation of Chebyshev centers and solving linear feasibility problems.

 This paper presents a unified optimization-based path planning approach to efficiently compute locally optimal solutions to optimal path planning problems in unstructured environments. The approach is motivated by showing that a lattice-based planner can be cast and analyzed as a bilevel optimization problem. This insight is used to integrate a lattice-based planner and an optimal control-based method in a novel way. The lattice-based planner is applied to the problem in a first step using a discretized search space. In a second step, an optimal control-based method is applied using the lattice-based solution as an initial iterate. In contrast to prior work, the system dynamics and objective function used in the first step are chosen to coincide with those used in the second step. As an important consequence, the lattice planner provides a solution which is highly suitable as a warm-start to the optimal control step. This proposed combination makes, in a structured way, benefit of sampling-based methods ability to solve combinatorial parts of the problem and optimal control-based methods ability to obtain locally optimal solutions. Compared to previous work, the proposed approach is shown in simulations to provide significant improvements in terms of computation time, numerical reliability and objective function value.

In this letter we propose a method to exactly certify the complexity of an active-set method which is based on reformulating strictly convex quadratic programs to nonnegative least-squares problems. The exact complexity of the method is determined by proving the correspondence between the method and a standard primal active-set method for quadratic programming applied to the dual of the quadratic program to be solved. Once this correspondence has been established, a complexity certification method which has already been established for the primal active-set method is used to also certify the complexity of the nonnegative least-squares method. The usefulness of the proposed method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum.

Model predictive control (MPC) is one of the most widely spread advanced control schemes in industry today. In MPC, a constrained finite-time optimal control (CFTOC) problem is solved at each iteration in the control loop. The CFTOC problem can be solved using, for example, second-order methods, such as interior-point or active-set methods, where the computationally most demanding part often consists of computing the sequence of second-order search directions. Each search direction can be computed by solving a set of linear equations that corresponds to solving an unconstrained finite-time optimal control (UFTOC) problem. In this paper, different direct (noniterative) parallel algorithms for solving UFTOC problems are presented. The parallel algorithms are all based on a recursive variable elimination and solution propagation technique. Numerical evaluations of one of the parallel algorithms indicate that a significant boost in performance can be obtained, which can facilitate high-performance second-order MPC solvers.

In Model Predictive Control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this work the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speed-up can be important for AS type solvers used for linear, nonlinear and hybrid MPC.

This note presents an efficient approach for the evaluation of multi-parametric mixed integer quadratic programming (mp-MIQP) solutions, occurring for instance in control problems involving discrete time hybrid systems with quadratic cost. Traditionally, the online evaluation requires a sequential comparison of piecewise quadratic value functions. We introduce a lifted parameter space in which the piecewise quadratic value functions become piecewise affine and can be merged to a single value function defined over a single polyhedral partition without any overlaps. This enables efficient point location approaches using a single binary search tree. Numerical experiments with a power electronics application demonstrate an online speedup up to an order of magnitude. We also show how the achievable online evaluation time can be traded off against the offline computational time.

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.

The main objective in this work is to compare different convex relaxations for Model Predictive Control (MPC) problems with mixed real valued and binary valued control signals. In the problem description considered, the objective function is quadratic, the dynamics are linear, and the inequality constraints on states and control signals are all linear. The relaxations are related theoretically and the quality of the bounds and the computational complexities are compared in numerical experiments. The investigated relaxations include the Quadratic Programming (QP) relaxation, the standard Semidefinite Programming (SDP) relaxation, and an equality constrained SDP relaxation. The equality constrained SDP relaxation appears to be new in the context of hybrid MPC and the result presented in this work indicates that it can be useful as an alternative relaxation, which is less computationally demanding than the ordinary SDP relaxation and which often gives a better bound than the bound from the QP relaxation. Furthermore, it is discussed how the result from the SDP relaxations can be used to generate suboptimal solutions to the control problem. Moreover, it is also shown that the equality constrained SDP relaxation is equivalent to a QP in an important special case.

In this chapter parallel implementations of hybrid MPC will be discussed. Different methods for achieving parallelism at different levels of the algorithms will be surveyed. It will be seen that there are many possible ways of obtaining parallelism for hybrid MPC, and it is by no means clear which possibilities that should be utilized to achieve the best possible performance. To answer this question is a challenge for future research.

In this paper, we present a method to exactly certify the computational complexity of standard suboptimal branch-and-bound (B&B) algorithms for computing suboptimal solutions to mixed-integer linear programming (MILP) problems. Three well-known approaches for suboptimal B&B are considered. This work shows that it is possible to exactly certify the computational complexity also when these approaches are used. Moreover, it also enables to compute exact bounds on the level of suboptimality actually to be obtained online, also for methods previously without any such guarantees. It additionally provides a novel deeper insight into how they affect the performance of the B&B algorithm in terms of the required computation time and memory storage. The exact bounds on the online worst-case computational complexity (e.g., the accumulated number of LP solver iterations or size of the B&B tree) and the worst-case suboptimality computed with the proposed method are very relevant for real-time applications such as Model Predictive Control (MPC) for hybrid systems. The numerical experiments confirm the correctness of the proposed method, and they demonstrate the usefulness of the certification method for certification of a standard online B&B-based MILP solver employing the three considered suboptimal techniques. Copyright (c) 2023 The Authors.

Model predictive control (MPC) with linear performance measure for hybrid systems requires the solution of a mixed-integer linear program (MILP) at each time instance. A well-known method to solve MILP problems is branch-and-bound (B&B). To enhance the performance of B&B, start heuristic methods are often used, where they have shown to be useful supplementary tools to find good feasible solutions early in the B&B search tree, hence, reducing the overall effort in B&B to find optimal solutions. In this work, we extend the recently-presented complexity certification framework for B&B-based MILP solvers to also certify computational complexity of the start heuristics that are integrated into B&B. Therefore, the exact worst-case computational complexity of the three considered start heuristics and, consequently, the B&B method when applying each one can be determined offline, which is of significant importance for real-time applications of hybrid MPC. The proposed algorithms are validated by comparing against the corresponding online heuristic-based MILP solvers in numerical experiments.

A case study of the use of reflections within the Applied physics and electrical engineering program at Linköping University is presented. Reflections have been used for several years and they are done at four stages in the program, in terms of reflections at the end of the Introductory course in year one, design-implement experiences in year three and five, and a reflection document that is the last component of the Master’s thesis. In the first three stages a project model is used to support the planning and execution of the project, and in the project model the project work ends with a reflection. In the reflection document connected to the Master’s thesis the student reflects upon both the thesis work itself and the entire education program, according to the sections and subsections of the CDIO Syllabus. The paper describes how the reflections are integrated in the program. Experiences from student perspective are collected in a small-scale study via interviews with students from year one and year five. 

Model predictive control (MPC) with linear cost function for hybrid systems requires the solution of a mixed-integer linear program (MILP) at each sampling time. The branch and bound (B&B) method is a commonly used tool for solving mixed-integer problems. In this work, we present an algorithm to exactly certify the computational complexity of a standard B&B-based MILP solver. By the proposed method, guarantees on worst-case complexity bounds, e.g., the worst-case iterations or size of the B&B tree, are provided. This knowledge is a fundamental requirement for the implementation of MPC in a real-time system. Different node selection strategies, including best-first, are considered when certifying the complexity of the B&B method. Furthermore, the proposed certification algorithm is extended to consider warm-starting of the inner solver in the B&B. We illustrate the usefulness of the proposed algorithm by comparing against the corresponding online MILP solver in numerical experiments using both cold-started and warm-started LP solvers.

Motion planning and decision-making while considering uncertainty is critical for an autonomous vehicle to safely and efficiently drive on a highway. This paper presents a new combined two-step approach for this problem, where a partially observable Markov decision process (POMDP) is tightly coupled with a scenario model predictive control (SCMPC) step. To generate the scenarios in the SCMPC step, the solution to the POMDP is used together with a novel scenario-reduction procedure, which selects a small representative subset of all scenarios considered in the POMDP. The resulting planner is evaluated in a simulation study where the impact of the two-step approach and the scenario-reduction method is shown.

Neural Networks (NNS) can solve very hard classification and estimation tasks but are less well suited to solve complex sensor fusion challenges, such as end-to-end control of autonomous vehicles. Nevertheless, NN can still be a powerful tool for particular sub-problems in sensor fusion. This would require a reliable and quantifiable measure of the stochastic uncertainty in the predictions that can be compared to classical sensor measurements. However, current NN'S output some figure of merit, that is only a relative model fit and not a stochastic uncertainty. We propose to embed the NN'S in a proper stochastic system identification framework. In the training phase, the stochastic uncertainty of the parameters in the (last layers of the) NN is quantified. We show that this can be done recursively with very few extra computations. In the classification phase, Monte-Carlo (MC) samples are used to generate a set of classifier outputs. From this set, a distribution of the classifier output is obtained, which represents a proper description of the stochastic uncertainty of the predictions. We also show how to use the calculated uncertainty for outlier detection by including an artificial outlier class. In this way, the NN fits a sensor fusion framework much better. We evaluate the approach on images of handwritten digits. The proposed method is shown to be on par with MC dropout, while having lower computational complexity, and the outlier detection almost completely eliminates false classifications.

We propose a semi-explicit approach for linear MPC in which a dual active-set quadratic programming algorithm is initialized through a pre-computed warm start. By using a recently developed complexity certification method for active-set algorithms for quadratic programming, we show how the computational complexity of the dual active-set algorithm can be determined offline for a given warm start. We also show how these complexity certificates can be used as quality measures when constructing warm starts, enabling the online complexity to be reduced further by iteratively refining the warm start. In addition to showing how the computational complexity of any pre-computed warm start can be determined, we also propose a novel technique for generating warm starts with low overhead, both in terms of computations and memory.

A belief-space planning problem for GNSS-denied areas is studied where the location and number of landmarks available are unknown when performing the planning. To be able to plan an informative path in this situation, an algorithm using virtual landmarks to position the platform during the planning phase is studied.  The virtual landmarks are selected to capture the expected information available in different regions of the map, based on the beforehand known landmark density. The main contribution of this work is a better approximation of the obtained information from the virtual landmarks and a theoretical study of the properties of the approximation. Furthermore, the proposed approximation, in itself and its use in a path planner, is investigated with successful results.

The design of reliable path-following controllers is a key ingredient for successful deployment of self-driving vehicles. This controller-design problem is especially challenging for a general 2-trailer with a car-like tractor due to the vehicles structurally unstable joint-angle kinematics in backward motion and the car-like tractors curvature limitations which can cause the vehicle segments to fold and enter a jackknife state. Furthermore, advanced sensors with a limited field of view have been proposed to solve the joint-angle estimation problem online, which introduce additional restrictions on which vehicle states that can be reliably estimated. To incorporate these restrictions at the level of control, a model predictive path-following controller is proposed. By taking the vehicles physical and sensing limitations into account, it is shown in real-world experiments that the performance of the proposed path-following controller in terms of suppressing disturbances and recovering from non-trivial initial states is significantly improved compared to a previously proposed solution where the constraints have been neglected.

The task of maneuvering a multi-steered articulated vehicle in confined environments is difficult even for experienced drivers. In this work, we present an optimization-based trajectory planner targeting low-speed maneuvers in unstructured environments for multi-steered N-trailer vehicles, which are comprised of a car-like tractor and an arbitrary number of interconnected trailers with fixed or steerable wheels. The proposed trajectory planning framework is divided into two steps, where a lattice-based trajectory planner is used in a first step to compute a resolution optimal solution to a discretized version of the trajectory planning problem. The output from the lattice planner is then used in a second step to initialize an optimal control problem solver, which enables the framework to compute locally optimal trajectories that start at the vehicles initial state and reaches the goal state exactly. The performance of the proposed optimization-based trajectory planner is evaluated in a set of practically relevant scenarios for a multi-steered 3-trailer vehicle with a car-like tractor where the last trailer is steerable. Copyright (C) 2020 The Authors.

In this paper we present a method to exactly certify the iteration complexity of a primal active-set algorithm for quadratic programs which is terminated early, given a specific multi-parametric quadratic program. The primal active-set algorithms real-time applicability is, hence, improved by early termination, increasing its computational efficiency, and by the proposed certification method, providing guarantees on worst-case behaviour. The certification method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum, for which the relationship between allowed suboptimality and iterations needed by the primal active-set algorithm is presented. Copyright (C) 2020 The Authors.

This paper presents an optimization-based receding horizon trajectory planning algorithm for dynamical systems operating in unstructured and cluttered environments. The proposed approach is a two-step procedure that uses a motion planning algorithm in a first step to efficiently find a feasible, but possibly suboptimal, nominal solution to the trajectory planning problem where in particular the combinatorial aspects of the problem are solved. The resulting nominal trajectory is then improved in a second optimization-based receding horizon planning step which performs local trajectory refinement over a sliding time window. In the second step, the nominal trajectory is used in a novel way to both represent a terminal manifold and obtain an upper bound on the cost-to-go online. This enables the possibility to provide theoretical guarantees in terms of recursive feasibility, objective function value, and convergence to the desired terminal state. The established theoretical guarantees and the performance of the proposed algorithm are verified in a set of challenging trajectory planning scenarios for a truck and trailer system.   

An approach for belief space planning is presented, where knowledge about the landmark density is used as prior, instead of explicit landmark positions.

Having detailed maps of landmark positions  in a previously unvisited environment is considered unlikely in practice. Instead, it is argued that landmark densities should be used, as they could be estimated from other sources, such as ordinary maps or aerial imagery.

It is shown that it is possible to use virtual landmarks to approximate the landmark density to solve the presented problem. This approximation is also shown to give small errors during evaluation.

The approach is tested in a simulated environment, in conjunction with an extended information filter (EIF), where the computed path is shown to be superior compared to other alternative paths used as benchmarks.

Model Predictive Control (MPC) requires an optimization problem to be solved at each time step. For real-time MPC, it is important to solve these problems efficiently and to have good upper bounds on how long time the solver needs to solve them. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving QPs is primal active-set methods, where a sequence of equality constrained QP subproblems are solved. This paper presents a method for computing which sequence of subproblems a primal active-set method will solve, for every parameter of interest in the parameter space. Knowledge about exactly which sequence of subproblems that will be solved can be used to compute a worst-case bound on how many iterations, and ultimately the maximum time, the active-set solver needs to converge to the solution. Furthermore, this information can be used to tailor the solver for the specific control task. The usefulness of the proposed method is illustrated on a set of MPC problems, where the exact worst-case number of iterations a primal active-set method requires to reach optimality is computed.

This paper considers the problem of gathering information about features of interest in adversarial environments using mobile robots equipped with sensors. The problem is formulated as an informative path planning problem where the objective is to maximize the gathered information while minimizing the tracking performance of the adversarial observer. The optimization problem, that at first glance seems intractable to solve to global optimality, is shown to be equivalent to a mixed-integer semidefinite program that can be solved to global optimality using off-the-shelf optimization tools.

In order to guarantee that a self-driving vehicle is behaving as expected, stability of the closed-loop system needs to be rigorously analyzed. The key components for the lowest levels of control in self-driving vehicles are the controlled vehicle, the low-level controller and the local planner.The local planner that is considered in this work constructs a feasible trajectory by combining a finite number of precomputed motions. When this local planner is considered, we show that the closed-loop system can be modeled as a nonlinear hybrid system. Based on this, we propose a novel method for analyzing the behavior of the tracking error, how to design the low-level controller and how to potentially impose constraints on the local planner, in order to guarantee that the tracking error is bounded and decays towards zero. The proposed method is applied on a truck and trailer system and the results are illustrated in two simulation examples.

This paper presents a systematic approach for computing local solutions to motion planning problems in non-convex environments using numerical optimal control techniques. It extends the range of use of state-of-the-art numerical optimal control tools to problem classes where these tools have previously not been applicable. Today these problems are typically solved using motion planners based on randomized or graph search. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. In this work, it is shown that by combining a Sequential Quadratic Programming (SQP) method with a homotopy approach that gradually transforms the problem from a relaxed one to the original one, practically relevant locally optimal solutions to the motion planning problem can be computed. The approach is demonstrated in motion planning problems in challenging 2D and 3D environments, where the presented method significantly outperforms both a state-of-the-art numerical optimal control method and a state-of-the-art open-source optimizing sampling-based planner commonly used as benchmark. 

In order to meet the requirements for autonomous systems in real world applications, reliable path following controllers have to be designed to execute planned paths despite the existence of disturbances and model errors. In this paper we propose a Linear Quadratic controller for stabilizing a 2-trailer system with possible off-axle hitching around preplanned paths in backward motion. The controller design is based on a kinematic model of a general 2-trailer system including the possibility for off-axle hitching. Closed-loop stability is proved around a set of paths, typically chosen to represent the possible output from the path planner, using theory from linear differential inclusions. Using convex optimization tools a single quadratic Lyapunov function is computed for the entire set of paths.

In many traffic situations there are times where interaction with other drivers is necessary and unavoidable in order to safely progress towards an intended destination. This is especially true for merge manoeuvres into dense traffic, where drivers sometimes must be somewhat aggressive and show the intention of merging in order to interact with the other driver and make the driver open the gap needed to execute the manoeuvre safely. Many motion planning frameworks for autonomous vehicles adopt a reactive approach where simple models of other traffic participants are used and therefore need to adhere to large margins in order to behave safely. However, the large margins needed can sometimes get the system stuck in congested traffic where time gaps between vehicles are too small. In other situations, such as a highway merge, it can be significantly more dangerous to stop on the entrance ramp if the gaps are found to be too small than to make a slightly more aggressive manoeuvre and let the driver behind open the gap needed. To remedy this problem, this work uses the Intelligent Driver Model (IDM) to explicitly model the interaction of other drivers and evaluates the risk by their required deceleration in a similar manner as the Minimum Overall Breaking Induced by Lane change (MOBIL) model that has been used in large scale traffic simulations before. This allows the algorithm to evaluate the effect on other drivers depending on our own trajectory plans by simulating the nearby traffic situation. Finding a globally optimal solution is often intractable in these situations so instead a large set of candidate trajectories are generated that are evaluated against the traffic scene by forward simulations of other traffic participants. By discretization and using an efficient trajectory generator together with efficient modelling of the traffic scene real-time demands can be met.

In this paper a cascaded approach for stabilizationand path tracking of a general 2-trailer vehicle configurationwith an off-axle hitching is presented. A low level LinearQuadratic controller is used for stabilization of the internalangles while a pure pursuit path tracking controller is used ona higher level to handle the path tracking. Piecewise linearityis the only requirement on the control reference which makesthe design of reference paths very general. A Graphical UserInterface is designed to make it easy for a user to design controlreferences for complex manoeuvres given some representationof the surroundings. The approach is demonstrated with challengingpath following scenarios both in simulation and on asmall scale test platform.

In this paper an extension to the sampling based motion planning framework CL-RRT is presented. The framework uses a system model and a stabilizing controller to sample the perceived environment and build a tree of possible trajectories that are evaluated for execution. Complex system models and constraints are easily handled by a forward simulation making the framework widely applicable. To increase operational safety we propose a sampling recovery scheme that performs a deterministic brake profile regeneration using collision information from the forward simulation. This greatly increases the number of safe trajectories and also reduces the number of samples that produce infeasible results. We apply the framework to a Scania G480 mining truck and evaluate the algorithm in a simple yet challenging obstacle course and show that our approach greatly increases the number of feasible paths available for execution.

In this chapter parallel implementations of hybrid MPC will be discussed. Different methods for achieving parallelism at different levels of the algorithms will be surveyed. It will be seen that there are many possible ways of obtaining parallelism for hybrid MPC, and it is by no means clear which possibilities that should be utilized to achieve the best possible performance. To answer this question is a challenge for future research.

In this paper we describe a procedure for computation of optimal and suboptimal explicit MPC controllers for hybrid systems. This procedure is based on a parametric branch and bound approach, which allows the user to specify a state-dependent suboptimality tolerance. Depending on the choice of the tolerance, an optimal solution can be sought for, a merely feasible solution can be sought for, a certain suboptimality can be enforced, or a priori stability guarantees can be given. Moreover, the proposed procedure does not require that the computation of the optimal solution is tractable.

This paper deals with efficient point location in large polytopic data sets, as required for the implementation of Explicit Model Predictive Control laws. The focus is on linear decision functions (LDF) which performs scalar product evaluations and an interval search to return the index set of candidate polytopes possibly containing the query point. We generalize a special LDF which uses the euclidean directions of the state space and the projection of the polytopes bounding boxes onto these directions to identify the candidate polytopes. Our generalized LDF may use any vector of the state space as direction and the projection of any points contained in the polytopes. We prove that there is a finite number of LDFs returning different index sets and show how to find the one returning the lowest worst-case number of candidate polytopes, a number that can be seen as a performance measure. Based on the results from an exhaustive study of low complexity problems, heuristics for the choice of the LDF are derived, involving the mean shift algorithm from pattern recognition. The result of extensive simulations on a larger problem attest the generalized LDF a 40% gain in performance, mainly through adjusted directions, at a small additional storage cost.

The objective of this work is to derive a QPalgorithm tailored for MPC. More specific, the primary targetapplication is MPC for discrete-time hybrid systems. A desiredproperty of the algorithm is that warm starts should be possibleto perform efficiently. This property is very important for online linear MPC, and it is crucial in branch and bound forhybrid MPC. In this paper, a dual active set-like QP methodwas chosen because of its warm start properties. A drawbackwith classical active set methods is that they often requiremany iterations in order to find the active set in optimum.Gradient projection methods are methods known to be ableto identify this active set very fast and such a method wastherefore chosen in this work. The gradient projection methodwas applied to the dual QP problem and it was tailored for theMPC application. Results from numerical experiments indicatethat the performance of the new algorithm is very good, bothfor linear MPC as well as for hybrid MPC. It is also noticed thatthe number of QP iterations is significantly reduced compared to classical active set methods.

In this work, different relaxations applicable to an MPC problem with a mix of real valued and binary valued control signals are compared. In the problem description considered, there are linear inequality constraints on states and control signals. The relaxations are related theoretically and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The relaxations considered are the quadratic programming (QP) relaxation, the standard semidefinite programming (SDP) relaxation and an equality constrained SDP relaxation. The result is that the standard SDP relaxation is the one that usually gives the best bound and is most computationally demanding, while the QP relaxation is the one that gives the worst bound and is least computationally demanding. The equality constrained relaxation presented in this paper often gives a better bound than the QP relaxation and is less computationally demanding compared to the standard SDP relaxation. Furthermore, it is also shown how the equality constrained SDP relaxation can be efficiently computed by solving the Newton system in an Interior Point algorithm using a Riccati recursion. This makes it possible to compute the equality constrained relaxation with approximately linear computational complexity in the prediction horizon.

The objective with this work is to derive an MIQP solver tailored for MPC. The MIQP solver is built on the branch and bound method, where QP relaxations of the original problem are solved in the nodes of a binary search tree. The difference between the subproblems is often small and therefore it is interesting to be able to use a previous solution as a starting point in a new subproblem. This is referred to as a warm start of the solver. Because of its good warm start properties, a dual active set QP method was chosen. The method is tailored for MPC by solving a part of the KKT system using a Riccati recursion, which makes the computational complexity of the QP iterations grow linearly with the prediction horizon. Simulation results are presented both for the QP solver itself and when it is incorporated as a part of the MIQP solver. In both cases the computational complexity is significantly reduced compared to if a primal active set solver not utilizing structure is used.

In this paper a preprocessing algorithm for binary quadratic programming problems is presented. For some types of binary quadratic programming problems, the algorithm can compute the optimal value for some or all integer variables without approximations in polynomial time. When the optimal multiuser detection problem is formulated as a maximum likelihood problem, a binary quadratic programming problem has to be solved. Fortunately, the low correlation between different users in the multiuser detection problem enables the use of the preprocessing algorithm. Simulations show that the preprocessing algorithm is able to compute almost all variables in the problem, even though the system is heavily loaded and affected by noise.

In this paper a preprocessing algorithm for unconstrained mixed integer quadratic programming problems and binary quadratic programming problems is presented. The algorithm applies to problems with certain properties, which are further described in the paper. When the algorithm is applied to a problem with these properties, the optimal value for some or all integer variables can be computed without approximations in polynomial time. The algorithm is first derived for the binary quadratic programming problem and the result is then extended to the mixed integer quadratic programming problem by transforming the latter problem into the first problem. Both mentioned quadratic programming problems have several important applications. In this paper, the focus is on model predictive control problems with both real-valued and binary control signals. As an illustration of the method, the algorithm is applied to two different problems of this type.

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.

Model Predictive Control (MPC) is increasing in popularity in industry as more efficient algorithms for solving the related optimization problem are developed. The main computational bottle-neck in on-line MPC is often the computation of the search step direction, \ie the Newton step, which is often done using generic sparsity exploiting algorithms or Riccati recursions. However, as parallel hardware is becoming increasingly popular the demand for efficient parallel algorithms for solving the Newton step is increasing. In this paper a tailored, non-iterative parallel algorithm for computing the Riccati factorization is presented. The algorithm exploits the special structure in the MPC problem, and when sufficiently many processing units are available, the complexity of the algorithm scales logarithmically in the prediction horizon. Computing the Newton step is the main computational bottle-neck in many MPC algorithms and the algorithm can significantly reduce the computation cost for popular state-of-the-art MPC algorithms.

The optimum multiuser detection problem can be formulated as a maximum likelihood problem, which yields a binary quadratic programming problem to be solved. Generally this problem is NP-hard and is therefore hard to solve in real time. In this paper, a preprocessing algorithm is presented which makes it possible to detect some or all users optimally for a low computational cost if signature sequences with low cross correlation, e.g., Gold sequences, are used. The algorithm can be interpreted as, e.g., an adaptive tradeoff between parallel interference cancellation and successive interference cancellation. Simulations show that the preprocessing algorithm is able to optimally compute more than 94,% of the bits in the problem when the users are time-synchronous, even though the system is heavily loaded and affected by noise. Any remaining bits, not computed by the preprocessing algorithm, can either be computed by a suboptimal detector or an optimal detector. Simulations of the time-synchronous case show that if a suboptimal detector is chosen, the bit error rate (BER) rate is significantly reduced compared with using the suboptimal detector alone.

The objective of this work is to derive a Mixed Integer Quadratic Programming algorithm tailored for Model Predictive Control for hybrid systems. The Mixed Integer Quadratic Programming algorithm is built on the branch and bound method, where Quadratic Programming relaxations of the original problem are solved in the nodes of a binary search tree. The difference between these subproblems is often small and therefore it is interesting to be able to use a previous solution as a starting point in a new subproblem. This is referred to as a warm start of the solver. Because of its warm start properties, an algorithm that works similar to an active set method is desired. A drawback with classical active set methods is that they often require many iterations in order to find the active set in optimum. So-called gradient projection methods are known to be able to identify this active set very fast. In the algorithm presented in this report, an algorithm built on gradient projection and projection of a Newton search direction onto the feasible set is used. It is a variant of a previously presented algorithm by the authors and makes it straightforward to utilize the previous result, where it is shown how the Newton search direction for the dual MPC problem can be computed very efficiently using Riccati recursions. As in the previous work, this operation can be performed with linear computational complexity in the prediction horizon. Moreover, the gradient computation used in the gradient projection part of the algorithm is also tailored for the problem in order to decrase the computational complexity. Furthermore, is is shown how a Riccati recursion still can be useful in the case when the system of equations for the ordinary search directino is inconsistent. In numerical experiments, the algorithm shows good performance, and it seems like the gradient projection strategy efficiently cuts down the number of Newton steps necessary to compute in order to reach the solution. When the algorithm is used as a part of an MIQP solver for hybrid MPC, the performance is still very good for small problems. However, for more difficult problems, there still seems to be some more work to do in order to get the performance of the commercial state-of-the-art solver CPLEX.

The objective of this work is to derive an MIQP solver tailored for MPC. The MIQP solver is built on the branch and bound method, where QP relaxations of the original problem are solved in the nodes of a binary search tree. The difference between the subproblems is often small and therefore it is interesting to be able to use a previous solution as a starting point in a new subproblem. This is referred to as a warm start of the solver. Because of its good warm start properties, a dual active set QP method was chosen. The method is tailored for MPC by solving a part of the KKT system using a Riccati recursion, which makes the computational complexity of the QP iterations grow linearly with the prediction horizon. Simulation results are presented both for the QP solver itself and when it is incorporated as a part of the MIQP solver. In both cases the computational complexity is significantly reduced compared to if a primal active set solver not utilizing structure is used.

In this paper a preprocessing algorithm for binary quadratic programming problems is presented. For some types of binary quadratic programming problems, the algorithm can compute the optimal value for some or all integer variables without approximations in polynomial time. When the optimal multiuser detection problem is formulated as a maximum likelihood problem, a binary quadratic programming problem has to be solved. Fortunately, the low correlation between different users in the multiuser detection problem enables the use of the preprocessing algorithm. Simulations show that the preprocessing algorithm is able to compute almost all variables in the problem, even though the system is heavily loaded and affected by noise.