| 1. |
- 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.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Nordlöf, Jonas, 1987-
(författare)
-
On Landmark Densities in Minimum-Uncertainty Motion Planning
- 2022
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Accurate self-positioning of autonomous mobile platforms is important when performing tasks such as target tracking, reconnaissance and resupply missions. Without access to an existing positioning infrastructure, such as Global Navigation Satellite Systems (GNSS), the platform instead needs to rely on its own sensors to obtain an accurate position estimate. This can be achieved by detecting and tracking landmarks in the environment using techniques such as simultaneous localization and mapping (SLAM). However, landmark-based SLAM approaches do not perform well in areas without landmarks or when the landmarks do not provide enough information about the environment. It is therefore desirable to estimate and minimize the position uncertainty while planning how to perform the task. A complicating factor is that the landmarks used in SLAM are not known at the time of planning.In this thesis, it is shown that by integrating SLAM and path planning, paths can be computed that are favorable, from a localization point of view, during motion execution. In particular, it is investigated how prior knowledge of landmark distributions, or densities, can be used to predict the information gained from a region. This is done without explicit knowledge of landmark positions. This prediction is then integrated into the path-planning problem.The first contribution is the introduction of virtual landmarks which represent the expected information in unexplored regions during planning. Two approaches to construct the virtual landmarks that capture the expected information available, based on the beforehand known landmark density, are given. The first approach can be used with any sensor configuration while the second one uses properties of range-bearing sensors, such as LiDAR sensors, to improve the quality of the approximation.The second contribution is a methodology for generating landmark densities from prior data for a forest scenario. These densities were generated from publicly available aerial data used in the Swedish forest industry.The third contribution is an approach to compute the probability of detecting pole-based landmarks in LiDAR point clouds. The approach uses properties of the sensor, the landmark detector, and the probability of occlusion from other landmarks in order to model the detection probability. The model accuracy has been validated in simulations where a real landmark detector and simulated Li-DAR point clouds have been used in a forest scenario.The final contribution is a position-uncertainty aware path-planning approach. This approach utilizes virtual landmarks, the landmark densities, and the land-mark detection probabilities, to produce paths which are advantageous from a positioning point of view. The approach is shown to reduce the platform position uncertainty in several different simulated scenarios without prior knowledge of explicit landmark positions. The computed position uncertainty is shown to be relatively comparable to the uncertainty obtained when executing the path. Furthermore, the generated paths show characteristics that make sense from an application point of view.
|
|
| 5. |
- Parvini Ahmadi, Shervin, 1989-
(författare)
-
Distributed Optimization for Control and Estimation
- 2022
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)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.
|
|
| 6. |
- 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).
|
|
| 7. |
- Malmström, Magnus, 1994-
(författare)
-
Uncertainties in Neural Networks : A System Identification Approach
- 2021
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In science, technology, and engineering, creating models of the environment to predict future events has always been a key component. The models could be everything from how the friction of a tire depends on the wheels slip to how a pathogen is spread throughout society. As more data becomes available, the use of data-driven black-box models becomes more attractive. In many areas they have shown promising results, but for them to be used widespread in safety-critical applications such as autonomous driving some notion of uncertainty in the prediction is required.An example of such a black-box model is neural networks (NNs). This thesis aims to increase the usefulness of NNs by presenting an method where uncertainty in the prediction is obtained by linearization of the model. In system identification and sensor fusion, under the condition that the model structure is identifiable, this is a commonly used approach to get uncertainty in the prediction from a nonlinear model. If the model structure is not identifiable, such as for NNs, the ambiguities that cause this have to be taken care of in order to make the approach applicable. This is handled in the first part of the thesis where NNs are analyzed from a system identification perspective, and sources of uncertainty are discussed.Another problem with data-driven black-box models is that it is difficult to know how flexible the model needs to be in order to correctly model the true system. One solution to this problem is to use a model that is more flexible than necessary to make sure that the model is flexible enough. But how would that extra flexibility affect the uncertainty in the prediction? This is handled in the later part of the thesis where it is shown that the uncertainty in the prediction is bounded from below by the uncertainty in the prediction of the model with lowest flexibility required for representing true system accurately. In the literature, many other approaches to handle the uncertainty in predictions by NNs have been suggested, of which some are summarized in this work. Furthermore, a simulation and an experimental studies inspired by autonomous driving are conducted. In the simulation study, different sources of uncertainty are investigated, as well as how large the uncertainty in the predictions by NNs are in areas without training data. In the experimental study, the uncertainty in predictions done by different models are investigated. The results show that, compared to existing methods, the linearization method produces similar results for the uncertainty in predictions by NNs.An introduction video is available at https://youtu.be/O4ZcUTGXFN0
|
|
| 8. |
- 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.
|
|
| 9. |
- Bergman, Kristoffer, 1990-
(författare)
-
Exploiting Direct Optimal Control for Motion Planning in Unstructured Environments
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the last decades, motion planning for autonomous systems has become an important area of research. The high interest is not the least due to the development of systems such as self-driving cars, unmanned aerial vehicles and robotic manipulators. The objective in optimal motion planning problems is to find feasible motion plans that also optimize a performance measure. From a control perspective, the problem is an instance of an optimal control problem. This thesis addresses optimal motion planning problems for complex dynamical systems that operate in unstructured environments, where no prior reference such as road-lane information is available. Some example scenarios are autonomous docking of vessels in harbors and autonomous parking of self-driving tractor-trailer vehicles at loading sites. The focus is to develop optimal motion planning algorithms that can reliably be applied to these types of problems. This is achieved by combining recent ideas from automatic control, numerical optimization and robotics.The first contribution is a systematic approach for computing local solutions to motion planning problems in challenging unstructured environments. The solutions are computed by combining homotopy methods and direct optimal control techniques. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. The approach is demonstrated in motion planning problems in 2D and 3D environments, where the presented method outperforms a state-of-the-art asymptotically optimal motion planner based on random sampling.The second contribution is an optimization-based framework for automatic generation of motion primitives for lattice-based motion planners. Given a family of systems, the user only needs to specify which principle types of motions that are relevant for the considered system family. Based on the selected principle motions and a selected system instance, the framework computes a library of motion primitives by simultaneously optimizing the motions and the terminal states.The final contribution of this thesis is a motion planning framework that combines the strengths of sampling-based planners with direct optimal control in a novel way. The sampling-based planner is applied to the problem in a first step using a discretized search space, where the system dynamics and objective function are chosen to coincide with those used in a second step based on optimal control. This combination ensures that the sampling-based motion planner provides a feasible motion plan which is highly suitable as warm-start to the optimal control step. Furthermore, the second step is modified such that it also can be applied in a receding-horizon fashion, where the proposed combination of methods is used to provide theoretical guarantees in terms of recursive feasibility, worst-case objective function value and convergence to the terminal state. The proposed motion planning framework is successfully applied to several problems in challenging unstructured environments for tractor-trailer vehicles. The framework is also applied and tailored for maritime navigation for vessels in archipelagos and harbors, where it is able to compute energy-efficient trajectories which complies with the international regulations for preventing collisions at sea.
|
|
| 10. |
- 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.
|
|
| 11. |
- Jonas, Nordlöf, 1987-, et al.
(författare)
-
LiDAR-Landmark Modeling for Belief-Space Planning using Aerial Forest Data
- 2022
-
Ingår i: Proceedings of the 25th International Conference on Information Fusion (FUSION). - : IEEE. - 9781737749721 - 9781665489416
-
Konferensbidrag (refereegranskat)abstract
- A belief-space planning problem for GNSS-denied areas is studied, where knowledge about the landmark density is used as prior, instead of explicit landmark positions. To get accurate predictions of the future information gained from observations, the probability of detecting landmarks needs to be taken into account in addition to the probability of the existence of landmarks. Furthermore, these probabilities need to be calculated from prior data without knowledge of explicit landmarks. It is shown in this paper how the landmark detection probabilities can be generated for a ground-to-ground LiDAR sensor and integrated in the path-planning problem. Moreover, it is also shown how prior information can be generated for a forest scenario. Lastly, the approach is evaluated in a simulated environment using a real landmark detector applied to a simulated point cloud. Compared to previous approaches, an informative path planner, integrating the proposed approximation, is able to reduce the platform pose uncertainty. This is achieved using only prior aerial data of the environment.
|
|
| 12. |
- 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.
|
|
| 13. |
- Nordlöf, Jonas, 1987-, et al.
(författare)
-
Improved Virtual Landmark Approximation for Belief-Space Planning
- 2021
-
Ingår i: Proceedings of 2021 IEEE 24th International Conference on Information Fusion (FUSION). - : IEEE. - 9781737749714 - 9781665414272 ; , s. 813-820
-
Konferensbidrag (refereegranskat)abstract
- A belief-space planning problem for GNSS-denied areas is studied where the location and number of landmarks available are unknown when performing the planning. To be able to plan an informative path in this situation, an algorithm using virtual landmarks to position the platform during the planning phase is studied. The virtual landmarks are selected to capture the expected information available in different regions of the map, based on the beforehand known landmark density. The main contribution of this work is a better approximation of the obtained information from the virtual landmarks and a theoretical study of the properties of the approximation. Furthermore, the proposed approximation, in itself and its use in a path planner, is investigated with successful results.
|
|
| 14. |
- 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.
|
|
| 15. |
- Ljungqvist, Oskar, 1990-
(författare)
-
Motion planning and feedback control techniques with applications to long tractor-trailer vehicles
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the last decades, improved sensor and hardware technologies as well as new methods and algorithms have made self-driving vehicles a realistic possibility in the near future. At the same time, there has been a growing demand within the transportation sector to increase efficiency and to reduce the environmental impact related to transportation of people and goods. Therefore, many leading automotive and technology companies have turned their attention towards developing advanced driver assistance systems and self-driving vehicles.Autonomous vehicles are expected to have their first big impact in closed environments, such as mines, harbors, loading and offloading sites. In such areas, the legal requirements are less restrictive and the surrounding environment is more controlled and predictable compared to urban areas. Expected positive outcomes include increased productivity and safety, reduced emissions and the possibility to relieve the human from performing complex or dangerous tasks. Within these sites, tractor-trailer vehicles are frequently used for transportation. These vehicles are composed of several interconnected vehicle segments, and are therefore large, complex and unstable while reversing. This thesis addresses the problem of designing efficient motion planning and feedback control techniques for such systems.The contributions of this thesis are within the area of motion planning and feedback control for long tractor-trailer combinations operating at low-speeds in closed and unstructured environments. It includes development of motion planning and feedback control frameworks, structured design tools for guaranteeing closed-loop stability and experimental validation of the proposed solutions through simulations, lab and field experiments. Even though the primary application in this work is tractor-trailer vehicles, many of the proposed approaches can with some adjustments also be used for other systems, such as drones and ships.The developed sampling-based motion planning algorithms are based upon the probabilistic closed-loop rapidly exploring random tree (CL-RRT) algorithm and the deterministic lattice-based motion planning algorithm. It is also proposed to use numerical optimal control offline for precomputing libraries of optimized maneuvers as well as during online planning in the form of a warm-started optimization step.To follow the motion plan, several predictive path-following control approaches are proposed with different computational complexity and performance. Common for these approaches are that they use a path-following error model of the vehicle for future predictions and are tailored to operate in series with a motion planner that computes feasible paths. The design strategies for the path-following approaches include linear quadratic (LQ) control and several advanced model predictive control (MPC) techniques to account for physical and sensing limitations. To strengthen the practical value of the developed techniques, several of the proposed approaches have been implemented and successfully demonstrated in field experiments on a full-scale test platform. To estimate the vehicle states needed for control, a novel nonlinear observer is evaluated on the full-scale test vehicle. It is designed to only utilize information from sensors that are mounted on the tractor, making the system independent of any sensor mounted on the trailer.
|
|
| 16. |
- Ljungqvist, Oskar, 1990-
(författare)
-
On motion planning and control for truck and trailer systems
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the last decades, improved sensor and hardware technologies as well as new methods and algorithms have made self-driving vehicles a realistic possibility in the near future. Thanks to this technology enhancement, many leading automotive and technology companies have turned their attention towards developing advanced driver assistance systems (ADAS) and self-driving vehicles. Autonomous vehicles are expected to have their first big impact in closed areas, such as mines, harbors and loading/offloading sites. In such areas, the legal requirements are less restrictive and the surrounding environment is more controlled and predictable compared to urban areas. Expected positive outcomes include increased productivity and safety, reduced emissions and the possibility to relieve the human from performing complex or dangerous tasks. Within these sites, different truck and trailer systems are used to transport materials. These systems are composed of several interconnected modules, and are thus large and highly unstable while reversing. This thesis addresses the problem of designing efficient motion planning and feedback control frameworks for such systems.First, a cascade controller for a reversing truck with a dolly-steered trailer is presented. The unstable modes of the system is stabilized around circular equilibrium configurations using a gain-scheduled linear quadratic (LQ) controller together with a higher-level pure pursuit controller to enable path following of piecewise linear reference paths. The cascade controller is then used within a rapidly-exploring random tree (RRT) framework and the complete motion planning and control framework is demonstrated on a small-scale test vehicle.Second, a path following controller for a reversing truck with a dolly-steered trailer is proposed for the case when the obtained motion plan is kinematically feasible. The control errors of the system are modeled in terms of their deviation from the nominal path and a stabilizing LQ controller with feedforward action is designed based on the linearization of the control error model. Stability of the closed-loop system is proven by combining global optimization, theory from linear differential inclusions and linear matrix inequality techniques.Third, a systematic framework is presented for analyzing stability of the closed-loop system consisting of a controlled vehicle and a feedback controller, executing a motion plan computed by a lattice planner. When this motion planner is considered, it is shown that the closed-loop system can be modeled as a nonlinear hybrid system. Based on this, a novel method is presented for analyzing the behavior of the tracking error, how to design the feedback controller and how to potentially impose constraints on the motion planner in order to guarantee that the tracking error is bounded and decays towards zero.Fourth, a complete motion planning and control solution for a truck with a dolly-steered trailer is presented. A lattice-based motion planner is proposed, where a novel parametrization of the vehicle’s state-space is proposed to improve online planning time. A time-symmetry result is established that enhance the numerical stability of the numerical optimal control solver used for generating the motion primitives. Moreover, a nonlinear observer for state estimation is developed which only utilizes information from sensors that are mounted on the truck, making the system independent of additional trailer sensors. The proposed framework is implemented on a full-scale truck with a dolly-steered trailer and results from a series of field experiments are presented.
|
|
