acceptodds
Under review as a conference paper at ICLR 2027

Learning Adaptive Communication Ranges for Decentralized Multi-Agent Pathfinding

Abstract

Communication is central to learned decentralized multi-agent pathfinding, en- abling agents to coordinate decisions beyond their local observations. Yet effec- tive coordination requires communication to match the needs of individual agents, which vary across locations and evolve throughout planning. Fixed-range com- munication cannot accommodate this variation: it may exclude relevant agents when coordination is needed or introduce redundant exchanges when local in- formation is sufficient. We propose a framework for state-adaptive communica- tion that learns to adjust each agent’s communication neighborhood from its local state. The resulting topology supports differentiated information exchange across agents and time. Experiments with three planners spanning distinct communica- tion architectures, across six map families and 21 map–population configurations, demonstrate improved planning success alongside reduced communication and overall runtime. The configuration-averaged success-rate improvement reaches approximately 13 percentage points across the evaluated planners. These findings highlight the value of learning how to organize communication for effective and efficient decentralized multi-agent coordination.

Primary area:
applications to robotics, autonomy, planning
Keywords:
multi-agent pathfinding, decentralized planning, adaptive communication, multi-agent coordination, learned communication, communication efficiency, graph neural networks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_jSV8OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the communication range selection problem in decentralized MAPF and proposes a state-based conditional selector that can adaptively adjust the frozen planning strategy. During the offline phase, candidate ranges are uniformly distributed among all agents based on recorded expert states. The frozen strategy provides range labels based on the negative log-likelihood values for each expert action. During the online phase, a selector based on a convolutional neural network (CNN) or multilayer perceptron (MLP) utilizes local occupancy observations, goal-relevant features, and neighbor counts specific to candidate ranges to select ranges with radii of 3, 5, or 7 for each agent at every step, thereby generating heterogeneous communication topologies without the need to retrain action strategies. The evaluation covered MAGAT, HMAGAT, and LC-MAPF across six map families and 21 configurations, each comprising a single layout and 128 rounds, using three selector training seeds. Compared to the default fixed range, HMAGAT’s average success rate increased from 70.2% to 83.7%, the cumulative planner message load was reduced to approximately 0.50 times, and the algorithm’s runtime was shortened to approximately 0.79 times. Additional experiments examined inputs, candidate node filtering, sampling, random selection, density rules, SW-UCB, and selected fixed-range alternatives.

Critical strengths
  1. Adaptive variants and fixed-range variants share backbone network checkpoints and evaluation instances, thereby reducing the confounding effects caused by retraining action policies. HMAGAT improves the average success rate by 13.5 percentage points, with 18 configurations showing improvements and 3 remaining unchanged, while MAGAT and LC-MAPF also benefit. This demonstrates that neighborhood construction serves as an effective interface for improving existing planners and provides evidence of compatibility across different architectures.

  2. The evaluation includes frequency-matched random selection, density rules optimized based on the validation set, online SW-UCB, input ablation experiments, sampling control, and additional fixed-range comparisons. These provide meaningful evidence of the value of state information beyond the default baseline comparisons. Timings cover feature extraction, selection, topological construction, and policy inference. Transparent timing records enhance interpretability and serve as an important consideration supporting the adoption of this method.

Critical weaknesses
  1. The main aggregated results were compared with the default fixed ranges of each backbone network. Table 11 provides useful additional control experiments, but these are limited to five HMAGAT configurations and indicate that the default settings may be far from optimal. On the DM-192 dataset, the adaptive method achieved a 21.9-point improvement over the default settings, but only a 2.3-point improvement over the strongest fixed candidate scheme. A broader comparison is needed to determine to what extent this improvement goes beyond the scope of conventional range tuning. DCC has learned to select decision-relevant neighbors from local observations. Although this is discussed in the paper, it is not demonstrated through comparable learning-based neighbor selection or gated control. While the approach of freezing the backbone network and using discrete thresholds is convenient, its unique advantages over established communication selection mechanisms have not been fully demonstrated. This is the primary concern that prompted me to make this suggestion.

  2. Appendices B–C indicate that the neighbor counts for specific candidates use dynamic positions provided by the simulator, while position acquisition, neighbor discovery, and range signaling are excluded Bdiscovery=0B_{\mathrm{discovery}}=0. Therefore, approximately 50% of the reduction pertains to the planner’s message payload after the aforementioned information is provided. The total cost remains undetermined when agents must discover more distant neighbors before deciding whether to use a larger range. The cumulative round-based communication volume also takes into account both the number of messages per step and the round duration. The research findings fail to sufficiently distinguish between savings resulting from communication sparsification and early termination. Although the relevant assumptions have been clearly disclosed, a more detailed cost accounting and breakdown is still needed to draw more convincing conclusions regarding decentralized efficiency.

Questions for authors
  1. For all 21 configurations and the three backbone networks, compare fixed-radius schemes with radii of 3, 5, and 7, and report the fixed-range baseline selected from the validation set as well as the remaining adaptive gain. For at least one representative backbone network, compare these schemes with those based on learned neighbor selection or communication gating, using matched inputs and comparable training budgets. Does discrete range selection still maintain a significant performance-payload advantage?

  2. How do agents obtain the neighbor counts for all candidate ranges—particularly those outside their observation window—before selecting a range? Which acquisition costs are shared with the fixed planner, and which are introduced by the adaptive mechanism? Please include position acquisition, discovery, and range signal transmission in communication simulations or multi-process implementations, and report the total payload and decision latency. How much of the approximately 0.50-fold planner payload advantage remains?

  3. The appendix describes “map/episode-level partitioning,” yet each evaluation configuration uses only a single layout. Please specify whether the training, validation, and test partitions share the same map topology, and how many distinct layouts each partition contains. Repeat key comparisons for multiple unseen layouts within each family, and report the distribution of layout-level improvements along with their confidence intervals. This will verify whether the learned adaptability consistently transfers to topologies outside the evaluation set.

  4. Equation 2 simultaneously modifies the range of each agent, whereas in actual deployment, range selection is performed independently for each agent. Under conditions of multi-round communication and a shared hypergraph, an agent’s score may be partially altered by changes in the ranges of other agents. Please compare the candidate rankings with the original labels in representative closed-loop scenarios by altering only the range of the focal agent (while fixing the ranges of other agents). Does the supervision mechanism built under a mixed topology alter closed-loop performance? How accurately do the current labels reflect the focal agent’s own range requirements?

  5. Success depends on step limits and real-time constraints, whereas HMAGAT’s SOC imposes a full-time-domain penalty on each agent during failed rounds. Please additionally report: the success rate under move limits without real-time constraints, the SOC values for successful collaborative instances, and the message load under fixed states or matching decision steps. These metrics will distinguish between improvements in coordination, avoidance of real-time timeouts, reduction in per-step communication volume, and shortening of round duration.

4 comments

We thank the reviewer for the careful review and for recognizing the matched-checkpoint protocol, the controls, and the transparent timing. Experiments added for this response are in the new App. H. They use the paper's protocol, with 95% confidence intervals where reported, and we add step-limit-only success where timing matters (W2/Q5). We write DM/SM for dense/sparse maze, DW/SW for dense/sparse warehouse, ER for the empty room, and OST for ost003d, followed by the agent count.

W1/Q1 (part 1, vs. tuned fixed radii)

We first clarify two points. (i) HMAGAT's default range is our large candidate (r=7), so the Large column of Table 11 equals the Fixed column of Table 7. MAGAT also defaults to r=7, and LC-MAPF to its 11×11 neighbor window (up to 12 neighbors). We kept each backbone's released default to avoid re-tuning published baselines, and revised Sec. 5.1 states this. (ii) Our selector is one model per backbone for all 21 configurations, whereas a tuned fixed range is chosen per configuration.

The existing results already show a gap. Over the five Table 11 configurations, mean ACC is 66.1 for the default, 69.1 for the best single radius in {3,5,7} (small), and 71.6 for the best radius in {3,5,7} per configuration chosen on test (an oracle). Adaptive reaches 76.1 and matches or exceeds this oracle in every configuration, by 12.5 and 4.7 pp on DM-160 and SW-192 and by 0.8–2.3 pp on the other three. Frequency-matched random selection (Table 2) keeps the marginal range mix but removes state dependence, and it falls below the default in 2 of 3 configurations. The gain is therefore not explained by using smaller ranges on average.

We also evaluated fixed r ∈ {3,5,7} on all 21 configurations × 3 backbones. The selection rule was fixed before test evaluation. For each configuration, r_val is the radius with the highest validation ACC (episode seeds disjoint from test), with ties broken by lower payload.

BackboneDefaultr_valAdaptiveGain vs r_val [95% CI]C (adapt./r_val)Adapt. ≥ r_val
HMAGAT70.274.983.7+8.8 [7.1, 10.5]0.9319/21
MAGAT26.529.835.6+5.8 [4.3, 7.3]0.8819/21
LC-MAPF30.732.436.1+3.7 [2.5, 4.9]0.9518/21

Against a per-configuration validated radius, adaptive still improves ACC by +8.8, +5.8, and +3.7 pp, all with intervals above zero, while using 0.88–0.95× the planner payload of r_val. For HMAGAT, every radius already reaches ≥99% success in OST-128/160/192 and SW-128. The final version will add a figure of ACC against payload for r=3/5/7 and adaptive in each configuration.

W1/Q1 (part 2, vs. learned selection and gating)

Our setting keeps the policy frozen, so we built two learned selectors on HMAGAT. Both use our inputs, supervision source (frozen-policy expert-action scores), training states, network size, and training budget. (i) An IC3Net-style gate chooses between no communication and the default range for each agent. (ii) In DCC-style neighbor selection, a classifier with our inputs plus each neighbor's relative position predicts which neighbors within r=7 to keep. It is trained on counterfactual neighbor-removal scores from the same frozen policy, with the threshold selected on validation.

ACC / C (vs. default)DM-160ER-224SW-192
Default (r=7)53.1 / 118.0 / 182.8 / 1
Learned gate55.5 / 0.7123.4 / 0.7884.4 / 0.69
DCC-style selection63.3 / 0.6241.4 / 0.7087.5 / 0.58
Ours67.2 / 0.5746.9 / 0.7590.6 / 0.47
Ours + DCC-style within selected range68.0 / 0.4947.7 / 0.6491.4 / 0.41

The gate helps (up to 5.4 pp) but less than range selection, as an all-or-nothing decision cannot shape the neighborhood. DCC-style selection is the strongest alternative but remains 3.1–5.5 pp below ours, with higher communication on DM-160 and SW-192 (best single mechanism in bold). Adding DCC-style selection on top changes success little but gives the lowest communication, so the mechanisms are complementary. They also differ in cost. Per-link selection predicts one output per neighbor, needs O(|N_i|) counterfactual passes per labeled state, and conditions on each neighbor's relative position. Range selection predicts one output per agent and needs only neighbor counts, which come from the r=7 discovery the HMAGAT baseline already performs. We adapt DCC's selection principle to our frozen-backbone, architecture-agnostic setting rather than reproduce its joint training.

W2/Q2. Neighbor counts and the full communication cost

Small (r=3) and medium (r=5) counts lie inside the 11×11 observation window (a Manhattan ball of radius ≤5 fits in the ±5 square), and only the large count needs positions beyond it. Neighbor discovery is largely shared, because any distance-based topology must identify the agents within its range. HMAGAT and MAGAT default to r=7, the largest radius in {3,5,7}, so their fixed planners already discover exactly the agents the large count needs. LC-MAPF's default neighborhood is its 11×11 window, so for LC-MAPF the large count also uses positions beyond that window. Range signaling adds a cost only under point-to-point delivery. Under broadcast, receivers filter by their own radius (Eq. 7) and nothing extra is sent. Our payload metric assumes point-to-point delivery, where a sender must know r_i, so we charge 1 byte per directed pair within r=7 per step (2 bits suffice).

A message-level replay of all logged HMAGAT episodes, normalized to the fixed planner's payload, gives 1.00 vs. 0.50 for planner messages, 0.03 vs. 0.03 for discovery, and 0 vs. 0.006 for signaling (fixed vs. adaptive), for a total of 1.03 vs. 0.54. The full-cost ratio is 0.52 (0.55 for MAGAT), so nearly all of the planner-payload saving remains. Decision latency (features + selector) is 2.4 ms per step and is already included in the reported runtime.

W2/Q5. Sparsification vs. shorter episodes vs. timeouts

Where both planners succeed, episode duration cannot explain the saving. OST-128/160/192 (100% vs. 100% ACC, SoC within 0.5%) still use 0.51×/0.48×/0.46× communication, and ER-128/SW-128 (≥98% success for both) use 0.46×/0.41×.

Several fixed baselines run close to their limit (87.9 of 90 s on DM-192 and 59.8 of 60 s on SW-224), so we separate success from the real-time budget. In the logs, 61% of fixed and 34% of adaptive failures end at the wall-clock limit. The new results below are for HMAGAT, averaged over 21 configurations (other backbones in App. H).

ACC step+timeACC step onlySoC, both solvedPayload/stepMatched-state payload
Fixed70.275.6111
Adaptive83.785.40.970.560.52

Under the step limit only, adaptive still gains 9.8 pp, and the remaining 3.7 pp of the 13.5 pp come from finishing within the real-time budget. Per-step and matched-state payloads (0.56×, 0.52×) show that most of the communication saving is sparsification rather than shorter episodes. The revision reports both success definitions in the main text and treats faster execution as a separate source of gain under real-time budgets.

Q3. Layout partitions and unseen layouts

For the dense and sparse maze families, the selector is trained and validated on layouts from other generator seeds, so each test layout is unseen (16/4/1 layouts in train/val/test). The warehouse generator produces a fixed layout, the empty room has no obstacle topology, and ost003d is a single benchmark map, so their split is episode-level.

We tested 20 new layouts per maze family, 32 episodes each, without retraining (HMAGAT, ACC %).

ConfigFixedOursΔACC [95% CI over layouts]Layouts improved
DM-16049.861.2+11.4 [8.9, 13.9]18/20
SM-16071.181.7+10.6 [8.3, 12.9]19/20

Q4. Are all-agent labels faithful to the focal agent?

Under Eq. 7, agent i's eligible incoming set depends only on r_i, and other agents' ranges act only indirectly, through multi-round propagation or shared hyperedges. Uniform assignment needs |R| forward passes per state instead of n·|R|. In a focal test on 2,000 held-out expert states each from DM-192/SW-224/ER-128, we set the other agents to their predicted ranges and vary only the focal agent's range. On non-tied states (ties are exactly equal scores), top-1 agreement with the original label is 81.6% for HMAGAT and 77.9% for LC-MAPF (87.7%/85.2% including ties), with Spearman ρ 0.78/0.72. Where they disagree, the score gap between the two choices is small (0.021 nats for HMAGAT vs. 0.164 between best and worst candidate), so the uniform-range labels largely reflect the focal agent's own preference. All reported gains are closed-loop, which remains the final criterion.

We are happy to clarify any further points.

Thank you for the careful response and the substantial effort devoted to the additional experiments. The new comparisons and analyses have addressed most of my concerns and I will therefore raise my rating.

We sincerely thank the reviewer for the thoughtful engagement and for raising the rating. We will incorporate the new results and clarifications into the revised paper. We would be glad to address any remaining concerns.

Reviewer_cwofOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a method for adapting communication ranges in decentralized multi-agent pathfinding. A lightweight selector learns to choose among three predefined radii for each agent at each timestep, while keeping the underlying navigation policy frozen. Training uses offline evaluations of how well each communication range supports expert actions. The method is evaluated on MAGAT, HMAGAT, and LC-MAPF across six map families and 21 map and population configurations. Results show higher success rates and reduced planner-message payload and runtime compared with the default fixed-range policies.

Critical strengths
  • Substantial reported gains. Despite the approach's simplicity, selecting among different communication ranges yields substantial improvements in success rate while reducing communication payload across the evaluated backbones. Under the paper’s evaluation assumptions and setup, these results suggest that adapting communication scope can be useful even without modifying the underlying action policies.
Critical weaknesses
  • The methodological contribution appears limited. The method learns to select among three predefined communication radii of 3, 5, and 7 grid cells. Choosing a different radius for each agent and timestep is useful, but I find the contribution incremental compared with existing adaptive communication approaches. Although the appendix describes candidate screening and compares the retained candidates with a broader pool, it is unclear which radii were initially considered and how screening led specifically to these values. How sensitive are the results to alternative choices, and would the same radii remain effective on unseen layouts or at different spatial scales? A more direct comparison with the approaches discussed at L118–125 would help show what this method adds. It would also be interesting to explore whether agents could learn the required communication extent more freely, or request further communication when the available information is insufficient. As presented, the results support the approach under the evaluated assumptions and configurations, but provide limited evidence that it would remain effective beyond them.

  • The experimental section is poorly communicated. The paper is reasonably clear through Section 4, but Section 5 becomes substantially harder to follow. “ost003d” is introduced without explaining what it represents or why it is included (L254–265). Configurations such as “ER-224” and “SW-224” are discussed at L302 before their abbreviations are explained at L316–318. Section 5.2 mainly reports improvement counts and selected numerical changes, with limited interpretation of the differences between configurations. For example, the substantial gains in ER-224 and SW-224 are highlighted without explaining what makes these configurations particularly challenging for fixed-range communication or why adaptation is especially beneficial in these settings. The main experimental findings should be understandable without repeatedly consulting the supplementary material.

  • Essential definitions are deferred to the appendix. The descriptions of local observations and auxiliary information at L201–208 are too general to understand what each agent actually knows. Understanding the observation channels, the meaning of the agent’s “broader state,” and the assumptions about map knowledge and access to other agents’ positions requires consulting Appendix B. Likewise, understanding what agents exchange and which communication costs are excluded requires consulting Appendix C. These concepts are central to understanding the method and interpreting its efficiency claims. Their essential definitions should appear in the main paper, with the appendix providing implementation details.

  • Generalization beyond the evaluated layouts is unclear. Each evaluation configuration uses one map layout. Appendix B mentions map- or episode-level partitions, but does not clearly identify which layouts are held out during training. Consequently, it is difficult to establish whether the learned range selection transfers to unseen layouts or substantially different spatial structures. Since the method selects among fixed spatial scales and uses features derived from a known map and simulator-provided agent positions, its applicability to different map scales and partially observable settings also remains uncertain.

Minor weaknesses

  • Table 1 normalizes communication against a fixed baseline reported in Appendix Table 7, forcing the reader to consult the supplementary material and disrupting the reading flow. The relevant fixed-baseline results should be included directly in Table 1 to make the main paper self-contained.
  • Although L282–289 reports aggregate uncertainty and variation across training seeds, Tables 1 and 2 and Figure 3 do not display uncertainty for the individual comparisons. Confidence intervals would help assess the reliability of the reported differences, particularly the smaller gains in the ablations.
Questions for authors
  • Which map layouts are held out during selector training? Could the authors clarify which splits are at the map level and which are at the episode level, and whether the evaluation demonstrates generalization to unseen layouts and different grid dimensions?
  • Appendix B states that agent positions are supplied by the simulator, while position acquisition, neighbor discovery, and range signaling are excluded from the communication measurements. How would including these costs affect the reported savings? What sensing or communication infrastructure would agents need to obtain this information, and in which deployment settings would these assumptions be realistic?
  • Could the authors provide confidence intervals for the individual comparisons in Tables 1 and 2, and discuss why the gains vary substantially across configurations?
4 comments

We thank the reviewer for the careful reading. We uploaded a revised PDF with changes in blue. Experiments added for this response are reported in the new App. H and use the paper's protocol (128 paired test episodes unless noted, same hardware, all settings fixed on validation data before test evaluation). We write DM/SM for dense/sparse maze, DW/SW for dense/sparse warehouse, ER for the empty room, and OST for ost003d, followed by the agent count (e.g., DM-160 is a dense maze with 160 agents).

W1. What this adds beyond adaptive communication (L118–125)

These methods decide whether to communicate (IC3Net), how to weight or target messages (TarMAC, ATOC), or which neighbors to use (DCC, PICO), and they are typically trained jointly with the action policy inside a neighborhood fixed in advance. We learn the extent of that neighborhood per agent and per step, which differs in three ways. (i) It plugs into frozen planners of three different architectures without retraining them. (ii) It is supervised by counterfactual scores of the same planner at identical states (Eq. 2). (iii) It needs one decision per agent rather than one per link.

We compare directly with learned gating and per-neighbor selection on HMAGAT (ACC % / communication relative to the default). All learned variants share our inputs, supervision source, frozen backbone, and training budget.

MethodDM-160ER-224SW-192
Default fixed (r=7)53.1 / 118.0 / 182.8 / 1
IC3Net-style gate {off, r=7}55.5 / 0.7123.4 / 0.7884.4 / 0.69
DCC-style per-neighbor selection63.3 / 0.6241.4 / 0.7087.5 / 0.58
Ours67.2 / 0.5746.9 / 0.7590.6 / 0.47
Ours + DCC-style within selected range68.0 / 0.4947.7 / 0.6491.4 / 0.41

Range selection gives the highest success of the three single mechanisms (best in bold). Adding per-neighbor selection on top changes success little but lowers communication further, so the two mechanisms are complementary. A full DCC reproduction would retrain the policy, which is outside our frozen-backbone protocol, and revised Sec. 2 discusses this.

Table R1 tests other candidate sets and perturbations of the selector's inputs (HMAGAT, ACC %).

VariantDM-192SW-224ER-128
Fixed (default, r=7)19.514.198.4
Ours, {3,5,7}41.485.299.2
Ours, {2,4,6}39.882.898.4
Ours, {4,6,8}38.383.699.2
Ours, {3,7}36.780.598.4
Ours, full trial pool (Table 1)39.184.497.7
Ours, position noise σ=139.183.698.4
Ours, 20% neighbor dropout38.382.099.2

In the two crowded configurations, every candidate set retains most of the gain over the fixed default (ER-128 is near ceiling for all variants), so the result does not hinge on {3,5,7}.

The three radii are screened from a trial pool r ∈ {1,…,9} (revised Sec. 4.1). We keep radii that are the label of ≥5% of validation samples and check that the retained set covers the minimizing radius of most validation states (88%). This yields {3,5,7} for all backbones, and the same set serves 21×21 mazes and the 194×194 ost003d map. Training on the full pool lets agents choose the extent more freely. Success stays within 2.3 pp (not significant, see Minor) with 20–39% less communication (Table 1). The selector already widens an agent's range when its local state calls for it (agent a6 in Sec. 5.5 selects large in a crowded area), and the full pool extends this to r=9. Requesting further messages after reading the received ones is a natural extension for future work.

W2. Presentation

Revised Sec. 5.1 defines ost003d before first use (a 194×194 game map from the MovingAI MAPF benchmark [Stern et al., 2019], included as a large, irregular map contrasting with the 21–39-cell generated layouts) and all configuration abbreviations (listed above). We removed redundant summary paragraphs in Sec. 5 to make room for the interpretation in Q3.

W3. Definitions moved to Sec. 3

The observation oio_i is a 2×11×11 egocentric window (agent and obstacle occupancy). The auxiliary state ziz_i contains normalized distance-to-goal, BFS cost-to-go on the known static map, and agent counts within each candidate radius. We assume that the static map is known (as in all three backbones) and that positions of agents within the largest radius are available. Counted communication is the backbone's own messages, as logical directed payload over all rounds.

Q3. Why gains vary (new analysis in revised Sec. 5.2)

We see three reasons.

(i) The real-time budget matters most in the most crowded settings, where the fixed planner runs at its budget (58.8 of 60 s on ER-224, 59.8 of 60 s on SW-224). Under the step limit only, fixed vs. adaptive is 31.3% vs. 53.9% on ER-224 and 57.0% vs. 88.3% on SW-224, so large gains remain without the wall-clock limit (22.6 and 31.3 pp). The rest comes from faster execution, which matters under real-time budgets. Over all 21 configurations the step-only gain is +9.8/+7.2/+4.6 pp for HMAGAT/MAGAT/LC-MAPF, compared with +13.5/+9.1/+5.4 under the paper protocol.

(ii) Gains grow with headroom. For HMAGAT, configurations with fixed ACC ≥90%, 60–90%, and <60% gain 1.5, 14.2, and 30.9 pp on average. Within each family the gain grows with population, except OST-256, where both planners mostly fail.

(iii) No single range fits all configurations. HMAGAT's default equals our large radius (r=7, Table 11), which admits many more senders in crowds (agent a6 has 38 neighbors at r=7 vs. 10 at r=3), and a smaller radius often performs better there. Small beats large on DM-192 (39.1 vs. 19.5) and SW-192 (85.9 vs. 82.8) but loses to medium on DM-128 and to large on ER-160. In SW-224 all agents start small and expand selectively (78/138/8 small/medium/large near the end, Table 13).

Q2. Excluded costs

(i) Neighbor discovery is largely shared with the baseline. A fixed-range planner must already know which agents lie within its range. HMAGAT and MAGAT default to r=7, our largest radius, so the selector needs no position information beyond the baseline's. LC-MAPF's default neighborhood is its 11×11 window (up to 12 neighbors), so for LC-MAPF the large count also uses positions beyond that window.

(ii) Range signaling is zero under broadcast, because links follow the receiver's radius (Eq. 7) and receivers filter locally. Our payload metric assumes point-to-point delivery, under which we charge 1 byte per directed pair within r=7 per step.

(iii) Including both costs changes little. A message-level replay of all logged episodes, normalized to the fixed planner, changes the ratio from 0.50/0.53 (planner messages) to 0.52/0.55 with discovery and signaling (HMAGAT/MAGAT).

(iv) The selector is robust to imperfect sensing. With position noise or 20% neighbor dropout in its inputs (Table R1), success drops by at most 3.2 pp and stays far above the fixed default on DM-192 and SW-224.

(v) The assumptions match warehouse fleets in which robots localize on board (e.g., floor fiducials) and exchange positions over local radio, which the fixed-range baseline already requires. Packet loss is tested in our response to Reviewer mfBs, and revised Sec. 6 discusses robot dynamics and other deployment factors.

W4 / Q1. Splits and generalization

For the two maze families, the test layout is held out, since the selector is trained and validated on 16/4 layouts from other generator seeds. The warehouse generator produces a fixed layout, and the empty room and ost003d have one layout each, so their split is episode-level (disjoint start–goal seeds). One selector per backbone serves all six families and grids from 21×21 to 194×194. Table R2 (HMAGAT, ACC %, no retraining) tests (i) 20 further unseen layouts per maze family, 32 episodes each, with 95% CI over layouts, and (ii) grids with 4× the area and 4× the agents of DM-160/DW-128, with horizon and time budget scaled accordingly.

TestConfigFixedOursΔACC [95% CI over layouts]Improved
20 new layoutsDM-16049.861.2+11.4 [8.9, 13.9]18/20
20 new layoutsSM-16071.181.7+10.6 [8.3, 12.9]19/20
4× gridMaze 42×42, 640 agents44.557.8+13.3n/a
4× gridWarehouse 46×46, 512 agents71.989.1+17.2n/a

On new layouts the gain stays large (+11.4 and +10.6 pp, with intervals well above zero) and is positive on 18 and 19 of 20 layouts. It also carries over to 4× larger mazes and warehouses without retraining (the 4× grid rows are point estimates).

Minor

Revised Table 1 includes the fixed baseline (ACC 19.5/14.1/98.4, communication 2,748k/1,580k/562k), and Table 2 its absolute values. The text now reports 95% paired-bootstrap intervals for key comparisons, for example +15.6 [+9.4, +21.9] pp for the full selector over the auxiliary-only variant on DM-192 and +2.3 [−3.1, +7.8] pp for screened {3,5,7} over the full pool. The final version will add them to Tables 1–2 and Figure 3. Differences whose interval contains zero are reported as not significant.

We are happy to clarify any further points.

Reviewer_cwofOpenReview ↗

Official Comment by Reviewer cwof

I thank the authors for the substantial effort put into addressing my concerns. I believe the paper has improved considerably in terms of presentation and soundness, with the new experiments clarifying how the set of radii was selected and evaluating alternative selections (W1). Requesting further communication when the available information is insufficient remains a direction for future work (W1).

The experimental section has improved and reads more fluently (W2). Results are presented more clearly in Section 5; however, I still find that some important interpretations are missing. For example:

"Second, gains grow with headroom: HMAGAT configurations with fixed ACC of at least 90%, 60-90%, and below 60% gain 1.5, 14.2, and 30.9 points on average." This observation would benefit from further interpretation and insight from the authors, rather than primarily reporting numerical improvements.

My other concerns have been addressed or substantially mitigated, but the one about the incremental nature of the methodology remains. The rebuttal strengthens the empirical justification for the method, but I believe the paper should offer more insight into why adapting the communication radius constitutes a significant contribution, and in which settings this methodology could be useful. The evaluation remains limited to grid-based simulations, leaving its applicability beyond these settings uncertain.

Nevertheless, the stronger empirical evidence and the substantial improvements to the manuscript led me to a more positive assessment. I will raise my score to weak accept, while leaving the final assessment of the contribution’s significance to the AC.

Dear Reviewer cwof,

Thank you for the thoughtful follow-up and for raising your score. Your feedback has substantially improved the paper. We will expand the interpretation of the results, including the headroom analysis, in the final version.

Best regards, The Authors

Reviewer_mfBsOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes an adaptive communication-range learning framework for decentralized Multi-Agent Pathfinding (MAPF). Rather than using a fixed communication radius for all agents throughout planning, the proposed method allows each agent to dynamically select an appropriate communication range—small, medium, or large—based on its current local state. To obtain supervision, the authors first perform offline evaluations on expert trajectories while keeping the underlying planner fixed, comparing how different communication ranges affect the planner’s agreement with expert actions. The resulting preferences are then used as training labels for a lightweight range selector that combines local spatial observations with auxiliary features, including distance to the goal, BFS-based cost-to-go, and the number of neighboring agents under different candidate ranges. During deployment, each agent independently updates its communication range at every time step, thereby dynamically determining the graph, hypergraph, or communication mask used by the underlying planner. The framework can be integrated with different existing communication-based MAPF planners without modifying their action policies. Overall, the proposed state-dependent and agent-specific communication mechanism is designed to better match communication scope to local coordination needs than a uniform fixed-range strategy.

Critical strengths

1.The research problem is clearly defined and practically relevant. The paper addresses a specific limitation in decentralized Multi-Agent Pathfinding (MAPF): a fixed communication range cannot adequately accommodate variations in local coordination demands across agents and planning stages. By treating the communication range as an agent-specific, state-dependent decision variable that can change over time, the paper provides a clear and well-motivated formulation that is closely connected to communication efficiency in multi-robot coordination.

2.The proposed method is simple, modular, and readily applicable to existing planners. Instead of retraining the entire MAPF policy, the authors keep the underlying backbone fixed and train only a lightweight communication-range selector. Through the common neighborhood-construction interface, the framework is integrated with three distinct communication architectures—MAGAT, HMAGAT, and LC-MAPF—demonstrating that the proposed mechanism is not tied to a single message-passing design and has a certain degree of generality.

3.The experimental evaluation is relatively comprehensive and produces consistent results across different settings. The method is evaluated on six map families and 21 map-population configurations, covering scenarios with 96 to 256 agents. Across all three backbones, adaptive communication consistently improves planning success rates while reducing communication payload and overall runtime, providing empirical support for the effectiveness of state-dependent communication-range selection.

Critical weaknesses

1.The communication range is restricted to three discrete choices, which limits the expressiveness of the proposed selector. In the current implementation, each agent can only choose among Manhattan radii of 3, 5, and 7, leaving finer-grained or continuous communication ranges unexplored. As a result, it remains unclear how well the framework would handle communication requirements that vary more smoothly across states, environments, or agent densities.

2.There is also a potential distribution mismatch between offline supervision and online deployment. During offline label generation, each candidate range is evaluated by assigning the same communication range to all agents, resulting in a uniform-range topology. During deployment, however, different agents may simultaneously select different ranges, producing a heterogeneous mixed-range topology. Consequently, the selector is trained from counterfactual evaluations under uniform communication structures but is ultimately used to construct mixed-range structures online. It would therefore be useful to assess the extent to which this train–deployment mismatch affects the reliability of the learned range preferences.

3.Finally, the experimental evaluation is limited to simulation and does not include validation on physical robots or under realistic communication imperfections. The paper itself notes that real-world deployment would require accounting for sensing uncertainty, robot dynamics, and communication failures. Since the current experiments are conducted under largely idealized simulation settings with known maps, the robustness of the proposed framework to factors such as packet loss, communication delay, asynchronous message exchange, and localization errors remains unclear.

Questions for authors

1.The selector uses both spatial occupancy information and per-candidate neighbor counts, which are closely related to local agent density. Although the paper includes a density-based baseline, it would be useful to further investigate whether the learned selector captures coordination patterns beyond density alone. For example, the authors could consider feature-importance analysis or controlled experiments in which local densities are similar but interaction structures differ. 2. The deployment topology can be asymmetric because each receiving agent independently selects its own communication range. Could the authors provide further motivation for this receiver-specific design? It would also be helpful to understand whether enforcing symmetric communication neighborhoods would significantly affect planning performance, communication efficiency, or the behavior of the underlying backbones. 3. The proposed approach relies on expert trajectories generated by a centralized search-based solver to construct the supervision signal. Could the authors clarify how sensitive the learned selector is to the quality of these expert trajectories? In particular, it would be interesting to know whether the method remains effective when supervision is obtained from a weaker expert or a suboptimal planner.

4 comments

We thank Reviewer mfBs for the accurate summary and for recognizing the well-motivated problem, the modular design, and the comprehensive evaluation. We uploaded a revised PDF with changes in blue, and the experiments added for this response are detailed in the new App. H. New HMAGAT runs use DM-192 (dense maze, 192 agents), SW-224 (sparse warehouse, 224 agents), and ER-128 (empty room, 128 agents), with 128 paired episodes each (the Table 1 protocol). We also write SM/DW for sparse maze/dense warehouse and OST for ost003d.

W1. Only three discrete ranges

(i) Grid ranges are discrete. Manhattan neighborhoods are defined by integer radii, so a continuous range reduces to a finer integer set.

(ii) The framework already handles a finer set. The three scales are screened from the trial pool r ∈ {1,…,9}, and the full candidate pool ablation (Table 1) trains the selector on every trial radius. Its success stays within 2.3 pp of ours, which is not significant (screened minus full pool on DM-192 is +2.3 [−3.1, +7.8] pp), and its communication drops further (0.59/0.41/0.28 vs. 0.74/0.57/0.46 on DM-192/SW-224/ER-128). Finer choices therefore give a lower-payload operating point. We keep three scales in the main results because their labels are better balanced and the behavior is easier to interpret, and the revision reports both.

(iii) Other candidate sets give similar results. Retraining with {2,4,6}, {4,6,8}, or {3,7} gives 39.8/82.8/98.4, 38.3/83.6/99.2, and 36.7/80.5/98.4 ACC on DM-192/SW-224/ER-128, compared with 41.4/85.2/99.2 for {3,5,7} and 19.5/14.1/98.4 for the fixed default. On the two crowded configurations every set retains most of the gain, and removing the medium scale costs the most, so the result does not hinge on {3,5,7}.

(iv) No single scale suffices. The best uniform range changes across configurations (in App. E, medium is best on DM-128, small on DM-160/192 and SW-192, and large on ER-160), and the selector uses all three within one episode (App. G).

(v) K=3 is not hard-coded. Scoring (Eq. 2) and labeling (Eq. 3) apply to any candidate set, as the full-pool and alternative-set results show.

W2. Uniform-range labels vs. mixed-range deployment

We checked this mismatch in three ways.

(i) The mismatch is confined to higher-order effects. Links are receiver-specific (Eq. 7), so when agent i selects range r, its eligible incoming set is the same set scored offline for r. Other agents' ranges affect i only indirectly, through what its neighbors aggregated in earlier rounds or layers and, for HMAGAT, through shared hyperedges.

(ii) All reported results are closed-loop on mixed topologies. Adaptive exceeds the best of small/medium/large in all five configurations of Table 11 (e.g., 67.2 vs. 54.7 on DM-160 and 90.6 vs. 85.9 on SW-192). Frequency-matched random also builds mixed topologies but falls below the fixed reference on DM-160 and SW-192, so the gain comes from state-dependent choices and is not explained by mixing itself.

(iii) Direct measurement shows high agreement. On 2,000 held-out expert states per configuration, we set every other agent to its predicted range, vary only the focal agent's range over the three candidates, and recompute CiC_i under the resulting mixed topology. For HMAGAT, the mixed-topology argmin agrees with the uniform-range label on 81.6% of non-tied samples (Spearman ρ = 0.78). When they disagree, the score gap between the two choices is 0.021 nats on average, against 0.164 between the best and worst candidate. Disagreements therefore cost little, and the uniform-range labels largely reflect the focal agent's own preference.

This analysis is included in the revision.

W3. Simulation only / imperfect communication

We leave physical robots to future work and test imperfect communication in simulation by dropping each directed message independently with probability p, identically for both planners (ACC %, DM-192 / SW-224 / ER-128).

SettingFixedAdaptive
No loss (paper)19.5 / 14.1 / 98.441.4 / 85.2 / 99.2
p = 0.118.0 / 13.3 / 97.739.1 / 83.6 / 99.2
p = 0.215.6 / 11.7 / 96.935.9 / 80.5 / 98.4

Both planners degrade gracefully, and the adaptive advantage persists at both loss rates (over 20 pp on DM-192 and SW-224). Position noise (σ=1) and 20% neighbor dropout in the selector's inputs reduce adaptive ACC by at most 3.2 pp (details in our response to Reviewer cwof). Under point-to-point delivery, which our payload metric models, adaptive communication roughly halves the transmitted planner payload (0.50× on HMAGAT). Revised Sec. 6 discusses asynchrony, delay, and localization error.

Q1. Does the selector capture more than density?

The existing results already point beyond density. The validation-tuned density rule (three bins, non-monotonic assignment allowed) stays 9.4 / 6.3 / 11.7 ACC points below our selector on DM-160 / ER-224 / SW-192 (Table 2). The auxiliary-only variant already contains per-candidate neighbor counts (density at all three scales) plus goal features, yet it is 8.6–15.6 points below the full selector and below observation-only (Table 1), so the spatial arrangement in the occupancy map carries information that counts do not.

Following the reviewer's suggestion, we added three analyses.

(i) A density-only classifier, trained only on the three neighbor counts, reaches 52.4% top-1 accuracy on held-out offline labels, vs. 68.9% for the full selector.

(ii) Labels remain mixed at matched density. Binning held-out states by their (small, medium, large) neighbor counts gives a size-weighted mean label entropy of 1.18 bits within bins vs. 1.43 overall (maximum 1.58), so density alone leaves the preferred scope largely undetermined.

(iii) Interaction structure matters at matched density. Within a bin, large labels are 2.3× more frequent when another agent lies on the focal agent's BFS shortest path within 7 cells, i.e., when its route is occupied.

Q2. Why receiver-specific (asymmetric) neighborhoods?

We chose this design for four reasons.

(i) It keeps decisions decentralized. Each agent decides its incoming context from its own state, without negotiation. Under broadcast, the receiver simply filters what it hears, so no range needs to be shared. A symmetric rule needs both rir_i and rjr_j for every pair, which means exchanging ranges whenever they change.

(ii) It is consistent with supervision, since agent i's eligible incoming set is the one scored for its label (W2).

(iii) It imposes no cost on other agents. Under Eq. 7, agent i choosing the large range only lets i receive from agents within 7 cells. Max-symmetrization adds the reverse links, so all those agents must also receive i's messages whatever they chose. Min-symmetrization cuts i off from neighbors that chose the small range, even when i needs broad context.

(iv) All three backbones support it natively. MAGAT (directed graph attention), HMAGAT (directed hypergraphs), and LC-MAPF (per-receiver masks) handle directed structures without modification.

The table compares symmetric variants on HMAGAT (ACC % / C).

TopologyDM-192SW-224ER-128
Receiver-specific (ours)41.4 / 0.7485.2 / 0.5799.2 / 0.46
Sym-max (d≤max⁡(ri,rj)d\le\max(r_i,r_j))39.8 / 0.9383.6 / 0.7898.4 / 0.69
Sym-min (d≤min⁡(ri,rj)d\le\min(r_i,r_j))33.6 / 0.5278.9 / 0.3996.9 / 0.31

Receiver-specific links dominate sym-max, which spends 26–50% more communication with lower success. Sym-min trades 2.3–7.8 pp of success for lower communication.

Q3. Sensitivity to expert quality

(i) The label is relative. Ci(R)C_i(R) compares candidate ranges for the same expert action under the same frozen policy, so an expert error that shifts all candidates equally leaves the label unchanged.

(ii) It is consistent with backbone training. The backbones are themselves trained by imitating search-based experts, so the same kind of expert keeps the supervision aligned with the planner's action distribution.

(iii) An expert-free strategy stays below ours. SW-UCB uses only goal-progress feedback and improves over the fixed reference, but remains 3.9–7.0 points below our selector (Table 2). Expert supervision adds value, but the framework does not require an optimal expert.

We also tested a weaker expert directly. We relabeled 1M states with the same solver under a 4× smaller expansion budget (expert SoC 7.9% higher on the same instances) and retrained the selector on them. ACC is 38.3 / 84.4 / 98.4 on DM-192 / SW-224 / ER-128, retaining most of the gain over the fixed default (19.5 / 14.1 / 98.4). A full-scale study (regenerating all trajectories and re-scoring about 10.9M samples) will be in the final version.

Presentation

The revised PDF improves presentation in four ways. It (i) adds an algorithm box covering offline scoring, labeling, training, and deployment, (ii) adds a notation table, (iii) moves key definitions into Secs. 3–5 (observation and auxiliary inputs, radii 3/5/7, each backbone's default range, the communication metric, and map and configuration abbreviations), and (iv) removes redundant paragraphs to make room for the new analyses.

We are happy to clarify any further points.

I thank the authors for their efforts in addressing my comments. Their response has helped clarify some of my concerns, although a few issues remain.

Dear Reviewer mfBs,

Thank you for reading our response and for your follow-up. We would be glad to address the remaining issues. Could you let us know which points you still have concerns about? We will respond promptly within the discussion period.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.