Approximation algorithms for distributed multi-robot coverage in non-convex environments
From MaRDI portal
Publication:3381981
Abstract: In this paper, we revisit the distributed coverage control problem with multiple robots on both metric graphs and in non-convex continuous environments. Traditionally, the solutions provided for this problem converge to a locally optimal solution with no guarantees on the quality of the solution. We consider sub-additive sensing functions, which capture the scenarios where sensing an event requires the robot to visit the event location. For these sensing functions, we provide the first constant factor approximation algorithms for the distributed coverage problem. The approximation results require twice the conventional communication range in the existing coverage algorithms. However, we show through extensive simulation results that the proposed approximation algorithms outperform several existing algorithms in convex, non-convex continuous, and discrete environments even with the conventional communication ranges. Moreover, the proposed algorithms match the state-of-the-art centralized algorithms in the solution quality.
Recommendations
- Distributed coverage control for concave areas by a heterogeneous Robot-Swarm with visibility sensing constraints
- Unifying Geometric, Probabilistic, and Potential Field Approaches to Multi-robot Coverage Control
- Efficient Boustrophedon multi-robot coverage: An algorithmic approach
- Complete distributed coverage of rectilinear environments
- Distributed coverage of nonconvex environments
Cites work
- scientific article; zbMATH DE number 1670526 (Why is no real title available?)
- A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
- Approximating \(k\)-median via pseudo-approximation
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Coverage problems in sensor networks: a survey
- Local Search Heuristics for k-Median and Facility Location Problems
- Local-search based approximation algorithms for mobile facility location problems (extended abstract)
- Planning Algorithms
Cited in
(16)- An MILP approach for persistent coverage tasks with multiple robots and performance guarantees
- Distributed sweep coverage algorithm of multi-agent systems using workload memory
- Multi-agent deployment for visibility coverage in polygonal environments with holes
- A framework for multi-robot node coverage in sensor networks
- Computing Convex Coverage Sets for Faster Multi-objective Coordination
- Distributed coverage control for concave areas by a heterogeneous Robot-Swarm with visibility sensing constraints
- Efficient Boustrophedon multi-robot coverage: An algorithmic approach
- Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm
- Multi-robots Gaussian estimation and coverage control: from client-server to peer-to-peer architectures
- Sweep coverage of discrete time multi-robot networks with general topologies
- Distributed coverage of nonconvex environments
- Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
- Complete distributed coverage of rectilinear environments
- Unifying Geometric, Probabilistic, and Potential Field Approaches to Multi-robot Coverage Control
- The giving tree: Constructing trees for efficient offline and online multi-robot coverage
- Sectorial coverage control with load balancing in non-convex hollow environments
This page was built for publication: Approximation algorithms for distributed multi-robot coverage in non-convex environments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3381981)
