Tyler H. Summers

Tyler H. Summers, Fabrizio L. Cortesi, John Lygeros

Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.

Tyler H. Summers, John Lygeros

We propose a distributed optimization method for solving a distributed model predictive consensus problem. The goal is to design a distributed controller for a network of dynamical systems to optimize a coupled objective function while respecting state and input constraints. The distributed optimization method is an augmented Lagrangian method called the Alternating Direction Method of Multipliers (ADMM), which was introduced in the 1970s but has seen a recent resurgence in the context of dramatic increases in computing power and the development of widely available distributed computing platforms. The method is applied to position and velocity consensus in a network of double integrators. We find that a few tens of ADMM iterations yield closed-loop performance near what is achieved by solving the optimization problem centrally. Furthermore, the use of recent code generation techniques for solving local subproblems yields fast overall computation times.

Yi Guo, Kyri Baker, Emiliano Dall'Anese et al.

We propose a data-based method to solve a multi-stage stochastic optimal power flow (OPF) problem based on limited information about forecast error distributions. The framework explicitly combines multi-stage feedback policies with any forecasting method and historical forecast error data. The objective is to determine power scheduling policies for controllable devices in a power network to balance operational cost and conditional value-at-risk (CVaR) of device and network constraint violations. These decisions include both nominal power schedules and reserve policies, which specify planned reactions to forecast errors in order to accommodate fluctuating renewable energy sources. Instead of assuming the uncertainties across the networks follow prescribed probability distributions, we consider ambiguity sets of distributions centered around a finite training dataset. By utilizing the Wasserstein metric to quantify differences between the empirical data-based distribution and the real unknown data-generating distribution, we formulate a multi-stage distributionally robust OPF problem to compute optimal control policies that are robust to both forecast errors and sampling errors inherent in the dataset. Two specific data-based distributionally robust stochastic OPF problems are proposed for distribution networks and transmission systems.

Tyler H. Summers, Konstantin Kunz, Nikolaos Kariotoglou et al.

We describe an approximate dynamic programming method for stochastic control problems on infinite state and input spaces. The optimal value function is approximated by a linear combination of basis functions with coefficients as decision variables. By relaxing the Bellman equation to an inequality, one obtains a linear program in the basis coefficients with an infinite set of constraints. We show that a recently introduced method, which obtains convex quadratic value function approximations, can be extended to higher order polynomial approximations via sum of squares programming techniques. An approximate value function can then be computed offline by solving a semidefinite program, without having to sample the infinite constraint. The policy is evaluated online by solving a polynomial optimization problem, which also turns out to be convex in some cases. We experimentally validate the method on an autonomous helicopter testbed using a 10-dimensional helicopter model.

Yi Guo, Kyri Baker, Emiliano Dall'Anese et al.

This is the second part of a two-part paper on data-based distributionally robust stochastic optimal power flow (OPF). The general problem formulation and methodology have been presented in Part I [1]. Here, we present extensive numerical experiments in both distribution and transmission networks to illustrate the effectiveness and flexibility of the proposed methodology for balancing efficiency, constraint violation risk, and out-of-sample performance. On the distribution side, the method mitigates overvoltages due to high photovoltaic penetration using local energy storage devices. On the transmission side, the method reduces N-1 security line flow constraint risks due to high wind penetration using reserve policies for controllable generators. In both cases, the data-based distributionally robust model predictive control (MPC) algorithm explicitly utilizes forecast error training datasets, which can be updated online. The numerical results illustrate inherent tradeoffs between the operational costs, risks of constraints violations, and out-of-sample performance, offering systematic techniques for system operators to balance these objectives.

Shilin You, Gael Luna, Tyler H. Summers

We present a framework for planning trajectories that avoid obstacles and satisfy logical precedence constraints expressed with a fragment of signal temporal logic (STL). Our approach models environments containing obstacles, keys, and doors, where collecting a key unlocks its associated door and potentially opens shorter paths to a goal. Based on an exact convex partitioning of the free space that encodes connectivity among convex free space, key, and door regions, we construct an augmented graph of convex sets (GCS) whose layered structure exactly encodes the key-door precedence logic. A shortest path in the augmented GCS simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution up to a finite Bézier curve parameterization.

Yi Guo, Tyler H. Summers

Traditional synchronous generators with rotational inertia are being replaced by low-inertia renewable energy resources (RESs) in many power grids and operational scenarios. Due to emerging market mechanisms, inherent variability of RESs, and existing control schemes, the resulting system inertia levels can not only be low but also markedly time-varying. In this paper, we investigate performance and stability of low-inertia power systems with stochastic system inertia. In particular, we consider system dynamics modelled by a linearized stochastic swing equation, where stochastic system inertia is regarded as multiplicative noise. The $\mathcal{H}_2$ norm is used to quantify the performance of the system in the presence of persistent disturbances or transient faults. The performance metric can be computed by solving a generalized Lyapunov equation, which has fundamentally different characteristics from systems with only additive noise. For grids with uniform inertia and damping parameters, we derive closed-form expressions for the $\mathcal{H}_2$ norm of the proposed stochastic swing equation. The analysis gives insights into how the $\mathcal{H}_2$ norm of the stochastic swing equation depends on 1) network topology; 2) system parameters; and 3) distribution parameters of disturbances. A mean-square stability condition is also derived. Numerical results provide additional insights for performance and stability of the stochastic swing equation.

Sebastian A. Nugroho, Ahmad F. Taha, Nikolaos Gatsis et al.

The problem of placing or selecting sensors and control nodes plays a pivotal role in the operation of dynamic networks. This paper proposes optimal algorithms and heuristics to solve the simultaneous sensor and actuator selection problem in linear dynamic networks. In particular, a sufficiency condition of static output feedback stabilizability is used to obtain the minimal set of sensors and control nodes needed to stabilize an unstable network. We show the joint sensor/actuator selection and output feedback control can be written as a mixed-integer nonconvex problem. To solve this nonconvex combinatorial problem, three methods based on (1) mixed-integer nonlinear programming, (2) binary search algorithms, and (3) simple heuristics are proposed. The first method yields optimal solutions to the selection problem---given that some constants are appropriately selected. The second method requires a database of binary sensor/actuator combinations, returns optimal solutions, and necessitates no tuning parameters. The third approach is a heuristic that yields suboptimal solutions but is computationally attractive. The theoretical properties of these methods are discussed and numerical tests on dynamic networks showcase the trade-off between optimality and computational time.

Sleiman Safaoui, Benjamin J. Gravell, Venkatraman Renganathan et al.

We propose a two-phase risk-averse architecture for controlling stochastic nonlinear robotic systems. We present Risk-Averse Nonlinear Steering RRT* (RANS-RRT*) as an RRT* variant that incorporates nonlinear dynamics by solving a nonlinear program (NLP) and accounts for risk by approximating the state distribution and performing a distributionally robust (DR) collision check to promote safe planning. The generated plan is used as a reference for a low-level tracking controller. We demonstrate three controllers: finite horizon linear quadratic regulator (LQR) with linearized dynamics around the reference trajectory, LQR with robustness-promoting multiplicative noise terms, and a nonlinear model predictive control law (NMPC). We demonstrate the effectiveness of our algorithm using unicycle dynamics under heavy-tailed Laplace process noise in a cluttered environment.

Kaveh Fathian, Sleiman Safaoui, Tyler H. Summers et al.

We present a distributed control strategy for a team of quadrotors to autonomously achieve a desired 3D formation. Our approach is based on local relative position measurements and does not require global position information or inter-vehicle communication. We assume that quadrotors have a common sense of direction, which is chosen as the direction of gravitational force measured by their onboard IMU sensors. However, this assumption is not crucial, and our approach is robust to inaccuracies and effects of acceleration on gravitational measurements. In particular, converge to the desired formation is unaffected if each quadrotor has a velocity vector that projects positively onto the desired velocity vector provided by the formation control strategy. We demonstrate the validity of proposed approach in an experimental setup and show that a team of quadrotors achieve a desired 3D formation.

Kaveh Fathian, Sleiman Safaoui, Tyler H. Summers et al.

We present a distributed formation control strategy for agents with a variety of dynamics to achieve a desired planar formation. Our approach is based on the barycentric-coordinate-based (BCB) control, which is fully distributed, does not require inter-agent communication or a common sense of orientation, and can be implemented using relative position measurements acquired by agents in their local coordinate frames. This removes the need for global positioning or alignment of local coordinate frames, which are required across several existing strategies. We show how the BCB control for agents with the simplest dynamical model, i.e., the single-integrator dynamics, can be extended to agents with higher-order dynamics such as quadrotors, and nonholonomic agents such as unicycles and cars. Specifically, our extension preserves the desired convergence and robustness guarantees of the BCB approach and is provably robust to saturations in the input and unmodeled linear actuator dynamics for unicycle and car agents. We further show that under our proposed BCB control design, the agents can move along a rotated and scaled control direction without affecting the convergence to the desired formation. This observation is used to design a fully distributed collision avoidance strategy, which is often not considered in the formation control literature. We demonstrate the proposed approach in simulations and further present a distributed robotic platform to test the strategy experimentally. Our experimental platform consists of off-the-shelf equipment that can be used to test and validate other multi-agent algorithms. The code and implementation instructions for this platform are available online.

Nikolaos Kariotoglou, Maryam Kamgarpour, Tyler H. Summers et al.

We consider finite horizon reach-avoid problems for discrete time stochastic systems. Our goal is to construct upper bound functions for the reach-avoid probability by means of tractable convex optimization problems. We achieve this by restricting attention to the span of Gaussian radial basis functions and imposing structural assumptions on the transition kernel of the stochastic processes as well as the target and safe sets of the reach-avoid problem. In particular, we require the kernel to be written as a Gaussian mixture density with each mean of the distribution being affine in the current state and input and the target and safe sets to be written as intersections of quadratic inequalities. Taking advantage of these structural assumptions, we formulate a recursion of semidefinite programs where each step provides an upper bound to the value function of the reach- avoid problem. The upper bounds provide a performance metric to which any suboptimal control policy can be compared, and can themselves be used to construct suboptimal control policies. We illustrate via numerical examples that even if the resulting bounds are conservative, the associated control policies achieve higher reach-avoid probabilities than heuristic controllers for problems of large state-input space dimensions (more than 20). The results presented in this paper, far exceed the limits of current approximation methods for reach-avoid problems in the specific class of stochastic systems considered.