Research Projects

My research centers around the design and analysis of algorithms that facilitate our understanding and ability to influence the behavior of network systems. I design algorithms that make use of network structure and the local interactions between components in order to predict, control, and guarantee of the safe and reliable operation of the aggregate system in a distributed way that requires no centralized coordination.

Spatially distributed models are fundamental to the study of complex systems. Diffusively coupled networks, in which different components of a network adjust their behavior according to the local differences between themselves and their neighbors, are a ubiquitous class of spatially-distributed models. Employing the tools of convex optimization, nonlinear dynamical systems theory, machine learning, and numerical computation allows us to characterize and control network systems in a variety of contexts, including multi-aircraft formation control, microelectronics, cellular reaction-diffusion networks, and social networks.

Adaptive synchronization in networks

Clustered graph 

We develop adaptive algorithms that guarantee synchronization in diffusively coupled systems. The algorithms are particularly suited to networks which evolve in time in addition to the individual components of the network. We demonstrate applications to vehicular path following and oscillator synchronization. We also highlight how the algorithms aids in the identification of bottlenecks and clusters in networks. We consider both spatially-discrete systems governed by compartmental systems of ODEs, where each compartment represents a spatial domain of components interconnected through diffusion terms with like components in different compartments, and reaction-diffusion PDEs with spatio-temporally varying diffusion coefficients.

Our approach is well-suited to several applications. For example, it can be used as an efficient distributed way to determine community structure in dynamic networks. Another potential application is image segmentation through identification of clusters in the graph structure underlying the image. Our approach can furthermore be applied to multi-vehicle synchronized path following and oscillator clock locking in electro-mechanical circuits, among other cooperative control problems.

References

S. Y. Shafi and M. Arcak. An adaptive algorithm for synchronization in diffusively-coupled systems, under review, 2013.

Synchronization of diffusively coupled limit cycle oscillators

Destabilized Oscillations 

We develop analytical and numerical conditions to determine whether limit cycle oscillations synchronize in diffusively coupled systems. We examine two classes of systems: reaction-diffusion PDEs with Neumann boundary conditions, and compartmental ODEs, where compartments are interconnected through diffusion terms with adjacent compartments. In both cases the uncoupled dynamics are governed by a nonlinear system that admits an asymptotically stable limit cycle. We provide two-time scale averaging methods for certifying stability of spatially homogeneous time-periodic trajectories in the presence of sufficiently small or large diffusion, and develop methods using the structured singular value for the case of intermediate diffusion. We highlight cases where diffusion stabilizes or destabilizes such trajectories.

References

S. Y. Shafi, M. Arcak, M. Jovanovic, and A. Packard. Synchronization of diffusively coupled limit cycle oscillators, Accepted, Automatica, 2013.

S. Y. Shafi, M. Arcak, and M. Jovanovic. “Synchronization of limit cycle oscillations in diffusively-coupled systems,” in Proc. American Control Conference, 2013.

Spatial uniformity in diffusively-coupled systems using weighted L_2 norm contractions

Ring Oscillator 

We present conditions that guarantee spatial uniformity in diffusively-coupled systems. Diffusive coupling is a ubiquitous form of local interaction, arising in diverse areas including multiagent coordination and pattern formation in biochemical networks. The conditions we derive make use of the Jacobian matrix and Neumann eigenvalues of elliptic operators, and generalize and unify existing theory about asymptotic convergence of trajectories of reaction-diffusion partial differential equations as well as compartmental ordinary differential equations. We present numerical tests making use of linear matrix inequalities that may be used to certify these conditions. We discuss an example pertaining to electromechanical oscillators. The paper's main contributions are unified verifiable relaxed conditions that guarantee synchrony.

References

S. Y. Shafi*, Z. Aminzare*, M. Arcak, and E. Sontag. “Weighted L_2 norm contractions in diffusively-coupled systems,” SIAM Conference on Control Theory and its Applications, 2013. (*The first two authors contributed equally.)

S. Y. Shafi*, Z. Aminzare*, M. Arcak, and E. Sontag. “Spatial uniformity in diffusively-coupled systems using weighted L_2 norm contractions,” in Proc. American Control Conference, 2013. (*The first two authors contributed equally.)

Z. Aminzare*, S. Y. Shafi*, M. Arcak, and E. Sontag. Guaranteeing spatial uniformity in reaction-diffusion systems using weighted L_2 norm contractions, To appear, System Theoretic Approaches to Systems and Synthetic Biology, 2013. (*The first two authors contributed equally.)

S. Y. Shafi. Guaranteeing spatial uniformity in diffusively-coupled systems, preprint on arXiv, 2012.

Distributed Control of Multiagent Systems

Planes 

We consider the problem of network optimization for cooperative control of multiagent (aircraft) systems. The systems consist of homogeneous plants with a network of feedback interconnections. We assume that the plant dynamics are stabilizable by local state feedback, and we want the agents to converge quickly to formation. However, it is often the case that the interconnection network introduces or magnifies undesirable properties such as high-gain feedback instability. We seek to eliminate or mitigate these problems by applying node and edge weighting to the interconnection structures.

We derive convex optimization problems to solve graph design problems that improve the stability properties of multiagent systems. Our method leads to measurable improvements in vehicle strings and planar vertical takeoff and landing aircraft. Furthermore, our approach identifies weak points in a network, and aids in developing strategies to enhance resiliency of the network. Finally, our method is related to the problem of spectral clustering in graphs, and we may formulate optimization problems to either accentuate or de-emphasize the effects of clusters in overall system dynamics.

References

S. Y. Shafi, M. Arcak, and L. El Ghaoui, Graph weight allocation to meet Laplacian spectral constraints, in IEEE Transactions on Automatic Control, 2012.

S. Y. Shafi, M. Arcak, and L. El Ghaoui, “Graph weight design for Laplacian eigenvalue constraints with multi-agent systems applications,” in Proc. Conference on Decision and Control, 2011.

S. Y. Shafi, M. Arcak, and L. El Ghaoui, “Designing node and edge weights of a graph to meet laplacian eigenvalue constraints,” in Proc. Allerton Conference, 2010.

Selected Course Projects

Distributed Approaches to Cooperative and Non-Cooperative Network Resource Sharing Problems using Simultaneous Primal-Dual Descent

We study network resource sharing problems. The aim of this project is twofold, and spans distributed optimization and game theory. First, it generalizes the network utility maximization problem to arbitrary inequality-constrained convex sets, and addresses the situation where individual agent costs are directly affected by the actions of others. We assume that the system objective is to minimize the sum of the individual loss functions. Each agent solves a decoupled problem to determine its resource use given the prices determined by the network. We show that the problem can be decomposed and expressed as continuous-time dynamical subsystems that share a common input-output structure. We show how the input output structure can be exploited using Lyapunov stability theory to prove asymptotic convergence to the equilibrium under use of primal-dual gradient descent methods. Our approach is similar to the classical Arrow-Hurwicz-Uzawa algorithm for resource allocation using saddle point formulations.

Numerical Schemes from the Perspective of Consensus: Exploring Connections between Agreement Problems and PDEs

We examine the connections between the modeling and control of partial differential equations and distributed control. In particular, the discussion focuses on parabolic and elliptic partial differential equations, which can be characterized from the point of view of graph theory. For example, when the Laplace operator is discretized over a spatial domain subject to certain boundary conditions, the resulting discrete operator can be analyzed through the lens of spectral graph theory. The structure and spectrum of the discretized graph Laplacian matrix can be used to characterize behavior of the continuous PDE such as synchronization and consensus as well as stability.