A Hierarchical Coverage Path Planning Algorithm for Unknown Environments

I. INTRODUCTION

• Unknown environments prevent complete advance planning, so robots must update coverage trajectories from sensor information while discovering regions and avoiding obstacles.In complex environments, inefficient decisions can produce dead ends, isolated uncovered regions, repeated traversal, and excessive overlap.Source: §I · p. 1
• Local decision rules can miss the broader structure of remaining coverage, risking dead ends, isolated uncovered regions, or repeated traversal.Checking whether a candidate motion disconnects uncovered space still uses a limited local neighborhood.Source: §I · p. 1
• The proposed method combines online decomposition, a global tour, and local coverage, organizing newly separated subareas in a tree that preserves parent-child relationships.The global planner prioritizes newly generated descendants by exploration state and distance from the robot.Source: §I · p. 1
• The two contributions are a hierarchical decomposition framework and a lightweight tree-based tour strategy, with local coverage in the selected subarea.The method is evaluated through simulation.Source: §I · p. 1

II. RELATED WORK

• The section refers readers to a comprehensive CPP review [9] and notes methods for 3D, multi-robot, curvature-constrained, tethered, and energy-constrained coverage –.Source: §II · p. 2
• Spanning-tree, spiral, backtracking, brick-and-mortar, and neural-network methods generate coverage paths through tree traversal, obstacle following, backtracking, traversability preservation, or cell-level activity –.The neural activity landscape can guide the robot toward distant uncovered regions when no local target is available.Source: §II · p. 2
• Directional priorities, multiscale potential surfaces, and multi-objective rewards guide subsequent coverage targets in BA∗, ε∗, and predator-prey methods –.The ε∗ method uses higher-level potential surfaces in dead ends; the reward method considers distance, smoothness, and uncovered-boundary following.Source: §II · p. 2
• Connectivity-aware hierarchical planning uses a global graph and TSP-based tour, while C∗ builds a sparse covering graph for nonlocal guidance and coverage-hole handling,.The former switches between exploratory coverage in partially observed subareas and optimized paths in explored regions.Source: §II · p. 2

III. PROPOSED ALGORITHM

• The initially unknown search area A is discretized into cells T, whose states are updated online from onboard sensor measurements.Source: §III · p. 2
• The tiling distinguishes obstacle, free, and unknown cells, with free cells further divided into covered and uncovered subsets.Source: §III · p. 2
• The method has online space decomposition, global tour planning, and local coverage components, exploiting the hierarchy that emerges during online coverage for task sequencing.Source: §III · p. 2

A. Online Space Decomposition

• The whole search area begins as the decomposition tree’s root, and recursive searches assign connected neighboring uncovered cells to subareas.Newly observed obstacles and covered cells can divide the target region into disconnected components.Source: A. Online Space Decomposition · p. 2
• When a target splits into disconnected components, each becomes a child node, preserving the region’s parent-child history in the tree.Source: A. Online Space Decomposition · p. 2
• Only leaf nodes are active coverage tasks; a leaf is exploring if it has an uncovered free cell adjacent to unknown space, otherwise it is explored.The tree expands until all active leaves are covered.Source: A. Online Space Decomposition · p. 2

B. Global Coverage Tour Planning

• Explored children precede exploring children, and children in the same state are ordered by increasing Euclidean distance from the robot.Distance is measured from the robot position to each subarea's representative position.Source: B. Global Coverage Tour Planning · p. 3
• When the target decomposes, its ordered children replace it in the tour, prioritizing descendants before other branches.A completed target without further decomposition is removed, and the first remaining node becomes the next target.Source: B. Global Coverage Tour Planning · p. 3
• The hierarchical update follows the structure revealed during coverage without repeatedly globally optimizing all remaining subareas.Source: B. Global Coverage Tour Planning · p. 3

C. Local Coverage Path Planning

• In an exploring subarea, the robot greedily selects a nearby uncovered cell by directional priority, covering visited cells while discovering new environmental information.Visited cells are marked covered, producing a back-and-forth coverage pattern.Source: C. Local Coverage Path Planning · p. 3
• If new mapping divides the remaining uncovered region into disconnected components, the current node is expanded and the global tour is updated.Source: C. Local Coverage Path Planning · p. 3
• For an explored subarea, the planner computes a shortest coverage path from the robot's position through remaining uncovered cells to a designated target cell.Source: C. Local Coverage Path Planning · p. 3
• Global and local planning repeat until the global tour is empty, indicating that no uncovered subarea remains.Source: C. Local Coverage Path Planning · p. 3

D. Time Complexity Analysis

• For L child subareas, tree insertion costs O(L), distance evaluation O(L), and sorting O(L log L); transition-path search costs O(|Tf|^2).The transition path is computed with A* over currently known free cells in the worst case.Source: D. Time Complexity Analysis · p. 3
• Local decisions in exploring subareas cost O(1) each, while coverage planning in an explored target subarea has worst-case cost O(|Atarget|^2).Source: D. Time Complexity Analysis · p. 3
• O(|Tf|^2) dominates the worst-case time complexity of one planning update under the stated size relationships among known cells, target cells, and child subareas.The passage states |Tf| ≥ |Atarget| and that L is generally much smaller than |Tf|.Source: D. Time Complexity Analysis · p. 3

IV. RESULTS AND DISCUSSION

• The authors attribute improved coverage efficiency to tracking disconnected subareas and using a global tour; TSP-based paths in explored subareas further minimize overlap and local coverage time.Source: §IV · p. 4
• Evaluation used four Gazebo scenes measuring 90m×90m, tiled 30×30, with a car-like robot starting at the bottom-left and using lidar with an 8m detection range.The simulated robot's maximum speed was 1m/s.Source: §IV · p. 4
• The proposed algorithm significantly improved path length and overlap ratio over ϵ∗, BINN, and PPCPP in the simulations.The comparison reports improvements across all metrics.Source: §IV · p. 4

• The method decomposes unknown search space into disconnected subareas, preserving parent-child relationships in a tree used to prioritize child areas by exploration state and robot distance.Source: §V · p. 4
• Adaptive local coverage planning lets the robot continuously update its trajectory as environmental information becomes available.Source: §V · pp. 4–5
• Simulation evaluations demonstrate the method's effectiveness in path length and overlap ratio.Source: §V · p. 5
• Future work proposes using the tree for multi-robot task allocation and coordination, and adapting decomposition to dynamic obstacles.Source: §V · p. 5