| 1. |
- Arnström, Daniel, 1994-, et al.
(författare)
-
Lift, Partition, and Project : Parametric Complexity Certification of Active-Set QP Methods in the Presence of Numerical Errors
- 2022
-
Ingår i: 2022 IEEE 61st Conference on Decision and Control (CDC). - NEW YORK, NY, USA : Institute of Electrical and Electronics Engineers (IEEE). - 9781665467612 - 9781665467605 - 9781665467629 ; , s. 4381-4387
-
Konferensbidrag (refereegranskat)abstract
- When Model Predictive Control (MPC) is used in real-time to control linear systems, quadratic programs (QPs) need to be solved within a limited time frame. Recently, several parametric methods have been proposed that certify the number of computations active-set QP solvers require to solve these QPs. These certification methods, hence, ascertain that the optimization problem can be solved within the limited time frame. A shortcoming in these methods is, however, that they do not account for numerical errors that might occur internally in the solvers, which ultimately might lead to optimistic complexity bounds if, for example, the solvers are implemented in single precision. In this paper we propose a general framework that can be incorporated in any of these certification methods to account for such numerical errors.
|
|
| 2. |
- Arnström, Daniel, 1994-
(författare)
-
On Complexity Certification of Active-Set QP Methods with Applications to Linear MPC
- 2021
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)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).
|
|
| 3. |
- Arnström, Daniel, 1994-
(författare)
-
Real-Time Certified MPC : Reliable Active-Set QP Solvers
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)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.
|
|
| 4. |
- Arnström, Daniel, et al.
(författare)
-
Semi-Explicit Linear MPC Using a Warm-Started Active-Set QP Algorithm with Exact Complexity Guarantees
- 2021
-
Ingår i: 2021 60TH IEEE CONFERENCE ON DECISION AND CONTROL (CDC). - : IEEE. - 9781665436595 ; , s. 2557-2562
-
Konferensbidrag (refereegranskat)abstract
- We propose a semi-explicit approach for linear MPC in which a dual active-set quadratic programming algorithm is initialized through a pre-computed warm start. By using a recently developed complexity certification method for active-set algorithms for quadratic programming, we show how the computational complexity of the dual active-set algorithm can be determined offline for a given warm start. We also show how these complexity certificates can be used as quality measures when constructing warm starts, enabling the online complexity to be reduced further by iteratively refining the warm start. In addition to showing how the computational complexity of any pre-computed warm start can be determined, we also propose a novel technique for generating warm starts with low overhead, both in terms of computations and memory.
|
|
| 5. |
- Boström-Rost, Per, 1988-, et al.
(författare)
-
Informative Path Planning for Active Tracking of Agile Targets
- 2019
-
Ingår i: Proceedings of 2019 IEEE Aerospace Conference. - : Institute of Electrical and Electronics Engineers (IEEE). - 9781538668542 - 9781538668559 ; , s. 1-11
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 6. |
- Boström-Rost, Per, 1988-
(författare)
-
On Informative Path Planning for Tracking and Surveillance
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis studies a class of sensor management problems called informative path planning (IPP). Sensor management refers to the problem of optimizing control inputs for sensor systems in dynamic environments in order to achieve operational objectives. The problems are commonly formulated as stochastic optimal control problems, where to objective is to maximize the information gained from future measurements. In IPP, the control inputs affect the movement of the sensor platforms, and the goal is to compute trajectories from where the sensors can obtain measurements that maximize the estimation performance. The core challenge lies in making decisions based on the predicted utility of future measurements.In linear Gaussian settings, the estimation performance is independent of the actual measurements. This means that IPP becomes a deterministic optimal control problem, for which standard numerical optimization techniques can be applied. This is exploited in the first part of this thesis. A surveillance application is considered, where a mobile sensor is gathering information about features of interest while avoiding being tracked by an adversarial observer. The problem is formulated as an optimization problem that allows for a trade-off between informativeness and stealth. We formulate a theorem that makes it possible to reformulate a class of nonconvex optimization problems with matrix-valued variables as convex optimization problems. This theorem is then used to prove that the seemingly intractable IPP problem can be solved to global optimality using off-the-shelf optimization tools.The second part of this thesis considers tracking of a maneuvering target using a mobile sensor with limited field of view. The problem is formulated as an IPP problem, where the goal is to generate a sensor trajectory that maximizes the expected tracking performance, captured by a measure of the covariance matrix of the target state estimate. When the measurements are nonlinear functions of the target state, the tracking performance depends on the actual measurements, which depend on the target’s trajectory. Since these are unavailable in the planning stage, the problem becomes a stochastic optimal control problem. An approximation of the problem based on deterministic sampling of the distribution of the predicted target trajectory is proposed. It is demonstrated in a simulation study that the proposed method significantly increases the tracking performance compared to a conventional approach that neglects the uncertainty in the future target trajectory.
|
|
| 7. |
- Boström-Rost, Per, 1988-, et al.
(författare)
-
Optimal Range and Beamwidth for Radar Tracking of Maneuvering Targets Using Nearly Constant Velocity Filters
- 2020
-
Ingår i: Proceedings of 2020 IEEE Aerospace Conference. - 9781728127347 - 9781728127354
-
Konferensbidrag (refereegranskat)abstract
- For a given radar system on an unmanned air vehicle, this work proposes a method to find the optimal tracking rangeand the optimal beamwidth for tracking a maneuvering target. An inappropriate optimal range or beamwidth is indicative ofthe need for a redesign of the radar system. An extended Kalman filter (EKF) is employed to estimate the state of the target using measurements of the range and bearing from the sensor to the target. The proposed method makes use of an alpha-beta filter to predict the expected tracking performanceof the EKF. Using an assumption of the maximum acceleration of the target, the optimal tracking range (or beamwidth) is determined as the one that minimizes the maximum mean squared error (MMSE) of the position estimates while satisfying a user-defined constraint on the probability of losing track of the target.The applicability of the design method is verified using Monte Carlo simulations.
|
|
| 8. |
- Boström-Rost, Per, 1988-, et al.
(författare)
-
PMBM Filter With Partially Grid-Based Birth Model With Applications in Sensor Management
- 2022
-
Ingår i: IEEE Transactions on Aerospace and Electronic Systems. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9251 .- 1557-9603 .- 2371-9877. ; 58:1, s. 530-540
-
Tidskriftsartikel (refereegranskat)abstract
- This article introduces a Poisson multi-Bernoulli mixture (PMBM) filter in which the intensities of target birth and undetected targets are grid-based. A simplified version of the Rao-Blackwellized point mass filter is used to predict the intensity of undetected targets and to initialize tracks of targets detected for the first time. The grid approximation can efficiently represents intensities with abrupt changes with relatively few grid points compared to the number of Gaussian components needed in conventional PMBM implementations. This is beneficial in scenarios where the sensors field of view is limited. The proposed method is illustrated in a sensor management setting, where trajectories of sensors with limited fields of view are controlled to search for and track the targets in a region of interest.
|
|
| 9. |
- Boström-Rost, Per, 1988-, et al.
(författare)
-
Sensor management for search and track using the Poisson multi-Bernoulli mixture filter
- 2021
-
Ingår i: IEEE Transactions on Aerospace and Electronic Systems. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9251 .- 1557-9603. ; 57:5, s. 2771-2783
-
Tidskriftsartikel (refereegranskat)abstract
- A sensor management method for joint multi-target search and track problems is proposed, where a single user-defined parameter allows for a trade-off between the two objectives. The multi-target density is propagated using the Poisson multi-Bernoulli mixture filter, which eliminates the need for a separate handling of undiscovered targets and provides the theoretical foundation for a unified search and track method. Monte Carlo simulations of two scenarios are used to evaluate the performance of the proposed method.
|
|
| 10. |
- Boström-Rost, Per, 1988-
(författare)
-
Sensor Management for Target Tracking Applications
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many practical applications, such as search and rescue operations and environmental monitoring, involve the use of mobile sensor platforms. The workload of the sensor operators is becoming overwhelming, as both the number of sensors and their complexity are increasing. This thesis addresses the problem of automating sensor systems to support the operators. This is often referred to as sensor management. By planning trajectories for the sensor platforms and exploiting sensor characteristics, the accuracy of the resulting state estimates can be improved. The considered sensor management problems are formulated in the framework of stochastic optimal control, where prior knowledge, sensor models, and environment models can be incorporated. The core challenge lies in making decisions based on the predicted utility of future measurements.In the special case of linear Gaussian measurement and motion models, the estimation performance is independent of the actual measurements. This reduces the problem of computing sensing trajectories to a deterministic optimal control problem, for which standard numerical optimization techniques can be applied. A theorem is formulated that makes it possible to reformulate a class of nonconvex optimization problems with matrix-valued variables as convex optimization problems. This theorem is then used to prove that globally optimal sensing trajectories can be computed using off-the-shelf optimization tools. As in many other fields, nonlinearities make sensor management problems more complicated. Two approaches are derived to handle the randomness inherent in the nonlinear problem of tracking a maneuvering target using a mobile range-bearing sensor with limited field of view. The first approach uses deterministic sampling to predict several candidates of future target trajectories that are taken into account when planning the sensing trajectory. This significantly increases the tracking performance compared to a conventional approach that neglects the uncertainty in the future target trajectory. The second approach is a method to find the optimal range between the sensor and the target. Given the size of the sensor's field of view and an assumption of the maximum acceleration of the target, the optimal range is determined as the one that minimizes the tracking error while satisfying a user-defined constraint on the probability of losing track of the target. While optimization for tracking of a single target may be difficult, planning for jointly maintaining track of discovered targets and searching for yet undetected targets is even more challenging. Conventional approaches are typically based on a traditional tracking method with separate handling of undetected targets. Here, it is shown that the Poisson multi-Bernoulli mixture (PMBM) filter provides a theoretical foundation for a unified search and track method, as it not only provides state estimates of discovered targets, but also maintains an explicit representation of where undetected targets may be located. Furthermore, in an effort to decrease the computational complexity, a version of the PMBM filter which uses a grid-based intensity to represent undetected targets is derived.
|
|
