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

C$^2$-Explorer is a decentralized framework for multi-UAV exploration that addresses communication limitations and inefficient traversal by utilizing connectivity-aware task representation and a contiguity-driven allocation strategy, achieving significant reductions in exploration time and path length compared to state-of-the-art methods.

The Gist

Imagine you have a team of three brave drone explorers sent into a giant, messy forest or a confusing office building to map it out. Their goal is to see everything without missing a spot, but they have a big problem: they can't talk to each other very well. They can only whisper when they are very close together.

In the past, when teams of drones tried to do this, they often made two big mistakes:

1. Bad Maps: They treated the whole area like a giant checkerboard. If two rooms were far apart but happened to be in the same "square" of the checkerboard, the drones thought they were neighbors. This sent drones on long, silly detours to cross walls or go around obstacles just to get to a "nearby" spot that was actually far away.
2. Jumping Around: Because they didn't plan ahead, a drone might be told to check the kitchen, then suddenly fly to the attic, then back to the basement, then to the garage. This is like a delivery driver who drops off a package in New York, then drives to London, then back to New York, just to drop off one more package. It wastes time and fuel.

Enter C2-Explorer.

The researchers behind this paper created a smarter way for drones to work together. Think of it as giving the drones a super-intelligent, shared mental map and a strict "stay in your lane" rule.

1. The "Connectivity Map" (Instead of a Checkerboard)

Imagine the forest isn't a grid of squares, but a web of paths.

• Old Way: The drones looked at a map and said, "Okay, this whole square is a job." But inside that square, there might be a river or a wall separating two parts. The drone would try to fly through the wall, fail, and waste time.
• C2-Explorer Way: The drones build a Connectivity Graph. Imagine they are drawing lines only where they can actually fly. If a room is blocked off by a wall, they realize, "Hey, this room is cut off from the rest!" They split that area into its own separate "job ticket."
• The Result: The drones never get stuck trying to fly through walls. They only get assigned jobs that are actually reachable.

2. The "Contiguity" Rule (No More Jumping Around)

This is the secret sauce. "Contiguity" is a fancy word for "sticking together."

• The Problem: Without this rule, a drone might get a list of jobs that look like this: Job A (Kitchen), Job B (Attic), Job C (Basement), Job D (Kitchen again). The drone is constantly crisscrossing the building.
• The C2-Explorer Solution: The system adds a "penalty" to the math. It says, "If you assign a drone to the Kitchen, and then immediately assign it to the Attic (which is far away), that's a bad idea. We will charge you extra 'points' for that."
• The Result: The system forces the drones to pick jobs that are neighbors. If a drone is in the Kitchen, it gets the next job in the Hallway, then the Living Room. It creates a smooth, logical path, like a person walking through a house room-by-room instead of teleporting.

3. The "Team Captain" System

Since the drones can't talk to everyone all the time, they use a clever trick. When a group of drones gets close enough to whisper, one of them (the one with the lowest ID number) becomes the temporary Captain.

• The Captain gathers the "job tickets" from everyone.
• The Captain solves the puzzle: "Who should go where to finish fastest?"
• The Captain hands out the new lists and says, "Go!"
• If the connection breaks, the drones keep doing their current job until they meet up again. It's like a relay race where the baton is only passed when runners are close enough to touch.

The Big Win

The researchers tested this in computer simulations and real life with actual drones flying in forests and buildings.

• Time Saved: They finished the mapping 43% faster than the best previous methods.
• Distance Saved: The drones flew 33% less distance.
• Real World: They successfully flew real drones through a wooded area and a building with pillars, proving it works outside the computer.

In short: C2-Explorer is like giving a team of explorers a map that only shows walkable paths and a rule that says, "Do your work in one neighborhood before moving to the next." This stops them from getting lost, wasting energy, or flying in circles, making them the most efficient explorers possible.

Technical Summary

Here is a detailed technical summary of the paper "C2-Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration."

1. Problem Statement

The paper addresses the challenges of decentralized multi-UAV exploration in unknown 3D environments under limited communication constraints. Existing methods suffer from two primary bottlenecks:

• Inadequate Task Representation: Traditional grid-based or frontier-based representations often ignore environmental topology. They may merge spatially disconnected unknown regions into a single task unit or include unreachable areas (e.g., enclosed by obstacles), leading to inefficient traversal and unnecessary detours.
• Lack of Spatiotemporal Contiguity: Current allocation strategies (often greedy or standard Vehicle Routing Problems) fail to enforce contiguity. This results in UAVs being assigned non-adjacent tasks, causing frequent cross-region detours, interleaved trajectories, and redundant exploration.

2. Methodology: C2-Explorer Framework

The proposed system is a decentralized framework consisting of three core components:

A. Connectivity-Aware Task Representation

Instead of using uniform grid centroids as task units, C2-Explorer constructs an Incremental Connectivity Graph ($G = (V, E)$) to model the topology of the environment.

• Graph Construction: The space is coarsely decomposed into grids. Within each grid, Connected Component Labeling (CCL) segments free and unknown regions. A graph is built where vertices represent region anchors and edges represent connectivity (free, unknown, or portal edges) found via restricted A* searches.
• Task Unit Definition: Each spatially disjoint unknown region is defined as an independent Task Unit.
  • Filtering: Unreachable regions (e.g., those enclosed by obstacles with no path to the free space) are identified and marked as INVALID, preventing wasted effort.
  • Data Structure: Each task unit stores a position, a convex hull (for lightweight communication), voxel count (workload), and status (Pending/Completed/Invalid).

B. Contiguity-Driven Task Allocation

The allocation problem is formulated as a Capacitated Vehicle Routing Problem (CVRP) with a novel Graph-Adjacency Contiguity Penalty.

• Objective: Minimize total traversal cost while balancing workload among UAVs.
• Contiguity Penalty: To prevent non-adjacent assignments, the cost matrix includes a penalty kernel $\psi(\rho_{ij})$.
  • If two tasks are topologically adjacent (within a connectivity radius $R_c$), no penalty is applied.
  • If tasks are separated beyond $R_c$, a quadratic penalty is applied based on the distance ratio.
  • This forces the optimizer to group spatially connected tasks for the same UAV, ensuring smooth, contiguous exploration sequences.
• Decentralized Execution: Within communication range, the lowest-ID UAV acts as a temporary host. It solves the CVRP and disseminates task sequences using a Commit-Style Handshake (Proposal $\to$ Commit $\to$ Finalize) to ensure consistency despite packet loss or out-of-order delivery.

C. CP-Guided Planning for Single UAV

Once tasks are allocated, each UAV executes a hierarchical planning strategy:

1. Global Planning: Solves an Asymmetric Traveling Salesman Problem (ATSP) over the allocated task units to determine the visitation order. The cost function includes a velocity-consistency penalty to ensure smooth transitions between tasks.
2. Local Planning: Within each task unit, the UAV performs local frontier clustering and viewpoint selection to generate a local tour.
3. Trajectory Generation: Converts the discrete tour into a smooth, dynamically feasible B-spline trajectory with explicit collision avoidance constraints.

3. Key Contributions

1. Connectivity-Aware Representation: A novel method that models environmental topology to split disconnected unknown regions into independent task units and filters out unreachable areas, improving task rationality.
2. Contiguity-Driven Allocation: An optimization formulation that integrates a graph-based adjacency penalty into the CVRP. This explicitly regularizes the allocation to promote spatiotemporally contiguous task sets, reducing cross-region detours.
3. Robust Decentralized System: A complete framework validated in both simulation and real-world flights, featuring a robust communication protocol for task consistency under limited bandwidth.

4. Experimental Results

The system was evaluated in simulation (MARSIM) and real-world outdoor environments against state-of-the-art baselines (RACER and FAME).

• Simulation Performance (4 UAVs):
  • Exploration Time: Reduced by 43.1% on average compared to baselines.
  • Path Length: Reduced by 33.3% on average.
  • Scenarios: Tested in Cubicle Office, Open-plan Office, and Octa Maze. C2-Explorer showed the most significant gains in complex, structured environments where baselines suffered from topology-agnostic errors.
• Ablation Studies:
  • Removing the contiguity penalty (No-Con) increased path length by 35.1%, proving the necessity of the adjacency constraint.
  • Removing the connectivity graph (No-Graph) increased path length by 60.6%, confirming the value of topology-aware task splitting.
• Real-World Validation:
  • Successfully deployed with 3 quadrotors in unstructured woodlands and structured buildings.
  • Demonstrated feasibility in completing exploration in 69s (woodland) and 52s (building) with stable flight trajectories.

5. Significance

C2-Explorer represents a significant advancement in multi-robot exploration by bridging the gap between topological awareness and task allocation efficiency.

• Efficiency: By eliminating the "topology-agnostic" flaw of grid-based methods, it prevents UAVs from wasting energy on impossible or disjoint tasks.
• Coordination: The contiguity-driven approach solves the "ping-pong" effect where UAVs frequently switch between distant targets, leading to smoother, more efficient team behaviors.
• Practicality: The system operates effectively under strict communication limits (5m range), making it suitable for real-world applications like search-and-rescue, structural inspection, and disaster response where communication is often intermittent.

The code is open-sourced, facilitating further research in decentralized multi-agent systems.