Mitra, Aritra; Richards, John R.; Bagchi, Saurabh; Sundaram, Shreyas
We study the problem of designing a distributed observer for an LTI system over a time-varying communication graph. The limited existing work on this topic imposes various restrictions either on the observation model or on the sequence of communication graphs. In contrast, we propose a single-time-scale distributed observer that works under mild assumptions. Specifically, our communication model only requires strong-connectivity to be preserved over nonoverlapping, contiguous intervals that are even allowed to grow unbounded over time. We show that under suitable conditions that bound the growth of such intervals, joint observability is sufficient to track the state of any discrete-time LTI system exponentially fast, at any desired rate. We also develop a variant of our algorithm that is provably robust to worst-case adversarial attacks, provided the sequence of graphs is sufficiently connected over time. The key to our approach is the notion of a 'freshness-index' that keeps track of the age-of-information being diffused across the network. Such indices enable nodes to reject stale estimates of the state, and, in turn, contribute to stability of the error dynamics.
Mitra, Aritra; Richards, John R.; Bagchi, Saurabh; Sundaram, Shreyas
We consider the problem of distributed inference where agents in a network observe a stream of private signals generated by an unknown state, and aim to uniquely identify this state from a finite set of hypotheses. We focus on scenarios where communication between agents is costly, and takes place over channels with finite bandwidth. To reduce the frequency of communication, we develop a novel event-triggered distributed learning rule that is based on the principle of diffusing low beliefs on each false hypothesis. Building on this principle, we design a trigger condition under which an agent broadcasts only those components of its belief vector that have adequate innovation, to only those neighbors that require such information. We prove that our rule guarantees convergence to the true state exponentially fast almost surely despite sparse communication, and that it has the potential to significantly reduce information flow from uninformative agents to informative agents. Next, to deal with finite-precision communication channels, we propose a distributed learning rule that leverages the idea of adaptive quantization. We show that by sequentially refining the range of the quantizers, every agent can learn the truth exponentially fast almost surely, while using just 1 bit to encode its belief on each hypothesis. For both our proposed algorithms, we rigorously characterize the trade-offs between communication-efficiency and the learning rate.
Here, we study a setting where a group of agents, each receiving partially informative private signals, seek to collaboratively learn the true underlying state of the world (from a finite set of hypotheses) that generates their joint observation profiles. To solve this problem, we propose a distributed learning rule that differs fundamentally from existing approaches, in that it does not employ any form of “belief-averaging”. Instead, agents update their beliefs based on a min-rule. Under standard assumptions on the observation model and the network structure, we establish that each agent learns the truth asymptotically almost surely. As our main contribution, we prove that with probability 1, each false hypothesis is ruled out by every agent exponentially fast, at a network-independent rate that is strictly larger than existing rates. We then develop a computationally-efficient variant of our learning rule that is provably resilient to agents who do not behave as expected (as represented by a Byzantine adversary model) and deliberately try to spread misinformation.
Proceedings of the IEEE Conference on Decision and Control
Khaledyan, Milad; Vinod, Abraham P.; Oishi, Meeko; Richards, John R.
We address the problem of simultaneous coverage control and stochastic, multi-target tracking with a single pursuer. We presume linear dynamics for the pursuer and linear stochastic dynamics for the targets. The pursuer is equipped with two sensors of varying fidelity: broad-range and narrow-range. We seek the optimal trajectory for the pursuer, as well as optimal sensor selection, over a finite time horizon. We formulate the problem as a mixed-integer program with quadratic constraints, and exploit a convex relaxation method to enable fast solution of local minima. We demonstrate our approach on several simulated scenarios.
We introduce a simple time-triggered protocol to achieve communication-efficient non-Bayesian learning over a network. Specifically, we consider a scenario where a group of agents interact over a graph with the aim of discerning the true state of the world that generates their joint observation profiles. To address this problem, we propose a novel distributed learning rule wherein agents aggregate neighboring beliefs based on a min-protocol, and the inter-communication intervals grow geometrically at a rate a ≥ 1. Despite such sparse communication, we show that each agent is still able to rule out every false hypothesis exponentially fast with probability 1, as long as a is finite. For the special case when communication occurs at every time-step, i.e., when a = 1, we prove that the asymptotic learning rates resulting from our algorithm are network-structure independent, and a strict improvement over existing rates. In contrast, when a>1, our analysis reveals that the asymptotic learning rates vary across agents, and exhibit a non-trivial dependence on the network topology and the relative entropies of the agents' likelihood models. This motivates us to consider the problem of allocating signal structures to agents to maximize appropriate performance metrics. In certain special cases, we show that the eccentricity centrality and the decay centrality of the underlying graph help identify optimal allocations; for more general cases, we bound the deviation from the optimal allocation as a function of the parameter a, and the diameter of the graph.
A small, consumable-free, low-power, ultra-high-speed comprehensive GC×GC system consisting of microfabricated columns, nanoelectromechanical system (NEMS) cantilever resonators for detection, and a valve-based stop-flow modulator is demonstrated. The separation of a highly polar 29-component mixture covering a boiling point range of 46 to 253 °C on a pair of microfabricated columns using a Staiger valve manifold in less than 7 seconds, and just over 4 seconds after the ensemble holdup time is demonstrated with a downstream FID. The analysis time of the second dimension was 160 ms, and peak widths in the second dimension range from 10-60 ms. A peak capacity of just over 300 was calculated for a separation of just over 6 s. Data from a continuous operation testing over 40 days and 20000 runs of the GC×GC columns with the NEMS resonators using a 4-component test set is presented. The GC×GC-NEMS resonator system generated second-dimension peak widths as narrow as 8 ms with no discernable peak distortion due to under-sampling from the detector.
Gas Chromatography (GC) is routinely used in the laboratory to temporally separate chemical mixtures into their constituent components for improved chemical identification. This paper will provide a overview of more than twenty years of development of one-dimensional field-portable micro GC systems, highlighting key experimental results that illustrate how a reduction in false alarm rate (FAR) is achieved in real-world environments. Significantly, we will also present recent results on a micro two-dimensional GC (micro GCxGC) technology. This ultra-small system consists of microfabricated columns, NanoElectroMechanical System (NEMS) cantilever resonators for detection, and a valve-based stop-flow modulator. The separation of a 29-component polar mixture in less than 7 seconds is demonstrated along with peak widths in the second dimension ranging from 10-60 ms. For this system, a peak capacity of just over 300 was calculated for separation in about 6 s. This work has important implications for field detection, to drastically reduce FAR and significantly improve chemical selectivity and identification. This separation performance was demonstrated with the NEMS resonator and bench scale FID. But other detectors, suitably fast and sensitive can work as well. Recent research has shown that the identification power of GCxGC-FID can match that of GC-MS. This result indicates a path to improved size, weight, power, and performance in micro GCxGC systems outfitted with relatively non-specific, lightweight detectors. We will briefly discuss the performance of possible options, such as the pulsed discharge helium ionization detector (PDHID) and miniature correlation ion mobility spectrometer (mini-CIMS).