Search

Many modern autonomous systems, particularly multi-agent systems, are time-critical and need to be robust against timing uncertainties. Previous works have studied left and right time robustness of signal temporal logic specifications by considering time shifts in the predicates that are either only to the left or only to the right. We propose a combined notion of temporal robustness which simultaneously considers left and right time shifts. For instance, in a scenario where a robot plans a trajectory around a pedestrian, this combined notion can now capture uncertainty of the pedestrian arriving earlier or later than anticipated. We first derive desirable properties of this new notion with respect to left and right time shifts and then design control laws for linear systems that maximize temporal robustness using mixed-integer linear programming. Finally, we present two case studies to illustrate how the proposed temporal robustness accounts for timing uncertainties.

Neural networks are known to be vulnerable to adversarial attacks, which are small, imperceptible perturbations that can significantly alter the network's output. Conversely, there may exist large, meaningful perturbations that do not affect the network's decision (excessive invariance). In our research, we investigate this latter phenomenon in two contexts: (a) discrete-time dynamical system identification, and (b) the calibration of a neural network's output to that of another network. We examine noninvertibility through the lens of mathematical optimization, where the global solution measures the ``safety" of the network predictions by their distance from the non-invertibility boundary. We formulate mixed-integer programs (MIPs) for ReLU networks and $L_p$ norms ($p=1,2,\infty$) that apply to neural network approximators of dynamical systems. We also discuss how our findings can be useful for invertibility certification in transformations between neural networks, e.g. between different levels of network pruning., Comment: 22 pages, 7 figures

Steady state multiplicity can occur in nonlinear systems, and this presents challenges to feedback control. Input multiplicity arises when the same steady state output values can be reached with system inputs at different values. Dynamic systems with input multiplicities equipped with controllers with integral action have multiple stationary points, which may be locally stable or not. This is undesirable for operation. For a 2x2 example system with three stationary points we demonstrate how to design a set of two single loop controllers such that only one of the stationary points is locally stable, thus effectively eliminating the "input multiplicity problem" for control. We also show that when MPC is used for the example system, all three closed-loop stationary points are stable. Depending on the initial value of the input variables, the closed loop system under MPC may converge to different steady state input instances (but the same output steady state). Therefore we computationally explore the basin boundaries of this closed loop system. It is not clear how MPC or other modern nonlinear controllers could be designed so that only specific equilibrium points are stable.

In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation., Comment: Accepted to COLT 2022

In this paper, we address the stochastic MPC (SMPC) problem for linear systems, subject to chance state constraints and hard input constraints, under unknown noise distribution. First, we reformulate the chance state constraints as deterministic constraints depending only on explicit noise statistics. Based on these reformulated constraints, we design a distributionally robust and robustly stable benchmark SMPC algorithm for the ideal setting of known noise statistics. Then, we employ this benchmark controller to derive a novel robustly stable adaptive SMPC scheme that learns the necessary noise statistics online, while guaranteeing time-uniform satisfaction of the unknown reformulated state constraints with high probability. The latter is achieved through the use of confidence intervals which rely on the empirical noise statistics and are valid uniformly over time. Moreover, control performance is improved over time as more noise samples are gathered and better estimates of the noise statistics are obtained, given the online adaptation of the estimated reformulated constraints. Additionally, in tracking problems with multiple successive targets our approach leads to an online-enlarged domain of attraction compared to robust tube-based MPC. A numerical simulation of a DC-DC converter is used to demonstrate the effectiveness of the developed methodology., Comment: To appear in L4DC 2022

We study the temporal robustness of temporal logic specifications and show how to design temporally robust control laws for time-critical control systems. This topic is of particular interest in connected systems and interleaving processes such as multi-robot and human-robot systems where uncertainty in the behavior of individual agents and humans can induce timing uncertainty. Despite the importance of time-critical systems, temporal robustness of temporal logic specifications has not been studied, especially from a control design point of view. We define synchronous and asynchronous temporal robustness and show that these notions quantify the robustness with respect to synchronous and asynchronous time shifts in the predicates of the temporal logic specification. It is further shown that the synchronous temporal robustness upper bounds the asynchronous temporal robustness. We then study the control design problem in which we aim to design a control law that maximizes the temporal robustness of a dynamical system. Our solution consists of a Mixed-Integer Linear Programming (MILP) encoding that can be used to obtain a sequence of optimal control inputs. While asynchronous temporal robustness is arguably more nuanced than synchronous temporal robustness, we show that control design using synchronous temporal robustness is computationally more efficient. This trade-off can be exploited by the designer depending on the particular application at hand. We conclude the paper with a variety of case studies., Comment: Submitted journal article under review

We propose a robust model predictive control (MPC) method for discrete-time linear systems with polytopic model uncertainty and additive disturbances. Optimizing over linear time-varying (LTV) state feedback controllers has been successfully used for robust MPC when only additive disturbances are present. However, it is challenging to design LTV state feedback controllers in the face of model uncertainty whose effects are difficult to bound. To address this issue, we propose a novel approach to over-approximate the effects of both model uncertainty and additive disturbances by a filtered additive disturbance signal. Using the System Level Synthesis framework, we jointly search for robust LTV state feedback controllers and the bounds on the effects of uncertainty online, which allows us to reduce the conservatism and minimize an upper bound on the worst-case cost in robust MPC. We provide a comprehensive numerical comparison of our method and representative robust MPC methods from the literature. Numerical examples demonstrate that our proposed method can significantly reduce the conservatism over a wide range of uncertainty parameters with comparable computational effort as the baseline methods., Comment: Expanded the conservatism comparison experiments. Under review of Automatica

We propose a robust model predictive control (MPC) method for discrete-time linear time-invariant systems with norm-bounded additive disturbances and model uncertainty. In our method, at each time step we solve a finite time robust optimal control problem (OCP) which jointly searches over robust linear state feedback controllers and bounds the deviation of the system states from the nominal predicted trajectory. By leveraging the System Level Synthesis (SLS) framework, the proposed robust OCP is formulated as a convex quadratic program in the space of closed-loop system responses. When an adaptive horizon strategy is used, we prove the recursive feasibility of the proposed MPC controller and input-to-state stability of the origin for the closed-loop system. We demonstrate through numerical examples that the proposed method considerably reduces conservatism when compared with existing SLS-based and tube-based robust MPC methods, while also enjoying low computational complexity.

Estimating the region of attraction (ROA) of general nonlinear autonomous systems remains a challenging problem and requires a case-by-case analysis. Leveraging the universal approximation property of neural networks, in this paper, we propose a counterexample-guided method to estimate the ROA of general nonlinear dynamical systems provided that they can be approximated by piecewise linear neural networks and that the approximation error can be bounded. Specifically, our method searches for robust Lyapunov functions using counterexamples, i.e., the states at which the Lyapunov conditions fail. We generate the counterexamples using Mixed-Integer Quadratic Programming. Our method is guaranteed to find a robust Lyapunov function in the parameterized function class, if exists, after collecting a finite number of counterexamples. We illustrate our method through numerical examples., Comment: Accepted to Conference on Decision and Control 2021

The main challenge in controlling hybrid systems arises from having to consider an exponential number of sequences of future modes to make good long-term decisions. Model predictive control (MPC) computes a control action through a finite-horizon optimisation problem. A key ingredient in this problem is a terminal cost, to account for the system's evolution beyond the chosen horizon. A good terminal cost can reduce the horizon length required for good control action and is often tuned empirically by observing performance. We build on the idea of using $N$-step $Q$-functions $(\mathcal{Q}^{(N)})$ in the MPC objective to avoid having to choose a terminal cost. We present a formulation incorporating the system dynamics and constraints to approximate the optimal $\mathcal{Q}^{(N)}$-function and algorithms to train the approximation parameters through an exploration of the state space. We test the control policy derived from the trained approximations on two benchmark problems through simulations and observe that our algorithms are able to learn good $\mathcal{Q}^{(N)}$-approximations for high dimensional hybrid systems based on a relatively small dataset. Finally, we compare our controller's performance against that of Hybrid MPC in terms of computation time and closed-loop cost., Comment: 8 pages, 4 figures, 1 algorithm, 2 tables, 1 appendix with 5 matrices

We present a robust control framework for time-critical systems in which satisfying real-time constraints robustly is of utmost importance for the safety of the system. Signal Temporal Logic (STL) provides a formal means to express a large variety of real-time constraints over signals and is suited for planning and control purposes as it allows us to reason about the time robustness of such constraints. The time robustness of STL particularly quantifies the extent to which timing uncertainties can be tolerated without violating real-time specifications. In this paper, we first pose a control problem in which we aim to find an optimal input sequence to a control system that maximizes the time robustness of an STL constraint. We then propose a Mixed Integer Linear Program (MILP) encoding and provide correctness guarantees along with a complexity analysis of the encoding. We also show in two case studies that maximizing STL time robustness allows to account for timing uncertainties of the underlying control system., Comment: Submitted to the Conference on Decision and Control 2021

We propose a sampling-based approach to learn Lyapunov functions for a class of discrete-time autonomous hybrid systems that admit a mixed-integer representation. Such systems include autonomous piecewise affine systems, closed-loop dynamics of linear systems with model predictive controllers, piecewise affine/linear complementarity/mixed-logical dynamical system in feedback with a ReLU neural network controller, etc. The proposed method comprises an alternation between a learner and a verifier to find a valid Lyapunov function inside a convex set of Lyapunov function candidates. In each iteration, the learner uses a collection of state samples to select a Lyapunov function candidate through a convex program in the parameter space. The verifier then solves a mixed-integer quadratic program in the state space to either validate the proposed Lyapunov function candidate or reject it with a counterexample, i.e., a state where the Lyapunov condition fails. This counterexample is then added to the sample set of the learner to refine the set of Lyapunov function candidates. By designing the learner and the verifier according to the analytic center cutting-plane method from convex optimization, we show that when the set of Lyapunov functions is full-dimensional in the parameter space, our method finds a Lyapunov function in a finite number of steps. We demonstrate our stability analysis method on closed-loop MPC dynamical systems and a ReLU neural network controlled PWA system., Comment: arXiv admin note: text overlap with arXiv:2008.06546

Complementarity problems, a class of mathematical optimization problems with orthogonality constraints, are widely used in many robotics tasks, such as locomotion and manipulation, due to their ability to model non-smooth phenomena (e.g., contact dynamics). In this paper, we propose a method to analyze the stability of complementarity systems with neural network controllers. First, we introduce a method to represent neural networks with rectified linear unit (ReLU) activations as the solution to a linear complementarity problem. Then, we show that systems with ReLU network controllers have an equivalent linear complementarity system (LCS) description. Using the LCS representation, we turn the stability verification problem into a linear matrix inequality (LMI) feasibility problem. We demonstrate the approach on several examples, including multi-contact problems and friction models with non-unique solutions.

We propose a learning-based method for Lyapunov stability analysis of piecewise affine dynamical systems in feedback with piecewise affine neural network controllers. The proposed method consists of an iterative interaction between a learner and a verifier, where in each iteration, the learner uses a collection of samples of the closed-loop system to propose a Lyapunov function candidate as the solution to a convex program. The learner then queries the verifier, which solves a mixed-integer program to either validate the proposed Lyapunov function candidate or reject it with a counterexample, i.e., a state where the stability condition fails. This counterexample is then added to the sample set of the learner to refine the set of Lyapunov function candidates. We design the learner and the verifier based on the analytic center cutting-plane method, in which the verifier acts as the cutting-plane oracle to refine the set of Lyapunov function candidates. We show that when the set of Lyapunov functions is full-dimensional in the parameter space, the overall procedure finds a Lyapunov function in a finite number of iterations. We demonstrate the utility of the proposed method in searching for quadratic and piecewise quadratic Lyapunov functions.

We solve active target tracking, one of the essential tasks in autonomous systems, using a deep reinforcement learning (RL) approach. In this problem, an autonomous agent is tasked with acquiring information about targets of interests using its onboard sensors. The classical challenges in this problem are system model dependence and the difficulty of computing information-theoretic cost functions for a long planning horizon. RL provides solutions for these challenges as the length of its effective planning horizon does not affect the computational complexity, and it drops the strong dependency of an algorithm on system models. In particular, we introduce Active Tracking Target Network (ATTN), a unified RL policy that is capable of solving major sub-tasks of active target tracking -- in-sight tracking, navigation, and exploration. The policy shows robust behavior for tracking agile and anomalous targets with a partially known target model. Additionally, the same policy is able to navigate in obstacle environments to reach distant targets as well as explore the environment when targets are positioned in unexpected locations., Comment: IEEE Transaction on Robotics (under review); Demo video: https://youtu.be/0ZFyOWJ2ulo ; Source code: https://github.com/coco66/ttenv

Autonomous race cars require perception, estimation, planning, and control modules which work together asynchronously while driving at the limit of a vehicle's handling capability. A fundamental challenge encountered in designing these software components lies in predicting the vehicle's future state (e.g. position, orientation, and speed) with high accuracy. The root cause is the difficulty in identifying vehicle model parameters that capture the effects of lateral tire slip. We present a model-based planning and control framework for autonomous racing that significantly reduces the effort required in system identification and control design. Our approach alleviates the gap induced by simulation-based controller design by learning from on-board sensor measurements. A major focus of this work is empirical, thus, we demonstrate our contributions by experiments on validated 1:43 and 1:10 scale autonomous racing simulations.

There has been an increasing interest in using neural networks in closed-loop control systems to improve performance and reduce computational costs for on-line implementation. However, providing safety and stability guarantees for these systems is challenging due to the nonlinear and compositional structure of neural networks. In this paper, we propose a novel forward reachability analysis method for the safety verification of linear time-varying systems with neural networks in feedback interconnection. Our technical approach relies on abstracting the nonlinear activation functions by quadratic constraints, which leads to an outer-approximation of forward reachable sets of the closed-loop system. We show that we can compute these approximate reachable sets using semidefinite programming. We illustrate our method in a quadrotor example, in which we first approximate a nonlinear model predictive controller via a deep neural network and then apply our analysis tool to certify finite-time reachability and constraint satisfaction of the closed-loop system.

A good racing strategy and in particular the racing line is decisive to winning races in Formula 1, MotoGP, and other forms of motor racing. The racing line defines the path followed around a track as well as the optimal speed profile along the path. The objective is to minimize lap time by driving the vehicle at the limits of friction and handling capability. The solution naturally depends upon the geometry of the track and vehicle dynamics. We introduce a novel method to compute the racing line using Bayesian optimization. Our approach is fully data-driven and computationally more efficient compared to other methods based on dynamic programming and random search. The approach is specifically relevant in autonomous racing where teams can quickly compute the racing line for a new track and then exploit this information in the design of a motion planner and a controller to optimize real-time performance.

Model predictive control (MPC) can provide significant energy cost savings in building operations in the form of energy-efficient control with better occupant comfort, lower peak demand charges, and risk-free participation in demand response. However, the engineering effort required to obtain physics-based models of buildings is considered to be the biggest bottleneck in making MPC scalable to real buildings. In this paper, we propose a data-driven control algorithm based on neural networks to reduce this cost of model identification. Our approach does not require building domain expertise or retrofitting of existing heating and cooling systems. We validate our learning and control algorithms on a two-story building with ten independently controlled zones, located in Italy. We learn dynamical models of energy consumption and zone temperatures with high accuracy and demonstrate energy savings and better occupant comfort compared to the default system controller.

In this work we adapt a prediction-correction algorithm for continuous time-varying convex optimization problems to solve dynamic programs arising from Model Predictive Control. In particular, the prediction step tracks the evolution of the optimal solution of the problem which depends on the current state of the system. The cost of said step is that of inverting one Hessian and it guarantees, under some conditions, that the iterate remains in the quadratic convergence region of the optimization problem at the next time step. These conditions imply (i) that the variation of the state in a control interval cannot be too large and that (ii) the solution computed in the previous time step needs to be sufficiently accurate. The latter can be guaranteed by running classic Newton iterations, which we term correction steps. Since this method exhibits quadratic convergence the number of iterations to achieve a desired accuracy $\eta$ is of order $\log_2\log_2 1/\eta$, where the cost of each iteration is approximately that of inverting a Hessian. This grants the prediction-correction control law low computational complexity. In addition, the solution achieved by the algorithm is such that the closed loop system remains stable, which allows extending the applicability of Model Predictive Control to systems with faster dynamics and less computational power. Numerical examples where we consider nonlinear systems support the theoretical conclusions.

In this paper, we consider the robust closed-loop model predictive control (MPC) of a linear time-variant (LTV) system with norm bounded disturbances and LTV model uncertainty, wherein a series of constrained optimal control problems (OCPs) are solved. Guaranteeing robust feasibility of these OCPs is challenging due to disturbances perturbing the predicted states, and model uncertainty, both of which can render the closed-loop system unstable. As such, a trade-off between the numerical tractability and conservativeness of the solutions is often required. We use the System Level Synthesis (SLS) framework to reformulate these constrained OCPs over closed-loop system responses, and show that this allows us to transparently account for norm bounded additive disturbances and LTV model uncertainty by computing robust state feedback policies. We further show that by exploiting the underlying linear fractional structure of the resulting robust OCPs, we can significantly reduce the conservativeness of existing SLS-based and tube-MPC-based robust control methods while also improving computational efficiency. We conclude with numerical examples demonstrating the effectiveness of our methods.

In this paper, we propose a novel Reinforcement Learning approach for solving the Active Information Acquisition problem, which requires an agent to choose a sequence of actions in order to acquire information about a process of interest using on-board sensors. The classic challenges in the information acquisition problem are the dependence of a planning algorithm on known models and the difficulty of computing information-theoretic cost functions over arbitrary distributions. In contrast, the proposed framework of reinforcement learning does not require any knowledge on models and alleviates the problems during an extended training stage. It results in policies that are efficient to execute online and applicable for real-time control of robotic systems. Furthermore, the state-of-the-art planning methods are typically restricted to short horizons, which may become problematic with local minima. Reinforcement learning naturally handles the issue of planning horizon in information problems as it maximizes a discounted sum of rewards over a long finite or infinite time horizon. We discuss the potential benefits of the proposed framework and compare the performance of the novel algorithm to an existing information acquisition method for multi-target tracking scenarios., Comment: IROS 2019, Video https://youtu.be/0ZFyOWJ2ulo

This work presents an explicit-implicit procedure to compute a model predictive control (MPC) law with guarantees on recursive feasibility and asymptotic stability. The approach combines an offline-trained fully-connected neural network with an online primal active set solver. The neural network provides a control input initialization while the primal active set method ensures recursive feasibility and asymptotic stability. The neural network is trained with a primal-dual loss function, aiming to generate control sequences that are primal feasible and meet a desired level of suboptimality. Since the neural network alone does not guarantee constraint satisfaction, its output is used to warm start the primal active set method online. We demonstrate that this approach scales to large problems with thousands of optimization variables, which are challenging for current approaches. Our method achieves a 2x reduction in online inference time compared to the best method in a benchmark suite of different solver and initialization strategies.

Quantifying the robustness of neural networks or verifying their safety properties against input uncertainties or adversarial attacks have become an important research area in learning-enabled systems. Most results concentrate around the worst-case scenario where the input of the neural network is perturbed within a norm-bounded uncertainty set. In this paper, we consider a probabilistic setting in which the uncertainty is random with known first two moments. In this context, we discuss two relevant problems: (i) probabilistic safety verification, in which the goal is to find an upper bound on the probability of violating a safety specification; and (ii) confidence ellipsoid estimation, in which given a confidence ellipsoid for the input of the neural network, our goal is to compute a confidence ellipsoid for the output. Due to the presence of nonlinear activation functions, these two problems are very difficult to solve exactly. To simplify the analysis, our main idea is to abstract the nonlinear activation functions by a combination of affine and quadratic constraints they impose on their input-output pairs. We then show that the safety of the abstracted network, which is sufficient for the safety of the original network, can be analyzed using semidefinite programming. We illustrate the performance of our approach with numerical experiments.

Tight estimation of the Lipschitz constant for deep neural networks (DNNs) is useful in many applications ranging from robustness certification of classifiers to stability analysis of closed-loop systems with reinforcement learning controllers. Existing methods in the literature for estimating the Lipschitz constant suffer from either lack of accuracy or poor scalability. In this paper, we present a convex optimization framework to compute guaranteed upper bounds on the Lipschitz constant of DNNs both accurately and efficiently. Our main idea is to interpret activation functions as gradients of convex potential functions. Hence, they satisfy certain properties that can be described by quadratic constraints. This particular description allows us to pose the Lipschitz constant estimation problem as a semidefinite program (SDP). The resulting SDP can be adapted to increase either the estimation accuracy (by capturing the interaction between activation functions of different layers) or scalability (by decomposition and parallel implementation). We illustrate the utility of our approach with a variety of experiments on randomly generated networks and on classifiers trained on the MNIST and Iris datasets. In particular, we experimentally demonstrate that our Lipschitz bounds are the most accurate compared to those in the literature. We also study the impact of adversarial training methods on the Lipschitz bounds of the resulting classifiers and show that our bounds can be used to efficiently provide robustness guarantees.

Certifying the safety or robustness of neural networks against input uncertainties and adversarial attacks is an emerging challenge in the area of safe machine learning and control. To provide such a guarantee, one must be able to bound the output of neural networks when their input changes within a bounded set. In this paper, we propose a semidefinite programming (SDP) framework to address this problem for feed-forward neural networks with general activation functions and input uncertainty sets. Our main idea is to abstract various properties of activation functions (e.g., monotonicity, bounded slope, bounded values, and repetition across layers) with the formalism of quadratic constraints. We then analyze the safety properties of the abstracted network via the S-procedure and semidefinite programming. Our framework spans the trade-off between conservatism and computational efficiency and applies to problems beyond safety verification. We evaluate the performance of our approach via numerical problem instances of various sizes.

Doubly curved thin concrete shells are very efficient building structures, suitable for light-weight construction because of their high structural stability. In the process of constructing such shells, an efficient innovative flexible formwork that is based on a cable network can be used instead of the costly conventional timber formwork. To guarantee the structural properties of such a shell, the desired form, that is designed and optimized in advance, needs to be precisely achieved. The sensitivity of the flexible cable net formwork to fabrication tolerances and uncertainties makes high accuracy challenging. We propose a new construction method where the form of the cable net structure is measured and controlled in a feedback loop during its construction. Two models based on a force and on an energy approach are reviewed and their equivalence is shown. An efficient control algorithm, which is based on a variant of Sequential Quadratic Programming, and which guarantees feasibility at every iteration, is derived. Based on mild assumptions on the cable net, global convergence to a stationary point is shown. For practical applicability, an extension of the control algorithm for computing sparse input vectors is given. Experimental results on a cable net formwork prototype for a shell roof structure are presented to demonstrate the control performance., Comment: 26 pages, 12 figures

In this paper, we propose a framework based on sum-of-squares programming to design iterative first-order optimization algorithms for smooth and strongly convex problems. Our starting point is to develop a polynomial matrix inequality as a sufficient condition for exponential convergence of the algorithm. The entries of this matrix are polynomial functions of the unknown parameters (exponential decay rate, stepsize, momentum coefficient, etc.). We then formulate a polynomial optimization, in which the objective is to optimize the exponential decay rate over the parameters of the algorithm. Finally, we use sum-of-squares programming as a tractable relaxation of the proposed polynomial optimization problem. We illustrate the utility of the proposed framework by designing a first-order algorithm that shares the same structure as Nesterov's accelerated gradient method.

This paper explores the privacy of cloud outsourced Model Predictive Control (MPC) for a linear system with input constraints. In our cloud-based architecture, a client sends her private states to the cloud who performs the MPC computation and returns the control inputs. In order to guarantee that the cloud can perform this computation without obtaining anything about the client's private data, we employ a partially homomorphic cryptosystem. We propose protocols for two cloud-MPC architectures motivated by the current developments in the Internet of Things: a client-server architecture and a two-server architecture. In the first case, a control input for the system is privately computed by the cloud server, with the assistance of the client. In the second case, the control input is privately computed by two independent, non-colluding servers, with no additional requirements from the client. We prove that the proposed protocols preserve the privacy of the client's data and of the resulting control input. Furthermore, we compute bounds on the errors introduced by encryption. We present numerical simulations for the two architectures and discuss the trade-off between communication, MPC performance and privacy., Comment: Full version of the eponymous work at CDC 2018

This paper describes autonomous racing of RC race cars based on mathematical optimization. Using a dynamical model of the vehicle, control inputs are computed by receding horizon based controllers, where the objective is to maximize progress on the track subject to the requirement of staying on the track and avoiding opponents. Two different control formulations are presented. The first controller employs a two-level structure, consisting of a path planner and a nonlinear model predictive controller (NMPC) for tracking. The second controller combines both tasks in one nonlinear optimization problem (NLP) following the ideas of contouring control. Linear time varying models obtained by linearization are used to build local approximations of the control NLPs in the form of convex quadratic programs (QPs) at each sampling time. The resulting QPs have a typical MPC structure and can be solved in the range of milliseconds by recent structure exploiting solvers, which is key to the real-time feasibility of the overall control scheme. Obstacle avoidance is incorporated by means of a high-level corridor planner based on dynamic programming, which generates convex constraints for the controllers according to the current position of opponents and the track layout. The control performance is investigated experimentally using 1:43 scale RC race cars, driven at speeds of more than 3 m/s and in operating regions with saturated rear tire forces (drifting). The algorithms run at 50 Hz sampling rate on embedded computing platforms, demonstrating the real-time feasibility and high performance of optimization-based approaches for autonomous racing.

In this paper, we develop a unified framework able to certify both exponential and subexponential convergence rates for a wide range of iterative first-order optimization algorithms. To this end, we construct a family of parameter-dependent nonquadratic Lyapunov functions that can generate convergence rates in addition to proving asymptotic convergence. Using Integral Quadratic Constraints (IQCs) from robust control theory, we propose a Linear Matrix Inequality (LMI) to guide the search for the parameters of the Lyapunov function in order to establish a rate bound. Based on this result, we formulate a Semidefinite Programming (SDP) whose solution yields the best convergence rate that can be certified by the class of Lyapunov functions under consideration. We illustrate the utility of our results by analyzing the gradient method, proximal algorithms and their accelerated variants for (strongly) convex problems. We also develop the continuous-time counterpart, whereby we analyze the gradient flow and the continuous-time limit of Nesterov's accelerated method.

Projected Gradient Descent denotes a class of iterative methods for solving optimization programs. Its applicability to convex optimization programs has gained significant popularity for its intuitive implementation that involves only simple algebraic operations. In fact, if the projection onto the feasible set is easy to compute, then the method has low complexity. On the other hand, when the problem is nonconvex, e.g. because of nonlinear equality constraints, the projection becomes hard and thus impractical. In this paper, we propose a projected gradient method for Nonlinear Programs (NLPs) that only requires projections onto the linearization of the nonlinear constraints around the current iterate, similarly to Sequential Quadratic Programming (SQP). Although the projection is easier to compute, it makes the intermediate steps unfeasible for the original problem. As a result, the gradient method does not fall either into the projected gradient descent approaches, because the projection is not performed onto the original nonlinear manifold, or into the standard SQP, since second-order information is not used. For nonlinear smooth optimization problems, we analyze the similarities of the proposed method with SQP and assess its local and global convergence to a Karush-Kuhn-Tucker (KKT) point of the original problem. Further, we show that nonlinear Model Predictive Control (MPC) is a promising application of the proposed method, due to the sparsity of the resulting optimization problem. We illustrate the computational efficiency of the proposed method in a numerical example with box constraints on the control input and a quadratic terminal constraint on the state variable.

Model predictive control problems for constrained hybrid systems are usually cast as mixed-integer optimization problems (MIP). However, commercial MIP solvers are designed to run on desktop computing platforms and are not suited for embedded applications which are typically restricted by limited computational power and memory. To alleviate these restrictions, we develop a novel low-complexity, iterative method for a class of non-convex, non-smooth optimization problems. This class of problems encompasses hybrid model predictive control problems where the dynamics are piece-wise affine (PWA). We give conditions such that the proposed algorithm has fixed points and show that, under practical assumptions, our method is guaranteed to converge locally to local minima. This is in contrast to other low-complexity methods in the literature, such as the non-convex alternating directions method of multipliers (ADMM), for which no such guarantees are known for this class of problems. By interpreting the PWA dynamics as a union of polyhedra we can exploit the problem structure and develop an algorithm based on operator splitting procedures. Our algorithm departs from the traditional MIP formulation, and leads to a simple, embeddable method that only requires matrix-vector multiplications and small-scale projections onto polyhedra. We illustrate the efficacy of the method on two numerical examples, achieving good closed-loop performance with computational times several orders of magnitude smaller compared to state-of-the-art MIP solvers. Moreover, it is competitive with ADMM in terms of suboptimality and computation time, but additionally provides local optimality and local convergence guarantees.

An effective means for analyzing the impact of novel operating schemes on power systems is time domain simulation, for example for investigating optimization-based curtailment of renewables to alleviate voltage violations. Traditionally, interior-point methods are used for solving the non-convex AC optimal power flow (OPF) problems arising in this type of simulation. This paper presents an alternative algorithm that better suits the simulation framework, because it can more effectively be warm-started, has linear computational and memory complexity in the problem size per iteration and globally converges to Karush-Kuhn-Tucker (KKT) points with a linear rate if they exist. The algorithm exploits a difference-of-convex-functions reformulation of the OPF problem, which can be performed effectively. Numerical results are presented comparing the method to state-of-the-art OPF solver implementations in MATPOWER, leading to significant speedups compared to the latter.

This manuscript contains technical details of recent results developed by the authors on the algorithm for direct design of controllers for nonlinear systems from data that has the ability to to automatically modify some of the tuning parameters in order to increase control performance over time.

This paper is concerned with the design of a linear control law for linear systems with stationary additive disturbances. The objective is to find a state feedback gain that minimizes a quadratic stage cost function, while observing chance constraints on the input and/or the state. Unlike most of the previous literature, the chance constraints (and the stage cost) are not considered on each input/state of the transient response. Instead, they refer to the input/state of the closed-loop system in its stationary mode of operation. Hence the control is optimized for a long-run, rather than a finite-horizon operation. The controller synthesis can be cast as a convex semi-definite program (SDP). The chance constraints appear as linear matrix inequalities. Both single chance constraints (SCCs) and joint chance constraints (JCCs) on the input and/or the state can be included. If the disturbance is Gaussian, additionally to WSS, this information can be used to improve the controller design. The presented approach can also be extended to the case of output feedback. The entire design procedure is flexible and easy to implement, as demonstrated on a short illustrative example., Comment: extended version of journal publication

Lagrangian duality in mixed integer optimization is a useful framework for problems decomposition and for producing tight lower bounds to the optimal objective, but in contrast to the convex counterpart, it is generally unable to produce optimal solutions directly. In fact, solutions recovered from the dual may be not only suboptimal, but even infeasible. In this paper we concentrate on large scale mixed--integer programs with a specific structure that is of practical interest, as it appears in a variety of application domains such as power systems or supply chain management. We propose a solution method for these structures, in which the primal problem is modified in a certain way, guaranteeing that the solutions produced by the corresponding dual are feasible for the original unmodified primal problem. The modification is simple to implement and the method is amenable to distributed computations. We also demonstrate that the quality of the solutions recovered using our procedure improves as the problem size increases, making it particularly useful for large scale instances for which commercial solvers are inadequate. We illustrate the efficacy of our method with extensive experimentations on a problem stemming from power systems., Comment: 23 pages, 9 figures

Airborne wind energy systems aim to harvest the power of winds blowing at altitudes higher than what conventional wind turbines reach. They employ a tethered flying structure, usually a wing, and exploit the aerodynamic lift to produce electrical power. In the case of ground-based systems, where the traction force on the tether is used to drive a generator on the ground, a two phase power cycle is carried out: one phase to produce power, where the tether is reeled out under high traction force, and a second phase where the tether is recoiled under minimal load. The problem of controlling a tethered wing in this second phase, the retraction phase, is addressed here, by proposing two possible control strategies. Theoretical analyses, numerical simulations, and experimental results are presented to show the performance of the two approaches. Finally, the experimental results of complete autonomous power generation cycles are reported and compared with first-principle models., Comment: This manuscript is a preprint of a paper submitted for possible publication on the IEEE Transactions on Control Systems Technology and is subject to IEEE Copyright. If accepted, the copy of record will be available at IEEEXplore library: http://ieeexplore.ieee.org

This paper presents an efficient approach for the evaluation of multi-parametric mixed integer quadratic programming (mp-MIQP) solutions, occurring for instance in control problems involving discrete time hybrid systems with quadratic cost. Traditionally, the online evaluation requires a sequential comparison of piecewise quadratic value functions. As the main contribution, we introduce a lifted parameter space in which the piecewise quadratic value functions become piecewise affine and can be merged to a single value function defined over a single polyhedral partition without any overlaps. This enables efficient point location approaches using a single binary search tree. Numerical experiments include a power electronics application and demonstrate an online speedup up to an order of magnitude. We also show how the achievable online evaluation time can be traded off against the offline computational time., Comment: 23 pages, update includes more details Theorem 1 proof

Airborne wind energy systems aim to generate renewable energy by means of the aerodynamic lift produced by a wing tethered to the ground and controlled to fly crosswind paths. The problem of maximizing the average power developed by the generator, in presence of limited information on wind speed and direction, is considered. At constant tether speed operation, the power is related to the traction force generated by the wing. First, a study of the traction force is presented for a general path parametrization. In particular, the sensitivity of the traction force on the path parameters is analyzed. Then, the results of this analysis are exploited to design an algorithm to maximize the force, hence the power, in real-time. The algorithm uses only the measured traction force on the tether and it is able to adapt the system's operation to maximize the average force with uncertain and time-varying wind. The influence of inaccurate sensor readings and turbulent wind are also discussed. The presented algorithm is not dependent on a specific hardware setup and can act as an extension of existing control structures. Both numerical simulations and experimental results are presented to highlight the effectiveness of the approach., Comment: This manuscript is a preprint of a paper submitted for possible publication on the IEEE Transactions on Control Systems Technology and is subject to IEEE Copyright. If accepted, the copy of record will be available at IEEEXplore library: http://ieeexplore.ieee.org/

Many practical applications of control require that constraints on the inputs and states of the system be respected, while optimizing some performance criterion. In the presence of model uncertainties or disturbances, for many control applications it suffices to keep the state constraints at least for a prescribed share of the time, as e.g. in building climate control or load mitigation for wind turbines. For such systems, a new control method of Scenario-Based Model Predictive Control (SCMPC) is presented in this paper. It optimizes the control inputs over a finite horizon, subject to robust constraint satisfaction under a finite number of random scenarios of the uncertainty and/or disturbances. While previous approaches have shown to be conservative (i.e. to stay far below the specified rate of constraint violations), the new method is the first to account for the special structure of the MPC problem in order to significantly reduce the number of scenarios. In combination with a new framework for interpreting the probabilistic constraints as average-in-time, rather than pointwise-in-time, the conservatism is eliminated. The presented method retains the essential advantages of SCMPC, namely the reduced computational complexity and the handling of arbitrary probability distributions. It also allows for adopting sample-and-remove strategies, in order to trade performance against computational complexity., Comment: Pre-print submitted to Automatica

This paper considers a combination of intelligent repositioning decisions and dynamic pricing for the improved operation of shared mobility systems. The approach is applied to London's Barclays Cycle Hire scheme, which the authors have simulated based on historical data. Using model-based predictive control principles, dynamically varying rewards are computed and offered to customers carrying out journeys. The aim is to encourage them to park bicycles at nearby under-used stations, thereby reducing the expected cost of repositioning them using dedicated staff. In parallel, the routes that repositioning staff should take are periodically recomputed using a model-based heuristic. It is shown that a trade-off between reward payouts to customers and the cost of hiring repositioning staff could be made, in order to minimize operating costs for a given desired service level.

Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We provide analysis ensuring the reliable operation of the resulting controller under reduced precision fixed-point arithmetic. Implementation of the proposed architectures in FPGAs shows that satisfactory control performance at a sample rate beyond 1 MHz is achievable even on low-end devices, opening up new possibilities for the application of MPC on embedded systems.

An approach to control tethered wings for airborne wind energy is proposed. A fixed length of the lines is considered, and the aim of the control system is to obtain figure-eight crosswind trajectories. The proposed technique is based on the notion of the wing's "velocity angle" and, in contrast with most existing approaches, it does not require a measurement of the wind speed or of the effective wind at the wing's location. Moreover, the proposed approach features few parameters, whose effects on the system's behavior are very intuitive, hence simplifying tuning procedures. A simplified model of the steering dynamics of the wing is derived from first-principle laws, compared with experimental data and used for the control design. The control algorithm is divided into a low-level loop for the velocity angle and a high-level guidance strategy to achieve the desired flight patterns. The robustness of the inner loop is verified analytically, and the overall control system is tested experimentally on a small-scale prototype, with varying wind conditions and using different wings., Comment: This manuscript is a preprint of a paper accepted for publication on the IEEE Transactions on Control Systems Technology and is subject to IEEE Copyright. The copy of record is available at IEEEXplore library: http://ieeexplore.ieee.org/

This paper introduces the concept of affine reserve policies for accommodating large, fluctuating renewable infeeds in power systems. The approach uses robust optimization with recourse to determine operating rules for power system entities such as generators and storage units. These rules, or policies, establish several hours in advance how these entities are to respond to errors in the prediction of loads and renewable infeeds once their values are discovered. Affine policies consist of a nominal power schedule plus a series of planned linear modifications that depend on the prediction errors that will become known at future times. We describe how to choose optimal affine policies that respect the power network constraints, namely matching supply and demand, respecting transmission line ratings, and the local operating limits of power system entities, for all realizations of the prediction errors. Crucially, these policies are time-coupled, exploiting the spatial and temporal correlation of these prediction errors. Affine policies are compared with existing reserve operation under standard modelling assumptions, and operating cost reductions are reported for a multi-day benchmark study featuring a poorly-predicted wind infeed. Efficient prices for such "policy-based reserves" are derived, and we propose new reserve products that could be traded on electricity markets., Comment: 27 pages, 4 figures

The scenario-based optimization approach (`scenario approach') provides an intuitive way of approximating the solution to chance-constrained optimization programs, based on finding the optimal solution under a finite number of sampled outcomes of the uncertainty (`scenarios'). A key merit of this approach is that it neither assumes knowledge of the uncertainty set, as it is common in robust optimization, nor of its probability distribution, as it is usually required in stochastic optimization. Moreover, the scenario approach is computationally efficient as its solution is based on a deterministic optimization program that is canonically convex, even when the original chance-constrained problem is not. Recently, researchers have obtained theoretical foundations for the scenario approach, providing a direct link between the number of scenarios and bounds on the constraint violation probability. These bounds are tight in the general case of an uncertain optimization problem with a single chance constraint. However, this paper shows that these bounds can be improved in situations where the constraints have a limited `support rank', a new concept that is introduced for the first time. This property is typically found in a large number of practical applications---most importantly, if the problem originally contains multiple chance constraints (e.g. multi-stage uncertain decision problems), or if a chance constraint belongs to a special class of constraints (e.g. linear or quadratic constraints). In these cases the quality of the scenario solution is improved while the same bound on the constraint violation probability is maintained, and also the computational complexity is reduced., Comment: This manuscript is the preprint of a paper submitted to the SIAM Journal on Optimization and it is subject to SIAM copyright. SIAM maintains the sole rights of distribution or publication of the work in all forms and media. If accepted, the copy of record will be available at http://www.siam.org