Search

In many applications of multi-agent systems (MAS), a set of leader agents acts as control inputs to the remaining follower agents. In this paper, we introduce an analytical approach to selecting leader agents in order to minimize the total mean-square error of the follower agent states from their desired value in steady-state in the presence of noisy communication links. We show that, for a set of link weights based on the second-order noise statistics, the problem of choosing leaders in order to minimize this error can be solved using supermodular optimization techniques, leading to efficient algorithms that are within a provable bound of the optimum. We formulate two leader selection problems within our framework, namely the problem of choosing a fixed number of leaders to minimize the error, as well as the problem of choosing the minimum number of leaders to achieve a tolerated level of error. We study both leader selection criteria for different scenarios, including MAS with static topologies, topologies experiencing random link or node failures, switching topologies, and topologies that vary arbitrarily in time due to node mobility. In addition to providing provable bounds for all of these cases, simulation results demonstrate that our approach outperforms other leader selection methods, such as node degree-based and random selection methods, and provides comparable performance to current state of the art algorithms. [ABSTRACT FROM AUTHOR]

This article studies the synthesis of control policies for an agent that has to satisfy a temporal logic specification in a partially observable environment, in the presence of an adversary. The interaction of the agent (defender) with the adversary is modeled as a partially observable stochastic game. The goal is to generate a defender policy to maximize satisfaction of a given temporal logic specification under any adversary policy. The search for policies is limited to the space of finite-state controllers, which leads to a tractable approach to determine policies. We relate the satisfaction of the specification to reaching (a subset of) recurrent states of a Markov chain. We present an algorithm to determine a set of defender and adversary finite-state controllers of fixed sizes that will satisfy the temporal logic specification and prove that it is sound. We then propose a value-iteration algorithm to maximize the probability of satisfying the temporal logic specification under finite-state controllers of fixed sizes. Finally, we extend this setting to the scenario where the size of the finite-state controller of the defender can be increased to improve the satisfaction probability. We illustrate our approach with an example. [ABSTRACT FROM AUTHOR]

Advanced persistent threats (APTs) infiltrate cyber systems and compromise specifically targeted data and/or resources through a sequence of stealthy attacks consisting of multiple stages. Dynamic information flow tracking has been proposed to detect APTs. In this article, we develop a dynamic information flow tracking game for resource-efficient detection of APTs via multistage dynamic games. The game evolves on an information flow graph, whose nodes are processes and objects (e.g., file, network endpoints) in the system and the edges capture the interaction between different processes and objects. Each stage of the game has prespecified targets that are characterized by a set of nodes of the graph. The goal of the APT is to evade detection and reach a target node of each stage. The goal of the defender is to maximize the detection probability while minimizing performance overhead on the system. The resource costs of the players are different and the information structure is asymmetric, resulting in a nonzero-sum imperfect information game. We first calculate the best responses of the players and then compute Nash equilibrium for single-stage attacks. We then provide a polynomial-time algorithm to compute a correlated equilibrium for the multistage attack case. Finally, we simulate our model and algorithm on real-world nation state attack data obtained from the Refinable Attack INvestigation (RAIN) system. [ABSTRACT FROM AUTHOR]

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in nonstationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to Markov decision processes, in which the target sets and control policies are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study. [ABSTRACT FROM AUTHOR]

In networked control systems, selecting a subset of input and output nodes is a crucial step in designing a stabilizing controller. Most existing approaches to input and output selection focus on nominal systems with known parameters. For systems with uncertainties and time delays, current selection methods are based on exploiting the convexity after relaxing the original problem, which is inherently discrete, to continuous optimization forms, and hence lack optimality guarantees. This paper studies the problem of identifying the minimum-size sets of input and output nodes to guarantee stability of a linear system with uncertainties and time delays. We derive sufficient conditions to guarantee the existence of a stabilizing controller for an uncertain linear system, based on a subset of system modes lying within the controllability and observability subspaces induced by the selected inputs and outputs. We then formulate the problems of selecting minimum-size sets of input and output nodes to satisfy the derived conditions, and prove that they are equivalent to discrete optimization problems with bounded submodularity ratios. We develop polynomial-time selection algorithms with provable guarantees on the minimum number of inputs and outputs required. Our approach is applicable to various types of uncertainties, including additive uncertainty, multiplicative uncertainty, uncertain output delay, and structured uncertainty. In a numerical study, we test our approach for the wide-area damping control in power systems to ensure small signal stability. Our results are validated on the IEEE 39-bus test power system. [ABSTRACT FROM AUTHOR]

Synchronization underlies phenomena including memory and perception in the brain, coordinated motion of animal flocks, and stability of the power grid. These synchronization phenomena are often modeled through networks of phase-coupled oscillating nodes. Heterogeneity in the node dynamics, however, may prevent such networks from achieving the required level of synchronization. In order to guarantee synchronization, external inputs can be used to pin a subset of nodes to a reference frequency, while the remaining nodes are steered toward synchronization via local coupling. In this paper, we present a submodular optimization framework for selecting a set of nodes to act as external inputs in order to achieve synchronization from a desired set of initial states. We derive threshold-based sufficient conditions for synchronization, and then prove that these conditions are equivalent to constraints on monotone submodular functions over partition matroids. Based on this connection, we map the sufficient conditions for synchronization to constraints on submodular functions, leading to efficient algorithms with provable optimality bounds for selecting input nodes. We illustrate our approach via numerical studies of synchronization in power systems. [ABSTRACT FROM AUTHOR]

Networked control systems consist of distributed sensors and actuators that communicate via a wireless network. The use of an open wireless medium and unattended deployment leaves these systems vulnerable to intelligent adversaries whose goal is to disrupt the system performance. In this paper, we study the wormhole attack on a networked control system, in which an adversary establishes a link between two geographically distant regions of the network by using either high-gain antennas, as in the out-of-band wormhole, or colluding network nodes as in the in-band wormhole. Wormholes allow the adversary to violate the timing constraints of real-time control systems by first creating low-latency links, which attract network traffic, and then delaying or dropping packets. Since the wormhole attack reroutes and replays valid messages, it cannot be detected using cryptographic mechanisms alone. We study the impact of the wormhole attack on the network flows and delays and introduce a passivity-based control-theoretic framework for modeling and mitigating the wormhole attack. We develop this framework for both the in-band and out-of-band wormhole attacks as well as complex, hereto-unreported wormhole attacks consisting of arbitrary combinations of in-and out-of band wormholes. By integrating existing mitigation strategies into our framework, we analyze the throughput, delay, and stability properties of the overall system. Through simulation study, we show that, by selectively dropping control packets, the wormhole attack can cause disturbances in the physical plant of a networked control system, and demonstrate that appropriate selection of detection parameters mitigates the disturbances due to the wormhole while satisfying the delay constraints of the physical system. [ABSTRACT FROM AUTHOR]

In a leader-follower multi-agent system (MAS), the leader agents act as control inputs and influence the states of the remaining follower agents. The rate at which the follower agents converge to their desired states, as well as the errors in the follower agent states prior to convergence, are determined by the choice of leader agents. In this paper, we study leader selection in order to minimize convergence errors experienced by the follower agents, which we define as a norm of the distance between the follower agents' intermediate states and the convex hull of the leader agent states. By introducing a novel connection to random walks on the network graph, we show that the convergence error has an inherent supermodular structure as a function of the leader set. Supermodularity enables development of efficient discrete optimization algorithms that directly approximate the optimal leader set, provide provable performance guarantees, and do not rely on continuous relaxations. We formulate two leader selection problems within the supermodular optimization framework, namely, the problem of selecting a fixed number of leader agents in order to minimize the convergence error, as well as the problem of selecting the minimum-size set of leader agents to achieve a given bound on the convergence error. We introduce algorithms for approximating the optimal solution to both problems in static networks, dynamic networks with known topology distributions, and dynamic networks with unknown and unpredictable topology distributions. Our approach is shown to provide significantly lower convergence errors than existing random and degree-based leader selection methods in a numerical study. [ABSTRACT FROM PUBLISHER]