More Like this

1. Distributed and Collision-Free Coverage Control of a Team of Mobile Sensors Using the Convex Uncertain Voronoi Diagram

   https://doi.org/10.23919/ACC45564.2020.9147359  

   Chen, Jun; Dames, Philip (July 2020, American Control Conference)

   In this paper, we propose a distributed coverage control algorithm for mobile sensing networks that can account for bounded uncertainty in the location of each sensor. Our algorithm is capable of safely driving mobile sensors towards areas of high information distribution while having them maintain coverage of the whole area of interest. To do this, we propose two novel variants of the Voronoi diagram. The first, the convex uncertain Voronoi (CUV) diagram, guarantees full coverage of the search area. The second, collision avoidance regions (CARs), guarantee collision-free motions while avoiding deadlock, enabling sensors to safely and successfully reach their goals. We demonstrate the efficacy of these algorithms via a series of simulations with different numbers of sensors and uncertainties in the sensors’ locations. The results show that sensor networks of different scales are able to safely perform optimized distribution corresponding to the information distribution density under different localization uncertainties 

   more » « less
2. Efficient multi-robot coverage of a known environment

   https://doi.org/10.1109/IROS.2017.8206000  

   Karapetyan, Nare; Benson, Kelly; McKinney, Chris; Taslakian, Perouz; Rekleitis, Ioannis (September 2017, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area. 

   more » « less
3. Distributed Multi-Target Search and Tracking Using a Coordinated Team of Ground and Aerial Robots

   Chen, Jun; Dames, Philip (July 2020, Robotics science and systems)

   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
4. Distributed Simultaneous Action and Target Assignment for Multi-Robot Multi-Target Tracking

   https://doi.org/10.1109/ICRA.2018.8460974  

   Sung, Yoonchang; Budhiraja, Ashish Kumar; Williams, Ryan K.; Tokekar, Pratap (May 2018, 2018 IEEE International Conference on Robotics and Automation (ICRA))

   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. Comparing Stochastic Optimization Methods for Multi-robot, Multi-target Tracking

   https://doi.org/10.1007/978-3-031-51497-5_27  

   Xin, Pujie; Dames, Philip (February 2024, Springer Nature Switzerland)

   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