liu.seSearch for publications in DiVA
Change search
Refine search result
12 1 - 50 of 57
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Andersson, Olov
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Ljungqvist, Oskar
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Tiger, Mattias
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Heintz, Fredrik
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Receding-Horizon Lattice-based Motion Planning with Dynamic Obstacle Avoidance2018In: 2018 IEEE Conference on Decision and Control (CDC), Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 4467-4474Conference paper (Refereed)
    Abstract [en]

    A key requirement of autonomous vehicles is the capability to safely navigate in their environment. However, outside of controlled environments, safe navigation is a very difficult problem. In particular, the real-world often contains both complex 3D structure, and dynamic obstacles such as people or other vehicles. Dynamic obstacles are particularly challenging, as a principled solution requires planning trajectories with regard to both vehicle dynamics, and the motion of the obstacles. Additionally, the real-time requirements imposed by obstacle motion, coupled with real-world computational limitations, make classical optimality and completeness guarantees difficult to satisfy. We present a unified optimization-based motion planning and control solution, that can navigate in the presence of both static and dynamic obstacles. By combining optimal and receding-horizon control, with temporal multi-resolution lattices, we can precompute optimal motion primitives, and allow real-time planning of physically-feasible trajectories in complex environments with dynamic obstacles. We demonstrate the framework by solving difficult indoor 3D quadcopter navigation scenarios, where it is necessary to plan in time. Including waiting on, and taking detours around, the motions of other people and quadcopters.

  • 2.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Applications of Integer Quadratic Programming in Control and Communication2005Licentiate thesis, monograph (Other academic)
    Abstract [en]

    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 principles is the discrete-time method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, 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 from constrained linear systems 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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two 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 simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as 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 QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers.

  • 3.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Att handleda en uppgift utan facit2007Report (Other academic)
  • 4.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Controlling the level of sparsity in MPC2015In: Systems & control letters (Print), ISSN 0167-6911, E-ISSN 1872-7956, Vol. 76, p. 1-7Article in journal (Refereed)
    Abstract [en]

    In optimization algorithms used for on-line Model Predictive Control (MPC), linear systems of equations are often solved in each iteration. This is true both for Active Set methods as well as for Interior Point methods, and for linear MPC as well as for nonlinear MPC and hybrid MPC. The main computational effort is spent while solving these linear systems of equations, and hence, it is of greatest interest to solve them efficiently. Classically, the optimization problem has been formulated in either of two ways. One leading to a sparse linear system of equations involving relatively many variables to compute in each iteration and another one leading to a dense linear system of equations involving relatively few variables. In this work, it is shown that it is possible not only to consider these two distinct choices of formulations. Instead it is shown that it is possible to create an entire family of formulations with different levels of sparsity and number of variables, and that this extra degree of freedom can be exploited to obtain even better performance with the software and hardware at hand. This result also provides a better answer to a recurring question in MPC; should the sparse or dense formulation be used.

  • 5.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Integer Quadratic Programming for Control and Communication2008Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    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.

    List of papers
    1. A Preprocessing Algorithm for MIQP Solvers with Applications to MPC
    Open this publication in new window or tab >>A Preprocessing Algorithm for MIQP Solvers with Applications to MPC
    2004 (English)In: Proceedings of the 43rd IEEE Conference on Decision and Control, 2004, p. 2497-2502Conference paper, Published paper (Refereed)
    Abstract [en]

    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 resultis 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.

    Keywords
    Predictive control, Integer programming, Quadratic programming
    National Category
    Engineering and Technology Control Engineering
    Identifiers
    urn:nbn:se:liu:diva-12902 (URN)10.1109/CDC.2004.1428790 (DOI)0-7803-8682-5 (ISBN)
    Conference
    43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, December, 2004
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
    2. A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences
    Open this publication in new window or tab >>A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences
    2008 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 56, no 9, p. 4377-4385Article in journal (Refereed) Published
    Abstract [en]

    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.

    Place, publisher, year, edition, pages
    IEEE Signal Processing Society, 2008
    Keywords
    Code division multiple access, Computational complexity, Error statistics, Interference suppression, Maximum likelihood detection, Multiuser detection, Quadratic programming, Sequences, CDMA channel models, Gold sequences, NP-hard problem, Binary quadratic programming problem, Bit error rate, Low cross correlation, Low-complexity high-performance preprocessing algorithm, Maximum likelihood problem, Optimal detector, Optimum multiuser detection problem, Parallel interference cancellation, Suboptimal detector, Successive interference cancellation, Time-synchronous users
    National Category
    Control Engineering
    Identifiers
    urn:nbn:se:liu:diva-12903 (URN)10.1109/TSP.2008.926190 (DOI)
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2017-12-13
    3. A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC
    Open this publication in new window or tab >>A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC
    2006 (English)In: Proceedings of the 45th IEEE Conference on Decision and Control, 2006, p. 5693-5698Conference paper, Published paper (Refereed)
    Abstract [en]

    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.

    Keywords
    Riccati equations, Computational complexity, Integer programming, Iterative methods, Predictive control, Quadratic programming, Tree searching, KKT system, QP iterations, QP relaxations, Riccati recursion, Binary search tree, Branch and bound method, Computational complexity, Mixed integer dual quadratic programming algorithm, Model predictive control, Prediction horizon
    National Category
    Control Engineering
    Identifiers
    urn:nbn:se:liu:diva-12904 (URN)10.1109/CDC.2006.377215 (DOI)1-4244-0171-2 (ISBN)
    Conference
    45th IEEE Conference on Decision and Control, San Diego, CA, USA, December, 2006
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
    4. A dual gradient projection quadratic programming algorithm tailored for mixed integer predictive control
    Open this publication in new window or tab >>A dual gradient projection quadratic programming algorithm tailored for mixed integer predictive control
    Manuscript (Other academic)
    Identifiers
    urn:nbn:se:liu:diva-12905 (URN)
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2010-01-13
    5. On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
    Open this publication in new window or tab >>On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
    2007 (English)In: Proceedings of the 7th IFAC Symposium on Nonlinear Control Systems, Curran Associates, Inc., 2007, p. 585-590Conference paper, Published paper (Refereed)
    Abstract [en]

    In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality constrained SDP relaxation. The relaxations are related theoretically, and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The result is that for long prediction horizons, the equality constrained SDP relaxation proposed in this paper provides a good trade-off between the quality of the relaxation and the computational time.

    Place, publisher, year, edition, pages
    Curran Associates, Inc., 2007
    Series
    LiTH-ISY-R, ISSN 1400-3902 ; 2771
    Keywords
    Predictive control, Hybrid systems, Binary control, Integer programing, Semidefinite programming
    National Category
    Control Engineering
    Identifiers
    urn:nbn:se:liu:diva-12906 (URN)10.3182/20070822-3-ZA-2920.00096 (DOI)978-3-902661-28-9 (ISBN)
    Conference
    7th IFAC Symposium on Nonlinear Control Systems, Pretoria, South Africa, August, 2007
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31Bibliographically approved
    6. Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations
    Open this publication in new window or tab >>Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations
    2007 (English)In: Proceedings of the 46th IEEE Conference on Decision and Control, 2007, p. 4103-4109Conference paper, Published paper (Refereed)
    Abstract [en]

    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.

    Keywords
    Newton method, Riccati equations, Computational complexity, Predictive control, Quadratic programming, Relaxation theory, Interior point algorithm, Newton system, Riccati recursion, Linear computational complexity, Linear inequality constraints, Mixed integer predictive control
    National Category
    Engineering and Technology Control Engineering
    Identifiers
    urn:nbn:se:liu:diva-12907 (URN)10.1109/CDC.2007.4434608 (DOI)978-1-4244-1497-0 (ISBN)978-1-4244-1498-7 (ISBN)
    Conference
    46th IEEE Conference on Decision and Control, New Orleans, LA, USA, December, 2007
    Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31Bibliographically approved
  • 6.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Besselmann, Thomas
    Asea Brown Boveri Corp Research, Switzerland ETH, Switzerland .
    Martino Raimondo, Davide
    University of Pavia, Italy ETH, Switzerland .
    Morari, Manfred
    ETH, Switzerland .
    A parametric branch and bound approach to suboptimal explicit hybrid MPC2014In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 50, no 1, p. 240-246Article in journal (Refereed)
    Abstract [en]

    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.

  • 7.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Besselmann, Thomas
    ETH Zürich, Switzerland.
    Raimondo, Davide
    ETH Zürich, Switzerland.
    Morari, Manfred
    ETH Zürich, Switzerland.
    Suboptimal Explicit Hybrid MPC via Branch and Bound2011In: Proceedings of the 18th IFAC World Congress, 2011, p. 10281-10286Conference paper (Refereed)
    Abstract [en]

    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.

  • 8.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Gunnarsson, Fredrik
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Preprocessing Algorithm Applicable to the Multiuser Detection Problem2005In: Proceedings of Radiovetenskap och Kommunikation 2005, 2005Conference paper (Other academic)
    Abstract [en]

    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.

  • 9.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Gunnarsson, Fredrik
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Preprocessing Algorithm Applicable to the Multiuser Detection Problem2005Report (Other academic)
    Abstract [en]

    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.

  • 10.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Mixed Integer Predictive Control2008Report (Other academic)
    Abstract [en]

    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.

  • 11.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Model Predictive Control2008In: Proceedings of Reglermöte 2008, 2008, p. 202-209Conference paper (Other academic)
    Abstract [en]

    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.

  • 12.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Model Predictive Control2008In: Proceedings of the 47th IEEE Conference on Decision and Control, 2008, p. 3057-3064Conference paper (Refereed)
    Abstract [en]

    The objective of this work is to derive a QP algorithm tailored for MPC. More specifically, the primary target application is MPC for discrete-time hybrid systems. A desired property of the algorithm is that warm starts should be possible to perform efficiently. This property is very important for on-line linear MPC, and it is crucial in branch and bound for hybrid MPC. In this paper, a dual active set-like QP method was chosen because of its warm start properties. A drawback with classical active set methods is that they often require many iterations in order to find the active set in optimum. Gradient projection methods are methods known to be able to identify this active set very fast and such a method was therefore chosen in this work. The gradient projection method was applied to the dual QP problem and it was tailored for the MPC application. Results from numerical experiments indicate that the performance of the new algorithm is very good, both for linear MPC as well as for hybrid MPC. It is also noticed that the number of QP iterations is significantly reduced compared to classical active set methods. 

  • 13.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC2007Report (Other academic)
    Abstract [en]

    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.

  • 14.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC2006In: Proceedings of the 45th IEEE Conference on Decision and Control, 2006, p. 5693-5698Conference paper (Refereed)
    Abstract [en]

    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.

  • 15.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Preprocessing Algorithm for MIQP Solvers with Applications to MPC2004In: Proceeding of Reglermöte 2004, 2004Conference paper (Other academic)
    Abstract [en]

    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.

  • 16.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Preprocessing Algorithm for MIQP solvers with Applications to MPC2004Report (Other academic)
    Abstract [en]

    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.

  • 17.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Preprocessing Algorithm for MIQP Solvers with Applications to MPC2004In: Proceedings of the 43rd IEEE Conference on Decision and Control, 2004, p. 2497-2502Conference paper (Refereed)
    Abstract [en]

    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 resultis 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.

  • 18.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Mixed Integer Predictive Control Using a Tailored Mixed Integer Dual Quadratic Programming Algorithm2006In: Proceedings of Reglermöte 2006, 2006Conference paper (Other academic)
    Abstract [en]

    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.

  • 19.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Parallel implementation of hybrid MPC2014In: Distributed Model Predictive Control Made Easy / [ed] José M. Maestre and Rudy R. Negenborn, Springer Netherlands, 2014, p. 375-392Chapter in book (Refereed)
    Abstract [en]

    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.

  • 20.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Towards Parallel Implementation of Hybrid MPC: A Survey and Directions for Future Research2012In: Distributed decision making and control / [ed] Rolf Johansson and Anders Rantzer, Springer London, 2012, p. 313-338Conference paper (Refereed)
    Abstract [en]

    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.

  • 21.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Gunnarsson, Fredrik
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences2008Report (Other academic)
    Abstract [en]

    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.

  • 22.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Gunnarsson, Fredrik
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences2008In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 56, no 9, p. 4377-4385Article in journal (Refereed)
    Abstract [en]

    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.

  • 23.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Vandenberghe, Lieven
    University of California, LA, USA.
    Relaxations Applicable to Mixed Integer Predictive Control - Comparisons and Efficient Computations2008Report (Other academic)
    Abstract [en]

    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.

  • 24.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Vandenberghe, Lieven
    University of Californa, LA, USA.
    Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations2007In: Proceedings of the 46th IEEE Conference on Decision and Control, 2007, p. 4103-4109Conference paper (Refereed)
    Abstract [en]

    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.

  • 25.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Morari, Manfred
    ETH Zürich, Switzerland.
    An Alternative use of the Riccati Recursion for Efficient Optimization2012In: Systems & control letters (Print), ISSN 0167-6911, E-ISSN 1872-7956, Vol. 61, no 1, p. 37-40Article in journal (Refereed)
    Abstract [en]

    In optimization routines used for on-line Model Predictive Control (MPC), linear systems of equations are solved in each iteration. This is true both for Active Set (AS) solvers as well as for Interior Point (IP) solvers, and for linear MPC as well as for nonlinear MPC and hybrid MPC. The main computational effort is spent while solving these linear systems of equations, and hence, it is of great interest to solve them efficiently. In high performance solvers for MPC, this is performed using Riccati recursions or generic sparsity exploiting algorithms. To be able to get this performance gain, the problem has to be formulated in a sparse way which introduces more variables. The alternative is to use a smaller formulation where the objective function Hessian is dense. In this work, it is shown that it is possible to exploit the structure also when using the dense formulation. More specifically, it is shown that it is possible to efficiently compute a standard Cholesky factorization for the dense formulation. This results in a computational complexity that grows quadratically in the prediction horizon length instead of cubically as for the generic Cholesky factorization.

  • 26.
    Axehill, Daniel
    et al.
    Automatic Control Laboratory, ETH Zürich, CH-8092, Switzerland .
    Morari, Manfred
    Automatic Control Laboratory, ETH Zürich, CH-8092, Switzerland .
    Improved complexity analysis of branch and bound for hybrid MPC2010In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC), 2010, p. 4216-4222Conference paper (Refereed)
    Abstract [en]

    In this work, the computational effort of Mixed Integer Quadratic Programming solvers based on branch and bound is studied. The origin of this interest is that hybrid MPC problems for Mixed Logical Dynamical systems can be formulated as optimization problems in this form and since these have to be solved in real-time, it is interesting to be able to compute a good bound on the computational complexity. Classically, the bound on the worst case computational complexity is given by the case when it is necessary to expand all nodes in the entire tree. The usefulness of branch and bound relies on the fact that this worst case scenario is very rare in practice. The objective in this work is to reduce the gap between the conservative worst case bound on the number of nodes and the number of nodes actually necessary to explore on-line in the optimization routine. Approaches to compute this bound are presented and motivated theoretically and the performance of the analysis is evaluated in numerical examples.

  • 27.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Sjöberg, Johan
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Lindqvist, Kristian
    Scania.
    Adaptive Cruise Control for Heavy Vehicles2004In: Proceedings of Reglermöte 2004, 2004Conference paper (Other academic)
    Abstract [en]

    An Adaptive Cruise Controller (ACC) is an extension of an ordinary cruise controller. In addition to maintaining a desired set speed, an ACC can also maintain a desired time gap to the vehicle ahead. For this end, both the engine and the brakes are controlled. The interest in the MPC-controller as a solution to the problem was to achieve automatic actuator switching, thus with no explicitly defined switch points. The MPC-controller is based on a model of the system including bounds on the control signals and on linear combinations of the states. Using this knowledge, the MPC-controller will choose the correct actuator for the current driving situation. Among the drawbacks, it can be mentioned that the variant of MPC, used in this paper, is too complex to implement in the control system currently used in trucks.

  • 28.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Vandenberghe, Lieven
    University of California Los Angeles, USA.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Convex Relaxations for Mixed Integer Predictive Control2010In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 46, no 9, p. 1540-1545Article in journal (Refereed)
    Abstract [en]

    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.

  • 29.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Vandenberghe, Lieven
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals2007Report (Other academic)
    Abstract [en]

    In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an equality constrained SDP relaxation. The relaxations are related theoretically and both the tightness of the bounds and the computational complexities are compared in numerical experiments.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 much less computationally demanding compared to the standard SDP relaxation. Furthermore, for a special case, it is shown that the equality constrained SDP relaxation can be cast in the form of a QP. This makes it possible to replace the ordinary QP relaxation usually used in branch and bound for these problems witha tighter SDP relaxation. Numerical experiments indicate that this relaxation can decrease the overall computational time spent in branch and bound.

  • 30.
    Axehill, Daniel
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Vandenberghe, Lieven
    University of California, USA.
    Hansson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals2007In: Proceedings of the 7th IFAC Symposium on Nonlinear Control Systems, Curran Associates, Inc., 2007, p. 585-590Conference paper (Refereed)
    Abstract [en]

    In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality constrained SDP relaxation. The relaxations are related theoretically, and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The result is that for long prediction horizons, the equality constrained SDP relaxation proposed in this paper provides a good trade-off between the quality of the relaxation and the computational time.

  • 31.
    Axelsson, Patrik
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Glad, Torkel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Norrlöf, Mikael
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Controllability Aspects for Iterative Learning ControlManuscript (preprint) (Other academic)
    Abstract [en]

    This paper discusses the aspects of controllability in the iteration domain for systems that are controlled using iterative learning control (ILC). The focus is on controllability for a proposed state space model in the iteration domain and it relates to an assumption often used to prove convergence of ILC algorithms. It is shown that instead of investigating controllability it is more suitable to use the concept of target path controllability (TPC), where it is investigated if a system can follow a trajectory instead of the ability to control the system to an arbitrary point in the state space. Finally, a simulation study is performed to show how the ILC algorithm can be designed using the LQ-method, if the state space model in the iteration domain is output controllable. The LQ-method is compared to the standard norm-optimal ILC algorithm, where it is shown that the control error can be reduced significantly using the LQ-method compared to the norm-optimal approach.

  • 32.
    Axelsson, Patrik
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Glad, Torkel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Norrlöf, Mikael
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Iterative Learning Control - From a Controllability Point of View2014In: Proceedings of Reglermöte 2014, 2014Conference paper (Other academic)
  • 33.
    Bergman, Kristoffer
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Combining Homotopy Methods and Numerical Optimal Control to Solve Motion Planning Problems2018In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium, 2018, p. 347-354Conference paper (Refereed)
    Abstract [en]

    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. 

  • 34.
    Bergman, Kristoffer
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Ljungqvist, Oskar
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Improved Optimization of Motion Primitives for Motion Planning in State Lattices2019Conference paper (Refereed)
    Abstract [en]

    In this paper, we propose a framework for generating motion primitives for lattice-based motion planners automatically. Given a family of systems, the user only needs to specify which principle types of motions, which are here denoted maneuvers, that are relevant for the considered system family. Based on the selected maneuver types and a selected system instance, the algorithm not only automatically optimizes the motions connecting pre-defined boundary conditions, but also simultaneously optimizes the end-point boundary conditions as well. This significantly reduces the time consuming part of manually specifying all boundary value problems that should be solved, and no exhaustive search to generate feasible motions is required. In addition to handling static a priori known system parameters, the framework also allows for fast automatic re-optimization of motion primitives if the system parameters change while the system is in use, e.g, if the load significantly changes or a trailer with a new geometry is picked up by an autonomous truck. We also show in several numerical examples that the framework can enhance the performance of the motion planner in terms of total cost for the produced solution.

  • 35.
    Boström-Rost, Per
    et al.
    Linköping University, Faculty of Science & Engineering. Linköping University, Department of Electrical Engineering, Automatic Control.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Hendeby, Gustaf
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Informative Path Planning for Active Tracking of Agile Targets2019In: 2019 IEEE Aerospace Conference, Institute of Electrical and Electronics Engineers (IEEE), 2019, p. 1-11, article id 06.0701Conference paper (Refereed)
    Abstract [en]

    This paper proposes a method to generate informative trajectories for a mobile sensor that tracks agile targets.The goal is to generate a sensor trajectory that maximizes the tracking performance, captured by a measure of the covariance matrix of the target state estimate. The considered problem is acombination of estimation and control, and is often referred to as informative path planning (IPP). When using nonlinear sensors, the tracking performance depends on the actual measurements, which are naturally unavailable in the planning stage.The planning problem hence becomes a stochastic optimization problem, where the expected tracking performance is used inthe objective function. The main contribution of this work is anapproximation of the problem based on deterministic sampling of the predicted target distribution. This is in contrast to prior work, where only the most likely target trajectory is considered.It is shown that the proposed method greatly improves the ability to track agile targets, compared to a baseline approach.   

  • 36.
    Boström-Rost, Per
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Hendeby, Gustaf
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Informative Path Planning in the Presence of Adversarial Observers2019In: 2019 22nd International Conference on Information Fusion (FUSION), 2019Conference paper (Refereed)
    Abstract [en]

    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.

  • 37.
    Boström-Rost, Per
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Hendeby, Gustaf
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    On Global Optimization for Informative Path Planning2018In: IEEE Control Systems Letters, ISSN 2475-1456, Vol. 2, no 4, p. 833-838Article in journal (Refereed)
    Abstract [en]

    The problem of path planning for mobilesensors with the task of target monitoring is considered. A receding horizon optimal control approach based on the information filter is presented, where the limited field of view of the sensor can be modeled by introducing binary variables. The resulting nonlinear mixed integer problem to be solved in each sample, with no apparent tractable solution, is shown to be equivalent to a problem that robustly can be solved to global optimality using off-the-shelf optimization tools.

  • 38.
    Elfstadius, Martin
    et al.
    Stockholm, Sweden.
    Gecer, Daniel
    KTH, Stockholm, Sweden.
    Nordström, Lars
    KTH, Stockholm, Sweden.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Method to detect and measure potential market power on electricity markets using the concept of monopolistic energy2009In: Proceedings of the Power Systems Conference and Exposition, 2009, IEEE , 2009, p. 1-7Conference paper (Refereed)
    Abstract [en]

    The existence of market power is a serious concern in modern electric energy markets. Systems and processes that monitor the trading is needed and much research and many proposals on how to deal with the problem have been introduced over the past couple of years. A challenge to all such methods is execution speed, since the identification of market power needs to be done in real-time as market prices are settled. To overcome this challenge the methods need to be simple, involving limited computational effort. This paper presents a simple method with the potential of overcoming the challenge of execution speed. The method is based on the idea of determining the participants with the ability to make considerable increases in price raises without losing all market shares. Such determination can be made in advance during day ahead trading to identify critical areas. During realtime settlement, the method can then be used in a second iteration to study the identified critical areas. In the paper we propose a way to calculate the remaining market shares after a large price raise and refer to these as Monopolistic Energy Levels. These calculated levels of energy, that are deliverable by a single certain participant or by a certain group of participants, are caused by the active congestions in the network. The method detects the quantity of these energy levels and their respective locations in the network. This is a prospective method when used with a prediction of the following days demand. The paper presents the background and development of the proposed method. The use of AC and DC power flow as means to determine the monopolistic energy levels are analyzed and discussed. The paper is concluded with examples of application of the method to a simple multi area power system.

  • 39.
    Evestedt, Niclas
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Trincavelli, Marco
    Research and Development, Scania CV AB, Södertälje, Sweden.
    Gustafsson, Fredrik
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Sampling Recovery for Closed Loop Rapidly Expanding Random Tree using Brake Profile Regeneration2015In: Intelligent Vehicles Symposium (IV), 2015 IEEE, IEEE , 2015, p. 101-106Conference paper (Refereed)
    Abstract [en]

    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.

  • 40.
    Evestedt, Niclas
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Ljungqvist, Oskar
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Motion planning for a reversing general 2-trailer configuration using Closed-Loop RRT2016In: 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Institute of Electrical and Electronics Engineers (IEEE), 2016, p. 3690-3697Conference paper (Refereed)
    Abstract [en]

    Reversing with a dolly steered trailer configura- tion is a hard task for any driver without extensive training. In this work we present a motion planning and control framework that can be used to automatically plan and execute complicated manoeuvres. The unstable dynamics of the reversing general 2- trailer configuration with off-axle hitching is first stabilised by an LQ-controller and then a pure pursuit path tracker is used on a higher level giving a cascaded controller that can track piecewise linear reference paths. This controller together with a kinematic model of the trailer configuration is then used for forward simulations within a Closed-Loop Rapidly Exploring Random Tree framework to generate motion plans that are not only kinematically feasible but also include the limitations of the controller’s tracking performance when reversing. The approach is evaluated over a series of Monte Carlo simulations on three different scenarios and impressive success rates are achieved. Finally the approach is successfully tested on a small scale test platform where the motion plan is calculated and then sent to the platform for execution. 

  • 41.
    Evestedt, Niclas
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Ljungqvist, Oskar
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Path tracking and stabilization for a reversing general 2-trailer configuration using a cascaded control approach2016In: Intelligent Vehicles Symposium (IV), 2016 IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2016, p. 1156-1161Conference paper (Refereed)
    Abstract [en]

    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.

  • 42.
    Evestedt, Niclas
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Ward, Erik
    KTH, Royal Institute of Technology in Stockholm, Sweden.
    Folkesson, John
    KTH, Royal Institute of Technology in Stockholm, Sweden.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Interaction aware trajectory planning for merge scenarios in congested traffic situations2016In: 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC), Institute of Electrical and Electronics Engineers (IEEE), 2016, p. 465-472Conference paper (Refereed)
    Abstract [en]

    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.

  • 43.
    Fuchs, Alexander
    et al.
    ETH, Switzerland.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Morari, Manfred
    ETH, Switzerland.
    Lifted Evaluation of mp-MIQP Solutions2015In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 60, no 12, p. 3328-3331Article in journal (Refereed)
    Abstract [en]

    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.

  • 44.
    Fuchs, Alexander
    et al.
    Automatic Control Laboratory, Swiss Federal Institute of Technology (ETH Zürich), Physikstrasse 3, CH - 8092, Switzerland.
    Axehill, Daniel
    Automatic Control Laboratory, Swiss Federal Institute of Technology (ETH Zürich), Physikstrasse 3, CH - 8092, Switzerland.
    Morari, Manfred
    Automatic Control Laboratory, Swiss Federal Institute of Technology (ETH Zürich), Physikstrasse 3, CH - 8092, Switzerland.
    On the choice of the linear decision functions for point location in polytopic data sets - Application to Explicit MPC2010In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC), 2010, p. 5283-5288Conference paper (Refereed)
    Abstract [en]

    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.

  • 45.
    Ljungqvist, Oskar
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Helmersson, Anders
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Path following control for a reversing general 2-trailer system2016In: 2016 IEEE 55TH CONFERENCE ON DECISION AND CONTROL (CDC), IEEE , 2016, p. 2455-2461Conference paper (Refereed)
    Abstract [en]

    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.

  • 46.
    Ljungqvist, Oskar
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Löfberg, Johan
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    On stability for state-lattice trajectory tracking control2018In: 2018 Annual American Control Conference (ACC), IEEE, 2018, p. 5868-5875Conference paper (Refereed)
    Abstract [en]

    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.

  • 47.
    Ljungqvist, Oskar
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Evestedt, Niclas
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Cirillo, Marcello
    Scania Tech Ctr, Sweden.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.
    Holmer, Olov
    Linköping University, Department of Electrical Engineering, Vehicular Systems. Linköping University, Faculty of Science & Engineering.
    Lattice-based Motion Planning for a General 2-trailer system2017In: 2017 28TH IEEE INTELLIGENT VEHICLES SYMPOSIUM (IV 2017), IEEE , 2017, p. 819-824Conference paper (Refereed)
    Abstract [en]

    Motion planning for a general 2-trailer system poses a hard problem for any motion planning algorithm and previous methods have lacked any completeness or optimality guarantees. In this work we present a lattice-based motion planning framework for a general 2-trailer system that is resolution complete and resolution optimal. The solution will satisfy both differential and obstacle imposed constraints and is intended either as a part of an autonomous system or as a driver support system to automatically plan complicated maneuvers in backward and forward motion. The proposed framework relies on a precomputing step that is performed offline to generate a finite set of kinematically feasible motion primitives. These motion primitives are then used to create a regular state lattice that can be searched for a solution using standard graph-search algorithms. To make this graph-search problem tractable for real-time applications a novel parametrization of the reachable state space is proposed where each motion primitive moves the system from and to a selected set of circular equilibrium configurations. The approach is evaluated over three different scenarios and impressive real-time performance is achieved.

  • 48.
    Nielsen, Isak
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Ankelhed, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Low-rank Modifications of Riccati Factorizations with Applications to Model Predictive Control2013In: Proceedings of 52nd IEEE Conference on Decision and Control, IEEE conference proceedings, 2013, p. 3684-3690Conference paper (Refereed)
    Abstract [en]

    In optimization algorithms used for on-line Model Predictive Control (MPC), the main computational effort is spent while solving linear systems of equations to obtain search directions. Hence, it is of greatest interest to solve them efficiently, which commonly is performed using Riccati recursions or generic sparsity exploiting algorithms. The focus in this work is efficient search direction computation for active-set methods. In these methods, the system of equations to be solved in each iteration is only changed by a low-rank modification of the previous one. This highly structured change of the system of equations from one iteration to the next one is an important ingredient in the performance of active-set solvers. It seems very appealing to try to make a structured update of the Riccati factorization, which has not been presented in the literature so far. The main objective of this paper is to present such an algorithm for how to update the Riccati factorization in a structured way in an active-set solver. The result of the work is that the computational complexity of the step direction computation can be significantly reduced for problems with bound constraints on the control signal. This in turn has important implications for the computational performance of active-set solvers used for linear, nonlinear as well as hybrid MPC.

  • 49.
    Nielsen, Isak
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    A Parallel Riccati Factorization Algorithm with Applications to Model Predictive Control2014Report (Other academic)
    Abstract [en]

    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.

  • 50.
    Nielsen, Isak
    et al.
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    Axehill, Daniel
    Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
    An O(log N) Parallel Algorithm for Newton Step Computation in Model Predictive Control2014Report (Refereed)
    Abstract [en]

    The use of Model Predictive Control in industry is steadily increasing as more complicated problems can be addressed. Due to that online optimization is usually performed, the main bottleneck with Model Predictive Control is the relatively high computational complexity. Hence, a lot of research has been performed to find efficient algorithms that solve the optimization problem. As parallelism is becoming more commonly used in hardware, the demand for efficient parallel solvers for Model Predictive Control has increased. In this paper, a tailored parallel algorithm that can adopt different levels of parallelism for solving the Newton step is presented. With sufficiently many processing units, it is capable of reducing the computational growth to logarithmic growth in the prediction horizon. Since the Newton step computation is where most computational effort is spent in both interior-point and active-set solvers, this new algorithm can significantly reduce the computational complexity of highly relevant solvers for Model Predictive Control.

12 1 - 50 of 57
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf