1,721,061 research outputs found
Distributed consensus on enclosing shapes and minimum time rendezvous
No full textIn this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order agents with bounded inputs and limited range communication. We propose two dynamic control and communication laws. These laws are based on consensus algorithms for distributed computation of the minimal enclosing ball and orthotope of a set of points. We prove that these control laws converge to the optimal solution of the centralized problem (i.e., when no communication constrains are enforced) as the bound on the control input goes to zero. Moreover, we give a bound for the time complexity of one of the two laws
Network abstract linear programming with application to minimum-time formation control
Full text linkWe identify a novel class of distributed optimization problems, namely a networked version of abstract linear programming. For such problems we propose distributed algorithms for networks with various connectivity and/or memory constraints. Finally, we show how various minimum-time formation control problems can be tackled through appropriate geometric examples of abstract linear programs
Distributed estimation via iterative projections with application to power network monitoring
No full textThis 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 operate safely and reliably a power grid. 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 voltage 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 the 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 network measurements
Accuracy and decision time for sequential decision aggregation
No full textThis 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 (CIP) literature
A distributed method for state estimation and false data detection in power networks
No full textThis work presents a distributed method for control centers to monitor the operating condition of a power network. Specifically 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 assumed, whereas, in the second method, a diffusive interaction is implemented. These estimation methods, which are proved to converge in finite time, are further exploited to develop a distributed algorithm to detect corrupted data among network measurements
Gossip coverage control for robotic networks: dynamical systems on the space of partitions
No full textFuture applications in environmental monitoring, delivery of services, and transportation
of goods motivate the study of deployment and partitioning tasks for groups of autonomous
mobile agents. These tasks may be achieved by recent coverage algorithms, based upon the classic
methods by Lloyd. These algorithms, however, rely upon critical requirements on the communication
network: information is exchanged synchronously among all agents and long-range communication
is sometimes required. This work proposes novel coverage algorithms that require only gossip communication,
i.e., asynchronous, pairwise, and possibly unreliable communication. Which robot pair
communicates at any given time may be selected deterministically or randomly. A key innovative
idea is describing coverage algorithms for robot deployment and environment partitioning as dynamical
systems on a space of partitions. In other words, we study the evolution of the regions assigned
to each agent rather than the evolution of the agents’ positions. The proposed gossip algorithms are
shown to converge to centroidal Voronoi partitions under mild technical conditions. Our treatment
features a broad variety of results in topology, analysis, and geometry. First, we establish the compactness
of a suitable space of partitions with respect to the symmetric difference metric. Second,
with respect to this metric, we establish the continuity of various geometric maps, including the
Voronoi diagram as a function of its generators, the location of a centroid as a function of a set,
and the widely known multicenter function studied in facility location problems. Third, we prove
two convergence theorems for dynamical systems on metric spaces described by deterministic and
stochastic switches
On the Security of Linear Consensus Networks
No full textThis work considers the problem of reaching consensus in linear networks with misbehaving agents. A solution to this problem is relevant for several tasks in multiagent systems including motion coordination, clock synchronization, and cooperative estimation. By modelling the misbehaving nodes as unknown and unmeasurable inputs affecting the network, we recast the problem into a system theoretic framework. Only relying on their direct measurements, the agents detect and identify uncooperative behaviors using fault detection and isolation techniques. We consider both the cases of Byzantine as well as non-colluding faults, and we express the solvability conditions of the two cases in terms of the observability properties of a linear system associated with the network, and from a graph theoretic perspective. It is shown that generically any node can correctly detect and identify the misbehaving agents, provided that the connectivity of the network is sufficiently high. Precisely, for a linear consensus network to be generically resilient to k concurrent faults, the connectivity of the communication graph needs to be 2k+1, if Byzantine agents are allowed, and k+1, if non-colluding agents are considered
Distributed Intrusion Detection for Secure Consensus Computations
No full textThis paper focuses on trustworthy computation systems and proposes a novel intrusion detection scheme for averaging networks with misbehaving nodes. This prototypical control problem is relevant in network security applications. The objective is for each node to detect and isolate the misbehaving nodes using only the information flow adopted by standard averaging protocols. We focus on the single misbehaving node problem. Our technical approach is based on the theory of Unknown Input Observability. First, we give necessary and sufficient conditions for the misbehavior to be observable and for the identity of the faulty node to be detectable. Second, we design a distributed unknown input estimator, and we characterize its convergence rate in the 'equal-neighbor' model and in the general case. Third and finally, we propose a complete detection and isolation scheme and provide some remarks on the filter convergence time. We conclude the paper with the numerical study of a consensus problem and of a robot deployment problem
Maintaining limited-range connectivity among second-order agents
Full text linkIn this paper we consider ad-hoc networks of robotic agents with double integrator dynamics. For such networks, the connectivity maintenance problems are: (i) do there exist control inputs for each agent to maintain network connectivity, and (ii) given desired controls for each agent, can one compute the closest connectivity-maintaining controls in a distributed fashion. The proposed solution is based on three contributions. First, we define and characterize admissible sets for double integrators to remain inside disks. Second, we establish an existence theorem for the connectivity maintenance problem by introducing a novel state-dependent graph, called the double-integrator disk graph. Finally, we design a distributed "flow-control" algorithm to compute optimal connectivity-maintaining controls
- …
