| 1. |
- Parvini Ahmadi, Shervin, 1989-
(author)
-
Distributed Optimization for Control and Estimation
- 2022
-
Doctoral thesis (other academic/artistic)abstract
- Adopting centralized optimization approaches in order to solve optimization problem arising from analyzing large-scale systems, requires a powerful computational unit. Such units, however, do not always exist. In addition, it is not always possible to form the optimization problem in a centralized manner due to structural constraints or privacy requirements. A possible solution in these cases is to use distributed optimization approaches. Many large-scale systems have inherent structures which can be exploited to develop scalable optimization approaches. In this thesis, chordal graph properties are used in order to design tailored distributed optimization approaches for applications in control and estimation, and especially for model predictive control and localization problems. The first contribution concerns a distributed primal-dual interior-point algorithm for which it is investigated how parallelism can be exploited. In particular, it is shown how the computations of the algorithm can be distributed on different processors so that they can be run in parallel. As a result, the algorithm execution time is accelerated compared to the case where the algorithm is run on a single processor. Simulation studies on linear model predictive control and robust model predictive control confirm the efficiency of the framework. The second contribution is to devise a tailored distributed algorithm for nonlinear least squares with application to a sensor network location problem. It relies on the Levenberg-Marquardt algorithm, in which the computations are distributed using message passing over the computational graph of the problem, which is obtained from what is known as the clique tree of the problem. The results indicate that the algorithm provides not only a good localization accuracy, but also it requires fewer iterations and communications between computational agents in order to converge compared to known first-order methods. The third contribution is a study of extending the message passing idea in order to design tailored distributed algorithm for general non-convex problems. The framework relies on an augmented Lagrangian algorithm in which a primal-dual interior-point method is used for the inner iteration. Application of the framework for general model predictive control of systems with several interconnected sub-systems is extensively investigated. The performance of the framework is then compared with distributed methods based on the alternating direction method of multipliers, where the superiority of the framework is illustrated.
|
|
| 2. |
- Haghshenas, Hamed, 1990-
(author)
-
Time-Optimal Cooperative Path Tracking for Multi-Robot Systems
- 2021
-
Licentiate thesis (other academic/artistic)abstract
- Robotic systems are nowadays the key technology in a wide variety of applications. The increasing demand for performance of robotic systems is often met by employing a team of cooperating robots for a specific task.When the task carried out by the robots involves manipulation of an object, the multi-robot system is said to perform a cooperative manipulation task.Cooperative manipulation is an important capability for extending the domain of robotic applications.This thesis studies the time-optimal path tracking problem for a cooperative manipulation scenario where an object is rigidly grasped by multiple manipulators. The goal is to move the object along a predefined geometric path in minimum time while satisfying the imposed constraints on the motion. First, it is shown that the time-optimal path tracking problem for cooperative manipulators can be cast as a convex optimization problem. A fundamental property of convex optimization problems is that any locally optimal solution is also a globally optimal one. Furthermore, by recognizing and formulating a problem as a convex optimization problem, it can be solved very reliably and efficiently using interior-point or other methods for convex optimization.These results are presented in two separate studies. In the first one which is a preliminary study, the manipulation setup is a particular setup comprised of two planar manipulators and a bar. Furthermore, the load distribution among the manipulators is considered to be equal. The second study extends the results in the preliminary study to a general scenario with $N$ generic manipulators and an object with a desired orientation during the motion. Here, the load distribution among the manipulators is determined via a generic pseudo-inverse of the grasp matrix that can be chosen by the user.The freedom in the choice of the pseudo-inverse allows to consider different load distributions which can be exploited to account for the potential differences in the capabilities of the manipulators.The second part of this thesis is devoted to finding load distributions that are free of internal forces. A drawback of using multiple manipulators in a cooperative manipulation task is that internal forces can be introduced.Internal forces are forces exerted by the end-effectors at the grasping points that do not contribute to the motion of the manipulated object. While a certain amount of such forces can be useful in some cases, in general they must be avoided to prevent object damage and unnecessary effort of the manipulators.This thesis proposes a new approach to obtain internal force-free load distributions.The proposed approach results in a new pseudo-inverse of the grasp matrix parameterized by coefficients that have the meaning of the inertial parameters of some parts of the object. The freedom in the choice of the parameters of the pseudo-inverse allows to assign different loads to the manipulators. This can be exploited to account for the differences in the power capabilities of the manipulators.The results are further explored for scenarios where the object is three-dimensional and convex and has uniform mass density. Finally, the proposed pseudo-inverse is combined with the results in the first part of the thesis to solve the problem of time-optimal cooperative path tracking subject to zero internal forces during the motion.
|
|
| 3. |
- Arnström, Daniel, 1994-
(author)
-
On Complexity Certification of Active-Set QP Methods with Applications to Linear MPC
- 2021
-
Licentiate thesis (other academic/artistic)abstract
- In model predictive control (MPC) an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. The primary contribution of this thesis is a method which determines which sequence of subproblems a popular class of such active-set algorithms need to solve, for every possible QP instance that might arise from a given linear MPC problem (i.e, for every possible state and reference signal). By knowing these sequences, worst-case bounds on how many iterations, floating-point operations and, ultimately, the maximum solution time, these active-set algorithms require to compute a solution can be determined, which is of importance when, e.g, linear MPC is used in safety-critical applications. After establishing this complexity certification method, its applicability is extended by showing how it can be used indirectly to certify the complexity of another, efficient, type of active-set QP algorithm which reformulates the QP as a nonnegative least-squares method. Finally, the proposed complexity certification method is extended further to situations when enhancements to the active-set algorithms are used, namely, when they are terminated early (to save computations) and when outer proximal-point iterations are performed (to improve numerical stability).
|
|
| 4. |
- Fontan, Angela, 1991-
(author)
-
Collective decision-making on networked systems in presence of antagonistic interactions
- 2021
-
Doctoral thesis (other academic/artistic)abstract
- Collective decision-making refers to a process in which the agents of a community exchange opinions with the objective of reaching a common decision. It is often assumed that a collective decision is reached through collaboration among the individuals. However in many contexts, concerning for instance collective human behavior, it is more realistic to assume that the agents can collaborate or compete with each other. In this case, different types of collective behavior can be observed. This thesis investigates collective decision-making problems in multiagent systems, both in the case of collaborative and of antagonistic interactions.The first problem studied in the thesis is a special instance of the consensus problem, denoted "interval consensus" in this work. It consists in letting the agents impose constraints on the possible common consensus value. It is shown that introducing saturated nonlinearities in the decision-making dynamics to describe how the agents express their opinions effectively allows the agents to influence the achievable consensus value and steer it to the intersection of all the intervals imposed by the agents. A second class of collective decision-making models discussed in the thesis is obtained by replacing the saturations with sigmoidal nonlinearities. This nonlinear interconnected model is first investigated in the collaborative case and then in the antagonistic case, represented as a signed graph of interactions. In both cases, it is shown that the behavior of the model can be described by means of bifurcation analysis, with the equilibria of the system encoding the possible decisions for the community. A scalar positive parameter, denoted "social effort", is added to the model to represent the strength of commitment between the agents, and plays the role of bifurcation parameter in the analysis. It is shown that if the social effort is small, then the community is in a deadlock situation (i.e., no decision is taken), while if the agents have the "right" amount of commitment two alternative consensus decision states for the community are achieved. However, by further increasing the social effort, the agents may fall in a situation of "overcommitment" where multiple (more than 2) decisions are possible. When antagonistic interactions between the agents are taken into account, they may lead to conflicts or social tensions during the decision-making process, which can be quantified by the notion of "frustration" of the signed network representing the community. The aim is to understand how the presence of antagonism (represented by the amount of frustration of the signed network) influences the collective decision-making process. It is shown that, while the qualitative behavior of the system does not change, the value of social effort required from the agents to break the deadlock (i.e., the value for which the bifurcation is crossed) increases with the frustration of the signed network: the higher the frustration, the higher the required social commitment.A natural context to apply these results is that of political decision-making. In particular it is shown in the thesis how the government formation process in parliamentary democracies can be modeled as a collective decision-making system, where the agents are the parliamentary members, the decision is the vote of confidence they cast to a candidate cabinet coalition, and the social effort parameter is a proxy for the duration of the government negotiation talks. A signed network captures the alliances/rivalries between the political parties in the parliament. The idea is that the frustration of the parliamentary networks should correlate well with the duration of the government negotiation, and it is supported by the analysis of the legislative elections in 29 European countries in the last 40 years. The final contribution of this thesis is an analysis of the structure of (signed) Laplacian matrices and of their pseudoinverses. It is shown that the pseudoinverse of a Laplacian is in general a signed Laplacian, and in particular that the set of eventually exponentially positive Laplacian matrices (i.e., matrices whose exponential is a matrix with negative entries which becomes and stays positive at a certain power) is closed under stability and matrix pseudoinversion.
|
|
| 5. |
- Forsling, Robin, 1988-, et al.
(author)
-
Conservative Linear Unbiased Estimation Under Partially Known Covariances
- 2022
-
In: IEEE Transactions on Signal Processing. - : IEEE. - 1053-587X .- 1941-0476. ; 70, s. 3123-3135
-
Journal article (peer-reviewed)abstract
- Mean square error optimal estimation requires the full correlation structure to be available. Unfortunately, it is not always possible to maintain full knowledge about the correlations. One example is decentralized data fusion where the cross-correlations between estimates are unknown, partly due to information sharing. To avoid underestimating the covariance of an estimate in such situations, conservative estimation is one option. In this paper the conservative linear unbiased estimator is formalized including optimality criteria. Fundamental bounds of the optimal conservative linear unbiased estimator are derived. A main contribution is a general approach for computing the proposed estimator based on robust optimization. Furthermore, it is shown that several existing estimation algorithms are special cases of the optimal conservative linear unbiased estimator. An evaluation verifies the theoretical considerations and shows that the optimization based approach performs better than existing conservative estimation methods in certain cases.
|
|
| 6. |
- Arnström, Daniel, 1994-
(author)
-
Real-Time Certified MPC : Reliable Active-Set QP Solvers
- 2023
-
Doctoral thesis (other academic/artistic)abstract
- In Model Predictive Control (MPC), optimization problems are solved recurrently to produce control actions. When MPC is used in real time to control safety-critical systems, it is important to solve these optimization problems with guarantees on the worst-case execution time. In this thesis, we take aim at such worst-case guarantees through two complementary approaches:(i) By developing methods that determine exact worst-case bounds on the computational complexity and execution time for deployed optimization solvers.(ii) By developing efficient optimization solvers that are tailored for the given application and hardware at hand.We focus on linear MPC, which means that the optimization problems in question are quadratic programs (QPs) that depend on parameters such as system states and reference signals. For solving such QPs, we consider active-set methods: a popular class of optimization algorithms used in real-time applications.The first part of the thesis concerns complexity certification of well-established active-set methods. First, we propose a certification framework that determines the sequence of subproblems that a class of active-set algorithms needs to solve, for every possible QP instance that might arise from a given linear MPC problem (i.e., for every possible state and reference signal). By knowing these sequences, one can exactly bound the number of iterations and/or floating-point operations that are required to compute a solution. In a second contribution, we use this framework to determine the exact worst-case execution time (WCET) for linear MPC. This requires factors such as hardware and software implementation/compilation to be accounted for in the analysis. The framework is further extended in a third contribution by accounting for internal numerical errors in the solver that is certified. In a similar vein, a fourth contribution extends the framework to handle proximal-point iterations, which can be used to improve the numerical stability of QP solvers, furthering their reliability.The second part of the thesis concerns efficient solvers for real-time MPC. We propose an efficient active-set solver that is contained in the above-mentioned complexity-certification framework. In addition to being real-time certifiable, we show that the solver is efficient, simple to implement, can easily be warm-started, and is numerically stable, all of which are important properties for a solver that is used in real-time MPC applications. As a final contribution, we use this solver to exemplify how the proposed complexity-certification framework developed in the first part can be used to tailor active-set solvers for a given linear MPC application. Specifically, we do this by constructing and certifying parameter-varying initializations of the solver.
|
|
| 7. |
- Klingspor, Måns, 1989-
(author)
-
Low-rank optimization in system identification
- 2019
-
Licentiate thesis (other academic/artistic)abstract
- In this thesis, the use of low-rank approximations in connection with problems in system identification is explored. Firstly, the motivation of using low-rank approximations in system identification is presented and the framework for low-rank optimization is derived. Secondly, three papers are presented where different problems in system identification are considered within the described low-rank framework. In paper A, a novel method involving the nuclear norm forestimating a Wiener model is introduced. As shown in the paper, this method performs better than existing methods in terms of finding an accurate model. In paper B and C, a group lasso framework is used to perform input selection in the model estimation which also is connected to the low rank framework. The model structures where these novel methods of input selection is used on are ARX models and state space models, respectively. As shown in the respective papers, these strategies of performing input selection perform better than existing methods in both terms of estimation and input selection.
|
|
| 8. |
- Ahmadi, Shervin Parvini, 1989-, et al.
(author)
-
Parallel Exploitation for Tree-Structured Coupled Quadratic Programming in Julia
- 2018
-
In: Proceedings of the 22nd International Conference on System Theory, Control and Computing. - : IEEE. - 9781538644447 - 9781538644430 - 9781538644454 ; , s. 597-602
-
Conference paper (peer-reviewed)abstract
- The main idea in this paper is to implement a distributed primal-dual interior-point algorithm for loosely coupled Quadratic Programming problems. We implement this in Julia and show how can we exploit parallelism in order to increase the computational speed. We investigate the performance of the algorithm on a Model Predictive Control problem.
|
|
| 9. |
- Hansson, Anders, Professor, 1964-, et al.
(author)
-
Exploiting chordality in optimization algorithms for model predictive control
- 2018
-
In: Large-scale and distributed optimization. - Cham : Springer. - 9783319974781 - 9783319974774 ; , s. 11-32
-
Book chapter (peer-reviewed)abstract
- In this chapter we show that chordal structure can be used to devise efficient optimization methods for many common model predictive control problems. The chordal structure is used both for computing search directions efficiently as well as for distributing all the other computations in an interior-point method for solving the problem. The chordal structure can stem both from the sequential nature of the problem as well as from distributed formulations of the problem related to scenario trees or other formulations. The framework enables efficient parallel computations.
|
|
| 10. |
- Ljung, Lennart, 1946-, et al.
(author)
-
Modeling and identification of dynamic systems
- 2021. - 2
-
Book (other academic/artistic)abstract
- Mathematical models of real life systems and processes are essential in today’s industrial work. To be able to construct such models is therefore a fundamental skill in modern engineering...
|
|
| 11. |
- Nielsen, Isak
(author)
-
Structure-Exploiting Numerical Algorithms for Optimal Control
- 2017
-
Doctoral thesis (other academic/artistic)abstract
- Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution.
|
|
| 12. |
- Parvini Ahmadi, Shervin, 1989-, et al.
(author)
-
Distributed optimal control of nonlinear systems using a second-order augmented Lagrangian method
- 2023
-
In: European Journal of Control. - : Elsevier. - 0947-3580 .- 1435-5671. ; 70
-
Journal article (peer-reviewed)abstract
- In this paper, we propose a distributed second-order augmented Lagrangian method for distributed optimal control problems, which can be exploited for distributed model predictive control. We employ a primal-dual interior-point approach for the inner iteration of the augmented Lagrangian and distribute the corresponding computations using message passing over what is known as the clique tree of the problem. The algorithm converges to its centralized counterpart and it requires fewer communications between sub-systems as compared to algorithms such as the alternating direction method of multipliers. We illustrate the efficiency of the framework when applied to randomly generated interconnected sub-systems as well as to a vehicle platooning problem.
|
|
