We address the problem of ensuring resource availability in a networked multi-robot system performing distributed target tracking. Specifically, we consider a multi-target tracking scenario where the targets are driven by exogenous inputs that are unknown to the robots performing the tracking task. Robots track the positions of targets using a form of the Distributed Kalman Filter (DKF). We use the trace of each robot’s sensor measurement noise covariance matrix as a measure of its sensing quality. When a robot’s sensing quality deteriorates, the team’s communication graph is modified by adding edges such that the robot with deteriorating sensor quality may share information with other robots to improve the team’s target tracking ability. This computation is performed centrally and is designed to work without a large change in the number of active inter-robot communication links. Our method generates coordinates for the robots such the new communication graph can be realized in 3D. To achieve this, we propose two mixed integer semi-definite programming formulations, namely an ‘agent-centric’ strategy and a ‘team-centric’ strategy. We implement both formulations and a greedy, baseline strategy in simulation. Our simulation results show that the team-centric approach outperforms both agent-centric and greedy methods. Additionally, we show the effectiveness of our method in real-world settings through a multi-robot experiment performed in real-timeNote to Practitioners—This paper is motivated by the need to track multiple targets by means of a multi-robot team. When robots in the team experience degradation in their sensing quality our method reconfigures the team’s communication graph by repositioning robots. This allows the robot with deteriorated sensing quality to benefit from sensor measurements from its neighbors. In previous work, we solved this problem under the strong assumption the targets moved under inputs that were known to the tracking team. In this paper we remove this assumption. Our experiments show comparable tracking accuracy for both settings, suggesting that this strong assumption is not always necessary for good tracking results. Our method is straightforward to implement in Python using off-the-shelf optimization solvers. We assume that the team performs target tracking using a distributed algorithm, but has access to a powerful centralized base station to solve the computationally expensive underlying optimization problems. Developing a fully decentralized method and finding better ways to solve the underlying optimization problems are potential directions for future work.

We propose a framework for resilience in a networked heterogeneous multirobot team subject to resource failures. Each robot in the team is equipped with resources that it shares with its neighbors, which are identified based on the team’s communication graph. Additionally, each robot in the team executes a task, whose performance depends on the resources to which it has access. When a resource on a particular robot becomes unavailable ( e.g., a camera ceases to function), the team optimally reconfigures its communication network so that the robots affected by the failure can continue their tasks. We focus on a monitoring task, where robots individually estimate the state of an exogenous process. We encode the end-to-end effect of a robot’s resource loss on the monitoring performance of the team by defining a new stronger notion of observability—one-hop observability. By abstracting the impact that low-level individual resources have on the task performance through the notion of one-hop observability, our framework leads to the principled reconfiguration of information flow in the team to effectively replace the lost resource on one robot with information from another, as long as certain conditions are met. Network reconfiguration is converted to the problem of selecting edges to be modified in the system’s communication graph after a resource failure has occurred. A controller based on finite-time convergence control barrier functions drives each robot to a spatial location that enables the communication links of the modified graph. We validate the effectiveness of our framework by deploying it on a team of differential-drive robots estimating the position of a group of quadrotors.

Light Detection and Ranging (LIDAR) sensors play an important role in the perception stack of autonomous robots, supplying mapping and localization pipelines with depth measurements of the environment. While their accuracy outperforms other types of depth sensors, such as stereo or time-of-flight cameras, the accurate modeling of LIDAR sensors requires laborious manual calibration that typically does not take into account the interaction of laser light with different surface types, incidence angles and other phenomena that significantly influence measurements. In this work, we introduce a physically plausible model of a 2D continuous-wave LIDAR that accounts for the surface-light interactions and simulates the measurement process in the Hokuyo URG-04LX LIDAR. Through automatic differentiation, we employ gradient-based optimization to estimate model parameters from real sensor measurements.

We address the problem of maintaining resource availability in a networked multi-robot system performing distributed target tracking. In our model, robots are equipped with sensing and computational resources enabling them to track a target's position using a Distributed Kalman Filter (DKF). We use the trace of each robot's sensor measurement noise covariance matrix as a measure of sensing quality. When a robot's sensing quality deteriorates, the systems communication graph is modified by adding edges such that the robot with deteriorating sensor quality may share information with other robots to improve the team's target tracking ability. This computation is performed centrally and is designed to work without a large change in the number of active communication links. We propose two mixed integer semi-definite programming formulations (an `agent-centric' strategy and a `team-centric' strategy) to achieve this goal. We implement both formulations and a greedy strategy in simulation and show that the team-centric strategy outperforms the agent-centric and greedy strategies.

We propose a centralized control framework to select suitable robots from a heterogeneous pool and place them at appropriate locations to monitor a region for events of interest. In the event of a robot failure, our framework repositions robots in a user-defined local neighborhood of the failed robot to compensate for the coverage loss. If repositioning robots locally fails to attain a user-specified level of desired coverage, the central controller augments the team with additional robots from the pool. The size of the local neighborhood around the failed robot and the desired coverage over the region are two objectives that can be varied to achieve a user-specified balance. We investigate the trade-off between the coverage compensation achieved through local repositioning and the computation required to plan the new robot locations. We also study the relationship between the size of the local neighborhood and the number of additional robots added to the team for a given user-specified level of desired coverage. Through extensive simulations and an experiment with a team of seven quadrotors we verify the effectiveness of our framework. We show that to reach a high level of coverage in a neighborhood with a large robot population, it is more efficient to enlarge the neighborhood size, instead of adding additional robots and repositioning them.

Pursuit-Evasion Game (PEG) consists of a team of pursuers trying to capture one or more evaders. PEG is important due to its application in surveillance, search and rescue, disaster robotics, boundary defense and so on. In general, PEG requires exponential time to compute the minimum number of pursuers to capture an evader. To mitigate this, we have designed a parallel optimal algorithm to minimize the capture time in PEG. Given a discrete topology, this algorithm also outputs the minimum number of pursuers to capture an evader. A classic example of PEG is the popular arcade game, Pac-Man. Although Pac-Man topology has almost 300 nodes, our algorithm can handle this. We show that Pac-Man is overkill, i.e., given the Pac-Man game topology, Pac-Man game contains more pursuers/ghosts (four) than it is necessary (two) to capture evader/Pac-man. We evaluate the proposed algorithm on many different topologies.

In this article, we present a novel distributed method for constructing an occupancy grid map of an unknown environment using a swarm of robots with global localization capabilities and limited interrobot communication. The robots explore the domain by performing Lévy walks in which their headings are defined by maximizing the mutual information between the robot's estimate of its environment in the form of an occupancy grid map and the distance measurements that it is likely to obtain when it moves in that direction. Each robot is equipped with laser range sensors, and it builds its occupancy grid map by repeatedly combining its own distance measurements with map information that is broadcast by neighboring robots. Using results on average consensus over time-varying graph topologies, we prove that all robots' maps will eventually converge to the actual map of the environment. In addition, we demonstrate that a technique based on topological data analysis, developed in our previous work for generating topological maps, can be readily extended for adaptive thresholding of occupancy grid maps. We validate the effectiveness of our distributed exploration and mapping strategy through a series of two-dimensional simulations and multirobot experiments.

We propose a method to maintain high resource availability in a networked heterogeneous multi-robot system subject to resource failures. In our model, resources such as sensing and computation are available on robots. The robots are engaged in a joint task using these pooled resources. When a resource on a particular robot becomes unavailable (e.g., a sensor ceases to function), the system automatically reconfigures so that the robot continues to have access to this resource by communicating with other robots. Specifically, we consider the problem of selecting edges to be modified in the system's communication graph after a resource failure has occurred. We define a metric that allows us to characterize the quality of the resource distribution in the network represented by the communication graph. Upon a resource becoming unavailable due to failure, we reconFigure the network so that the resource distribution is brought as close to the maximal resource distribution as possible without a large change in the number of active inter-robot communication links. Our approach uses mixed integer semi-definite programming to achieve this goal. We employ a simulated annealing method to compute a spatial formation that satisfies the inter-robot distances imposed by the topology, along with other constraints. Our method can compute a communication topology, spatial formation, and formation change motion planning in a few seconds. We validate our method in simulation and real-robot experiments with a team of seven quadrotors.