A Hierarchical Coverage Path Planning Algorithm for Unknown Environments

• URL: http://arxiv.org/abs/2609.12595v1
• Date: Fri, 11 Sep 2026 08:47:49 GMT
• Title: A Hierarchical Coverage Path Planning Algorithm for Unknown Environments
• Abstract summary: This paper presents an online coverage path planning algorithm for unknown environments.<n>During navigation, the initially unknown search area is progressively decomposed into disconnected subareas.<n>A global coverage tour is maintained and updated online by prioritizing newly generated child subareas.
• Score: 6.815877243940533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents an online coverage path planning algorithm for unknown environments. During navigation, the initially unknown search area is progressively decomposed into disconnected subareas as new obstacle information is acquired and coverage proceeds. These subareas are organized in an incrementally constructed decomposition tree that preserves their hierarchical parent-child relationships. Based on this tree, a global coverage tour is maintained and updated online by prioritizing newly generated child subareas according to their exploration states and distances from the robot. A local planner then generates coverage motions within each selected subarea, allowing the robot to adapt its trajectory as the environment is gradually revealed. Its performance is evaluated via high-fidelity simulations in complex scenarios. The results show improved coverage efficiency in terms of path length and overlap ratio in comparison to three baseline algorithms.

Related papers

• Explore From Sketch: Accelerating UAV Exploration in Large-scale Environments with Prior Maps [20.559950853029]
  This paper presents a novel exploration framework that leverages sparse, unaligned, and even discrepant 2D prior maps for LiDAR-based UAV exploration.<n> Benchmark evaluations reveal up to 34.2% improvement in exploration efficiency and 37.9% reduction in flight distance compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-06-10T06:30:29Z)
• Accelerating Robot Path Planning via Connectivity-Preserving Region Proposal Network [5.81838331663612]
  Mobile robot path planning methods are often constrained by vast search spaces, resulting in latency in samplingbased algorithms.<n>We present the Connectivity- Preserving Region Proposal Network (CP-RPN), a segmentationguided model designed to predict compact and topologically connected candidate regions.
  arXiv  Detail & Related papers  (2026-05-27T11:59:03Z)
• Hierarchical Informative Path Planning via Graph Guidance and Trajectory Optimization [10.020847331719398]
  We study informative path planning (IPP) with travel budgets in cluttered environments, where an agent collects measurements of a latent field modeled as a Gaussian process (GP) to reduce uncertainty at target locations.<n>We propose a hierarchical framework with three stages: (i) graph-based global planning, (ii) segment-wise budget allocation using geometric and kernel bounds, and (iii) spline-based refinement of each segment with hard constraints and obstacle pruning.
  arXiv  Detail & Related papers  (2026-01-23T23:27:20Z)
• Comparison of Path Planning Algorithms for Autonomous Vehicle Navigation Using Satellite and Airborne LiDAR Data [2.979579757819132]
  This work provides a comparative evaluation of mainstream and well-established path planning algorithms.<n>For 2D road-map navigation, A*, Dijkstra, RRT*, and NIACO are tested on the DeepGlobe satellite dataset.<n>For 3D road-map path planning, 3D A*, 3D Dijkstra, RRT-Connect, and NIACO are evaluated using the Hamilton airborne LiDAR dataset.
  arXiv  Detail & Related papers  (2025-07-08T11:15:21Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning [17.69984142788365]
  Coverage path planning ( CPP) is the problem of finding a path that covers the entire free space of a confined area. We investigate how suitable reinforcement learning is for this challenging problem. We propose a computationally feasible egocentric map representation based on frontiers, and a novel reward term based on total variation.
  arXiv  Detail & Related papers  (2023-06-29T14:32:06Z)
• Autonomous search of real-life environments combining dynamical system-based path planning and unsupervised learning [0.0]
  This study develops a novel applied framework for real-world applications of chaotic coverage path planners.<n>It provides techniques for effective obstacle avoidance, chaotic trajectory dispersal, and accurate real-time coverage calculation.<n>The performance of this application was comparable to that of a conventional optimal path planner.
  arXiv  Detail & Related papers  (2023-05-03T00:09:31Z)
• Systematic Comparison of Path Planning Algorithms using PathBench [55.335463666037086]
  Path planning is an essential component of mobile robotics. Development of learning-based path planning algorithms has been experiencing rapid growth. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future path planning algorithms.
  arXiv  Detail & Related papers  (2022-03-07T01:52:57Z)
• Large-scale Autonomous Flight with Real-time Semantic SLAM under Dense Forest Canopy [48.51396198176273]
  We propose an integrated system that can perform large-scale autonomous flights and real-time semantic mapping in challenging under-canopy environments. We detect and model tree trunks and ground planes from LiDAR data, which are associated across scans and used to constrain robot poses as well as tree trunk models. A drift-compensation mechanism is designed to minimize the odometry drift using semantic SLAM outputs in real time, while maintaining planner optimality and controller stability.
  arXiv  Detail & Related papers  (2021-09-14T07:24:53Z)
• PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms [59.3879573040863]
  Path planning is a key component in mobile robotics. Few attempts have been made to benchmark the algorithms holistically or unify their interface. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future path planning algorithms.
  arXiv  Detail & Related papers  (2021-05-04T21:48:18Z)
• GANav: Group-wise Attention Network for Classifying Navigable Regions in Unstructured Outdoor Environments [54.21959527308051]
  We present a new learning-based method for identifying safe and navigable regions in off-road terrains and unstructured environments from RGB images. Our approach consists of classifying groups of terrain classes based on their navigability levels using coarse-grained semantic segmentation. We show through extensive evaluations on the RUGD and RELLIS-3D datasets that our learning algorithm improves the accuracy of visual perception in off-road terrains for navigation.
  arXiv  Detail & Related papers  (2021-03-07T02:16:24Z)
• Risk-Averse MPC via Visual-Inertial Input and Recurrent Networks for Online Collision Avoidance [95.86944752753564]
  We propose an online path planning architecture that extends the model predictive control (MPC) formulation to consider future location uncertainties. Our algorithm combines an object detection pipeline with a recurrent neural network (RNN) which infers the covariance of state estimates. The robustness of our methods is validated on complex quadruped robot dynamics and can be generally applied to most robotic platforms.
  arXiv  Detail & Related papers  (2020-07-28T07:34:30Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.