Energy-Efficient Multi-Robot Coverage Path Planning of Non-Convex Regions of Interests

Coverage path planning (CPP) is a fundamental problem in robot motion planning, whose aim is to produce robot trajectories that provide complete coverage of target workspaces while minimizing task-specific objectives such as path length, overlap, number of turns, and energy consumption. CPP has widespread applications in cleaning, inspection, mapping, agriculture, manufacturing, surveillance, demining, and environmental monitoring. Although classical CPP has been extensively studied, recent advances have extended CPP beyond single-robot settings to multi-robot systems, complex 3D environments, constrained platforms, learning-based coverage planning, and visual coverage tasks. This paper presents a comprehensive survey of 125 representative works published primarily between 2015 and 2026, while presenting the evolution of recent developments in light of the classical CPP methods published before 2015. The CPP methods are organized into six main categories: single-robot CPP, multi-robot CPP, 3D CPP, constrained CPP, learning-based CPP, and visual CPP. For each category, the review summarizes the main planning formulations, representative algorithms, strengths, and limitations. In addition, the review analyzes how environmental knowledge, workspace geometry, robot constraints, sensing objectives, and coordination requirements shape the CPP problem. The survey further discusses open challenges in scalable online planning, multi-robot coordination, 3D and visual coverage, unified platform-constrained and resource-aware coverage, and learning-enhanced coverage. Thus, the survey provides a structured overview of recent CPP developments and future research directions.

Autonomous robot navigation requires the rapid generation of obstacle-free regions for trajectory planning. However, existing corridor generators struggle to meet real-time, sensor-rate computational constraints. To resolve this bottleneck, we introduce PathCover, a framework driven by RISP; a novel randomized algorithm that constructs convex polytopes directly from raw point cloud data in expected linear time under a mild probabilistic elimination condition. PathCover generates sequences of overlapping, obstacle-free polytopes that safely constrain downstream MPC and trajectory optimization. We mathematically guarantee that the algorithm terminates in finite steps while ensuring continuous progress along any obstacle-free reference path. Extensive benchmarks on synthetic and real-world LiDAR datasets demonstrate an order-of-magnitude speedup over state-of-the-art methods while maintaining comparable corridor volumes. The complete pipeline is validated via high-fidelity quadrotor simulations and physical deployment on a quadrupedal robot navigating constrained environments using live LiDAR perception.

Autonomous drone swarms deployed for surveillance, environmental monitoring, and infrastructure inspection must maintain reliable coverage of critical assets despite robot failures. This requires multicoverage: each asset must be observed by multiple robots for redundancy, with coverage requirements varying by asset importance. While recent work has solved the centralized problem optimally using integer programming, practical deployments face constraints that demand distributed solutions: robots operate with limited communication ranges, onboard computation restricts global planning, and partial system failures must not cause mission abort. We present a distributed multicoverage algorithm for robot swarms operating with local sensing, local communication, and no global coordination.