Search

In this paper we present a novel distributed coverage control framework for a network of mobile agents, in charge of covering a finite set of points of interest (PoI), such as people in danger, geographically dispersed equipment or environmental landmarks. The proposed algorithm is inspired by C-Means, an unsupervised learning algorithm originally proposed for non-exclusive clustering and for identification of cluster centroids from a set of observations. To cope with the agents' limited sensing range and avoid infeasible coverage solutions, traditional C-Means needs to be enhanced with proximity constraints, ensuring that each agent takes into account only neighboring PoIs. The proposed coverage control framework provides useful information concerning the ranking or importance of the different PoIs to the agents, which can be exploited in further application-dependent data fusion processes, patrolling, or disaster relief applications., To appear in the 56th IEEE Conference on Decision and Control, to be held in Melbourne, Australia, December 12-15, 2017

In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.

This paper investigates how the topology of a dynamical network affects its robustness against exogenous disturbances. We consider Laplacian-based network dynamics, and we adopt the H2 system norm to measure the robustness of the network against disturbances. For networks arising from the composition of atomic structures, we provide a closed-form expression of the robustness against disturbances, and we identify optimal composition rules. Specifically, we show that networks consisting of multiple atomic structures are less robust than each isolated part, and that robust structures arise by interconnecting nodes of the atomic components with highest degree. Finally, we describe an algorithm for the design of robust composite networks.

In this paper we propose a novel local interaction protocol which solves the discrete time dynamic average consensus problem, i.e., the consensus problem on the average value of a set of time-varying input signals in an undirected graph. The proposed interaction protocol is based on a multi-stage cascade of consensus filters which tracks the average value of the inputs with small error. We characterize how the number of stages influences the steady state error. The main novelty of the proposed algorithm is that, with respect to other dynamic average consensus protocols, we do not exploit the k-th order derivatives of the inputs nor we require that the average of the network state is preserved to achieve convergence to the desired quantity, thus increasing the robustness of the method in several practical scenarios. In addition, the proposed design allows to trade-off convergence time with steady-state error by choosing a proper number of stages in the cascade. Finally, we provide a preliminary asynchronous and randomized version of the proposed protocol along with numerical examples to corroborate the theoretical findings.

In this paper, we consider the problem of decentralized evaluation of redundant rigidity of a multi-agent network topology. Redundancy is an important restriction of a graph's rigidity property as it is a necessary condition for the global rigidity of a graph, a combinatorial notion that is vital for graph realizability with consequences for example in localization. Furthermore, redundant rigidity enforces additional structure which allows for link loss or failure while maintaining an underlying rigid topology. First, we map the combinatorial conditions for determining redundant rigidity to the context of a centralized pebble game. By exploiting intuition from a bipartite matching characterization, we demonstrate decentralized conditions based in graph search and agent agreement. Then we provide a complete description of a decentralized algorithm for evaluating redundant rigidity, exploiting auctions and boolean consensus. To illustrate our methods, we provide a brief simulation study of redundant rigidity evaluation and nonholonomic control that closes the paper.

In this paper, we investigate set Input to State Stability (set-ISS) in the context of multi-agent systems, specifically when agent interaction is spatial in nature. As a case study we consider an aggregative objective with collision avoidance, where it is assumed that interacting agents are symmetrically disturbed. By considering constraints on physical occupancy in the workspace, we obtain insights into the tradeoffs of disturbance, collective behaviors, and the parameters of interaction. Finally, a feedback loop is generated using the disturbance information yielded by set-ISS analysis to strengthen cohesion against disturbance.

We consider the problem of controlling the motion of a set of robots to ferry messages between a given set of statically-placed nodes. The design and analysis of an arrivalrate unaware throughput-optimal policy for this problem is challenging because of the coupling between position and link rate. We propose a fine-grained backpressure message ferrying algorithm (FBMF) for joint motion and transmission control of robots. Unlike traditional backpressure settings, because the controlled motion of the relay nodes changes the channel rates, it turns out that the conventional approach to prove throughput optimality does not work in this problem setting. We prove for the simplest setting (single-flow, single-robot, constant arrival) that this policy indeed achieves throughput optimality. The analysis reveals that under feasible traffic, even when queues are highly over-loaded, the change in the total queue size can be positive over a time step, nevertheless the system exhibits a limit-cycle behavior and stability holds because the change in the total queue size is negative over the cycle for sufficiently large queues. We pose the design and analysis of a throughput optimal policy for the general case as a challenging open problem for network theory.

We present two novel distributed algorithms for hole detection in a wireless sensor network (WSN) based on the distributed Delaunay triangulation of the underlying communication graph. The first, which we refer to as the distance-vector hole determination (DVHD) algorithm, is based on traditional distance vector routing for multi-hop networks and shortest path lengths between node pairs. The second, which we refer to as the Gaussian curvature-based hole determination (GCHD) algorithm, applies the Gauss-Bonnet theorem on the Delaunay graph to calculate the number of holes based on the graph's Gaussian curvature. We present a detailed comparative performance analysis of both methods based on simulations, showing that while DVHD is conceptually simpler, the GCHD algorithm shows better performance with respect to run-time and message count per node.

In this work we consider a multi-robot system composed of three robotic units running the seminal swarm aggregation control law proposed in [1] for which a pairwise interaction is considered among each couple of units. In particular, we provide a characterization of all the possible equilibria for such a system while varying the parameters of interaction and investigate their stability properties. Simulations along with experimental results are given to corroborate the theoretical analysis.