CAP: A Connectivity-Aware Hierarchical Coverage Path Planning Algorithm for Unknown Environments using Coverage Guidance Graph

Efficient coverage of unknown environments requires robots to adapt their paths in real time based on on-board sensor data. In this paper, we introduce CAP, a connectivity-aware hierarchical coverage path planning algorithm for efficient coverage of unknown environments. During online operation, CAP incrementally constructs a coverage guidance graph to capture essential information about the environment. Based on the updated graph, the hierarchical planner determines an efficient path to maximize global coverage efficiency and minimize local coverage time. The performance of CAP is evaluated and compared with five baseline algorithms through high-fidelity simulations as well as robot experiments. Our results show that CAP yields significant improvements in coverage time, path length, and path overlap ratio.

Authors

• Zongyuan Shen
• Burhanuddin Shirose
• Prasanna Sriganesh
• Matthew J. Travers

Keywords

• Motion planning
• Robot sensing systems
• Path planning
• Real-time systems
• Intelligent robots
• Coverage Path
• Coverage Path Planning
• Coverage Path Planning Algorithm
• Path Length
• Local Time
• Essential Information
• Global Efficiency
• High-fidelity Simulation
• Baseline Algorithms
• Local Coverage
• Online Operation
• Significant Improvement In Time
• Improvement In Length
• Efficient Coverage
• Predators
• Current Position
• Undirected
• Real-world Experiments
• Graph Construction
• Free Cells
• Traveling Salesman Problem
• Uncovered Areas
• Greedy Strategy
• Nearest Neighbor Algorithm
• Hamiltonian Path
• End Nodes
• Local Vicinity
• Environment Map
• Spanning Tree
• Activity Landscape
• Motion and Path Planning
• Unknown Environments