An official website of the United States government
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
Comparing Stochastic Optimization Methods for Multi-robot, Multi-target Tracking
This paper compares different distributed control approaches which enable a team of robots search for and track an unknown number of targets. The robots are equipped with sensors which have a limited field of view (FoV) and they 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 subsequent 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). This paper presents novel formulations of PSO and SA to solve the multi-target tracking problem, which 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):
- 2143312
- PAR ID:
- 10416740
- Publisher / Repository:
- Springer Nature Switzerland
- Date Published:
- ISBN:
- 978-3-031-51497-5
- Page Range / eLocation ID:
- 378 to 393
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
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
-
Background/Objective: Nutritionists play a crucial role in guiding individuals toward healthier lifestyles through personalized meal planning; however, this task involves navigating a complex web of factors, including health conditions, dietary restrictions, cultural preferences, and socioeconomic constraints. The Analytic Hierarchy Process (AHP) offers a valuable framework for structuring these multi-faceted decisions but inconsistencies can hinder its effectiveness in pairwise comparisons. Methods: This paper proposes a novel hybrid Particle Swarm Optimization–Simulated Annealing (PSO-SA) algorithm to refine inconsistent AHP weight matrices, ensuring a consistent and accurate representation of the nutritionist’s expertise and client preferences. Our approach merges PSO’s global search capabilities with SA’s local search precision, striking an optimal balance between exploration and exploitation. Results: We demonstrate the practical utility of our algorithm through real-world use cases involving personalized meal planning for individuals with specific dietary needs and preferences. Results showcase the algorithm’s efficiency in achieving consistency and surpassing standard PSO accuracy. Conclusion: By integrating the PSO-SA algorithm into a mobile app, we empower nutritionists with an advanced decision-making tool for creating tailored meal plans that promote healthier dietary choices and improved client outcomes. This research represents a significant advancement in multi-criteria decision-making for nutrition, offering a robust solution to the inconsistency challenge in AHP and paving the way for more effective and personalized dietary interventions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Book Chapter:
- https://doi.org/10.1007/978-3-031-51497-5_27
