PaperlayerView exact revision on arXiv

Source-linked AI summary

Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration

Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard, David Filliat

arXiv:2609.00804v1cs.RO

TL;DR

Multi-UAV exploration must coordinate under intermittent communication. The paper introduces a decentralized frontier-connectivity graph extension applied to Voronoi and K-medoids partitioning, and simulations report improved performance under limited communication. The method also supports stable partitioning and deeper exploration across the evaluated settings.

  • Problem

    Multi-UAV exploration requires efficient, consistent task allocation despite unreliable communication and partial observations.

  • Method

    A decentralized method deterministically extends a shared topological graph from frontier connectivity and applies the extension to Voronoi and K-medoids partitioning.

  • Results

    Graph extension improves both partitioning methods; sampling-based extension reduces Ttot and Davg by 15% for K-medoids globally, while local Voronoi gains 20s in Ttot and 20m in Davg.

  • Takeaways & Limitations

    Under low communication rates, enriching the exploration graph supports deeper exploration, reduces overlap, and mitigates performance degradation.

Abstract

from arXiv · show

Exploring unknown environments with multiple UAVs requires coordination under intermittent communication, making decentralized operation a baseline assumption. We propose, within a decentralized framework, a novel exploration graph extension strategy based on frontier connectivity to extend exploration plans and maintain area partitioning among agents stable and robust to disconnections and changes in spatial layout. The proposed extension method is applied to two state-of-the-art area partitioning methods and evaluated in simulation. Experiments show improved performance over existing graph extension approaches with higher exploration efficiency under low communication rate.

I. INTRODUCTION

Multi-UAV exploration must coordinate efficient coverage despite intermittent communication. The paper proposes a decentralized, connectivity-aware graph extension strategy to stabilize area partitioning and reduce inefficient revisits.

  • Motivation: Intermittent UAV communication makes balancing communication constraints with fast, coordinated exploration a central multi-agent challenge.The framework treats limited range, frequency, reliability, obstacles, and interference as baseline conditions.
  • Motivation: MRE frames exploration as MRTA, allocating exploration areas while using partial information to align decisions and limit inefficient revisits.The stated objectives include efficient wide-ranging exploration, consistent task allocation, and guidance toward distant, structurally meaningful regions.
  • Approach: The proposed decentralized framework uses a shared, partially observed topological graph and partitions it with Voronoi or K-medoids.Each UAV makes local decisions from graph connectivity information.
  • Approach: The main contribution extends the exploration graph through frontier addition and connectivity preservation to keep partitions robust to disconnections and spatial-layout changes.The design targets stable partition shapes and consistent subregion assignments across drones and time without explicit allocation-stage communication.
  • Novelty and evaluation: Unlike local sampling around each UAV, the method deterministically adds nodes across the graph domain using topological parent-set intersection.The evaluation compares both extension styles across two partitioning methods and two topologically distinct environments under limited communication.

B. Area partitioning for exploration

Area partitioning assigns exploration space among UAVs, with methods ranging from proximity-based Voronoi cells to graph-structured clustering. Prior work often assumes reliable communication, leaving fully distributed robustness under uncertainty comparatively limited.

  • Area partitioning: Allocating cells or frontier sets reduces computational cost and supports longer-horizon planning with more stable, spatially distributed assignments.Frontiers are still explored sequentially within each allocated cell or subregion.
  • Area partitioning: Voronoi partitions dynamically assign frontiers to spatially closest agents, while clustering groups frontiers by similarity and requires a later UAV-cell assignment stage.Voronoi is attractive for low computational cost and distributed implementation.
  • Graph-based partitioning: Graph-based methods address obstacle-constrained environments by encoding traversal costs from real-time shortest-path planners rather than relying only on Euclidean distance.Frontier nodes carry exploration state and graph edges represent traversal costs.
  • Graph-based partitioning: GVD-based Voronoi uses geodesic distance, while K-medoids selects actual graph nodes suited to non-Euclidean pairwise distances.The passage contrasts medoids with Euclidean centroids and describes graph-theoretic measures for K-medoids.
  • Graph extension: Some prior methods extend graphs with agent positions, visited free-space locations, or farther frontiers to guide map expansion.These extensions go beyond frontier-only representations.
  • Communication assumptions: Most prior work assumes continuous, reliable communication or preserves connectivity at the cost of reactivity and swarm expansion.Only a minority of cited studies address uncertain communication and fully distributed MRE.

A. Problem formulation

The system represents a static 3-D environment as grid exploration subregions and maintains a locally updated topological graph. UAVs asynchronously extend, partition, share, and plan over this graph using opportunistic communication.

  • A. Problem formulation: The static 3-D volume is discretized into regularly spaced cubic Grid Exploration Subregions, or GES, represented by their centers.GES pass through undiscovered, discovered-to-be-explored, and fully explored or infeasible stages.
  • A. Problem formulation: Each of NM homogeneous UAVs maintains a consistent graph containing frontier, history, and UAV nodes.Frontier nodes are discovered explorable GES; history nodes are previously reached free-space waypoints; UAV nodes represent agents.
  • A. Problem formulation: Graph edges connect history-history or history-frontier nodes, with frontier nodes linked to one or more history parents through Dijkstra-based shortest-path trees.The graph is dynamically maintained as edges are created or removed.
  • A. Problem formulation: UAVs exchange current positions, frontier goals, GES stages, and history locations opportunistically within communication range.Nodes are shared among agents, while edge weights and endpoints are computed locally; data sharing is assumed noise-free during map merging.
  • B. System Overview: At each asynchronous step, a UAV updates its volumetric map and graph from local sensing and last-known swarm information, then performs allocation and motion planning.The ground station receives the updated map for visualization only.
  • B. System Overview: Every second, the system extends the graph with neighboring GES candidates, optionally computes APSP geodesic distances, and partitions the extended graph with Voronoi or K-medoids.Each UAV then plans within its assigned partition toward a selected GES node.
  • B. System Overview: Graph updates and local plans are opportunistically shared, whereas graph extension and partitioning remain local and are not communicated.The framework exchanges graphs when neighboring UAVs are within communication range and repeatedly executes allocation while free space remains unexplored.

1) Task Allocation:

The study compares Voronoi and K-medoids partitioning within the graph-extension framework. Their allocation mechanisms differ in whether UAV positions or graph-defined medoids determine partitions and assignments.

  • Partitioning methods: Voronoi uses current UAV positions as medoids, whereas K-medoids forms NM clusters from graph structure independently of UAV positions.This is the principal partitioning difference illustrated in Fig. 3.
  • K-medoids: K-medoids removes UAV nodes and initializes medoids with K-means++ using distant graph nodes to reduce initialization variance.The method also uses closeness centrality because it emphasizes graph distance.
  • UAV assignment: K-medoids requires explicit one-to-one medoid-to-UAV assignment through a distance cost matrix and the Hungarian algorithm.Voronoi assignment is inherently coupled to partitioning because UAVs themselves act as medoids.
  • Exploration planning: Each UAV sequentially explores its assigned GES using a weighted distance combining UAV position and partition-medoid position.This avoids overly peripheral destinations and planning based only on the partition center.

2) Planning:

The method temporarily extends the exploration graph by adding neighboring frontier-connected regions, while preserving topological consistency to avoid spurious shortcuts. Planning balances medoid proximity and UAV position, with quadratic overall complexity from pairwise shortest-path distances.

  • Newly discovered frontier nodes are assigned to the discovering UAV when adjacent to its partition or better positioned relative to its medoid.
  • The adjacency matrix makes overall planning complexity quadratic, while K-medoids additionally degrades toward quadratic growth as the number of medoids approaches graph size.
  • The extension temporarily augments Gm by connecting selected GES and attaching neighboring stage-1 GES to steer exploration toward regions with higher GES concentration.
  • A neighboring GES is added only when all its frontier parents belong to the same largest connected component; otherwise, it is ignored to prevent spurious shortest paths.
  • Added extension edges use Euclidean node distance scaled by ρ_FF > 1.0 to account for uncertain obstacle-aware reachability.

IV. EXPERIMENTS AND RESULTS

The evaluation measures exploration efficiency, motion, imbalance, connectivity, and partition consistency in ROS/Gazebo simulations. It compares the proposed extension across Voronoi and K-medoids methods under different communication and graph-extension settings.

  • The experiments evaluate total exploration time, average UAV distance, and distance standard deviation to capture speed, unnecessary motion, and inter-agent imbalance.Times are reported in seconds and distances in meters.
  • The study also measures connectivity ratio, exchanged data volume, intra-UAV medoid stability, and inter-UAV consensus under varying communication conditions.
  • Medoid stability is meaningful only for K-medoids approaches, whereas Voronoi partitioning does not provide the same medoid-based trajectory measure.
  • Stability is defined from the covariance trace of each UAV’s medoid trajectory over a sliding window and averaged across disconnection intervals.
  • Simulations use ROS and Gazebo with three drones, and each configuration is run 20 times with averaged metrics and box-and-whisker variability plots.
  • The proposed extension is applied to graph-based K-medoids and communication-constrained Voronoi, with comparison to a method that samples points within a sensing-range window.

B. Results analysis

Figure 6 compares environments and communication scopes using the total time required to explore 95% of the map.

  • The comparison uses total exploration time required to reach 95% map exploration across environments and communication scopes.

1) Environment dependence:

Performance depends on environment topology and frontier structure. Maze shows little communication-regime effect, whereas SubT’s sparse connectivity and structural complexity create instability that makes robust extension beneficial.

  • Maze performance is similar for Voronoi and K-medoid under local and global communication, with no significant loss under limited communication.
  • SubT methods generally perform better with global communication, while K-medoids shows higher variability because sparse frontiers create connectivity bottlenecks.
  • Sparse connectivity in SubT rapidly shifts clusters across UAVs, producing frequent changes in partition structure.
  • Thin walls and tight separations can make geographically close nodes topologically distant, causing inefficient backtracking.
  • SubT dead-ends and crossroads limit partitioning effectiveness, making robust graph extension beneficial.

2) Effect of graph extension:

Graph extension improves both partitioning methods and can stabilize assignments under limited communication. Its benefits differ by partitioning method and communication regime.

  • Graph extension improves both Voronoi and K-medoids partitioning methods.
  • Under global communication, topological extension preserves Voronoi performance, while sampling-based extension improves K-medoids stability.
  • Sampling-based extension reduces K-medoids Ttot and Davg by 15% under global communication.
  • Under local communication, topological extension maintains K-medoids performance, while both extensions improve Voronoi by 20s in Ttot and 20m in Davg.
  • Graph extension stabilizes K-medoid cluster shape, position, and assignment while drones prioritize broader exploration.

3) Local dynamics:

Graph extension affects partition stability and exploration dynamics differently across partitioning methods. Topological extension improves consistency and distance balance, while Voronoi benefits more in exploration efficiency than K-medoids.

  • Local dynamics: Voronoi is consistently improved by both extension methods, whereas K-medoids shows little benefit from graph extension.Under limited communications, the proposed extension does not significantly improve K-medoids exploration efficiency.
  • Local dynamics: 20 s lower T tot and 18 m lower Davg per UAV are reported for the extension methods.
  • Local dynamics: Topological extension significantly lowers Dstd for both partitioning methods, producing more similar UAV travel distances independently of frontier exploration rate.
  • Local dynamics: K-medoids benefits from high V s,disc, while sampling-based extension promotes early spatial dispersion but becomes less efficient later as awareness of other agents declines.
  • Local dynamics: Voronoi remains more robust than K-medoids, which has higher total exploration times and average traveled distances across categories.The methods trade off strengths: K-medoids better supports exploitation and coordination, while Voronoi drives deeper exploration.
  • Local dynamics: Without extension, Voronoi can diverge across disconnected neighborhoods and K-medoids can create fragmented clusters, while both rely on short-lived single-source information.
  • Local dynamics: Future work targets topology robustness, decision-criterion refinement, knowledge-accuracy improvements, and recovery strategies for more frequent information sharing.
Loading 2609.00804v1…