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

Xinlu Yan; Mingjie Zhang; Yuhao Fang; Yanke Sun; Jun Ma; Youmin Gong; Boyu Zhou; Jie Mei

cs.ROMar 8, 2026

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

Authors: Xinlu Yan, Mingjie Zhang, Yuhao Fang, Yanke Sun, Jun Ma, Youmin Gong, Boyu Zhou, Jie Mei

Organizations: 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

Abstract

Efficient multi-UAV exploration under limited communication is severely bottlenecked by inadequate task representation and allocation. Previous task representations either impose heavy communication requirements for coordination or lack the flexibility to handle complex environments, often leading to inefficient traversal. Furthermore, short-horizon allocation strategies neglect spatiotemporal contiguity, causing non-contiguous assignments and frequent cross-region detours. To address this, we propose C $^2$ -Explorer, a decentralized framework that constructs a connectivity graph to decompose disconnected unknown components into independent task units. We then introduce a contiguity-driven allocation formulation with a graph-based neighborhood penalty to discourage non-adjacent assignments, promoting more contiguous task sequences over time. Extensive simulation experiments show that C $^2$ -Explorer consistently outperforms state-of-the-art (SOTA) baselines, reducing average exploration time by 43.1% and path length by 33.3%. Real-world flights further demonstrate the system's feasibility. The code will be released at https://github.com/Robotics-STAR-Lab/C2-Explorer

Figures & tables

Fig. 2: System Architecture of C 2 -Explorer. Within communication range, Drone 1 (the lowest-ID UAV) acts as a temporary host. It builds volumetric maps via LIO and extracts task units using a connectivity-aware representation. The host then solves a contiguity-regularized CVRP to generate per-UAV task sequences and disseminates them to the other drones. Each drone subsequently executes CP-guided planning for navigation. In parallel, drones exchange local map updates, states, and trajectories within communication range to reduce redundant exploration and support collision avoidance.

Fig. 3: Comparison of Connectivity-Aware and Traditional Task Representations. (a) and (c) contrast environmental modeling: (a) shows our connectivity graph modeling the topology of free and unknown spaces, while (c) uses uniform grid decomposition based on unknown voxel centroids. (b) and (d) compare task representation and allocation outcomes: (b) illustrates our connectivity-aware approach, treating spatially disjoint unknown regions as task units and excluding obstacle-enclosed areas. Conversely, (d)’s topology-agnostic approach merges disconnected regions and retains unreachable tasks.

Data	Explanation
$\mathbf{p}_{u,i}$	Unknown vertex position
$\mathcal{H}_{i}$	2D convex hull (if split)
$g_{i}$	Parent grid ID (if not split)
$\text{NUM}_{i}$	Number of unknown voxels
$\text{d}_{i}$	UAV ID

TABLE I: Data contained by a

\mathcal{T}_{i}

task unit.

Fig. 4: Benchmark Results of 4-UAV Decentralized Multi-UAV Exploration. Visualizations of the final executed flight trajectories for C 2 -Explorer, RACER, and FAME are presented across three complex scenarios: (a) Cubicle Office, (b) Open-plan Office, and (c) Octa Maze. Additionally, the rightmost column presents curves illustrating the evolution of the environment coverage ratio against exploration time for each method.

Scene	Drone Num	Method	Exploration Time (s)	Total Path Length (m)	Flight Vel. (m/s)
		RACER	128.1 $\pm$ 24.1	372.6 $\pm$ 57.9	1.84 $\pm$ 0.03
		FAME	142.6 $\pm$ 11.0	473.8 $\pm$ 35.9	1.71 $\pm$ 0.05
			73.1 $\pm$ 4.9	253.1 $\pm$ 14.4
	2	Ours	(↓42.9%)	(↓32.1%)	1.85 $\pm$ 0.01
		RACER	106.2 $\pm$ 8.5	408.0 $\pm$ 43.3	1.84 $\pm$ 0.03
		FAME	115.9 $\pm$ 14.8	560.5 $\pm$ 62.9	1.70 $\pm$ 0.05

TABLE II: Comparison of Exploration Performance

Method	Exploration Time (s)	Path Length (m)
Ours	43.0	243.9
No-Con	51.7	329.6
No-Graph	90.1	391.4

TABLE III: Ablation on core modules.

Fig. 5: Ablation on Communication Range . Exploration time and total path length of C 2 -Explorer under different communication ranges

r_{\mathrm{comm}}

Explore similar work

Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints
Jul 10, 2026Janghyun Cho, Jimmy Chiun, Guillaume Sartoretti +1Aerial Robotics Multi-Robot Exploration
1Dept. of Artificial Intelligence, Sogang University. · 2Dept. of Mechanical Engineering, College of Design and Engineering, National University of Singapore. · 3Dept. of Electronic Engineering, Sogang University.
Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration
Sep 1, 2026Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard +1Multi-Robot Exploration Multi-Robot Coordination
⋆Pˆole recherche, AMIAD, Palaiseau, France · †UI2S, ENSTA, IP Paris, Palaiseau, France
Centralized Multi-UAV Exploration and 3D Reconstruction Using Single-UAV Planners
Sep 30, 2026João Félix Mendes, Meysam Basiri, Rodrigo VenturaMulti-Robot Motion Planning 3D Reconstruction
Institute for Systems and Robotics, Department of Electrical and Computer Engineering, Instituto Superior Técnico, Lisboa, Portugal

Jul 10, 2026J/K move · Enter open · S save

Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints

Janghyun Cho, Jimmy Chiun, Guillaume Sartoretti, Changjoo Nam

1Dept. of Artificial Intelligence, Sogang University. · 2Dept. of Mechanical Engineering, College of Design and Engineering, National University of Singapore. · 3Dept. of Electronic Engineering, Sogang University.

Aerial Robotics Multi-Robot Exploration Multi-Robot Coordination Decentralized MARL

Open paper AskPDF arXiv

Multi-UAV exploration is often constrained by unreliable communication, limited field-of-view sensing (e.g., lightweight onboard camera), and finite travel budgets that require each robot to reserve enough budget to return to its base. We present Dec-MARVEL, a decentralized budget-aware exploration framework for communication-free teams with directional sensing. Rather than exchanging maps, goals, or messages, each robot coordinates through its incidental observations: any teammate trajectory within its field of view serves as a coordination signal. A graph-attention actor fuses local frontier geometry, teammate motion, and budget features to select return-feasible waypoint-heading actions. The actor is trained with phase-conditioned critics, a training-only task-oriented privileged critic, and a mixture-based budget curriculum. Across 900 held-out trials spanning three team sizes (2, 4, 8 robots) and three travel budgets (720, 800, 1024 meters) against four baselines, Dec-MARVEL achieves the highest or tied-highest exploration rate and lowest sensing overlap across all nine team-size budget configurations. Under our tightest 720m budget, it reaches 53%, 94%, and 100% success for 2, 4, and 8 robots, versus 37%, 83%, and 99% for the strongest baseline. Physical-robot experiments demonstrate successful sim-to-real transfer and real-world deployment of Dec-MARVEL.

Abstract

Explore similar work

Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints

Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration

Centralized Multi-UAV Exploration and 3D Reconstruction Using Single-UAV Planners