TRACE: Coverage Path Planning for Unknown Environments Using Hierarchical Coverage Tree
Authors: Zongyuan Shen, Haodong Liu, Gao Wang, Shancheng Zhao, Dehua Zhou, Yaming Ou, Zhongqiang Ren, Yikui Zhai, C. L. Philip Chen
Organizations: College of Information Science and Technology, Jinan University, Guangzhou 510632, China. · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China. · Global College, Shanghai Jiao Tong University, Shanghai 200240, China. · School of Electronics and Information Engineering, Wuyi University, Jiangmen 529000, China. · School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China.
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.
Figures & tables
Figure 1: Overview of the proposed TRACE algorithm.
Figure 2: Illustration of hierarchical coverage tree evolution and incremental coverage planning. (a) The entire unknown workspace is initially represented by the root node n11 . (b) As the environment is revealed and covered, the residual region of n11 is divided into three disconnected subareas, represented by child nodes n12 , n22 , and n32 . A global tour is then generated to guide their subsequent coverage. (c) With further environmental discovery and coverage progress, the residual region associated with n22 is further divided into two disconnected subareas, represented by child nodes n13 and n23 . The hierarchical coverage tree and global tour are updated accordingly.
Figure 3: Illustration of local target-cell selection and dead-end recovery. (a) The target cell is selected within the local vicinity according to the priority of neighboring laps, generating a back-and-forth coverage pattern. (b) When no candidate target cell is available in the local vicinity, the robot reaches a dead-end. The nearest free-uncovered cell adjacent to the covered area is then selected as the target, allowing the robot to escape the dead-end and resume coverage.
Figure 4: An Overview of the test scenarios for simulation experiments.
Figure 5: Office Scenario: Performance comparison with the baseline algorithms.
Figure 6: Warehouse Scenario: Performance comparison with the baseline algorithms.
Figure 7: Forest Scenario: Performance comparison with the baseline algorithms.
Figure 8: Mall 1 Scenario: Performance comparison with the baseline algorithms.
Figure 9: Mall 2 Scenario: Performance comparison with the baseline algorithms.
Figure 10: Mall 3 Scenario: Performance comparison with the baseline algorithms.
Figure 11: Coverage rate versus localization noise.
Figure 12: Real-Robot Experiment: Performance comparison with the baseline algorithms in a laboratory with complex obstacle layout.
Coverage path planning designs robot routes that systematically survey or act across an area or surface while limiting missed regions, overlap, and travel cost.
College of Information Science and Technology, Jinan University, Guangzhou 510632, China. · School of Automation, Beijing Institute of Technology, Beijing 100081, China. · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing 100049, China.
College of Information Science and Technology, Jinan University, Guangzhou 510632, China. · Department of Electrical and Computer Engineering, University of Connecticut, Storrs, CT 06269, USA. · Global College, Shanghai Jiao Tong University, Shanghai 200240, China. +3
Aug 6, 2026·Kunal S. Narkhede, Abhijeet M. Kulkarni, Guoquan Huang +1Robot Motion Planning
Department of Mechanical Engineering, University of Delaware, Newark, DE 19716, USA · Robotics Institute, Athena Research Center, Marousi, Greece; School of Mechanical Engineering, National Technical University of Athens, Greece; HERON–Center of Excellence in Robotics, Athens, Greece