SCOPE: Skeleton Graph-Based Computation-Efficient Framework for Autonomous UAV Exploration

Kai Li; Shengtao Zheng; Linkun Xiu; Yuze Sheng; Xiao-Ping Zhang; Dongyue Huang; Xinlei Chen

cs.ROFeb 26, 2026

SCOPE: Skeleton Graph-Based Computation-Efficient Framework for Autonomous UAV Exploration

Authors: Kai Li, Shengtao Zheng, Linkun Xiu, Yuze Sheng, Xiao-Ping Zhang, Dongyue Huang, Xinlei Chen

Organizations: Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China · School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639956

Abstract

Autonomous exploration in unknown environments is key for mobile robots, helping them perceive, map, and make decisions in complex areas. However, current methods often rely on frequent global optimization, suffering from high computational latency and trajectory oscillation, especially on resource-constrained edge devices. To address these limitations, we propose SCOPE, a novel framework that incrementally constructs a real-time skeletal graph and introduces Implicit Unknown Region Analysis for efficient spatial reasoning. The planning layer adopts a hierarchical on-demand strategy: the Proximal Planner generates smooth, high-frequency local trajectories, while the Region-Sequence Planner is activated only when necessary to optimize global visitation order. Comparative evaluations in simulation demonstrate that SCOPE achieves competitive exploration performance comparable to state-of-the-art global planners, while reducing computational cost by an average of 86.9%. Real-world experiments further validate the system's robustness and low latency in practical scenarios.

Figures & tables

Fig. 1: System overview of the proposed SCOPE framework. The architecture integrates two subsystems: (1) Skeleton Graph Maintenance & Implicit Region Generation (Blue Blocks): The system constructs a skeleton graph and activates nodes associated with frontiers. Using geometric ray probes for depth estimation, activated nodes are clustered into Implicit Unknown Regions—abstract volumetric representations where clustered nodes likely lead to the same contiguous unknown area. (2) Skeleton-Based Hierarchical Planning (Yellow Blocks): The UAV searches for a proximal target in its vicinity. If found (Exist), the Proximal Planner executes rapid local exploration; otherwise (Not Exist), the Region-Sequence Planner optimizes a global sequence over implicit sub-regions to guide the UAV to the next strategic area.

Fig. 2: Region analysis: probes are cast from the frontiers associated with activated nodes into unknown space, and nodes are clustered based on their intersection patterns and spatial proximity.

Fig. 3: A schematic diagram of the region-sequence planner. During region-guided planning, it assumes exploration proceeds only through currently activated nodes into unknown regions, while inter-regional costs are computed on the skeletal graph.

Environment	Method	Exploration Time (s)		Computational Cost ( $ms$ )		Flight Speed ( $m/s$ )		Path Length ( $m$ )		Coverage ( $m^{3}$ )
		Avg	Std	Avg	Std	Avg	Std	Avg	Std	Avg	Std
Complex Office	FUEL	277.31	16.17	34.15	4.19	1.35	0.03	375.02	29.34	1730.14	9.35
	FAEP	208.93	7.02	39.46	4.51	1.32	0.05	275.98	12.96	1738.12	7.18
	RACER	252.33	21.64	127.62	16.29	1.60	0.02	405.06	48.13	1721.79	8.49
	FALCON	171.97	7.28	147.96	20.18	1.65	0.03	284.82	18.43	1734.12	6.89
	Proposed	158.24	9.78	7.71	0.73	1.88	0.03	297.92	37.62	1727.61	9.28

TABLE I: Comparative Results of All Methods

Fig. 5: Visualization of exploration paths and velocity for four algorithms in the Complex Office environment, corresponding respectively to (a) FUEL, (b) FAEP, (c) RACER, (d) FALCON, (e) Proposed.

Fig. 6: Boxplot of computation time per planning iteration (log scale).

Method Variant	Exploration Time ( $s$ )	Computational Cost ( $ms$ )
w/o PIR	236.28	5.76
w/o RSP	269.18	5.15
w/o PP	261.89	22.98
w/o SG	225.17	43.67
Proposed	228.79	5.70

TABLE II: Ablation Study Results Compared to the Initial Model

Module	Avg. Time ( $ms$ )	Percentage (%)
Skeleton Update	3.06	53.7%
Region Analysis	1.08	18.9%
Planner(RSP/PP)	0.57 (14.09 / 0.46)	10.0%
Trajectory Optimization	0.99	17.4%
Total System Latency	5.70	100.0%

TABLE III: Breakdown of Computational Time per Control Cycle

Fig. 7: Exploration results in real-world environments: (a) is a laboratory with irregular obstacles. (b) is a cluttered office. The occupancy maps obtained in each case are displayed at the bottom.

Fig. 8: The UAV platform used in real-world experiments.

Explore similar work

Semantic-Aware Autonomous Exploration for UAVs in Unknown Indoor Environments
Jun 21, 2026Duc-Thien Nguyen, Ngoc Minh Do, Xiem HoangVan +1Robot Navigation Informative Path Planning
University of Engineering and Technology, Vietnam National University, 10000, Hanoi, Vietnam. · School of Information Science, Japan Advanced Institute of Science and Technology, Nomi, 923-1211, Ishikawa, Japan.
C $^2$ -Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration
Mar 8, 2026Xinlu Yan, Mingjie Zhang, Yuhao Fang +5Multi-Robot Exploration Multi-Robot Task Allocation
School of Intelligence Science and Engineering, Harbin Institute of Technology, Shenzhen, Guangdong, China · Robotics and Autonomous Systems Thrust, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, China · Department of Mechanical and Energy Engineering, Southern University of Science and Technology, Shenzhen, Guangdong, China
Palm-sized Omnidirectional Vision-Based UAV Exploration with Sparse Topological Map Guidance
May 8, 2026Zirui Wang, Xinjia Luo, Haotian Sun +3Robot Navigation UAV Navigation
Department of Mechanical and Energy Engineering, Southern University of Science and Technology, Shenzhen, 518055, China

Jun 21, 2026J/K move · Enter open · S save

Semantic-Aware Autonomous Exploration for UAVs in Unknown Indoor Environments

Duc-Thien Nguyen, Ngoc Minh Do, Xiem HoangVan, Thanh Nguyen Canh

University of Engineering and Technology, Vietnam National University, 10000, Hanoi, Vietnam. · School of Information Science, Japan Advanced Institute of Science and Technology, Nomi, 923-1211, Ishikawa, Japan.

Robot Navigation Informative Path Planning UAV Navigation Sampling-Based Motion Planning

Open paper AskPDF arXiv

Autonomous exploration in unknown environments requires unmanned aerial vehicles (UAVs) to efficiently generate informative trajectories while simultaneously constructing accurate maps. Although many existing exploration methods rely on geometric information, they often lack semantic awareness, resulting in suboptimal exploration efficiency and limited environmental understanding. To address this limitation, this paper proposes a semantic-aware exploration framework that adds semantic information to a roadmap-based exploration strategy. The proposed method builds on the Dynamic Exploration Planner (DEP), which incrementally constructs a Probabilistic Roadmap (PRM), and augments this roadmap with a semantic layer. A semantic reward function is introduced to prioritize regions containing meaningful objects and structures, enabling the UAV to focus on areas with higher information value. Furthermore, the roadmap is continuously updated to support efficient frontier selection and path planning during exploration. The proposed framework is implemented in ROS Noetic and Gazebo using an RGB-D sensor for simultaneous acquisition of geometric and semantic information. Experimental results in multiple simulated environments demonstrate that the proposed approach achieves exploration coverage rates between 90% and 94% while reducing exploration time and travel distance compared with conventional geometry-based exploration methods.

Abstract

Explore similar work

Semantic-Aware Autonomous Exploration for UAVs in Unknown Indoor Environments

C2^22-Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration

Palm-sized Omnidirectional Vision-Based UAV Exploration with Sparse Topological Map Guidance

C $^2$ -Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration