Approximation algorithms for distributed multi-robot coverage in non-convex environments

DOI10.1007/978-3-030-66723-8_20zbMATH Open1469.68134arXiv2005.02471OpenAlexW3167897096MaRDI QIDQ3381981FDOQ3381981

Ahmad Bilal Asghar, Stephen Smith, Armin Sadeghi

Publication date: 20 September 2021

Published in: Algorithmic Foundations of Robotics XIV (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2005.02471

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

zbMATH Keywords

sensor networksdistributed robots

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Artificial intelligence for robotics (68T40)

Cites Work

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
• Planning Algorithms
• Title not available (Why is that?)
• Local Search Heuristics for k-Median and Facility Location Problems
• Local-Search based Approximation Algorithms for Mobile Facility Location Problems: (Extended Abstract)
• Approximating \(k\)-median via pseudo-approximation
• Coverage problems in sensor networks: a survey

Cited In (6)

• Computing Convex Coverage Sets for Faster Multi-objective Coordination
• Unifying Geometric, Probabilistic, and Potential Field Approaches to Multi-robot Coverage Control
• Distributed sweep coverage algorithm of multi-agent systems using workload memory
• Complete distributed coverage of rectilinear environments
• Sectorial coverage control with load balancing in non-convex hollow environments
• Efficient Boustrophedon multi-robot coverage: An algorithmic approach

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)