CS Paper Radar

TRACE: Coverage Path Planning for Unknown Environments Using Hierarchical Coverage Tree

Zongyuan Shen, Haodong Liu, Gao Wang, Shancheng Zhao, Dehua Zhou, Yaming Ou, Zhongqiang Ren, Yikui Zhai, C. L. Philip Chen

cs.RO ·submitted 2026-09-18 13:50 UTC · v1

Abstract

This paper presents a novel online coverage path planning (CPP) algorithm, called TRACE, for real-time coverage of unknown environments. TRACE is built upon a hierarchical coverage tree that provides a global representation of the evolving connectivity of the uncovered space. As the environment is incrementally revealed and covered, newly discovered obstacles and covered cells may fragment the remaining uncovered space into disconnected regions. TRACE recursively expands the corresponding tree nodes to explicitly represent these regions and organize them for subsequent coverage planning. Based on the updated tree, an incremental global tour is maintained to guide the coverage process. TRACE locally refines only the affected portions while preserving the visiting order of unchanged regions, thereby reducing the computational burden of global replanning and maintaining a consistent coverage progression. Guided by the global tour, a local planner generates back-and-forth coverage paths and switches to global-tour-aware planning to efficiently complete the target regions. Theoretical analysis establishes the computational complexity and complete coverage property of TRACE, and derives an approximation bound for the incremental global tour refinement. The performance of TRACE is evaluated through extensive high-fidelity simulations and real-robot experiments using a mobile robot. Comparative evaluations against six existing CPP methods demonstrate significant improvements in coverage time, path length, overlap ratio, and number of turns.

Closest papers

Nearest neighbours by meaning across the whole index.

A Hierarchical Coverage Path Planning Algorithm for Unknown Environments

cs.RO ·2026-09-11 ·Zongyuan Shen, Haodong Liu, Gao Wang, Hongbin Ma, Yaming Ou +2 more
similarity 0.85
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.

0.26

Distributed area coverage path planning subject to the inclusion of a headland path

cs.RO ·2026-10-11 ·Mogens Plessen
similarity 0.69
Abstract · 9 pages, 8 figures

A deterministic method for the problem of distributed area coverage path planning subject to the inclusion of a headland path is presented. Given a, in general, non-convex area to be covered that may, in general, include obstacle areas, multiple robots, at least one robot depot, and constraints on each machinery such as a working width, work capacity limits, travel capacity limits, nonholonomic dynamical constraints and, possibly, a robot start and end depot assignment, distributed paths for each machinery are calculated that collectively enable full area coverage. Variations are discussed, in particular, a scenario where unconstrained depots assignment can attain a global optimal solution to the problem. The importance of inclusion of a headland path for area coverage, as well as the benefits in comparison to an alternative Boustrophedon-pattern based approach are highlighted.

0.41

Obstacle-Aware Autonomous Coverage and Navigation for Outdoor Robots

cs.RO ·2026-09-01 ·Leonardo Gargani, Matteo Frosi, Matteo Matteucci
similarity 0.66
Abstract

Long-duration outdoor coverage with autonomous platforms remains challenging beyond classical planning: deployments face localization drift in open spaces, obstacles in cluttered sites, controller feasibility in turn-heavy maneuvers, and persistent autonomy with energy management. We propose a unified ROS 2 architecture for single-robot outdoor coverage: a dual-antenna RTK-GNSS fused in an EKF keeps both position and heading accurate across long missions; three controller-aware refinements extend a mature coverage planner; a Nav2-based behavior-tree mission executive coordinates multi-goal execution, layered recovery, cost-aware goal management, and autonomous docking for return-to-charge. In real-world trials across five outdoor areas with varying geometries and obstacle densities, the robot completed every coverage route, sweeping 93.1% to 96.1% of the planned coverage area.

0.29

Asymmetric Scout-Worker Reconnaissance for Route Validation in Unknown Environments

cs.RO ·2026-09-29 ·Kashif Khurshid Noori, Jaskrit Singh, Athanasios Ch. Kapoutsis, Jing Xiao, Constantinos Chamzas
similarity 0.66
Abstract

This paper studies asymmetric scout-worker reconnaissance in unknown environments, where a small, agile autonomous scout explores routes for a larger worker robot that must visit an ordered sequence of goal locations. Because the scout has a smaller footprint and greater mobility, a scout-traversable route may be infeasible for the worker; worker feasibility must therefore be inferred from scout observations. This setting is not explicitly addressed by existing exploration and replanning methods, which typically assume a single traversability model and seek optimal paths for the same robot performing the exploration. We introduce a symbiotic scout-based framework that exploits the scout's superior mobility to explore only the portions of the unknown environment needed to identify worker-feasible path segments connecting the ordered goals. Evaluations in simulated and real-world settings demonstrate that the proposed approach validates feasible routes, repairs blocked segments with validated worker-feasible detours, and substantially reduces scout travel compared to baseline exploration and planning methods. A real-world indoor deployment further demonstrates the scout navigating narrow corridors to identify a worker-feasible route.

0.16

Inspection-SPARS: Task-Oriented Sparse Roadmaps for Inspection Planning

cs.RO ·2026-09-28 ·Adir Morgan, Oren Salzman, Kiril Solovey
similarity 0.65
Abstract

Inspection planning seeks a minimum-length collision-free robot tour that observes a given set of points of interest (POIs). Sampling-based methods reduce this continuous problem to a graph inspection planning (GIP) problem over a discrete roadmap, which is then solved using combinatorial solvers. Dense roadmaps capture diverse inspection viewpoints and motion shortcuts, and thus admit higher-quality solutions, but they induce large combinatorial search spaces on which state-of-the-art GIP solvers struggle to find good solutions within practical time budgets. Roadmap sparsification---restructuring a dense roadmap into a compact representation that preserves connectivity and path lengths---can alleviate this burden. However, existing sparsification approaches are either agnostic to the underlying inspection task, or strive to ensure coverage of the POIs without accounting for the quality of the resulting inspection plan. We present Inspection-SPARS, which is, to our knowledge, the first inspection-roadmap sparsifier with POI coverage and path-quality guarantees relative to the dense roadmap. To this end, we generalize the SPARS framework, a popular task-agnostic sparsifier, from purely geometric criteria to task-oriented ones, introducing an inspection-aware vertex admission mechanism that treats POI coverage as a first-class sparsification criterion alongside connectivity and path quality. Experiments in realistic 3D environments show that Inspection-SPARS reduces vertex and edge counts by 4-8x while preserving coverage, allowing the GIP solver to compute tours up to 25% shorter than with the dense roadmap or state-of-the-art inspection roadmap. More broadly, Inspection-SPARS shows that sparsification can be made task-aware without sacrificing guarantees on solution quality.

0.16

TASG-Explore: Traversability-Aware Sector-Guided Exploration for Ground Robot on Uneven Terrain

cs.RO ·2026-09-08 ·Shaocong Wang, Shiliang Shao, Ting Wang, Guangjie Han, Lianqing Liu
benchmark similarity 0.65
Abstract · 20 pages, 17 figures

Autonomous exploration on uneven terrain requires ground robots to balance exploration efficiency, coverage completeness, and terrain safety. Detailed tsrrain reasoning improves local reliability but can slow large-scale exploration, whereas coarse region guidance expands quickly in open areas but can miss narrow passages and irregular traversable boundaries. To address this challenge, this paper presents TASG-Explore, a traversability-aware sector-guided exploration framework for ground robots. The framework first performs hierarchical traversability analysis using variable-voxel ground fitting and adaptive 8-bit obstacle encoding. It then splitting cost map into sectors, incrementally updates sector clusters, extracts terrain-coupled frontier viewpoints, and maintains a dynamic topological roadmap with unknown topological hypotheses. Finally, a sector-guided planner selects region targets and inserts local viewpoints to generate efficient exploration routes. Benchmark experiments in diverse challenging environments, including caves, forests, and rugged hills, show that TASG-Explore achieves the best overall performance among six representative state-of-the-art planners. The proposed traversability analysis improves processing efficiency by 6.3 times while maintaining high accuracy, and the exploration planner improves exploration efficiency by 51% and increases coverage by up to 2.95 times in rugged hill scene. Large-scale real-world experiments further demonstrate the practical value of the proposed method.

0.24

PushAround: Collaborative Path Clearing via Physics-Informed Hybrid Search

cs.RO ·2026-10-26 ·Zili Tang, Zongyuan Li, Zishao Qiao, Meng Guo
top venue similarity 0.64
Abstract · Accepted for publication in IEEE Robotics and Automation Letters (RA-L). 8 pages, 11 figures. Supplementary video and evaluation records are…

Large vehicles in cluttered environments are often blocked by movable obstacles, motivating mobile robot teams to clear traversable corridors. Navigation Among Movable Obstacles (NAMO) approaches often abstract obstacle displacements while neglecting robot dimensions, obstacle mass, contact geometry and forces, yielding physically infeasible plans. PushAround is a physics-informed hybrid search that couples geometric connectivity reasoning with short-horizon simulation to construct executable clearing plans. Repeated W-clearance connectivity graph (WCCG) queries expose frontier gaps requiring widening and rank them by estimated downstream costs. The search generates direct or recursive pushing candidates, selecting obstacles, directions, contacts and forces, and admits physics-evaluated candidates. Numerical experiments validate WCCG against standard connectivity checks and demonstrate scaling to denser clutter and teams of up to four robots, with robustness to simulated execution-side physical-parameter mismatch.

0.43

Coverage Path Planning for Redundant Manipulators using Generalized Spanning Trees

cs.RO ·2026-09-08 ·Raksi Kopo, Kostas J. Kyriakopoulos
published similarity 0.61
Abstract · Accepted for publication in IROS 2026

Surface coverage with task-redundant manipulators is challenging because each surface point may admit multiple inverse kinematics (IK) solutions, and configuration choices strongly affect motion quality. This paper extends the classical Spanning Tree Coverage (STC) method to redundant manipulators through offline and online Joint Spanning Tree Coverage (JSTC) algorithms. Offline JSTC samples multiple Inverse Kinematics (IK) solutions per grid cell and formulates the problem as a Generalized Minimum Spanning Tree (GMST), selecting one configuration per cell and tracing the resulting tree to obtain a non-revisiting coverage path. Online JSTC incrementally expands and backtracks a spanning tree with feasibility and cost evaluation while handling dynamic grid updates. Simulation results show that offline JSTC reduces computation time, reconfigurations, and joint motion compared to other methods, while online JSTC achieves fast per-step planning in dynamic scenarios.

0.44