| 1. |
- Hellander, Anja, 1996-
(författare)
-
On Optimal Integrated Task and Motion Planning with Applications to Tractor-Trailers
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- An important aspect in autonomous systems is the ability of a system to plan before acting. This includes both high-level task planning to determine what sequence of actions to take in order for the system to reach a goal state, as well as low-level motion planning to detail how to perform the actions required.While it is sometimes possible to plan hierarchically, i.e., to first compute a task plan and then compute motion plans for each action in the task plan, there are also many problem instances where this approach fails to find a feasible plan as not all task plans lead to motion-planning problems that have feasible solutions. For this reason, it is desirable to solve the two problems jointly rather than sequentially. Additionally, it is often desirable to find plans that optimize a performance measure, such as the energy used, the length of the path travelled by the system or the time required. This thesis focuses on the problem of finding joint task and motion plans that optimize a performance measure.The first contribution is a method for solving a joint task and motion planning problem, that can be formulated as a traveling salesman problem with dynamic obstacles and motion constraints, to resolution optimality. The proposed method uses a planner comprising two nested graph-search planners. Several different heuristics are considered and evaluated.The second contribution is a method for solving a joint task and motion planning problem, in the form of a rearrangement problem for a tractor-trailer system, to resolution optimality. The proposed method combines a task planner with motion planners, all based on heuristically guided graph search, and uses branch-and-bound techniques in order to improve the efficiency of the search algorithm.The final contribution is a method for improving task and motion plans for rearrangement problems using optimal control. The proposed method takes inspiration from finite-horizon optimal control and decomposes the optimization problem into several smaller optimization problems rather than solving one larger optimization problem. Compared to solving the original larger optimization problem, it is demonstrated that this can lead to reduced computation time without any significant decrease in solution quality.
|
|
| 2. |
- 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.
|
|
| 3. |
- Malmström, Magnus, 1994-
(författare)
-
Approximative Uncertainty in Neural Network Predictions
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Suppose data-driven black-box models, e.g., neural networks, should be used as components in safety-critical systems such as autonomous vehicles. In that case, knowing how uncertain they are in their predictions is crucial. However, this needs to be provided for standard formulations of neural networks. Hence, this thesis aims to develop a method that can, out-of-the-box, extend the standard formulations to include uncertainty in the prediction. The proposed method in the thesis is based on a local linear approximation, using a two-step linearization to quantify the uncertainty in the prediction from the neural network. First, the posterior distribution of the neural network parameters is approximated using a Gaussian distribution. The mean of the distribution is at the maximum a posteriori estimate of the parameters, and the covariance is estimated using the shape of the likelihood function in the vicinity of the estimated parameters. The second linearization is used to propagate the uncertainty in the parameters to uncertainty in the model’s output. Hence, to create a linear approximation of the nonlinear model that a neural network is. The first part of the thesis considers regression problems with examples of road-friction experiments using simulated and experimentally collected data. For the model-order selection problem, it is shown that the method does not under-estimate the uncertainty in the prediction of overparametrized models. The second part of the thesis considers classification problems. The concept of calibration of the uncertainty, i.e., how reliable the uncertainty is and how close it resembles the true uncertainty, is considered. The proposed method is shown to create calibrated estimates of the uncertainty, evaluated on classical image data sets. From a computational perspective, the thesis proposes a recursive update of the parameter covariance, enhancing the method’s viability. Furthermore, it shows how quantified uncertainty can improve the robustness of a decision process by formulating an information fusion scheme that includes both temporal correlational and correlation between classifiers. Moreover, having access to a measure of uncertainty in the prediction is essential when detecting outliers in the data, i.e., examples that the neural network has yet to see during the training. On this task, the proposed method shows promising results. Finally, the thesis proposes an extension that enables a multimodal representation of the uncertainty. The third part of the thesis considers the tracking of objects in image sequences, where the object is detected using standard neural network-based object detection algorithms. It formulates the problem as a filtering problem with the prediction of the class and the position of the object viewed as the measurements. The filtering formulation improves robustness towards false classifications when evaluating the method on examples from animal conservation in the Swedish forests.
|
|
| 4. |
- Shoja, Shamisa, 1991-
(författare)
-
On Complexity Certification of Branch-and-Bound Methods for MILP and MIQP with Applications to Hybrid MPC
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In model predictive control (MPC), an optimization problem is solved at each time step, in which the system dynamics and constraints can directly be taken into account. The MPC concept can be further extended to the control of hybrid systems, where a part of the state and control variables has a discrete set of values. When applying MPC to linear hybrid systems with performance measures based on the 1-norm or the∞-norm, the resulting optimal control problem can be formulated as a mixed-integer linear program (MILP), while the optimal control problem with a quadratic performance measure can be cast as a mixed-integer quadratic program (MIQP). An efficient method to solve these non-convex MILP and MIQP problems is branch and bound (B&B) which relies on solving convex relaxations of the problem ordered in a binary search tree. For the safe and reliable real-time operation of hybrid MPC, it is desirable to have a priori guarantees on the worst-case complexity such that the computational requirements of the problem do not exceed the time and hardware capabilities.Motivated by this need, this thesis aims to certify the computational complexity of standard B&B methods for solving MILPs and MIQPs in terms of, e.g., the size of the search tree or the number of linear systems of equations (iterations) that are needed to be solved online to compute optimal solution. In particular, this knowledge enables us to compute relevant worst-case complexity bounds for the B&B-based MILP and MIQP solvers, which has significant importance in, e.g., real-time hybrid MPC where hard real-time requirements have to be fulfilled. The applicability of the proposed certification method is further extended to suboptimal B&B methods for solving MILPs, where the computational effort is reduced by relaxing the requirement to find a globally optimal solution to instead finding a suboptimal solution, considering three different suboptimal strategies. Finally, the proposed framework is extended to the cases where the performance of B&B is enhanced by considering three common start heuristic methods that can help to find good feasible solutions early in the B&B search process.
|
|
