Flocking in Fixed and Switching Networks

This note analyzes the stability properties of a group of mobile agents that align their velocity vectors, and stabilize their inter-agent distances, using decentralized, nearest-neighbor interaction rules, exchanging information over networks that change arbitrarily (no dwell time between consecutive switches). These changes introduce discontinuities in the agent control laws. To accommodate for arbitrary switching in the topology of the network of agent interactions we employ nonsmooth analysis. The main result is that regardless of switching, convergence to a common velocity vector and stabilization of inter-agent distances is still guaranteed as long as the network remains connected at all times     

Density Functions for Navigation-Function-Based Systems

In this paper, we present a scheme for constructing density functions for systems that are almost globally asymptotically stable (i.e., systems for which all trajectories converge to an equilibrium except for a set of measure zero) using navigation functions (NFs). Although recently-proven converse theorems guarantee the existence of density functions for such systems, such results are only existential and the construction of a density function for almost globally asymptotically stable systems remains a challenging task. We show that for a specific class of dynamical systems that are defined based on an NF, a density function can be easily derived from the system's underlying NF.     

Input-to-state stable finite horizon MPC for neutrally stable linear discrete-time systems with input constraints

MPC or model predictive control is representative of control methods which are able to handle inequality constraints. Closed-loop stability can therefore be ensured only locally in the presence of constraints of this type. However, if the system is neutrally stable, and if the constraints are imposed only on the input, global asymptotic stability can be obtained; until recently, use of infinite horizons was thought to be inevitable in this case. A globally stabilizing finite-horizon MPC has lately been suggested for neutrally stable continuous-time systems using a non-quadratic terminal cost which consists of cubic as well as quadratic functions of the state. The idea originates from the so-called small gain control, where the global stability is proven using a non-quadratic Lyapunov function. The newly developed finite-horizon MPC employs the same form of Lyapunov function as the terminal cost, thereby leading to global asymptotic stability. A discrete-time version of this finite-horizon MPC is presented here. Furthermore, it is proved that the closed-loop system resulting from the proposed MPC is ISS (Input-to-State Stable), provided that the external disturbance is sufficiently small. The proposed MPC algorithm is also coded using an SQP (Sequential Quadratic Programming) algorithm, and simulation results are given to show the effectiveness of the method.     

Robust non-fragile LQ controllers: The static state feedback case

This paper describes the synthesis of non-fragile or resilient regulators for linear systems. A general framework for fragility is described using state-space methodologies, and the LQ/H₂ static state-feedback problem is examined in detail. We discuss the multiplicative structured uncertainties case, and propose remedies of the fragility problem using an optimization programming framework via matrix inequalities. A special case that leads to a convex optimization framework via linear matrix inequalities (LMIs) will be considered. The benchmark problem is taken as an example to show how special controller gain variations can affect the performance of the closed-loop system.     

Unconstrained receding-horizon control of nonlinear systems

It is well known that unconstrained infinite-horizon optimal control may be used to construct a stabilizing controller for a nonlinear system. We show that similar stabilization results may be achieved using unconstrained finite horizon optimal control. The key idea is to approximate the tail of the infinite horizon cost-to-go using, as terminal cost, an appropriate control Lyapunov function. Roughly speaking, the terminal control Lyapunov function (CLF) should provide an (incremental) upper bound on the cost. In this fashion, important stability characteristics may be retained without the use of terminal constraints such as those employed by a number of other researchers. The absence of constraints allows a significant speedup in computation. Furthermore, it is shown that in order to guarantee stability, it suffices to satisfy an improvement property, thereby relaxing the requirement that truly optimal trajectories be found. We provide a complete analysis of the stability and region of attraction/operation properties of receding horizon control strategies that utilize finite horizon approximations in the proposed class. It is shown that the guaranteed region of operation contains that of the CLF controller and may be made as large as desired by increasing the optimization horizon (restricted, of course, to the infinite horizon domain). Moreover, it is easily seen that both CLF and infinite-horizon optimal control approaches are limiting cases of our receding horizon strategy. The key results are illustrated using a familiar example, the inverted pendulum, where significant improvements in guaranteed region of operation and cost are noted     

Distributed Multi-Parametric Quadratic Programming

One of the fundamental problems in the area of large-scale optimization is to study locality features of spatially distributed optimization problems in which the variables are coupled in the cost function as well as constraints. Such problems can motivate the development of fast and well-conditioned distributed algorithms. In this paper, we study spatial locality features of large-scale multi-parametric quadratic programming (MPQP) problems with linear inequality constraints. Our main application focus is receding horizon control of spatially distributed linear systems with input and state constraints. We propose a new approach for analysis of large-scale MPQP problems by blending tools from duality theory with operator theory. The class of spatially decaying matrices is introduced to capture couplings between optimization variables in the cost function and the constraints. We show that the optimal solution of a convex MPQP is piecewise affine- represented as convolution sums. More importantly, we prove that the kernel of each convolution sum decays in the spatial domain at a rate proportional to the inverse of the corresponding coupling function of the optimization problem.     

A Framework for Worst-Case and Stochastic Safety Verification Using Barrier Certificates

This paper presents a methodology for safety verification of continuous and hybrid systems in the worst-case and stochastic settings. In the worst-case setting, a function of state termed barrier certificate is used to certify that all trajectories of the system starting from a given initial set do not enter an unsafe region. No explicit computation of reachable sets is required in the construction of barrier certificates, which makes it possible to handle nonlinearity, uncertainty, and constraints directly within this framework. In the stochastic setting, our method computes an upper bound on the probability that a trajectory of the system reaches the unsafe set, a bound whose validity is proven by the existence of a barrier certificate. For polynomial systems, barrier certificates can be constructed using convex optimization, and hence the method is computationally tractable. Some examples are provided to illustrate the use of the method.     

Coordination of groups of mobile autonomous agents using nearest neighbor rules

In a recent Physical Review Letters article, Vicsek et al. propose a simple but compelling discrete-time model of n autonomous agents (i.e., points or particles) all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors." In their paper, Vicsek et al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.     

On the stability of receding horizon control with a general terminal cost

We study the stability and region of attraction properties of a family of receding horizon schemes for nonlinear systems. Using Dini's theorem on the uniform convergence of functions, we show that there is always a finite horizon for which the corresponding receding horizon scheme is stabilizing without the use of a terminal cost or terminal constraints. After showing that optimal infinite horizon trajectories possess a uniform convergence property, we show that exponential stability may also be obtained with a sufficient horizon when an upper bound on the infinite horizon cost is used as terminal cost. Combining these important cases together with a sandwiching argument, we are able to conclude that exponential stability is obtained for input-constrained receding horizon schemes with a general nonnegative terminal cost for sufficiently long horizons. Region of attraction estimates are also included in each of the results.     

A Necessary and Sufficient Condition for Consensus Over Random Networks

We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1.