- 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
-
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.
-
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
-
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.
-
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 . 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
-
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?
-
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?
-
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.
-
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?
-
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
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+time | ACC step only | SoC, both solved | Payload/step | Matched-state payload | |
|---|---|---|---|---|---|
| Fixed | 70.2 | 75.6 | 1 | 1 | 1 |
| Adaptive | 83.7 | 85.4 | 0.97 | 0.56 | 0.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 %).
| Config | Fixed | Ours | ΔACC [95% CI over layouts] | Layouts improved |
|---|---|---|---|---|
| DM-160 | 49.8 | 61.2 | +11.4 [8.9, 13.9] | 18/20 |
| SM-160 | 71.1 | 81.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.
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.
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.
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.