Given a twodimensional polygonal space, the multirobot visibilitybased pursuitevasion problem tasks several pursuer robots with the goal of establishing visibility with an arbitrarily fast evader. The best known complete algorithm for this problem takes time doubly exponential in the number of robots. However, samplingbased techniques have shown promise in generating feasible solutions in these scenarios. One of the primary drawbacks to employing existing samplingbased methods is that existing algorithms have long execution times and high failure rates for complex environments. This paper addresses that limitation by proposing a new algorithm that takes an environment as its input and returns a joint motion strategy which ensures that the evader is captured by one of the pursuers. Starting with a single pursuer, we sequentially construct SampleGenerated PursuitEvasion Graphs to create such a joint motion strategy. This sequential graph structure ensures that our algorithm will always terminate with a solution, regardless of the complexity of the environment. We describe an implementation of this algorithm and present quantitative results that show significant improvement in comparison to the existing algorithm.
Efficient multirobot coverage of a known environment
This paper addresses the complete area coverage problem of a known environment by multiplerobots. Complete area coverage is the problem of moving an endeffector 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 NPcomplete. In this paper we present two approximation heuristics for solving the multirobot 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 singlerobot 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.
 Award ID(s):
 1637876
 Publication Date:
 NSFPAR ID:
 10127554
 Journal Name:
 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
 Page Range or eLocationID:
 1846 to 1852
 Sponsoring Org:
 National Science Foundation
More Like this


In large scale coverage operations, such as marine exploration or aerial monitoring, single robot approaches are not ideal, as they may take too long to cover a large area. In such scenarios, multirobot approaches are preferable. Furthermore, several real world vehicles are nonholonomic, but can be modeled using Dubins vehicle kinematics. This paper focuses on environmental monitoring of aquatic environments using Autonomous Surface Vehicles (ASVs). In particular, we propose a novel approach for solving the problem of complete coverage of a known environment by a multirobot team consisting of Dubins vehicles. It is worth noting that both multirobot coverage and Dubins vehicle coverage are NPcomplete problems. As such, we present two heuristics methods based on a variant of the traveling salesman problemkTSPformulation and clustering algorithms that efficiently solve the problem. The proposed methods are tested both in simulations to assess their scalability and with a team of ASVs operating on a 200 km 2 lake to ensure their applicability in real world.

Sensor coverage is the critical multirobot problem of maximizing the detection of events in an environment through the deployment of multiple robots. Large multirobot systems are often composed of simple robots that are typically not equipped with a complete set of sensors, so teams with comprehensive sensing abilities are required to properly cover an area. Robots also exhibit multiple forms of relationships (e.g., communication connections or spatial distribution) that need to be considered when assigning robot teams for sensor coverage. To address this problem, in this paper we introduce a novel formulation of sensor coverage by multirobot systems with heterogeneous relationships as a graph representation learning problem. We propose a principled approach based on the mathematical framework of regularized optimization to learn a unified representation of the multirobot system from the graphs describing the heterogeneous relationships and to identify the learned representation’s underlying structure in order to assign the robots to teams. To evaluate the proposed approach, we conduct extensive experiments on simulated multirobot systems and a physical multirobot system as a case study, demonstrating that our approach is able to effectively assign teams for heterogeneous multirobot sensor coverage.

Obeid, I. ; Selesnik, I. ; Picone, J. (Ed.)The Neuronix highperformance computing cluster allows us to conduct extensive machine learning experiments on big data [1]. This heterogeneous cluster uses innovative scheduling technology, Slurm [2], that manages a network of CPUs and graphics processing units (GPUs). The GPU farm consists of a variety of processors ranging from lowend consumer grade devices such as the Nvidia GTX 970 to higherend devices such as the GeForce RTX 2080. These GPUs are essential to our research since they allow extremely computeintensive deep learning tasks to be executed on massive data resources such as the TUH EEG Corpus [2]. We use TensorFlow [3] as the core machine learning library for our deep learning systems, and routinely employ multiple GPUs to accelerate the training process. Reproducible results are essential to machine learning research. Reproducibility in this context means the ability to replicate an existing experiment – performance metrics such as error rates should be identical and floatingpoint calculations should match closely. Three examples of ways we typically expect an experiment to be replicable are: (1) The same job run on the same processor should produce the same results each time it is run. (2) A job run on a CPU and GPU should producemore »

We study the labeled multirobot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constantfactor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constantfactor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but nonpolynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes nearoptimal solutions. Hardware experiments on the microMVP platform composed of nonholonomic robots confirms the practical applicability of our algorithmic pipeline.