In this article, we study multirobot path planning for persistent monitoring tasks. We consider the case where robots have a limited battery capacity with a discharge time$D$. We represent the areas to be monitored as the vertices of a weighted graph. For each vertex, there is a constraint on the maximum allowable time between robot visits, called the latency. The objective is to find the minimum number of robots that can satisfy these latency constraints while also ensuring that the robots periodically charge at a recharging depot. The decision version of this problem is known to be PSPACE-complete. We present a$O\left(\frac{\log D}{\log \log D} h \log \rho\right)$approximation algorithm for the problem where$\rho$is the ratio of the maximum and the minimum latency constraints, and$h$reflects the ratio of distance of vertices from the depot to their latency constraints. We also present an orienteering-based heuristic to solve the problem and show empirically that it typically provides higher quality solutions than the approximation algorithm. We extend our results to provide an algorithm for the problem of minimizing the maximum weighted latency given a fixed number of robots. We evaluate our algorithms on large problem instances in a patrolling scenario and in a wildfire monitoring application. We also compare the algorithms with an existing solver on benchmark instances.

This paper addresses consensus-based networked estimation of the state of a nonlinear dynamical system. This paper first presents an information form of the recently proposed Bayesian recursive update filter (BRUF), a Kalman filter that uses a recursive update to incorporate information from nonlinear measurement systems. Under the assumptions that the system is collectively observable and the network is strongly connected, a distributed information Bayesian recursive update filter (DIBRUF), a distributed form of the information Bayesian recursive update filter (IBRUF), is proposed, which exploits consensus on information vectors and matrices. Compared to the distributed extended Kalman filter (DEKF), the DIBRUF reduces the linearization error of the extended Kalman filter (EKF) by dividing the measurement update into N steps. Unlike the BRUF and IBRUF, which require local observability, the DIBRUF requires only the network to be collectively observable, as the sensors can share information among the network. Simulation experiments demonstrate the validity of the proposed approach.

This article investigates the problem of communication-efficient and resilient multiagent reinforcement learning (MARL). Specifically, we consider a setting where a set of agents are interconnected over a given network, and can only exchange information with their neighbors. Each agent observes a common Markov Decision Process and has a local cost which is a function of the current system state and the applied control action. The goal of MARL is for all agents to learn a policy that optimizes the infinite horizon discounted average of all their costs. Within this general setting, we consider two extensions to existing MARL algorithms. First, we provide an event-triggered learning rule where agents only exchange information with their neighbors if a certain triggering condition is satisfied. We show that this enables learning while reducing the amount of communication. Next, we consider the scenario where some of the agents can be adversarial (as captured by the Byzantine attack model), and arbitrarily deviate from the prescribed learning algorithm. We establish a fundamental trade-off between optimality and resilience when Byzantine agents are present. We then create a resilient algorithm and show almost sure convergence of all reliable agents' value functions to the neighborhood of the optimal value function of all reliable agents, under certain conditions on the network topology. When the optimal Q -values are sufficiently separated for different actions, we show that all reliable agents can learn the optimal policy under our algorithm.

Designing distributed control systems (DCS) is challenging because we need to balance the application control performance with the real-time hardware resource costs. Compared to the abundance of automated tools for monolithic systems, managing the design and implementation of DCS still heavily relies on human expertise. To address this challenge, we propose a human-augmenting design tool that suggests and explores tradeoffs in co-optimizing controller simplification and multiprocessor distributed task scheduling with a simple dial. Our work creatively combines sparsity-based optimal controller simplification with task consolidation, to achieve an optimal control performance on the smallest distributed hardware footprint. Our unique task consolidator adapts to various real-time scheduling algorithms and allocates control tasks to the fewest nodes under the utilization bounds of the chosen real-time scheduler. To account for real-time guarantees when assigning the controller, we introduce an improved worst-case execution time (WCET) model based on a mixed Weibull distribution. This new WCET model provides state-of-the-art accuracy of WCET based upon fewer data samples, thus reducing design-time effort and improving run-time performance. With our tool, designers can virtually simulate the theoretical optimum, physically download it, or experimentally explore alternative tradeoffs between system cost and controller performance. In a real-world implementation, our tool reduced 60% of hardware costs by trading off merely 0.14% of control performance. By automating the “simplification – demux – WCET estimation – task consolidation” pipeline, our tool allows control engineers to balance control performance and system cost directly, speeding up manual distributed controller design by 16 times.

We consider interdependent systems managed by multiple defenders that are under the threat of stepping-stone attacks. We model such systems via game-theoretic models and incorporate the effect of behavioral probability weighting that is used to model biases in human decision-making, as descended from the field of behavioral economics. We then incorporate into our framework called TASHAROK, two types of tax-based mechanisms for such interdependent security games where the central regulator incentivizes defenders to invest well in securing their assets so as to achieve the socially optimal outcome. We first show that due to the nature of our interdependent security game, no reliable tax-based mechanism can incentivize the socially optimal investment profile while maintaining a weakly balanced budget. We then show the effect of behavioral probability weighting bias on the amount of taxes paid by defenders, and prove that higher biases make defenders pay more taxes under the two mechanisms. We then explore voluntary participation in tax-based mechanisms. To evaluate our mechanisms, we use four representative real-world interdependent systems where we compare the game-theoretic optimal investments to the socially optimal investments under the two mechanisms. We show that the mechanisms yield higher decrease in the social cost for behavioral decision-makers compared to rational decision-makers.

We model the behavioral biases of human decision-making in securing interdependent systems and show that such behavioral decision-making leads to a suboptimal pattern of resource allocation compared to non-behavioral (rational) decision-making. We provide empirical evidence for the existence of such behavioral bias model through a controlled subject study with 145 participants. We then propose three learning techniques for enhancing decision-making in multi-round setups. We illustrate the benefits of our decision-making model through multiple interdependent real-world systems and quantify the level of gain compared to the case in which the defenders are behavioral. We also show the benefit of our learning techniques against different attack models. We identify the effects of different system parameters (e.g., the defenders' security budget availability and distribution, the degree of interdependency among defenders, and collaborative defense strategies) on the degree of suboptimality of security outcomes due to behavioral decision-making.

Unmanned Aerial Systems (UAS) collect and transmit data such as live video and radar images, which have different latency and reliability requirements, over wireless links that exhibit much performance variability. In this paper, we make three contributions. First, we show through a characterization of two real-world UAS flight datasets that there is significant opportunity to optimize data transmission in UAS settings by exploiting knowledge of UAS flight paths. Second, we developed Chimera, a system that taps into this opportunity while transmitting heterogeneous data streams over UAS networks. Chimera learns a model online that relates UAS network throughput to the flight path, and combines the model with a control framework that optimizes transmissions based on long-range throughput prediction. Third, with a combination of emulation and simulation experiments using real-world flight traces, we show Chimera’s effectiveness. Specifically, Chimera reduces penalties related to dropped radar images by 72.4%−100% compared to an algorithm agnostic to flight path information, and achieves an average bitrate of 90.5% compared to an optimal scheme that knows the exact future throughput, with only a minimal increase in radar images dropped.

There is much emerging interest in operating Unmanned Aerial Systems (UAS) at long-range distances. Unfortunately, it is unclear whether network connectivity at these distances is sufficient to enable applications with stringent performance needs. In this paper, we consider this question in the context of video streaming, an important UAS use-case. We make three contributions. First, we characterize network data collected from real-world UAS flight tests. Our results show that while dropouts (i.e., extended periods of poor performance) present challenges, there is potential to enable video streaming with modest delays, and correlation of throughput with flight path (both distance and orientation) provides new opportunities. Second, we present Proteus, the first system for video streaming targeted at long-range UAS settings. Proteus is distinguished from Adaptive Bit Rate (ABR) algorithms developed for Internet settings by explicitly accounting for dropouts, and leveraging flight path information. Third, through experiments with real-world flight traces on an emulation test-bed, we show that at distances of around 4 miles, Proteus reduces the fraction of a viewing session encountering rebuffering from 14.33% to 1.57%, while also significantly improving well-accepted composite video delivery metrics. Overall, our results show promise for enabling video streaming with dynamic UAS networks at long-range distances.

Reliable estimation of vehicle speed is an active topic of research in the automotive industry and academia due to its technical challenges as well as applications to vehicle traction and stability control. In this direction, the emergence of new generations of communication technologies has brought new perspectives to traditional studies on vehicle speed estimation and control. To this end, this paper introduces a cooperative vehicle speed fault diagnosis and correction algorithm. The distributed part of the algorithm is based on a distributed function calculation algorithm for vehicle networks. The introduced algorithm enables each vehicle to gather some information from other vehicles in the network in a distributed manner and is robust to communication failures. A procedure to use such information for a single vehicle to diagnose and correct a possible fault in its own speed estimation/measurement is discussed. The functionality and performance of the proposed algorithms are verified via illustrative examples and simulation results.

We introduce a network design game where the objective of the players is to design the interconnections between the nodes of two different networks G1and G2in order to maximize certain local utility functions. In this setting, each player is associated with a node in G1and has functional dependencies on certain nodes in G2. We use a distance-based utility for the players in which the goal of each player is to purchase a set of edges (incident to its associated node) such that the sum of the distances between its associated node and the nodes it depends on G2is minimized. We consider a heterogeneous set of players (i.e., players have their own costs and benefits for constructing edges). We show that finding a best response of a player in this game is NP-hard. Despite this, we characterize some properties of the best response actions, which are helpful in determining a Nash equilibrium for certain instances of this game. In particular, we prove the existence of pure Nash equilibria in this game when G2contains a star subgraph, and provide an algorithm that outputs such an equilibrium for any set of players. Finally, we show that the price of anarchy in this game can be arbitrarily large.

Real-time applications have deadline constraints. The system should provision sufficient resources for the application to meet the deadlines, and use supply and demand bound functions to analyze the schedulability of workloads. The concept of the demand bound function describes the upper bound on the resources required by the application, while the supply-bound function specifies the lower bound on the resources supplied to the tasks. If the system provides fewer resources than required, the application will experience an overload. Most work concentrates on designing systems that cannot experience short periods of overloads. This work explores resource provisioning for control applications that can tolerate overloads. It introduces analysis techniques for supply and demand bound functions that specifically consider overloads and delays in a periodic resource model. With this extended model, the work addresses three problems: (1) determine the worst-case delay for a given resource demand and supply under a periodic resource model, (2) find a periodic resource supply for a given workload and worst-case tolerable delay, and (3) for a control system with a given robustness criterion, identify a periodic resource supply with a worst-case delay.

This paper addresses the problem of resilient in-network consensus in the presence of misbehaving nodes. Secure and fault-tolerant consensus algorithms typically assume knowledge of nonlocal information; however, this assumption is not suitable for large-scale dynamic networks. To remedy this, we focus on local strategies that provide resilience to faults and compromised nodes. We design a consensus protocol based on local information that is resilient to worst-case security breaches, assuming the compromised nodes have full knowledge of the network and the intentions of the other nodes. We provide necessary and sufficient conditions for the normal nodes to reach asymptotic consensus despite the influence of the misbehaving nodes under different threat assumptions. We show that traditional metrics such as connectivity are not adequate to characterize the behavior of such algorithms, and develop a novel graph-theoretic property referred to as network robustness. Network robustness formalizes the notion of redundancy of direct information exchange between subsets of nodes in the network, and is a fundamental property for analyzing the behavior of certain distributed algorithms that use only local information.

We study the problem of stabilizing a linear system over a wireless network using a simple in-network computation method. Specifically, we study an architecture called the "Wireless Control Network" (WCN), where each wireless node maintains a state, and periodically updates it as a linear combination of neighboring plant outputs and node states. This architecture has previously been shown to have low computational overhead and beneficial scheduling and compositionality properties. In this paper we characterize fundamental topological conditions to allow stabilization using such a scheme. To achieve this, we exploit the fact that the WCN scheme causes the network to act as a linear dynamical system, and analyze the coupling between the plant's dynamics and the dynamics of the network. We show that stabilizing control inputs can be computed in-network if the vertex connectivity of the network is larger than the geometric multiplicity of any unstable eigenvalue of the plant. This condition is analogous to the typical min-cut condition required in classical information dissemination problems. Furthermore, we specify equivalent topological conditions for stabilization over a wired (or point-to-point) network that employs network coding in a traditional way - as a communication mechanism between the plant's sensors and decentralized controllers at the actuators.

Online learning has become increasingly popular on handling massive data. The sequential nature of online learning, however, requires a centralized learner to store data and update parameters. In this paper, we consider online learning with distributed data sources. The autonomous learners update local parameters based on local data sources and periodically exchange information with a small subset of neighbors in a communication network. We derive the regret bound for strongly convex functions that generalizes the work by Ram et al. for convex functions. More importantly, we show that our algorithm has intrinsic privacy-preserving properties, and we prove the sufficient and necessary conditions for privacy preservation in the network. These conditions imply that for networks with greater-than-one connectivity, a malicious learner cannot reconstruct the subgradients (and sensitive raw data) of other learners, which makes our algorithm appealing in privacy-sensitive applications.

We present a distributed scheme used for control over a network of wireless nodes. As opposed to traditional networked control schemes where the nodes simply route information to and from a dedicated controller (perhaps performing some encoding along the way), our approach, Wireless Control Network (WCN), treats the network itself as the controller. In other words, the computation of the control law is done in a fully distributed way inside the network. We extend the basic WCN strategy, where at each time-step, each node updates its internal state to be a linear combination of the states of the nodes in its neighborhood. This causes the entire network to behave as a linear dynamical system, with sparsity constraints imposed by the network topology. We demonstrate that with observer style updates, the WCN's robustness to link failures is substantially improved. Furthermore, we show how to design a WCN that can maintain stability even in cases of node failures. We also address the problem of WCN synthesis with guaranteed optimal performance of the plant, with respect to standard cost functions. We extend the synthesis procedure to deal with continuous-time plants and demonstrate how the WCN can be used on a practical, industrial application, using a process-in-the-loop setup with real hardware.

We examine the problem of reliable networked control when the communication channel between the controller and the actuator periodically drops packets and is faulty (i.e., corrupts/alters data). We first examine the use of a standard triple modular redundancy scheme (where the control input is sent via three independent channels) with majority voting to achieve mean square stability. While such a scheme is able to tolerate a single faulty channel when there are no packet drops, we show that the presence of lossy channels prevents a simple majority-voting approach from stabilizing the system. Moreover, the number of redundant channels that are required in order to maintain stability under majority voting increases with the probability of packet drops. We then propose the use of a reputation management scheme to overcome this problem, where each channel is assigned a reputation score that predicts its potential accuracy based on its past behavior. The reputation system builds on the majority voting scheme and improves the overall probability of applying correct (stabilizing) inputs to the system. Finally, we provide analytical conditions on the probabilities of packet drops and corrupted control inputs under which mean square stability can be maintained, generalizing existing results on stabilization under packet drops.

Given an arbitrary network of interconnected nodes, we develop and analyze a distributed strategy that enables a subset of the nodes to calculate any given function of the node values. Our scheme utilizes a linear iteration where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix of the linear iteration, and with outputs for each node that are captured by the set of values that are available to that node at each time-step. In connected networks with time-invariant topologies, we use observability theory to show that after running the linear iteration for a finite number of time-steps with almost any choice of weight matrix, each node obtains enough information to calculate any arbitrary function of the initial node values. The problem of distributed consensus via linear iterations, where all nodes in the network calculate the same function, is treated as a special case of our approach. In particular, our scheme allows nodes in connected networks with time-invariant topologies to reach consensus on any arbitrary function of the initial node values in a finite number of steps for almost any choice of weight matrix.

We study the problem of performing sensor fusion and distributed consensus in networks, where the objective is to calculate some linear function of the initial sensor values at some or all of the sensors. We utilize a linear iteration where, at each time-step, each sensor updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix for the linear iteration, and with outputs for each sensor that are captured by the subset of the state vector that is measurable by that sensor. We then cast the fusion and consensus problems as that of observing a linear functional of the initial state vector using only local measurements (that are available at each sensor). When the topology of the network is time-invariant, we show that the weight matrix can be chosen so that each sensor can calculate the desired function as a linear combination of its measurements over a finite number of time-steps.