Constructing a spatial map of environmental parameters is a crucial step to preventing hazardous chemical leakages, forest fires, or while estimating a spatially distributed physical quantities such as terrain elevation. Although prior methods can do such mapping tasks efficiently via dispatching a group of autonomous agents, they are unable to ensure satisfactory convergence to the underlying ground truth distribution in a decentralized manner when any of the agents fail. Since the types of agents utilized to perform such mapping are typically inexpensive and prone to failure, this results in poor overall mapping performance in real-world applications, which can in certain cases endanger human safety. This paper presents a Bayesian approach for robust spatial mapping of environmental parameters by deploying a group of mobile robots capable of ad-hoc communication equipped with short-range sensors in the presence of hardware failures. Our approach first utilizes a variant of the Voronoi diagram to partition the region to be mapped into disjoint regions that are each associated with at least one robot. These robots are then deployed in a decentralized manner to maximize the likelihood that at least one robot detects every target in their associated region despite a non-zero probability of failure. A suite of simulation results is presented to demonstrate the effectiveness and robustness of the proposed method when compared to existing techniques.

In this paper, we propose a distributed control policy to achieve rendezvous by a set of robots even when some robots in the system do not follow the prescribed policy. These nonconforming robots correspond to faults in the multirobot system, and our control policy is thus a fault-tolerant policy. Each robot has a limited sensing range and is able to directly estimate the state of only those robots within that sensing range, which induces a network topology for the multirobot system. We assume that it is not possible for the fault-free robots to identify the faulty robots, and thus our approach is robust even to undetected faults in the system. The main contribution of this paper is a fault-tolerant distributed control algorithm that is guaranteed to converge to consensus under certain reasonable connectivity conditions. We first present a general algorithm that exploits the notion of a Tverberg partition of a point set in Rd, and give a proof of convergence. We then provide three instantiations of this algorithm, based on three different sensing models. For each case, we analyze performance via extensive simulations. The effectiveness and performance of our algorithms on real platforms are demonstrated through experiments on a multirobot testbed.

In this paper, we explore the problem of rendezvous of synchronous multi-robot systems. Each robot has its own unique, bounded yet controllable sensing range which can be adjusted. The state of those robots within the sensing range can be estimated, which induces the directed network topology of the multi-robot systems. In particular, we consider multi-robot systems containing faulty robots which can behave arbitrarily. Our recent work [1] has addressed the problem of achieving rendezvous in the presence of faulty robots under a restrictive class of conditions on network topology. In this work, we presented a theoretically correct, but computationally intractable algorithm. We extend our past work by proposing a new approximate algorithm that is computationally efficient, and by showing that the proposed algorithm solves our problem given faulty robots in general configurations under mild assumptions on the network topology. Thus, the main contribution of this paper is to provide an efficient computational framework and analysis of robust rendezvous algorithm in the presence of faulty robots. Several simulation results are provided to demonstrate that our algorithm performs well in the face of both stationary and dynamic faults.

In this paper, we propose a distributed control policy to achieve rendezvous by a set of robots even when some robots in the system do not follow the prescribed policy. These nonconforming robots correspond to faults in the multi-robot systems, and our control policy is thus a fault-tolerant policy. We consider the case in which each robot is an autonomous decision maker that is anonymous (i.e., robots are indistinguishable to one another), memoryless (i.e., each robot makes decisions based upon only its current information), and dimensionless (i.e., collision checking is not considered). Each robot has a limited sensing range, and is able to directly estimate the state of only those robots within that sensing range, which induces a network topology for the multi-robot systems. We assume that it is not possible for the fault-free robots to identify the faulty robots (e.g., due to the anonymous property of the robots). Our main result is a practical algorithm that achieves approximate rendezvous in the face of faulty robots under a few assumptions on the network topology. In simulation results, we show that our algorithm performs better in the face of faulty robots than other contemporary convergence algorithms, e.g., the circumcenter law, and local coordinate averaging.

This paper presents a distributed robust deployment algorithm for optimal coverage by a mobile sensor network (MSN). Much past research has focused on versions of the coverage problem that partition the workspace into regions, and then assign exactly one sensor to cover each region. For this case it has been shown that the optimal partition is the Voronoi partition, and that Lloyd's algorithm converges to the optimal solution, with each sensor located at the centroid of its Voronoi region. In this paper, we consider the case in which k sensors are assigned to each region in the partition, in order to obtain coverage that is robust to sensor failure. For this case, we prove that the optimal workspace partition is the order-k Voronoi partition, with each sensor assigned to those order-k Voronoi regions for which it is a generator. The collection of these regions for a given sensor defines its effective sensing region (ESR), and we prove that in the optimal configuration each sensor is located at the centroid of its ESR. Finally we introduce a distributed algorithm for our optimal sensor placement problem that requires only simple peer-to-peer (P2P) communications. We show via simulation results that our algorithm converges in finite time, and provides competitive coverage performance in the presence of individual node failures.

In this paper, we consider the problem of designing distributed control algorithms to solve the rendezvous problem for multi-robot systems with limited sensing, for situation in which random nodes may fail during execution. We first formulate a distributed solution based upon averaging algorithms that have been reported in the consensus literature. In this case, at each stage of execution a 1-step sequential optimal control (i.e., naïve greedy algorithm) is used. We show that by choosing an appropriate constraint set, finite-time point convergence is guaranteed. We then propose a distributed stochastic optimal control algorithm that minimizes a mean-variance cost function for each stage, given that the probability distribution for possible node failures is known a priori. We show via simulation results that our algorithm provides competitive rendezvous task performance in comparison to that of the classical circumcenter algorithm for cases in which there are no node failures. Then we show, via examples with multiple node failures, that our proposed algorithm provides better rendezvous task performance than contemporary algorithms in cases for which failures occur. Additionally, we generate and compare a spectrum of results by varying the probabilities of node failures, or varying the weight value for the variance term in the cost functional. The results suggest that by choosing the design parameters appropriately, one may adjust the degree of soft constraints of the controller as well.

In this paper, we consider the problem of worst-case performance by a mobile sensor network (MSN) when some of the nodes in the network fail. We formulate the problem as a game in which some subset of the nodes act in an adversarial manner, choosing their motion strategies to maximally degrade overall performance of the network as a whole. We restrict our attention in the present paper to a target detection problem in which the goal is to minimize the probability of missed detection. We use a partitioned cost function that is minimized when each sensor executes a motion strategy given by Lloyd's algorithm (i.e., each agent moves toward the centroid of its Voronoi partition at each time instant), and when the probability of missed detection for each functioning sensor increases with the distance between sensor and target for correctly functioning sensors; adversarial nodes in the network are unable to detect the target, and move to maximally increase the probability of missed detection by the properly functioning sensors. We pose the problem as a multi-stage decision process, and use forward dynamic programming over a finite horizon to numerically compute optimal strategies for the adversaries. We compare the resulting strategies to a greedy algorithm, providing both system trajectories and evolution of the probability of missed detection during execution.

In this paper, we consider the performance of distributed control algorithms for networked robotic systems when one or more robots fail to execute the optimal policy. In particular, we investigate the performance of the circumcenter algorithm with connectivity maintenance [1]-[3] when one or more adversarial agents act maliciously to maximally disrupt convergence of the remaining, cooperative agents. To this end, we formulate a performance objective for each adversary node in terms of the circumradii of its cooperative neighbors in a communication graph which does not require omniscience of adversaries as is often assumed in the literature (e.g., [4], [5]). We provide an optimization algorithm based on finite-horizon dynamic programming, and obtain solutions through numerical simulation. Our results show that in general adversarial nodes are able not only to impede convergence toward consensus, but can also affect global changes in the topology of the communication graph for the cooperative agents.