PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

Ben Rossano, Jaein Lim, Jonathan P. How

arXiv:2609.12502v1cs.RO

TL;DR

Intermittent communication makes multi-robot exploration a trade-off between sharing information and diverting from exploration to meet. MACE evaluates communication costs during scheduled windows, and in simulation reduces total exploration time by up to 23% against two baselines.

  • Problem

    Rendezvous strategies can impose long detours to meeting locations that become poorly positioned, whereas opportunistic communication can leave robots without contact and more prone to redundant exploration.

    Source: §I · p. 1

  • Method

    MACE is a decentralized framework that uses scheduled windows and a Vehicle Orienteering Problem variant to assess whether reaching a communication point is worthwhile given travel and en-route exploration.

    Source: §I · pp. 1–2

  • Results

    Up to 23% less total exploration time: MACE reduces the time needed to explore simulated environments compared with two baseline approaches.

    Source: §I · p. 2

  • Takeaways & Limitations

    Graph-based metrics show a relationship between exploration strategy and environment structure, suggesting an avenue for strategies conditioned on map geometry.

    Source: §VI · p. 7

Abstract

from arXiv · show

Exploring unknown environments with multi-robot teams can improve efficiency by allowing robots to explore in parallel. However, realizing these gains requires effective information sharing. When communication is intermittent, robots must balance the benefits of sharing information against the cost of diverting from exploration to establish communication. This paper introduces MACE, a decentralized exploration framework that actively evaluates whether establishing communication is worthwhile. At scheduled communication windows, robots estimate the cost of reaching previously identified communication locations. By formulating this decision as a variant of the Vehicle Orienteering Problem, robots evaluate routes based on the travel required to establish communication and the exploration that can be completed along the way. This approach enables robots to communicate more frequently than under purely opportunistic strategies while reducing the unnecessary travel associated with fixed rendezvous strategies. Across a set of simulated environments with varying size and geometry, we demonstrate that MACE reduces the total exploration time by up to 23% compared to existing communication-constrained exploration strategies.

I. INTRODUCTION

Intermittent communication makes information sharing a trade-off: rendezvous can require costly detours, while opportunistic contact can leave robots exploring redundantly. MACE evaluates the cost of seeking communication during scheduled windows and improves exploration time in simulation.

I. INTRODUCTION

  • Parallel exploration can improve efficiency, but realizing that gain requires coordination to avoid robots unknowingly re-exploring areas already covered by teammates.Continuous team-wide communication can be difficult to sustain in environments where materials attenuate radio signals.Source: §I · p. 1
  • Rendezvous strategies can force long detours to outdated meeting locations, while opportunistic strategies risk redundant exploration after long periods without contact.These trade-offs motivate balancing exploration progress against information exchange.Source: §I · p. 1
  • MACE uses scheduled communication windows to estimate the cost of reaching previously identified communication locations, attempting contact when the cost is low and otherwise continuing exploration.The decision is formulated as a variant of the Vehicle Orienteering Problem, accounting for travel and exploration along the route.Source: §I · pp. 1–2
  • Up to 23% less total exploration time: MACE reduces the time needed to explore simulated environments compared with two baseline approaches.The evaluations span environments with varying size and geometry.Source: §I · p. 2
  • The evaluation also examines how environment size and geometry relate to exploration-strategy performance using graph-based connectivity metrics.Source: §I · p. 2

II. BACKGROUND AND RELATED WORK

Prior work addresses exploration through frontier selection, continuous connectivity, and scheduled rendezvous. These approaches differ in how they trade planning effort and team spread against coordination and information exchange.

A. Frontier Exploration

  • Frontier exploration visits boundaries between known and unknown space; greedy selection replans quickly but can be myopic, while frontier sequences may add little as the frontier set changes.Source: A. Frontier Exploration · p. 2

B. Connectivity-Constrained Methods

  • Connectivity-constrained methods maintain team-wide connectivity and avoid redundant exploration, but can limit how widely robots spread, especially in large or geometrically complex environments.Connected-subgraph optimization has been used to identify meeting locations satisfying communication constraints.Source: B. Connectivity-Constrained Methods · p. 2

C. Rendezvous-Based Methods

  • Rendezvous methods schedule regular information exchange, with variants requiring full-team meetings or optimizing pairwise and subteam meetings.Choosing future meeting locations is difficult because exploration shifts frontier boundaries; current-frontier centers and random frontiers can become poor choices.Source: C. Rendezvous-Based Methods · p. 2

D. Opportunistic Methods

Opportunistic methods avoid scheduled meetings but can leave robots without contact; MACE's formulation treats exploration, robot plans, and candidate communication locations as parts of the coordination problem.

D. Opportunistic Methods

  • Opportunistic strategies exchange information when robots meet by chance, avoiding rendezvous backtracking but risking extended communication gaps and redundant exploration.Source: D. Opportunistic Methods · p. 2
  • Pursuit-based communication lets robots seek teammates using their last known positions and plans, but stale estimates may poorly predict actual locations and promote redundant exploration.Source: D. Opportunistic Methods · p. 2

III. PROBLEM FORMULATION

  • The formulation represents each robot's local map as free, occupied, or unknown cells and defines frontiers at free–unknown boundaries; the team objective is minimum cumulative time to cover explorable space.Each frontier is represented by a free-space coordinate nearest its centroid.Source: §III · p. 3
  • Robots are assumed to localize perfectly and map surroundings accurately, enabling direct map alignment and merging; they also retain teammate plans and timestamps to favor more recent information.Source: §III · p. 3
  • For each robot pair, communication points are locations where simultaneous presence guarantees contact; the communication interval schedules the next opportunity, and the lookahead horizon determines when planning begins.Source: §III · p. 3

IV. METHOD

MACE combines default exploration, communication-point updates, and communication-aware exploration. Robots plan toward communication opportunities when a feasible frontier route fits the remaining time, and otherwise fall back to exploration.

IV. METHOD

  • MACE's planning loop combines default exploration, communication-point updates, and communication-aware exploration, updating high-level regions after sufficiently large map changes.Source: §IV · p. 3
  • When a communication opportunity falls within the lookahead horizon, the robot selects the teammate it has been out of contact with longest and seeks a feasible frontier chain ending at a communication point.The route must fit the remaining time before the scheduled opportunity; its first frontier becomes the target.Source: §IV · p. 3
  • If no feasible communication route is found, or no communication-aware window is active, the robot uses its default exploration strategy and plans a path with A* search.Source: §IV · p. 3
  • Missed communication opportunities are rescheduled, while a mandatory rendezvous fallback forces robots to meet at their communication points after many missed opportunities.The fallback threshold is offset across robot pairs to avoid simultaneous mandatory meetings with multiple teammates.Source: §IV · p. 4

A. Default Exploration

Default exploration first assigns each robot a region, then selects frontiers to visit. Region assignments weigh travel, information gain, and coverage spread, and communicating robots can revise them through a greedy auction.

A. Default Exploration

  • The default strategy assigns each robot an exploration region before greedily selecting frontier targets within that region.Source: A. Default Exploration · p. 4

1) Exploration Region Selection:

  • Candidate regions cluster nearby frontiers into centroids and are refreshed after fused-map changes or when frontiers near a centroid are exhausted.The two stated update conditions are a sufficiently changed fused map during communication, or exploration of all frontiers within distance df of the centroid.Source: 1) Exploration Region Selection · p. 4
  • Region utility combines normalized travel distance, expected information gain, and coverage spread to favor useful, dispersed assignments.Travel distance is measured to region centroids; information gain estimates unknown area revealed at frontiers, and spread penalizes proximity to regions claimed by teammates.Source: 1) Exploration Region Selection · p. 4
  • During communication, a greedy auction assigns available regions by robot bids, removing claimed regions between rounds to repel later bidders.One communicating robot computes the assignments and broadcasts them to the subteam.Source: 1) Exploration Region Selection · p. 4

2) Frontier Selection:

After receiving an exploration region, each robot chooses a frontier to visit using a utility that balances travel, information gain, alignment with the assigned region, and coverage spread.

2) Frontier Selection:

  • Once assigned an exploration region, a robot selects a specific frontier as its next target.Source: 2) Frontier Selection · p. 4
  • For each candidate frontier, utility weighs travel distance and expected information gain against region-alignment and coverage-spread penalties.Travel and information gain follow the region-selection definitions; the spread term penalizes frontiers near already-claimed frontiers.Source: 2) Frontier Selection · p. 4
  • Region alignment favors frontiers that reduce the remaining distance to the assigned region without requiring the robot to ignore frontiers encountered en route.It compares robot-to-region distance with frontier-to-region distance.Source: 2) Frontier Selection · p. 4

B. Updating Communication Points

MACE updates communication points by partitioning unexplored space into regions, finding reachable communicating locations near robots’ expected coverage, and sampling a corridor of possible contact points.

B. Updating Communication Points

  • The procedure clusters fused-map frontiers into regions, distributes unclaimed regions across the team using last-known information for disconnected robots, and computes aggregate centroids.Source: B. Updating Communication Points · pp. 4–5
  • The solver searches movement-graph vertices for a communication-connected pair that minimizes the maximum travel distance from the two robots’ cluster centroids.The movement and communication graphs share vertices but encode traversability and communication connectivity, respectively.Source: B. Updating Communication Points · p. 5
  • Sampling points along the selected vertex pair creates a corridor where a robot can plan to re-establish contact at the next communication opportunity.Source: B. Updating Communication Points · p. 5

C. Communication-Aware Exploration

Communication-aware exploration plans frontier visits en route to a communication point under the remaining time budget. It replans after each visited frontier and provides fallbacks when a feasible route is unavailable.

C. Communication-Aware Exploration

  • The budgeted Vehicle Orienteering Problem routes a robot from its current position to a communication point while collecting frontier prizes within the remaining time budget.Frontier prizes omit the travel-distance term because travel cost is represented by route edge weights.Source: C. Communication-Aware Exploration · p. 5
  • When no feasible route exists, the planner tests reachability with added slack time; if the communication points remain unreachable, it falls back to default exploration.Source: C. Communication-Aware Exploration · p. 5
  • The planner permits arrival before the scheduled communication time and re-solves after each frontier because newly revealed areas may change which route is most valuable.The formulation has no lower-bound budget constraint, supporting frequent replanning as exploration reveals new frontiers.Source: C. Communication-Aware Exploration · p. 5

V. SIMULATION AND RESULTS

The simulations evaluate MACE under line-of-sight communication across maps of different sizes and structures. They compare its exploration times with two baselines and adjust parameters to each environment's scale.

A. Simulation Setup

  • The evaluation uses four structurally distinct maps, 20 randomly sampled starting locations per map, and three robots per trial.Trials continue until at least 99% shared map coverage; each robot has a 200 m LiDAR range.Source: A. Simulation Setup · p. 5
  • Parameters governing traversal, utility weights, and clustering are adjusted proportionally to map size.Robots arriving at a communication point wait for a duration proportional to Δtslack to accommodate slightly different arrival times.Source: A. Simulation Setup · pp. 5–6
  • MACE consistently outperforms both baselines on mean, minimum, and maximum exploration time under line-of-sight communication.Figure 3 reports results across different environments and starting locations.Source: Figure 3 · p. 6

B. Baselines

MACE outperforms both baselines across the evaluated environments, with an increased advantage over opportunistic exploration in the worst-performing trials. The results also show how map structure and scale relate to communication opportunities and exploration progress.

B. Baselines

  • Rendezvous schedules meetings at the center of previously observed frontier centroids, while opportunistic robots rely on chance line-of-sight contacts.Both baselines use MACE's default exploration approach during exploration phases.Source: B. Baselines · p. 6

C. Exploration Results

  • MACE outperforms both baselines in every environment; in the worst 25% of trials, its performance gap over opportunistic exploration increases by up to 13.6%.After many missed communication opportunities, MACE's fallback rendezvous helps prevent the worst-case redundant exploration seen with the opportunistic approach.Source: C. Exploration Results · p. 6

D. Map Connectivity

  • Current-flow betweenness captures local corridor and junction centrality, while encounter probability measures map-wide likelihood of communication edges and tends to be lower on larger maps.The encounter-probability denominator grows as O(|V|^2).Source: D. Map Connectivity · pp. 6–7
  • Additional connections reduce current-flow betweenness in the modified tunnel; maze and urban environments also have lower maximum values than tunnel networks, indicating more directions at junctions.Source: D. Map Connectivity · pp. 6–7

C. Exploration Results

  • Rendezvous tends to lead in shared knowledge but lag in global knowledge, while MACE avoids the long late-stage plateaus seen with opportunistic exploration.Figure 4 shows global knowledge as the union and shared knowledge as the intersection of robots' explored areas; shaded regions indicate one standard deviation.Source: C. Exploration Results · p. 6, Figure 4 · p. 7

D. Map Connectivity

  • Compact scale favors opportunistic encounters in the maze despite its low current-flow betweenness; the original tunnel is also favorable, unlike the modified tunnel and urban map.The large urban environment is least conducive to opportunistic communication because of its scale and lack of bottleneck corridors.Source: D. Map Connectivity · p. 7
  • MACE's mean performance improvement over the opportunistic approach is 3.1% in the maze and 1.9% in the original tunnel, versus 10.3% in the modified tunnel and 8.9% in the urban environment.Source: D. Map Connectivity · p. 7

VI. CONCLUSION

MACE achieves the lowest average exploration time across diverse maps. The conclusion also relates exploration strategy to environment structure through graph-based metrics and identifies higher-fidelity simulation as future work.

VI. CONCLUSION

  • MACE consistently achieves the lowest average exploration time across maps of diverse sizes and geometries.Source: §VI · p. 7
  • The conclusion connects exploration strategy with environment structure through two graph-based metrics.Fig. 5 shows each map’s top 5% of edges ranked by current-flow betweenness; Fig. 6 plots map suitability for opportunistic exploration, with arrows indicating the better-suited direction.Source: §VI · p. 7, Figure 5 · p. 8, Figure 6 · p. 8
  • Future work proposes moving beyond grid-world experiments to a higher-fidelity simulator such as Gazebo, enabling tests against methods including the pursuit-based M-TARE planner.Source: §VI · p. 7
Loading 2609.12502v1…