skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.

Title: Comparing Stochastic Optimization Methods for Multi-Robot, Multi-Target Tracking
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
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
International Symposium on Distributed and Autonomous Systems
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. null (Ed.)
    Abstract Swarm robotic search aims at searching targets using a large number of collaborating simple mobile robots, with applications to search and rescue and hazard localization. In this regard, decentralized swarm systems are touted for their coverage scalability, time efficiency, and fault tolerance. To guide the behavior of such swarm systems, two broad classes of approaches are available, namely, nature-inspired swarm heuristics and multi-robotic search methods. However, the ability to simultaneously achieve efficient scalability and provide fundamental insights into the exhibited behavior (as opposed to exhibiting a black-box behavior) remains an open problem. To address this problem, this paper extends the underlying search approach in batch-Bayesian optimization to perform search with embodied swarm agents operating in a (simulated) physical 2D arena. Key contributions lie in (1) designing an acquisition function that not only balances exploration and exploitation across the swarm but also allows modeling knowledge extraction over trajectories and (2) developing its distributed implementation to allow asynchronous task inference and path planning by the swarm robots. The resulting collective informative path planning approach is tested on target-search case studies of varying complexity, where the target produces a spatially varying (measurable) signal. Notably, superior performance, in terms of mission completion efficiency, is observed compared to exhaustive search and random walk baselines as well as a swarm optimization-based state-of-the-art method. Favorable scalability characteristics are also demonstrated. 
    more » « less
  4. 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
  5. This paper addresses the visibility-based pursuit-evasion problem where a team of pursuer robots operating in a two-dimensional polygonal space seek to establish visibility of an arbitrarily fast evader. This is a computationally challenging task for which the best known complete algorithm takes time doubly exponential in the number of robots. However, recent advances that utilize sampling-based methods have shown progress in generating feasible solutions. An aspect of this problem that has yet to be explored concerns how to ensure that the robots can recover from catastrophic failures which leave one or more robots unexpectedly incapable of continuing to contribute to the pursuit of the evader. To address this issue, we propose an algorithm that can rapidly recover from catastrophic failures. When such failures occur, a replanning occurs, leveraging both the information retained from the previous iteration and the partial progress of the search completed before the failure to generate a new motion strategy for the reduced team of pursuers. We describe an implementation of this algorithm and provide quantitative results that show that the proposed method is able to recover from robot failures more rapidly than a baseline approach that plans from scratch. 
    more » « less