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 · N/A · 2026
Framework
N/A
License
N/A
Stars
N/A
Summary
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.
Abstract Summary
Key Points
- 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
Problem Description
As shown in Fig. 1 , consider a mobile robot equipped with: A range detector (e.g., LiDAR) to detect obstacles within its field of view and map the environment. A localization device (e.g., IMU) to provide position information of the robot. A coverage device or sensor (e.g., cleaning brush) to perform the task (e.g., floor cleaning).
Let $\mathcal{X}\subset\mathbb{R}^{2}$ be the initially unknown area whose boundary is defined either by a hard border (e.g., a wall) or a soft barrier (e.g., user-defined buffer zone).
TRACE Algorithm
This section presents the details of the proposed TRACE algorithm, which adaptively updates the coverage path as the environment is revealed through onboard sensing. An overview of the TRACE algorithm is shown in Fig. 1 . During navigation, the symbolic map is continuously updated according to sensor measurements and coverage progress (Sec. IV-A ).
Based on the updated map, a hierarchical coverage tree is incrementally constructed to represent the remaining coverage regions and their connectivity changes (Sec. IV-B ).
Algorithm Analysis
This section presents a formal analysis of both computational complexity and theoretical guarantees. Hierarchical coverage tree update has a time complexity of $O(/\mathcal{T}/)$. As described in Alg. 1 , the affected leaf-node set $\Delta\mathcal{N}_{\mathrm{leaf}}$ is first identified by mapping each changed cell $\tau_{j}\in\Delta\mathcal{T}$ to its corresponding leaf node through the leaf index map $\Psi$.
Since each lookup of $\Psi(\tau_{j})$ takes constant time, this step requires $O(/\Delta\mathcal{T}/)$.
Sources and Demonstrations
Figures are reproduced from Shen et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.
Related Papers
A Browser-Native Digital Test Range for Benchmarking 4D Ocean-Glider Planning Algorithms
Edward Holmberg, Elias Ioup, Mahdi Abdelguerfi
Repeated in-situ evaluation of ocean-glider planners requires scarce vehicles, operators, deployment and recovery resources, and ocean conditions that cannot be reset for competing algorithms.
Aim Short to Reach Far: Your Frozen World Model Can Plan Better Than You Think
Xvyuan Liu, Jianjie Fang, Chen Gao et al.
Planners built on visual world models commonly score each predicted outcome by its distance to the encoded goal image. We show that this target can limit control even with exact dynamics and globally optimal short-horizon search: reaching a goal may require actions that initially move away from it.
Beyond Episodic Evaluation: Memory Architectural Bottlenecks in Sequential Embodied Question Answering
Zikui Cai, Kaushal Janga, Tan Dat Dao et al.
Embodied question answering (EQA) is traditionally evaluated under an episodic formulation, where agents solve each task independently and reset internal state between episodes.
Collective Learning for Unified Robotic Manipulation via Predictive Dynamics Adaptation
Shaocheng Liu, Yuan Meng, Zhenshan Bing et al.
Learning a collective policy for state-based Cartesian manipulation across diverse robotic embodiments presents a fundamental challenge due to embodiment-dependent transition dynamics.