Efficient Multi-Robot Coverage of a Known Environment

Abstract

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.

In proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017

Cited by in corpus (15)

• Active Learning in Robotics: A Review of Control Principles
• CARE: Cooperative Autonomy for Resilience and Efficiency of Robot Teams for Complete Coverage of Unknown Environments under Robot Failures
• Adaptive Workload Allocation for Multi-human Multi-robot Teams for Independent and Homogeneous Tasks
• Integrated Guidance and Gimbal Control for Coverage Planning With Visibility Constraints
• Area Coverage with Multiple Capacity-Constrained Robots
• Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction
• Unscented Optimal Control for 3D Coverage Planning with an Autonomous UAV Agent
• Integrated Ray-Tracing and Coverage Planning Control using Reinforcement Learning
• Optimal Sequential Stochastic Deployment of Multiple Passenger Robots
• A Versatile Multi-Robot Monte Carlo Tree Search Planner for On-Line Coverage Path Planning
• Autonomous Intruder Detection Using a ROS-Based Multi-Robot System Equipped with 2D-LiDAR Sensors
• GMC-Pos: Graph-Based Multi-Robot Coverage Positioning Method
• Dynamic Autonomous Surface Vehicle Control and Applications in Environmental Monitoring
• Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles
• Constrained Heterogeneous Vehicle Path Planning for Large-area Coverage