Search

This paper presents a safe by construction methodology to produce collision-free control laws for a population of Unmanned Aerial Vehicles (UAVs) that can be computed in a distributed manner. We view this problem under a game theoretic lens, with UAVs seeking to reach individual locations, while being coupled by safety requirements to avoid collision as well as due to the presence of an aggregate objective encoding the population’s common goal to keep track of a common target. To achieve this, we bring together Control Barrier Functions (CBFs) and a recently developed primal-dual algorithm for Nash equilibrium seeking in generalized games. Moreover, we introduce feedback by means of a receding horizon Model Predictive Control (MPC) strategy and analyze this in terms of its stability properties. The combination of these tools allows for a distributed, collision-free equilibrium solution, despite agents being coupled due to the common target they seek to track and the collision avoidance constraints. Our algorithmic results are supported theoretically and their efficacy is demonstrated via extensive numerical simulations, illustrating convergence of the proposed scheme to a safe solution, while meeting the UAVs’ individual objectives.

In this paper, we evaluate the different fully homomorphic encryption schemes, propose an implementation, and numerically analyze the applicability of gradient descent algorithms to solve quadratic programming in a homomorphic encryption setup. The limit on the multiplication depth of homomorphic encryption circuits is a major challenge for iterative procedures such as gradient descent algorithms. Our analysis not only quantifies these limitations on prototype examples, thus serving as a benchmark for future investigations, but also highlights additional trade-offs like the ones pertaining the choice of gradient descent or accelerated gradient descent methods, opening the road for the use of homomorphic encryption techniques in iterative procedures widely used in optimization based control. In addition, we argue that, among the available homomorphic encryption schemes, the one adopted in this work, namely CKKS, is the only suitable scheme for implementing gradient descent algorithms. The choice of the appropriate step size is crucial to the convergence of the procedure. The paper shows firsthand the feasibility of homomorphically encrypted gradient descent algorithms.

We consider multi-agent coalitional games with uncertainty in the coalitional values. We provide a novel methodology to study the stability of the grand coalition in the case where each coalition constructs ambiguity sets for the (possibly) unknown probability distribution of the uncertainty. As a less conservative solution concept compared to worst-case approaches for coalitional stability, we consider a stochastic version of the so-called core set, i.e., the expected value core. Unfortunately, without exact knowledge of the probability distribution, the evaluation of the expected value core is an extremely challenging task. Hence, we propose the concept of distributionaly robust (DR) core. Leveraging tools from data-driven DR optimization under the Wasserstein distance, we provide finite-sample guarantees that any allocation which lies in the DR core is also stable with respect to the true probability distribution. Furthermore, we show that as the number of samples grows unbounded, the DR core converges almost surely to the true expected value core. We dedicate the last section to the computational tractability of finding an allocation in the DR core.

We propose distributed iterative algorithms for safe control design and safety verification for networked multi-agent systems. These algorithms rely on distributing a control barrier function (CBF) related quadratic programming (QP) problem. The proposed distributed algorithm addresses infeasibility issues of existing schemes by dynamically allocating auxiliary variables across iterations. The resulting control input is guaranteed to be optimal, and renders the system safe. Furthermore, a truncated algorithm is proposed to facilitate computational implementation, with probabilistically guaranteed constraint satisfication, while generating a Lipschitz continuous control input. We further develop a distributed safety verification algorithm to quantify safety for a multi-agent system by means of CBFs in probability. Both upper and lower bounds on the probability of safety are obtained using the so called scenario approach. Both the scenario sampling and safety verification procedures are fully distributed. The efficacy of our algorithms is demonstrated by an example on multi-robot collision avoidance.

In this paper we consider the safety verification and safe controller synthesis problems for nonlinear control systems. The Control Barrier Certificates (CBC) approach is proposed as an extension to the Barrier certificates approach. Our approach can be used to characterize the control invariance of a given set in terms of safety of a general nonlinear control system subject to input constraints. From the point of view of controller design, the proposed method provides an approach to synthesize a safe control law that guarantees that the trajectories of the system starting from a given initial set do not enter an unsafe set. Unlike the related control Barrier functions approach, our formulation only considers the vector field within the tangent cone of the zero level set defined by the certificates, and is shown to be less conservative by means of numerical evidence. For polynomial systems with semi-algebraic initial and safe sets, CBCs and safe control laws can be synthesized using sum-of-squares decomposition and semi-definite programming. Examples demonstrate our method.

Hamilton-Jacobi reachability methods for safety-critical control have been well studied, but the safety guarantees derived rely on the accuracy of the numerical computation. Thus, it is crucial to understand and account for any inaccuracies that occur due to uncertainty in the underlying dynamics and environment as well as the induced numerical errors. To this end, we propose a framework for modeling the error of the value function inherent in Hamilton-Jacobi reachability using a Gaussian process. The derived safety controller can be used in conjuncture with arbitrary controllers to provide a safe hybrid control law. The marginal likelihood of the Gaussian process then provides a confidence metric used to determine switches between a least restrictive controller and a safety controller. We test both the prediction as well as the correction capabilities of the presented method in a classical pursuit-evasion example., Comment: Paper published in 2022 European Control Conference (ECC), 6 pages, 4 figures

We propose a reachability approach for infinite and finite horizon multi-objective optimization problems for low-thrust spacecraft trajectory design. The main advantage of the proposed method is that the Pareto front can be efficiently constructed from the zero level set of the solution to a Hamilton-Jacobi-Bellman equation. We demonstrate the proposed method by applying it to a low-thrust spacecraft trajectory design problem. By deriving the analytic expression for the Hamiltonian and the optimal control policy, we are able to efficiently compute the backward reachable set and reconstruct the optimal trajectories. Furthermore, we show that any reconstructed trajectory will be guaranteed to be weakly Pareto optimal. The proposed method can be used as a benchmark for future research of applying reachability analysis to low-thrust spacecraft trajectory design., Comment: Extended version of the paper published in 2021 European Control Conference (ECC), 9 pages, 2 figures

The so-called scenario approach offers an efficient framework to address uncertain optimisation problems with uncertainty represented by means of scenarios. The sampling-and-discarding approach within the scenario approach literature allows the decision maker to trade feasibility to performance. We focus on a removal scheme composed by a cascade of scenario programs that removes at each stage a superset of the support set associated to the optimal solution of each of these programs. This particular removal scheme yields a scenario solution with tight guarantees on the probability of constraint violation; however, existing analysis restricts the number of discarded scenarios to be a multiple of the dimension of the optimisation problem. Motivated by this fact, this paper presents pathways to extend the theoretical analysis of this removal scheme. We first provide an extension for a restricted class of scenarios programs for which tight bounds can be obtained, and then we provide a conservative bound on the probability of constraint violation that is valid for any scenario program and an arbitrary number of removed scenarios, which is, however, not tight.

We develop a data-driven approach to the computation of a-posteriori feasibility certificates to the solution sets of variational inequalities affected by uncertainty. Specifically, we focus on instances of variational inequalities with a deterministic mapping and an uncertain feasibility set, and represent uncertainty by means of scenarios. Building upon recent advances in the scenario approach literature, we quantify the robustness properties of the entire set of solutions of a variational inequality, with feasibility set constructed using the scenario approach, against a new unseen realization of the uncertainty. Our results extend existing results that typically impose an assumption that the solution set is a singleton and require certain non-degeneracy properties, and thereby offer probabilistic feasibility guarantees to any feasible solution. We show that assessing the violation probability of an entire set of solutions, rather than of a singleton, requires enumeration of the support constraints that "shape" this set. Additionally, we propose a general procedure to enumerate the support constraints that does not require a closed form description of the solution set, which is unlikely to be available. We show that robust game theory problems can be modelling via uncertain variational inequalities, and illustrate our theoretical results through extensive numerical simulations on a case study involving an electric vehicle charging coordination problem.

Power systems globally are significantly integrating renewable energy to achieve net zero emission targets. Nonetheless, these renewable energy sources are weather-dependent and uncertain, bringing challenges to ensure operational reliability. Additionally, extreme weather and natural disasters damage power infrastructure, leading to contingencies or large-scale blackouts occasionally. These pressing issues necessitate uncertainty-aware power system management and give rise to the main research question, how to apply the joint chance-constrained (JCC) formulation in uncertainty-aware power system operations using probabilistic forecasting information? A literature review discusses different machine learning (ML) probabilistic forecasting models and uncertainty-aware formulations in power system operations. Selected ML models are then compared for weather-informed net-load probabilistic forecasting. Leveraging probabilistic forecast, this thesis investigates and applies two uncertainty-aware formulations in power system operations, the JCC and distributionally robust optimization (DRO). Case studies are demonstrated on solar-powered networked microgrids. The first case study investigates solar-powered networked microgrids during utility contingencies. A distributionally robust joint chance-constrained (DRJCC) framework is developed to control this networked microgrid considering the worst-case solar forecast error distribution. The DRJCC problem is reformulated into a tractable individual chance-constrained formulation with unspecified individual violation rates. A novel evolutionary algorithm is designed to approximate the optimal individual violation rates, known as the NP-hard Bonferroni Approximation problem. The solution is proven to be reliable and less conservative in out-of-sample tests compared to other methods. The second one focuses on networked microgrids in the power markets. It envisages that, due to stochastic solar power generations, the imperfect real-time reserve provisions from multiple microgrids simultaneously could result in unexpected load shedding. Lever- aging historical forecast error samples, the reserve bidding strategy of each microgrid is formulated into a two-stage Wasserstein-metrics DRO model. A JCC regulates the under-delivered reserve capacities of all microgrids in a non-cooperative game. To approximate the optimal individual violation rates of microgrids with the changing correlation, the Bayesian optimization method is introduced. This DRJCC game framework is simulated with up to 14 players in a 30-bus network. The proposed Bayesian optimization method can identify the optimal reserve violation rates, which effectively regulate the joint violation rate of the under-delivered reserve whereas securing the profit of microgrids.

Mathematical optimisation plays a crucial role in providing efficient solutions to modern engineering applications. Despite enormous advances in the past decades, some of these applications involve solving optimisation problems that may not be computationally tractable or that call for new theoretical advancements. Hence, obtaining robust and scalable methods and developing new analytic tools to optimisation problems is of paramount importance. This thesis addresses some of the main challenges when solving optimisation programs, namely, scalability, the presence of integer decision variables and the presence of uncertainty. Scalability throughout this thesis is achieved by means of distributed computation. Technological advancements that lead to the increase of computational devices per capita have attracted research on the development of algorithms that can exploit such a distributed and unstructured computational power to solve large-scale optimisation problems. In this context, multi-agent optimisation has emerged, as it enables distributed computation by allowing devices (or agents) to communicate over a network. This thesis proposes an algorithmic scheme based on subgradient averaging to perform multi-agent optimisation. Some optimisation problems are computationally intractable due to the presence of integer variables. Optimising over integers is, in general, hard due to the lack of polynomial-time algorithms to obtain an optimal solution. In fact, some well-known NP-hard problems can be cast as optimisation programs involving integer decision variables. In this thesis we investigate the so-called actuator placement problem and show that a particular instance of this problem, despite being an integer program can be solved exactly by means of a convex relaxation. We also link such a relaxation to the multi-agent optimisation framework explored previously, showing how distributed schemes can be leveraged to obtain the optimal solution. Other challenging optimisation problems arise with the presence of uncertain constraints. Indeed, even the well-studied class of linear optimisation problems may require theoretical and algorithmic advancements under this type of constraints. Uncertain constraints represent our lack of knowledge about the underlying phenomena and appear in several applications, including the optimal power flow problem under renewable energy generation, robotics, and transportation applications. Motivated by this fact, the last part of this thesis focuses on a randomised approximation to chance-constrained optimisation problems. We show a new theoretical bound on the probability of constraint violation that can improve the conservatism with respect to the state-of-the-art.

In this dissertation we focus on safe model based policy search, a subfield of reinforcement learning with two main objectives: data efficiency and safety. To achieve data efficient learning, we use Gaussian process regression to model the dynamics of unknown non-linear systems. The flexibility and probabilistic nature of GPs, along with their useful mathematical properties that often allow for closed form calculations, facilitate building accurate models efficiently, and using these models to optimise control policies for the underlying systems. Furthermore, our safety objective, also probabilistic in nature, is formalised as predefined state space constraints. The model's predictions are used to certify the safety of a candidate policy before deploying it on the system, and we thus manage to avoid constraint violations while training. We present an open source, openly available software tool implementing our proposed algorithm for safe and data efficient policy search. Furthermore, we propose a novel method for planning over multiple time steps with Gaussian processes, and provide formal guarantees bounding the predictive uncertainty. We consider safety and data efficiency critical challenges for the wider adoption of reinforcement learning algorithms, and we hope that our contributions will be useful in this effort.

We consider the problem of finding profit-maximising prices for delivery time slots in the context of attended home delivery. This is a multi-stage optimal control problem that admits a dynamic programming formulation. However, this formulation is intractable for realistic problem sizes due to the so-called "curse of dimensionality''. To facilitate an approximation of this problem, we characterise some mathematical properties of the dynamic program: We show that the underlying Bellman operator has a unique fixed point and provide a closed-form expression for it. Moreover, we show that – under certain technical assumptions – the value function, which has a discrete domain and a continuous codomain, admits a continuous extension, which is a finite-valued, concave function of its state variables, at every time step. Motivated by these results, we develop an approximate dynamic programming algorithm for a more general class of problems, characterised by value functions that are concave extensible and submodular in their state-space. Our new algorithm computes deterministic upper and stochastic lower bounds of the value function in the realm of dual dynamic programming. We show that the proposed algorithm terminates after a finite number of iterations. Moreover, we also derive probabilistic guarantees on the value accumulated under the associated policy for a single realisation of the dynamic program and for its expected value. Furthermore, we compare our algorithm with two other approximate dynamic programming solutions proposed in the literature. Our analysis entails a theoretical examination from a control-theoretical perspective and a parametric numerical case study. Our experiments are based on real-world data, from which we generate multiple scenarios to stress-test the robustness of the pricing policies to errors in model parameter estimates. Our analysis shows that the proposed algorithm dominates the others with respect to computation time and profit-generation capabilities of the delivery slot pricing policies that it generates.

We consider a multi-agent setting with agents exchanging information over a possibly time-varying network, aiming at minimising a separable objective function subject to constraints. To achieve this objective we propose a novel subgradient averaging algorithm that allows for non-differentiable objective functions and different constraint sets per agent. Allowing different constraints per agent simultaneously with a time-varying communication network constitutes a distinctive feature of our approach, extending existing results on distributed subgradient methods. To highlight the necessity of dealing with a different constraint set within a distributed optimisation context, we analyse a problem instance where an existing algorithm does not exhibit a convergent behaviour if adapted to account for different constraint sets. For our proposed iterative scheme we show asymptotic convergence of the iterates to a minimum of the underlying optimisation problem for step sizes of the form η k + 1 , η > 0 . We also analyse this scheme under a step size choice of η k + 1 , η > 0 , and establish a convergence rate of O ( ln k k ) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an l 2 regression problem with regularisation .

We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form $c(k) = \frac{\eta }{{k + 1}}$, for some η > 0. We then restrict attention to step-size choices $c(k) = \frac{\eta }{{\sqrt {k + 1} }},\eta > 0$, and establish a convergence of $\mathcal{O}\left( {\frac{{\ln (k)}}{{\sqrt k }}} \right)$ in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm.