BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Francesco Bullo

Francesco Bullo appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and Controleess.SYmath.DSRoboticsMultiagent SystemsSocial and Information Networksmath-phmath.MPMachine LearningArtificial Intelligencephysics.soc-phApplicationsComputer Science and Game TheoryData Structures and AlgorithmsDistributed, Parallel, and Cluster Computingecon.THHuman-Computer Interactionmath.COmath.PRmath.STnlin.AOnlin.CDphysics.data-anQuantitative MethodsStatistics Theory

Catalog footprint

What is connected

60works
26topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

60 published item(s)

preprint2026arXiv

Sampled-data Systems: Stability, Contractivity and Single-iteration Suboptimal MPC

This paper analyzes the stability of interconnected continuous-time (CT) and discrete-time (DT) systems coupled through sampling and zero-order hold mechanisms. The DT system updates its output at regular intervals $T>0$ by applying an $n$-fold composition of a given map. This setup is motivated by online and sampled-data implementations of optimization-based controllers - particularly model predictive control (MPC) - where the DT system models $n$ iterations of an algorithm approximating the solution of an optimization problem. We introduce the concept of a reduced model, defined as the limiting behavior of the sampled-data system as $T \to 0^+$ and $n \to +\infty$. Our main theoretical contribution establishes that when the reduced model is contractive, there exists a threshold duration $T(n)$ for each iteration count $n$ such that the CT-DT interconnection achieves exponential stability for all sampling periods $T < T(n)$. Finally, under the stronger condition that both the CT and DT systems are contractive, we show exponential stability of their interconnection using a small-gain argument. Our theoretical results provide new insights into suboptimal MPC stability, showing that convergence guarantees hold even when using a single iteration of the optimization algorithm - a practically significant finding for real-time control applications.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows

Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated optimization problem. Such a design approach poses an important problem: how to find a principled methodology to design and discretize appropriate ODEs. This paper aims to provide a solution to this problem through the use of contraction theory. We first introduce general mathematical results that explain how contraction theory guarantees the stability of the implicit and explicit Euler integration methods. Then, we propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow, and use contraction theory to establish it is an optimization flow with exponential convergence rate, from which the linear convergence rate of its associated optimization algorithm is immediately established. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method. Finally, we present how our approach leads to performance guarantees in the design of optimization algorithms for time-varying optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks

We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs). INNs are a class of implicit learning models that use implicit equations as layers and have been shown to exhibit several notable benefits over traditional deep neural networks. We first establish that tight inclusion functions of neural networks, which provide the tightest rectangular over-approximation of an input-output map, lead to sharper robustness guarantees than the well-studied robustness measures of local Lipschitz constants. Like Lipschitz constants, tight inclusions functions are computationally challenging to obtain, and we thus propose using mixed monotonicity and contraction theory to obtain computationally efficient estimates of tight inclusion functions for INNs. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs. We design a novel optimization problem for training robust INNs and we provide empirical evidence that suitably-trained INNs can be more robust than comparably-trained feedforward networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Convex Optimization of the Basic Reproduction Number

The basic reproduction number $R_0$ is a fundamental quantity in epidemiological modeling, reflecting the typical number of secondary infections that arise from a single infected individual. While $R_0$ is widely known to scientists, policymakers, and the general public, it has received comparatively little attention in the controls community. This note provides two novel characterizations of $R_0$: a stability characterization and a geometric program characterization. The geometric program characterization allows us to write $R_0$-constrained and budget-constrained optimal resource allocation problems as geometric programs, which are easily transformed into convex optimization problems. We apply these programs to allocating vaccines and antidotes in numerical examples, finding that targeting $R_0$ instead of the spectral abscissa of the Jacobian matrix (a common target in the controls literature) leads to qualitatively different solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Data-driven Self-triggered Control via Trajectory Prediction

Self-triggered control, a well-documented technique for reducing the communication overhead while ensuring desired system performance, is gaining increasing popularity. However, existing methods for self-triggered control require explicit system models that are assumed perfectly known a priori. An end-to-end control paradigm known as data-driven control learns control laws directly from data, and offers a competing alternative to the routine system identification-then-control method. In this context, the present paper puts forth data-driven self-triggered control schemes for unknown linear systems using data collected offline. Specifically, for output feedback control systems, a data-driven model predictive control (MPC) scheme is proposed, which computes a sequence of control inputs while generating a predicted system trajectory. A data-driven self-triggering law is designed using the predicted trajectory, to determine the next triggering time once a new measurement becomes available. For state feedback control systems, instead of capitalizing on MPC to predict the trajectory, a data-fitting problem using the pre-collected input-state data is solved, whose solution is employed to construct the self-triggering mechanism. Both feasibility and stability are established for the proposed self-triggered controllers, which are validated using numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Wasserstein Barycenters via Displacement Interpolation

Consider a multi-agent system whereby each agent has an initial probability measure. In this paper, we propose a distributed algorithm based upon stochastic, asynchronous and pairwise exchange of information and displacement interpolation in the Wasserstein space. We characterize the evolution of this algorithm and prove it computes the Wasserstein barycenter of the initial measures under various conditions. One version of the algorithm computes a standard Wasserstein barycenter, i.e., a barycenter based upon equal weights; and the other version computes a randomized Wasserstein barycenter, i.e., a barycenter based upon random weights for the initial measures. Finally, we specialize our algorithm to Gaussian distributions and draw a connection with the modeling of opinion dynamics in mathematical sociology.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimax Flow over Acyclic Networks: Distributed Algorithms and Microgrid Application

Given a flow network with variable suppliers and fixed consumers, the minimax flow problem consists in minimizing the maximum flow between nodes, subject to flow conservation and capacity constraints. We solve this problem over acyclic graphs in a distributed manner by showing that it can be recast as a consensus problem between the maximum downstream flows, which we define here for the first time. Additionally, we present a distributed algorithm to estimate these quantities. Finally, exploiting our theoretical results, we design an online distributed controller to prevent overcurrent in microgrids consisting of loads and droop-controlled inverters. Our results are validated numerically on the CIGRE benchmark microgrid.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimum effort decentralized control design for contracting network systems

We consider the problem of making a networked system contracting by designing minimal effort local controllers. Our method combines a hierarchical contraction characterization and a matrix-balancing approach to stabilizing a Metzler matrix via minimal diagonal perturbations. We demonstrate our approach by designing local controllers that render contractive a network of FitzHugh-Nagumo neurons with a general topology of interactions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Modeling Human-AI Team Decision Making

AI and humans bring complementary skills to group deliberations. Modeling this group decision making is especially challenging when the deliberations include an element of risk and an exploration-exploitation process of appraising the capabilities of the human and AI agents. To investigate this question, we presented a sequence of intellective issues to a set of human groups aided by imperfect AI agents. A group's goal was to appraise the relative expertise of the group's members and its available AI agents, evaluate the risks associated with different actions, and maximize the overall reward by reaching consensus. We propose and empirically validate models of human-AI team decision making under such uncertain circumstances, and show the value of socio-cognitive constructs of prospect theory, influence dynamics, and Bayesian learning in predicting the behavior of human-AI groups.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multistability and anomalies in oscillator models of lossy power grids

The analysis of dissipatively coupled oscillators is challenging and highly relevant in power grids. Standard mathematical methods are not applicable, due to the lack of network symmetry induced by dissipative couplings. Here we demonstrate a close correspondence between stable synchronous states in dissipatively coupled oscillators, and the {winding partition} of their state space, a geometric notion induced by the network topology. Leveraging this winding partition, we accompany this article with an algorithms to compute all synchronous solutions of complex networks of dissipatively coupled oscillators. These geometric and computational tools allow us to identify anomalous behaviors of lossy networked systems. Counterintuitively, we show that loop flows and dissipation can increase the system's transfer capacity, and that dissipation can promote multistability. We apply our geometric framework to compute power flows on the IEEE RTS-96 test system, where we identify two high voltage solutions with distinct loop flows.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Non-Euclidean Contraction Theory for Monotone and Positive Systems

In this note we study contractivity of monotone systems and exponential convergence of positive systems using non-Euclidean norms. We first introduce the notion of conic matrix measure as a framework to study stability of monotone and positive systems. We study properties of the conic matrix measures and investigate their connection with weak pairings and standard matrix measures. Using conic matrix measures and weak pairings, we characterize contractivity and incremental stability of monotone systems with respect to non-Euclidean norms. Moreover, we use conic matrix measures to provide sufficient conditions for exponential convergence of positive systems to their equilibria. We show that our framework leads to novel results on (i) the contractivity of excitatory Hopfield neural networks, and (ii) the stability of interconnected systems using non-monotone positive comparison systems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Non-Euclidean Contraction Theory for Robust Nonlinear Stability

We study necessary and sufficient conditions for contraction and incremental stability of dynamical systems with respect to non-Euclidean norms. First, we introduce weak pairings as a framework to study contractivity with respect to arbitrary norms, and characterize their properties. We introduce and study the sign and max pairings for the $\ell_1$ and $\ell_\infty$ norms, respectively. Using weak pairings, we establish five equivalent characterizations for contraction, including the one-sided Lipschitz condition for the vector field as well as matrix measure and Demidovich conditions for the corresponding Jacobian. Third, we extend our contraction framework in two directions: we prove equivalences for contraction of continuous vector fields and we formalize the weaker notion of equilibrium contraction, which ensures exponential convergence to an equilibrium. Finally, as an application, we provide (i) incremental input-to-state stability and finite input-state gain properties for contracting systems, and (ii) a general theorem about the Lipschitz interconnection of contracting systems, whereby the Hurwitzness of a gain matrix implies the contractivity of the interconnected system.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robust Implicit Networks via Non-Euclidean Contractions

Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability. This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_{\infty}$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_{\infty}$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code is available at https://github.com/davydovalexander/Non-Euclidean_Mon_Op_Net.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach

This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks based upon non-Euclidean contraction theory. The basic idea is to cast the robustness analysis of a neural network as a reachability problem and use (i) the $\ell_{\infty}$-norm input-output Lipschitz constant and (ii) the tight inclusion function of the network to over-approximate its reachable sets. First, for a given implicit neural network, we use $\ell_{\infty}$-matrix measures to propose sufficient conditions for its well-posedness, design an iterative algorithm to compute its fixed points, and provide upper bounds for its $\ell_\infty$-norm input-output Lipschitz constant. Second, we introduce a related embedded network and show that the embedded network can be used to provide an $\ell_\infty$-norm box over-approximation of the reachable sets of the original network. Moreover, we use the embedded network to design an iterative algorithm for computing the upper bounds of the original system's tight inclusion function. Third, we use the upper bounds of the Lipschitz constants and the upper bounds of the tight inclusion functions to design two algorithms for the training and robustness verification of implicit neural networks. Finally, we apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Verifying $k$-Contraction without Computing $k$-Compounds

Compound matrices have found applications in many fields of science including systems and control theory. In particular, a sufficient condition for $k$-contraction is that a logarithmic norm (also called matrix measure) of the $k$-additive compound of the Jacobian is uniformly negative. However, this may be difficult to check in practice because the $k$-additive compound of an $n\times n$ matrix has dimensions $\binom{n}{k}\times \binom{n}{k}$. For an $n\times n$ matrix $A$, we prove a duality relation between the $k$ and $(n-k)$ compounds of $A$. We use this duality relation to derive a sufficient condition for $k$-contraction that does not require the computation of any $k$-compounds. We demonstrate our results by deriving a sufficient condition for $k$-contraction of an $n$-dimensional Hopfield network that does not require to compute any compounds. In particular, for $k=2$ this sufficient condition implies that the network is $2$-contracting and this implies a strong asymptotic property: every bounded solution of the network converges to an equilibrium point, that may not be unique. This is relevant, for example, when using the Hopfield network as an associative memory that stores patterns as equilibrium points of the dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

From Contraction Theory to Fixed Point Algorithms on Riemannian and Non-Euclidean Spaces

The design of fixed point algorithms is at the heart of monotone operator theory, convex analysis, and of many modern optimization problems arising in machine learning and control. This tutorial reviews recent advances in understanding the relationship between Demidovich conditions, one-sided Lipschitz conditions, and contractivity theorems. We review the standard contraction theory on Euclidean spaces as well as little-known results for Riemannian manifolds. Special emphasis is placed on the setting of non-Euclidean norms and the recently introduced weak pairings for the $\ell_1$ and $\ell_\infty$ norms. We highlight recent results on explicit and implicit fixed point schemes for non-Euclidean contracting systems.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Resilient Control under Quantization and Denial-of-Service: Co-designing a Deadbeat Controller and Transmission Protocol

This paper is concerned with the problem of stabilizing continuous-time linear time-invariant systems subject to quantization and Denial-of-Service (DoS) attacks. In this context, two DoS-induced challenges emerge with the design of resilient encoding schemes, namely, the coupling between encoding strategies of different signals, and the synchronization between the encoder and decoder. To address these challenges, a novel structure that is equipped with a deadbeat controller as well as a delicate transmission protocol for the input and output channels, co-designed leveraging the controllability index, is put forward. When both input and output channels are subject to DoS attacks and quantization, the proposed structure is shown able to decouple the encoding schemes for input, output, and estimated output signals. This property is further corroborated by designing encoding schemes as well as conditions that ensure exponential stability of the closed-loop system. On the other hand, when only the output channel is subject to network phenomenon, the proposed structure can achieve exponential stabilization without acknowledgment (ACK) signals, in contrast to existing ACK-based results. Finally, a numerical example is given to demonstrate the practical merits of the proposed approach as well as the theory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Assign and Appraise: Achieving Optimal Performance in Collaborative Teams

Tackling complex team problems requires understanding each team member's skills in order to devise a task assignment maximizing the team performance. This paper proposes a novel quantitative model describing the decentralized process by which individuals in a team learn who has what abilities, while concurrently assigning tasks to each of the team members. In the model, the appraisal network represents team member's evaluations of one another and each team member chooses their own workload. The appraisals and workload assignment change simultaneously: each member builds their own local appraisal of neighboring members based on the performance exhibited on previous tasks, while the workload is redistributed based on the current appraisal estimates. We show that the appraisal states can be reduced to a lower dimension due to the presence of conserved quantities associated to the cycles of the appraisal network. Building on this, we provide rigorous results characterizing the ability, or inability, of the team to learn each other's skill and thus converge to an allocation maximizing the team performance. We complement our analysis with extensive numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Flow and Elastic Networks on the $n$-torus: Geometry, Analysis, and Computation

Networks with phase-valued nodal variables are central in modeling several important societal and physical systems, including power grids, biological systems, and coupled oscillator networks. One of the distinctive features of phase-valued networks is the existence of multiple operating conditions corresponding to critical points of an energy function or feasible flows of a balance equation. For networks with phase-valued states, it is not yet fully understood how many operating conditions exist, how to characterize them, and how to compute them efficiently. A deeper understanding of feasible operating conditions, including their dependence upon network structures, may lead to more reliable and efficient network systems. This paper introduces flow and elastic network problems on the $n$-torus and provides a rigorous and comprehensive framework for their study. Based on a monotonicity assumption, this framework localizes the solutions, bounds their number, and leads to an algorithm to compute them. Our analysis is based on a novel winding partition of the $n$-torus into winding cells, induced by Kirchhoff's angle law for undirected graphs. The winding partition has several useful properties, including notably that, each winding cell contains at most one solution. The proposed algorithm is based on a novel contraction mapping and is guaranteed to compute all solutions. Finally, we apply our results to numerically study the active power flow equations in several test cases and estimate power capacity and congestion of a power network.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph-Theoretic Stability Conditions for Metzler Matrices and Monotone Systems

This paper studies the graph-theoretic conditions for stability of positive monotone systems. Using concepts from input-to-state stability and network small-gain theory, we first establish necessary and sufficient conditions for the stability of linear positive systems described by Metzler matrices. Specifically, we derive two sets of stability conditions based on two forms of input-to-state stability gains for Metzler systems, namely max-interconnection gains and sum-interconnection gains. Based on the max-interconnection gains, we show that the cyclic small-gain theorem becomes necessary and sufficient for the stability of Metzler systems; based on the sum-interconnection gains, we obtain novel graph-theoretic conditions for the stability of Metzler systems. All these conditions highlight the role of cycles in the interconnection graph and unveil how the structural properties of the graph affect stability. Finally, we extend our results to the nonlinear monotone system and obtain similar sufficient conditions for global asymptotic stability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

LaSalle Invariance Principle for Discrete-time Dynamical Systems: A Concise and Self-contained Tutorial

LaSalle invariance principle was originally proposed in the 1950's and has become a fundamental mathematical tool in the area of dynamical systems and control. In both theoretical research and engineering practice, discrete-time dynamical systems have been at least as extensively studied as continuous-time systems. For example, model predictive control is typically studied in discrete-time via Lyapunov methods. However, there is a peculiar absence in the standard literature of standard treatments of Lyapunov functions and LaSalle invariance principle for discrete-time nonlinear systems. Most of the textbooks on nonlinear dynamical systems focus only on continuous-time systems. In Chapter 1 of the book by LaSalle [11], the author establishes the LaSalle invariance principle for difference equation systems. However, all the useful lemmas in [11] are given in the form of exercises with no proof provided. In this document, we provide the proofs of all the lemmas proposed in [11] that are needed to derive the main theorem on the LaSalle invariance principle for discrete-time dynamical systems. We organize all the materials in a self-contained manner. We first introduce some basic concepts and definitions in Section 1, such as dynamical systems, invariant sets, and limit sets. In Section 2 we present and prove some useful lemmas on the properties of invariant sets and limit sets. Finally, we establish the original LaSalle invariance principle for discrete-time dynamical systems and a simple extension in Section~3. In Section 4, we provide some references on extensions of LaSalle invariance principles for further reading. This document is intended for educational and tutorial purposes and contains lemmas that might be useful as a reference for researchers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Markov Chain-Based Stochastic Strategies for Robotic Surveillance

This article surveys recent advancements of strategy designs for persistent robotic surveillance tasks with the focus on stochastic approaches. The problem describes how mobile robots stochastically patrol a graph in an efficient way where the efficiency is defined with respect to relevant underlying performance metrics. We first start by reviewing the basics of Markov chains, which is the primary motion model for stochastic robotic surveillance. Then two main criteria regarding the speed and unpredictability of surveillance strategies are discussed. The central objects that appear throughout the treatment is the hitting times of Markov chains, their distributions and expectations. We formulate various optimization problems based on the concerned metrics in different scenarios and establish their respective properties.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Matching-Based Capture Strategies for 3D Heterogeneous Multiplayer Reach-Avoid Differential Games

This paper studies a 3D multiplayer reach-avoid differential game with a goal region and a play region. Multiple pursuers defend the goal region by consecutively capturing multiple evaders in the play region. The players have heterogeneous moving speeds and the pursuers have heterogeneous capture radii. Since this game is hard to analyze directly, we decompose the whole game as many subgames which involve multiple pursuers and only one evader. Then, these subgames are used as a building block for the pursuer-evader matching. First, for multiple pursuers and one evader, we introduce an evasion space (ES) method characterized by a potential function to construct a guaranteed pursuer winning strategy. Then, based on this strategy, we develop conditions to determine whether a pursuit team can guard the goal region against one evader. It is shown that in 3D, if a pursuit team is able to defend the goal region against an evader, then at most three pursuers in the team are necessarily needed. We also compute the value function of the Hamilton-Jacobi-Isaacs (HJI) equation for a special subgame of degree. To capture the maximum number of evaders in the open-loop sense, we formulate a maximum bipartite matching problem with conflict graph (MBMC). We show that the MBMC is NP-hard and design a polynomial-time constant-factor approximation algorithm to solve it. Finally, we propose a receding horizon strategy for the pursuit team where in each horizon an MBMC is solved and the strategies of the pursuers are given. We also extend our results to the case of a bounded convex play region where the evaders escape through an exit. Two numerical examples are provided to demonstrate the obtained results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Policy Evaluation and Seeking for Multi-Agent Reinforcement Learning via Best Response

This paper introduces two metrics (cycle-based and memory-based metrics), grounded on a dynamical game-theoretic solution concept called sink equilibrium, for the evaluation, ranking, and computation of policies in multi-agent learning. We adopt strict best response dynamics (SBRD) to model selfish behaviors at a meta-level for multi-agent reinforcement learning. Our approach can deal with dynamical cyclical behaviors (unlike approaches based on Nash equilibria and Elo ratings), and is more compatible with single-agent reinforcement learning than alpha-rank which relies on weakly better responses. We first consider settings where the difference between largest and second largest underlying metric has a known lower bound. With this knowledge we propose a class of perturbed SBRD with the following property: only policies with maximum metric are observed with nonzero probability for a broad class of stochastic games with finite memory. We then consider settings where the lower bound for the difference is unknown. For this setting, we propose a class of perturbed SBRD such that the metrics of the policies observed with nonzero probability differ from the optimal by any given tolerance. The proposed perturbed SBRD addresses the opponent-induced non-stationarity by fixing the strategies of others for the learning agent, and uses empirical game-theoretic analysis to estimate payoffs for each strategy profile obtained due to the perturbation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Singular Perturbation and Small-signal Stability for Inverter Networks

This paper examines small-signal stability of electrical networks composed dominantly of three-phase grid-following inverters. We show that the mere existence of a high-voltage power flow solution does not necessarily imply small-signal stability; this motivates us to develop a framework for stability analysis that systematically acknowledges inverter dynamics. We identify a suitable time-scale decomposition for the inverter dynamics, and using singular perturbation theory, obtain an analytic sufficient condition to verify small-signal stability. Compared to the alternative of performing an eigenvalue analysis of the full-order network dynamics, our analytic sufficient condition reduces computational complexity and yields insights on the role of network topology and constitution as well as inverter-filter and control parameters on small-signal stability. Numerical simulations for a radial network validate the approach and illustrate the efficiency of our analytic conditions for designing and monitoring grid-tied inverter networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stable and Efficient Structures in Multigroup Network Formation

In this work we present a strategic network formation model predicting the emergence of multigroup structures. Individuals decide to form or remove links based on the benefits and costs those connections carry; we focus on bilateral consent for link formation. An exogenous system specifies the frequency of coordination issues arising among the groups. We are interested in structures that arise to resolve coordination issues and, specifically, structures in which groups are linked through bridging, redundant, and co-membership interconnections. We characterize the conditions under which certain structures are stable and study their efficiency as well as the convergence of formation dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The 1995-2018 Global Evolution of the Network of Amicable and Hostile Relations Among Nation-States

We draw on the data collected by the Integrated Crisis Early Warning System on millions of international and regional public news stories, and this system's indicators of the orientation toward a specific nation-state. We construct the networks of international amicable and hostile relations among nation-states that occur in specific time-periods in order to study the global evolution of the network of such international appraisals. Our analysis presents evidence of an evolution of the structure of this network and a model of the probabilistic micro-dynamics of the alterations of international appraisals during the 1995-2018 span of the available data. Our research provides empirical findings on long-standing debates in the interdisciplinary field of work on Structural Balance Theory. Also remarkably, we find that the trajectory of the Frobenius norm of sequential transition probabilities, which govern the evolution of international appraisals among nations, dramatically stabilizes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Transient Stability of Droop-Controlled Inverter Networks with Operating Constraints

Due to the rise of distributed energy resources, the control of networks of grid-forming inverters is now a pressing issue for power system operation. Droop control is a popular control strategy in the literature for frequency control of these inverters. In this paper, we analyze transient stability in droop-controlled inverter networks that are subject to multiple operating constraints. Using a physically-meaningful Lyapunov-like function, we provide two sets of criteria (one mathematical and one computational) to certify that a post-fault trajectory achieves frequency synchronization while respecting operating constraints. We show how to obtain less-conservative transient stability conditions by incorporating information from loop flows, i.e., net flows of active power around cycles in the network. Finally, we use these conditions to quantify the scale of parameter disturbances to which the network is robust. We illustrate our results with numerical case studies of the IEEE 24-bus system.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Competitive Propagation: Models, Asymptotic Behavior and Multi-stage Games

In this paper we propose a class of propagation models for multiple competing products over a social network. We consider two propagation mechanisms: social conversion and self conversion, corresponding, respectively, to endogenous and exogenous factors. A novel concept, the product-conversion graph, is proposed to characterize the interplay among competing products. According to the chronological order of social and self conversions, we develop two Markov-chain models and, based on the independence approximation, we approximate them with two respective difference equations systems. Theoretical analysis on these two approximation models reveals the dependency of the systems' asymptotic behavior on the structures of both the product-conversion graph and the social network, as well as the initial condition. In addition to the theoretical work, accuracy of the independence approximation and the asymptotic behavior of the Markov-chain model are investigated via numerical analysis, for the case where social conversion occurs before self conversion. Finally, we propose a class of multi-player and multi-stage competitive propagation games and discuss the seeding-quality trade-off, as well as the allocation of seeding resources among the individuals. We investigate the unique Nash equilibrium at each stage and analyze the system's behavior when every player is adopting the policy at the Nash equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dynamic Models of Appraisal Networks Explaining Collective Learning

This paper proposes models of learning process in teams of individuals who collectively execute a sequence of tasks and whose actions are determined by individual skill levels and networks of interpersonal appraisals and influence. The closely-related proposed models have increasing complexity, starting with a centralized manager-based assignment and learning model, and finishing with a social model of interpersonal appraisal, assignments, learning, and influences. We show how rational optimal behavior arises along the task sequence for each model, and discuss conditions of suboptimality. Our models are grounded in replicator dynamics from evolutionary games, influence networks from mathematical sociology, and transactive memory systems from organization science.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Controllability Metrics, Limitations and Algorithms for Complex Networks

This paper studies the problem of controlling complex networks, that is, the joint problem of selecting a set of control nodes and of designing a control input to steer a network to a target state. For this problem (i) we propose a metric to quantify the difficulty of the control problem as a function of the required control energy, (ii) we derive bounds based on the system dynamics (network topology and weights) to characterize the tradeoff between the control energy and the number of control nodes, and (iii) we propose an open-loop control strategy with performance guarantees. In our strategy we select control nodes by relying on network partitioning, and we design the control input by leveraging optimal and distributed control techniques. Our findings show several control limitations and properties. For instance, for Schur stable and symmetric networks: (i) if the number of control nodes is constant, then the control energy increases exponentially with the number of network nodes, (ii) if the number of control nodes is a fixed fraction of the network nodes, then certain networks can be controlled with constant energy independently of the network dimension, and (iii) clustered networks may be easier to control because, for sufficiently many control nodes, the control energy depends only on the controllability properties of the clusters and on their coupling strength. We validate our results with examples from power networks, social networks, and epidemics spreading.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Consensus Networks over Finite Fields

This work studies consensus strategies for networks of agents with limited memory, computation, and communication capabilities. We assume that agents can process only values from a finite alphabet, and we adopt the framework of finite fields, where the alphabet consists of the integers {0,...,p-1}, for some prime number p, and operations are performed modulo p. Thus, we define a new class of consensus dynamics, which can be exploited in certain applications such as pose estimation in capacity and memory constrained sensor networks. For consensus networks over finite fields, we provide necessary and sufficient conditions on the network topology and weights to ensure convergence. We show that consensus networks over finite fields converge in finite time, a feature that can be hardly achieved over the field of real numbers. For the design of finite-field consensus networks, we propose a general design method, with high computational complexity, and a network composition rule to generate large consensus networks from smaller components. Finally, we discuss the application of finite-field consensus networks to distributed averaging and pose estimation in sensor networks.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Mixed Human-Robot Team Surveillance

We study the mixed human-robot team design in a system theoretic setting using the context of a surveillance mission. The three key coupled components of a mixed team design are (i) policies for the human operator, (ii) policies to account for erroneous human decisions, and (iii) policies to control the automaton. In this paper, we survey elements of human decision-making, including evidence aggregation, situational awareness, fatigue, and memory effects. We bring together the models for these elements in human decision-making to develop a single coherent model for human decision-making in a two-alternative choice task. We utilize the developed model to design efficient attention allocation policies for the human operator. We propose an anomaly detection algorithm that utilizes potentially erroneous decision by the operator to ascertain an anomalous region among the set of regions surveilled. Finally, we propose a stochastic vehicle routing policy that surveils an anomalous region with high probability. Our mixed team design relies on the certainty-equivalent receding-horizon control framework.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sparsity-Promoting Optimal Wide-Area Control of Power Networks

Inter-area oscillations in bulk power systems are typically poorly controllable by means of local decentralized control. Recent research efforts have been aimed at developing wide- area control strategies that involve communication of remote signals. In conventional wide-area control, the control structure is fixed a priori typically based on modal criteria. In contrast, here we employ the recently-introduced paradigm of sparsity- promoting optimal control to simultaneously identify the optimal control structure and optimize the closed-loop performance. To induce a sparse control architecture, we regularize the standard quadratic performance index with an l1-penalty on the feedback matrix. The quadratic objective functions are inspired by the classic slow coherency theory and are aimed at imitating homogeneous networks without inter-area oscillations. We use the New England power grid model to demonstrate that the proposed combination of the sparsity-promoting control design with the slow coherency objectives performs almost as well as the optimal centralized control while only making use of a single wide-area communication link. In addition to this nominal performance, we also demonstrate that our control strategy yields favorable robustness margins and that it can be used to identify a sparse control architecture for control design via alternative means.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Attack Detection and Identification in Cyber-Physical Systems -- Part I: Models and Fundamental Limitations

Cyber-physical systems integrate computation, communication, and physical capabilities to interact with the physical world and humans. Besides failures of components, cyber-physical systems are prone to malignant attacks, and specific analysis tools as well as monitoring mechanisms need to be developed to enforce system security and reliability. This paper proposes a unified framework to analyze the resilience of cyber-physical systems against attacks cast by an omniscient adversary. We model cyber-physical systems as linear descriptor systems, and attacks as exogenous unknown inputs. Despite its simplicity, our model captures various real-world cyber-physical systems, and it includes and generalizes many prototypical attacks, including stealth, (dynamic) false-data injection and replay attacks. First, we characterize fundamental limitations of static, dynamic, and active monitors for attack detection and identification. Second, we provide constructive algebraic conditions to cast undetectable and unidentifiable attacks. Third, by using the system interconnection structure, we describe graph-theoretic conditions for the existence of undetectable and unidentifiable attacks. Finally, we validate our findings through some illustrative examples with different cyber-physical systems, such as a municipal water supply network and two electrical power grids.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Attack Detection and Identification in Cyber-Physical Systems -- Part II: Centralized and Distributed Monitor Design

Cyber-physical systems integrate computation, communication, and physical capabilities to interact with the physical world and humans. Besides failures of components, cyber-physical systems are prone to malicious attacks so that specific analysis tools and monitoring mechanisms need to be developed to enforce system security and reliability. This paper builds upon the results presented in our companion paper [1] and proposes centralized and distributed monitors for attack detection and identification. First, we design optimal centralized attack detection and identification monitors. Optimality refers to the ability of detecting (respectively identifying) every detectable (respectively identifiable) attack. Second, we design an optimal distributed attack detection filter based upon a waveform relaxation technique. Third, we show that the attack identification problem is computationally hard, and we design a sub-optimal distributed attack identification procedure with performance guarantees. Finally, we illustrate the robustness of our monitors to system noise and unmodeled dynamics through a simulation study.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Random Convex Programming via Constraints Consensus

This paper discusses distributed approaches for the solution of random convex programs (RCP). RCPs are convex optimization problems with a (usually large) number N of randomly extracted constraints; they arise in several applicative areas, especially in the context of decision under uncertainty, see [2],[3]. We here consider a setup in which instances of the random constraints (the scenario) are not held by a single centralized processing unit, but are distributed among different nodes of a network. Each node "sees" only a small subset of the constraints, and may communicate with neighbors. The objective is to make all nodes converge to the same solution as the centralized RCP problem. To this end, we develop two distributed algorithms that are variants of the constraints consensus algorithm [4],[5]: the active constraints consensus (ACC) algorithm, and the vertex constraints consensus (VCC) algorithm. We show that the ACC algorithm computes the overall optimal solution in finite time, and with almost surely bounded communication at each iteration. The VCC algorithm is instead tailored for the special case in which the constraint functions are convex also w.r.t. the uncertain parameters, and it computes the solution in a number of iterations bounded by the diameter of the communication graph. We further devise a variant of the VCC algorithm, namely quantized vertex constraints consensus (qVCC), to cope with the case in which communication bandwidth among processors is bounded. We discuss several applications of the proposed distributed techniques, including estimation, classification, and random model predictive control, and we present a numerical analysis of the performance of the proposed methods. As a complementary numerical result, we show that the parallel computation of the scenario solution using ACC algorithm significantly outperforms its centralized equivalent.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Eulerian Opinion Dynamics with Bounded Confidence and Exogenous Input

The formation of opinions in a large population is governed by endogenous (human interactions) and exogenous (media influence) factors. In the analysis of opinion evolution in a large population, decision making rules can be approximated with non-Bayesian "rule of thumb" methods. This paper focuses on an Eulerian bounded-confidence model of opinion dynamics with a potential time-varying input. First, we prove some properties of this system's dynamics with time-varying input. Second, we derive a simple sufficient condition for opinion consensus, and prove the convergence of the population's distribution with no input to a sum of Dirac Delta functions. Finally, we define an input's attraction range, and for a normally distributed input and uniformly distributed initial population, we conjecture that the length of attraction range is an increasing affine function of population's confidence bound and input's variance.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Exploring Synchronization in Complex Oscillator Networks

The emergence of synchronization in a network of coupled oscillators is a pervasive topic in various scientific disciplines ranging from biology, physics, and chemistry to social networks and engineering applications. A coupled oscillator network is characterized by a population of heterogeneous oscillators and a graph describing the interaction among the oscillators. These two ingredients give rise to a rich dynamic behavior that keeps on fascinating the scientific community. In this article, we present a tutorial introduction to coupled oscillator networks, we review the vast literature on theory and applications, and we present a collection of different synchronization notions, conditions, and analysis approaches. We focus on the canonical phase oscillator models occurring in countless real-world synchronization phenomena, and present their rich phenomenology. We review a set of applications relevant to control scientists. We explore different approaches to phase and frequency synchronization, and we present a collection of synchronization conditions and performance estimates. For all results we present self-contained proofs that illustrate a sample of different analysis methods in a tutorial style.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Stochastic Surveillance Strategies for Spatial Quickest Detection

We design persistent surveillance strategies for the quickest detection of anomalies taking place in an environment of interest. From a set of predefined regions in the environment, a team of autonomous vehicles collects noisy observations, which a control center processes. The overall objective is to minimize detection delay while maintaining the false alarm rate below a desired threshold. We present joint (i) anomaly detection algorithms for the control center and (ii) vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms (one for each region) to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, in which the regions to be visited are chosen according to a probability vector. We study stationary routing policy (the probability vector is constant) as well as adaptive routing policies (the probability vector varies in time as a function of the likelihood of regional anomalies). In the context of stationary policies, we design a performance metric and minimize it to design an efficient stationary routing policy. Our adaptive policy improves upon the stationary counterpart by adaptively increasing the selection probability of regions with high likelihood of anomaly. Finally, we show the effectiveness of the proposed algorithms through numerical simulations and a persistent surveillance experiment.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Synchronization in Complex Oscillator Networks and Smart Grids

The emergence of synchronization in a network of coupled oscillators is a fascinating topic in various scientific disciplines. A coupled oscillator network is characterized by a population of heterogeneous oscillators and a graph describing the interaction among them. It is known that a strongly coupled and sufficiently homogeneous network synchronizes, but the exact threshold from incoherence to synchrony is unknown. Here we present a novel, concise, and closed-form condition for synchronization of the fully nonlinear, non-equilibrium, and dynamic network. Our synchronization condition can be stated elegantly in terms of the network topology and parameters, or equivalently in terms of an intuitive, linear, and static auxiliary system. Our results significantly improve upon the existing conditions advocated thus far, they are provably exact for various interesting network topologies and parameters, they are statistically correct for almost all networks, and they can be applied equally to synchronization phenomena arising in physics and biology as well as in engineered oscillator networks such as electric power networks. We illustrate the validity, the accuracy, and the practical applicability of our results in complex networks scenarios and in smart grid applications.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Consensus Computation in Unreliable Networks: A System Theoretic Approach

This work addresses the problem of ensuring trustworthy computation in a linear consensus network. A solution to this problem is relevant for several tasks in multi-agent systems including motion coordination, clock synchronization, and cooperative estimation. In a linear consensus network, we allow for the presence of misbehaving agents, whose behavior deviate from the nominal consensus evolution. We model misbehaviors as unknown and unmeasurable inputs affecting the network, and we cast the misbehavior detection and identification problem into an unknown-input system theoretic framework. We consider two extreme cases of misbehaving agents, namely faulty (non-colluding) and malicious (Byzantine) agents. First, we characterize the set of inputs that allow misbehaving agents to affect the consensus network while remaining undetected and/or unidentified from certain observing agents. Second, we provide worst-case bounds for the number of concurrent faulty or malicious agents that can be detected and identified. Precisely, the consensus network needs to be 2k+1 (resp. k+1) connected for k malicious (resp. faulty) agents to be generically detectable and identifiable by every well behaving agent. Third, we quantify the effect of undetectable inputs on the final consensus value. Fourth, we design three algorithms to detect and identify misbehaving agents. The first and the second algorithm apply fault detection techniques, and affords complete detection and identification if global knowledge of the network is available to each agent, at a high computational cost. The third algorithm is designed to exploit the presence in the network of weakly interconnected subparts, and provides local detection and identification of misbehaving agents whose behavior deviates more than a threshold, which is quantified in terms of the interconnection structure.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Cyber-Physical Attacks in Power Networks: Models, Fundamental Limitations and Monitor Design

Future power networks will be characterized by safe and reliable functionality against physical malfunctions and cyber attacks. This paper proposes a unified framework and advanced monitoring procedures to detect and identify network components malfunction or measurements corruption caused by an omniscient adversary. We model a power system under cyber-physical attack as a linear time-invariant descriptor system with unknown inputs. Our attack model generalizes the prototypical stealth, (dynamic) false-data injection and replay attacks. We characterize the fundamental limitations of both static and dynamic procedures for attack detection and identification. Additionally, we design provably-correct (dynamic) detection and identification procedures based on tools from geometric control theory. Finally, we illustrate the effectiveness of our method through a comparison with existing (static) detection algorithms, and through a numerical study.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Discrete Partitioning and Coverage Control for Gossiping Robots

We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a non-convex environment. To handle arbitrary non-convex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise "gossip" communication. The algorithm has two components: (1) a motion protocol to ensure that neighboring robots communicate at least sporadically, and (2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, we detail how our algorithm scales well for large teams in large environments and how the computation can run in anytime with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Estimation via Iterative Projections with Application to Power Network Monitoring

This work presents a distributed method for control centers to monitor the operating condition of a power network, i.e., to estimate the network state, and to ultimately determine the occurrence of threatening situations. State estimation has been recognized to be a fundamental task for network control centers to ensure correct and safe functionalities of power grids. We consider (static) state estimation problems, in which the state vector consists of the voltage magnitude and angle at all network buses. We consider the state to be linearly related to network measurements, which include power flows, current injections, and voltages phasors at some buses. We admit the presence of several cooperating control centers, and we design two distributed methods for them to compute the minimum variance estimate of the state given the network measurements. The two distributed methods rely on different modes of cooperation among control centers: in the first method an incremental mode of cooperation is used, whereas, in the second method, a diffusive interaction is implemented. Our procedures, which require each control center to know only the measurements and structure of a subpart of the whole network, are computationally efficient and scalable with respect to the network dimension, provided that the number of control centers also increases with the network cardinality. Additionally, a finite-memory approximation of our diffusive algorithm is proposed, and its accuracy is characterized. Finally, our estimation methods are exploited to develop a distributed algorithm to detect corrupted data among the network measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Flow Cytometry Based State Aggregation of a Stochastic Model of Protein Expression

In this article, we introduce the new approach "fluorescence grid based aggregation (FGBA)" to justify a dynamical model of protein expression using experimental fluorescence histograms. In this approach, first, we describe the dynamics of the gene-protein system by a chemical master equation (CME), while the protein production rates are unknown. Then, we aggregate the states of the CME into unknown group sizes. We show that these unknown values can be replaced by the data from the experimental fluorescence histograms. Consequently, final probability distributions correspond to the experimental fluorescence histograms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On cooperative patrolling: optimal trajectories, complexity analysis, and approximation algorithms

The subject of this work is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties, and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region, and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory, and we propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Opinion Dynamics in Heterogeneous Networks

This paper studies the opinion dynamics model recently introduced by Hegselmann and Krause: each agent in a group maintains a real number describing its opinion; and each agent updates its opinion by averaging all other opinions that are within some given confidence range. The confidence ranges are distinct for each agent. This heterogeneity and state-dependent topology leads to poorly-understood complex dynamic behavior. We classify the agents via their interconnection topology and, accordingly, compute the equilibria of the system. We conjecture that any trajectory of this model eventually converges to a steady state under fixed topology. To establish this conjecture, we derive two novel sufficient conditions: both conditions guarantee convergence and constant topology for infinite time, while one condition also guarantees monotonicity of the convergence. In the evolution under fixed topology for infinite time, we define leader groups that determine the followers' rate and direction of convergence.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Critical Coupling for Kuramoto Oscillators

The Kuramoto model captures various synchronization phenomena in biological and man-made systems of coupled oscillators. It is well-known that there exists a critical coupling strength among the oscillators at which a phase transition from incoherency to synchronization occurs. This paper features four contributions. First, we characterize and distinguish the different notions of synchronization used throughout the literature and formally introduce the concept of phase cohesiveness as an analysis tool and performance index for synchronization. Second, we review the vast literature providing necessary, sufficient, implicit, and explicit estimates of the critical coupling strength for finite and infinite-dimensional, and for first and second-order Kuramoto models. Third, we present the first explicit necessary and sufficient condition on the critical coupling to achieve synchronization in the finite-dimensional Kuramoto model for an arbitrary distribution of the natural frequencies. The multiplicative gap in the synchronization condition yields a practical stability result determining the admissible initial and the guaranteed ultimate phase cohesiveness as well as the guaranteed asymptotic magnitude of the order parameter. Fourth and finally, we extend our analysis to multi-rate Kuramoto models consisting of second-order Kuramoto oscillators with inertia and viscous damping together with first-order Kuramoto oscillators with multiple time constants. We prove that the multi-rate Kuramoto model is locally topologically conjugate to a first-order Kuramoto model with scaled natural frequencies, and we present necessary and sufficient conditions for almost global phase synchronization and local frequency synchronization. Interestingly, these conditions do not depend on the inertiae which contradicts prior observations on the role of inertiae in synchronization of second-order Kuramoto models.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Vehicle Placement to Intercept Moving Targets

We address optimal placement of vehicles with simple motion to intercept a mobile target that arrives stochastically on a line segment. The optimality of vehicle placement is measured through a cost function associated with intercepting the target. With a single vehicle, we assume that the target moves (i) with fixed speed and in a fixed direction perpendicular to the line segment, or (ii) to maximize the distance from the line segment, or (iii) to maximize intercept time. In each case, we show that the cost function is strictly convex, its gradient is smooth, and the optimal vehicle placement is obtained by a standard gradient-based optimization technique. With multiple vehicles, we assume that the target moves with fixed speed and in a fixed direction perpendicular to the line segment. We present a discrete time partitioning and gradient-based algorithm, and characterize conditions under which the algorithm asymptotically leads the vehicles to a set of critical configurations of the cost function.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Opinion Dynamics in Heterogeneous Networks: Convergence Conjectures and Theorems

Recently, significant attention has been dedicated to the models of opinion dynamics in which opinions are described by real numbers, and agents update their opinions synchronously by averaging their neighbors' opinions. The neighbors of each agent can be defined as either (1) those agents whose opinions are in its "confidence range," or (2) those agents whose "influence range" contain the agent's opinion. The former definition is employed in Hegselmann and Krause's bounded confidence model, and the latter is novel here. As the confidence and influence ranges are distinct for each agent, the heterogeneous state-dependent interconnection topology leads to a poorly-understood complex dynamic behavior. In both models, we classify the agents via their interconnection topology and, accordingly, compute the equilibria of the system. Then, we define a positive invariant set centered at each equilibrium opinion vector. We show that if a trajectory enters one such set, then it converges to a steady state with constant interconnection topology. This result gives us a novel sufficient condition for both models to establish convergence, and is consistent with our conjecture that all trajectories of the bounded confidence and influence models eventually converge to a steady state under fixed topology.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Synchronization and Transient Stability in Power Networks and Non-Uniform Kuramoto Oscillators

Motivated by recent interest for multi-agent systems and smart power grid architectures, we discuss the synchronization problem for the network-reduced model of a power system with non-trivial transfer conductances. Our key insight is to exploit the relationship between the power network model and a first-order model of coupled oscillators. Assuming overdamped generators (possibly due to local excitation controllers), a singular perturbation analysis shows the equivalence between the classic swing equations and a non-uniform Kuramoto model. Here, non-uniform Kuramoto oscillators are characterized by multiple time constants, non-homogeneous coupling, and non-uniform phase shifts. Extending methods from transient stability, synchronization theory, and consensus protocols, we establish sufficient conditions for synchronization of non-uniform Kuramoto oscillators. These conditions reduce to and improve upon previously-available tests for the standard Kuramoto model. Combining our singular perturbation and Kuramoto analyses, we derive concise and purely algebraic conditions that relate synchronization and transient stability of a power network to the underlying system parameters and initial conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Accuracy and Decision Time for Sequential Decision Aggregation

This paper studies prototypical strategies to sequentially aggregate independent decisions. We consider a collection of agents, each performing binary hypothesis testing and each obtaining a decision over time. We assume the agents are identical and receive independent information. Individual decisions are sequentially aggregated via a threshold-based rule. In other words, a collective decision is taken as soon as a specified number of agents report a concordant decision (simultaneous discordant decisions and no-decision outcomes are also handled). We obtain the following results. First, we characterize the probabilities of correct and wrong decisions as a function of time, group size and decision threshold. The computational requirements of our approach are linear in the group size. Second, we consider the so-called fastest and majority rules, corresponding to specific decision thresholds. For these rules, we provide a comprehensive scalability analysis of both accuracy and decision time. In the limit of large group sizes, we show that the decision time for the fastest rule converges to the earliest possible individual time, and that the decision accuracy for the majority rule shows an exponential improvement over the individual accuracy. Additionally, via a theoretical and numerical analysis, we characterize various speed/accuracy tradeoffs. Finally, we relate our results to some recent observations reported in the cognitive information processing literature.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Multi-Agent Deployment for Visibility Coverage in Polygonal Environments with Holes

This article presents a distributed algorithm for a group of robotic agents with omnidirectional vision to deploy into nonconvex polygonal environments with holes. Agents begin deployment from a common point, possess no prior knowledge of the environment, and operate only under line-of-sight sensing and communication. The objective of the deployment is for the agents to achieve full visibility coverage of the environment while maintaining line-of-sight connectivity with each other. This is achieved by incrementally partitioning the environment into distinct regions, each completely visible from some agent. Proofs are given of (i) convergence, (ii) upper bounds on the time and number of agents required, and (iii) bounds on the memory and communication complexity. Simulation results and description of robust extensions are also included.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Pairwise Optimal Discrete Coverage Control for Gossiping Robots

We propose distributed algorithms to automatically deploy a group of robotic agents and provide coverage of a discretized environment represented by a graph. The classic Lloyd approach to coverage optimization involves separate centering and partitioning steps and converges to the set of centroidal Voronoi partitions. In this work we present a novel graph coverage algorithm which achieves better performance without this separation while requiring only pairwise ``gossip'' communication between agents. Our new algorithm provably converges to an element of the set of pairwise-optimal partitions, a subset of the set of centroidal Voronoi partitions. We illustrate that this new equilibrium set represents a significant performance improvement through numerical comparisons to existing Lloyd-type methods. Finally, we discuss ways to efficiently do the necessary computations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Task Release Control for Decision Making Queues

We consider the optimal duration allocation in a decision making queue. Decision making tasks arrive at a given rate to a human operator. The correctness of the decision made by human evolves as a sigmoidal function of the duration allocated to the task. Each task in the queue loses its value continuously. We elucidate on this trade-off and determine optimal policies for the human operator. We show the optimal policy requires the human to drop some tasks. We present a receding horizon optimization strategy, and compare it with the greedy policy.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Visibility maintenance via controlled invariance for leader-follower Dubins-like vehicles

The paper studies the visibility maintenance problem (VMP) for a leader-follower pair of Dubins-like vehicles with input constraints, and proposes an original solution based on the notion of controlled invariance. The nonlinear model describing the relative dynamics of the vehicles is interpreted as linear uncertain system, with the leader robot acting as an external disturbance. The VMP is then reformulated as a linear constrained regulation problem with additive disturbances (DLCRP). Positive D-invariance conditions for linear uncertain systems with parametric disturbance matrix are introduced and used to solve the VMP when box bounds on the state, control input and disturbance are considered. The proposed design procedure is shown to be easily adaptable to more general working scenarios. Extensive simulation results are provided to illustrate the theory and show the effectiveness of our approach

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

A Dynamic Boundary Guarding Problem with Translating Targets

We introduce a problem in which a service vehicle seeks to guard a deadline (boundary) from dynamically arriving mobile targets. The environment is a rectangle and the deadline is one of its edges. Targets arrive continuously over time on the edge opposite the deadline, and move towards the deadline at a fixed speed. The goal for the vehicle is to maximize the fraction of targets that are captured before reaching the deadline. We consider two cases; when the service vehicle is faster than the targets, and; when the service vehicle is slower than the targets. In the first case we develop a novel vehicle policy based on computing longest paths in a directed acyclic graph. We give a lower bound on the capture fraction of the policy and show that the policy is optimal when the distance between the target arrival edge and deadline becomes very large. We present numerical results which suggest near optimal performance away from this limiting regime. In the second case, when the targets are slower than the vehicle, we propose a policy based on servicing fractions of the translational minimum Hamiltonian path. In the limit of low target speed and high arrival rate, the capture fraction of this policy is within a small constant factor of the optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Distributed and Adaptive Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment

In this paper we present distributed and adaptive algorithms for motion coordination of a group of m autonomous vehicles. The vehicles operate in a convex environment with bounded velocity and must service demands whose time of arrival, location and on-site service are stochastic; the objective is to minimize the expected system time (wait plus service) of the demands. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized a-priori task assignment and are not robust against changes in the environment, e.g. changes in load conditions; therefore, they are of limited applicability in scenarios involving ad-hoc networks of autonomous vehicles operating in a time-varying environment. First, we present a new class of policies for the 1-DTRP problem that: (i) are provably optimal both in light- and heavy-load condition, and (ii) are adaptive, in particular, they are robust against changes in load conditions. Second, we show that partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules in its own region, are optimal in heavy-load conditions. Finally, by combining the new class of algorithms for the 1-DTRP with suitable partitioning policies, we design distributed algorithms for the m-DTRP problem that (i) are spatially distributed, scalable to large networks, and adaptive to network changes, (ii) are within a constant-factor of optimal in heavy-load conditions and stabilize the system in any load condition. Simulation results are presented and discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Asynchronous Distributed Searchlight Scheduling

This paper develops and compares two simple asynchronous distributed searchlight scheduling algorithms for multiple robotic agents in nonconvex polygonal environments. A searchlight is a ray emitted by an agent which cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which can move continuously with unbounded speed. The objective of the proposed algorithms is for the agents to coordinate the slewing (rotation about a point) of their searchlights in a distributed manner, i.e., using only local sensing and limited communication, such that any target will necessarily be detected in finite time. The first algorithm we develop, called the DOWSS (Distributed One Way Sweep Strategy), is a distributed version of a known algorithm described originally in 1990 by Sugihara et al \cite{KS-IS-MY:90}, but it can be very slow in clearing the entire environment because only one searchlight may slew at a time. In an effort to reduce the time to clear the environment, we develop a second algorithm, called the PTSS (Parallel Tree Sweep Strategy), in which searchlights sweep in parallel if guards are placed according to an environment partition belonging to a class we call PTSS partitions. Finally, we discuss how DOWSS and PTSS could be combined with with deployment, or extended to environments with holes.

0 citations0 reviewsNo code linkedOpen access