skip to main content


Title: Distributed Multi-robot Tracking of Unknown Clustered Targets with Noisy Measurements
Distributed multi-target tracking is a canonical task for multi-robot systems, encompassing applications from environmental monitoring to disaster response to surveillance. In many situations, the distribution of unknown objects in a search area is irregular, with objects are likely to distribute in clusters instead of evenly distributed. In this paper, we develop a novel distributed multi-robot multi-target tracking algorithm for effectively tracking clustered targets from noisy measurements. Our algorithm contains two major components. Firstly, both the instantaneous and cumulative target density are estimated, providing the best guess of current target states and long-term coarse distribution of clusters, respectively. Secondly, the power diagram is implemented in Lloyd’s algorithm to optimize task space assignment for each robot to trade-off between tracking detected targets in clusters and searching for potential targets outside clusters. We demonstrate the efficacy of our proposed method and show that our method outperforms of other candidates in tracking accuracy through a set of simulations.  more » « less
Award ID(s):
1830419
NSF-PAR ID:
10416736
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
International Symposium on Distributed and Autonomous Systems
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. This paper proposes a distributed estimation and control algorithm to allow a team of robots to search for and track an unknown number of targets. The number of targets in the area of interest varies over time as targets enter or leave, and there are many sources of sensing uncertainty, including false positive detections, false negative detections, and measurement noise. The robots use a novel distributed Multiple Hypothesis Tracker (MHT) to estimate both the number of targets and the states of each target. A key contribution is a new data association method that reallocates target tracks across the team. The distributed MHT is compared against another distributed multi-target tracker to test its utility for multi-robot, multi-target tracking. 
    more » « less
  2. Presented at the Workshop on Heterogeneous Multi-Robot Task Allocation and Coordination. The authors recently developed a distributed algorithm to enable a team of homogeneous robots to search for and track an unknown and time-varying number of dynamic targets. This algorithm combined a distributed version of the PHD filter (for multi-target tracking) with Lloyd’s algorithm to drive the motion of the robots. In this paper we extend this previous work to allow a heterogeneous team of groundand aerial robots to perform the search and tracking tasks in a coordinated manner. Both types of robots are equipped with sensors that have a finite field of view and which may receive both false positive and false negative detections. Theaerial robots may vary the size of their sensor field of view (FoV) by changing elevation. This increase in the FoV coincides with a decrease in the accuracy and reliability of the sensor. The ground robots maintain the target tracking information while the aerial robots provide additional sensor coverage. We develop two new distributed algorithms to provide filter updates and to make control decisions in this heterogeneous team. Both algorithms only require robots to communicate with nearby robots and use minimal bandwidth.We demonstrate the efficacy of our approach through a series of simulated experiments which show that the heterogeneous teams are able to achieve more accurate tracking in less time than our previous work. 
    more » « less
  3. This paper compares different distributed control approaches that enable a team of robots search for and track an unknown number of targets. The robots are equipped with sensors which have limited field of view (FoV) and are required to explore the environment. The team uses a distributed formulation of the Probability Hypothesis Density (PHD) filter to estimate the number and the position of the targets. The resulting target estimate is used to select the future search locations for each robot. This paper compares Lloyd’s algorithm, a traditional method for distributed search, with two typical stochastic optimization methods, Particle Swarm Optimization (PSO) and Simulated Annealing (SA). PSO and SA are traditionally used to find a single global maximum, therefore this paper describes novel formulations of PSO and SA to solve the problem of multi-target tracking. These new methods more effectively trade off between exploration and exploitation. Simulations demonstrate that the use of these stochastic optimization techniques improves coverage of the search space and reduces the error in the target estimates compared to the baseline approach. 
    more » « less
  4. We study two multi-robot assignment problems for multi-target tracking. We consider distributed approaches in order to deal with limited sensing and communication ranges. We seek to simultaneously assign trajectories and targets to the robots. Our focus is on \emph{local} algorithms that achieve performance close to the optimal algorithms with limited communication. We show how to use a local algorithm that guarantees a bounded approximate solution within $\mathcal{O}(h\log{1/\epsilon})$ communication rounds. We compare with a greedy approach that achieves a $2$--approximation in as many rounds as the number of robots. Simulation results show that the local algorithm is an effective solution to the assignment problem. 
    more » « less
  5. Accurately detecting, localizing, and tracking an unknown and time-varying number of dynamic targets using a team of mobile robots is a challenging problem that requires robots to reason about the uncertainties in their collected measurements. The problem is made more challenging when robots are uncertain about their own states, as this makes it difficult to both collectively localize targets and avoid collisions with one another. In this paper, we introduce the convex uncertain Voronoi (CUV) diagram, a generalization of the standard Voronoi diagram that accounts for the uncertain pose of each individual robot. We then use the CUV diagram to develop distributed multi-target tracking and coverage control algorithms that enable teams of mobile robots to account for bounded uncertainty in the location of each robot. Our algorithms are capable of safely driving mobile robots towards areas of high information distribution while maintaining coverage of the whole area of interest. We demonstrate the efficacy of these algorithms via a series of simulated and hardware tests, and compare the results to our previous work which assumes perfect localization. 
    more » « less