acceptodds
Under review as a conference paper at ICLR 2027

TAGS: Topology-Aware Graph Scheduling of Heterogeneous Robots for Delivery and Collaboration

Abstract

Heterogeneous robots serve capacity-limited delivery requests and synchronized collaborative tasks by coordinating repeated cargo trips and capability-covering teams over a shared travel network. These operations compete for robot availability: a delivery can delay team formation, while a partial team reserves robots needed for cargo transport. We introduce Topology-Aware Graph Scheduling (TAGS), a unified learning framework that couples delivery progress and partial-team commitments through an event-driven representation of shared robot availability. On this evolving state, a topology-aware entity graph relates available robot resources to task requirements and travel costs, enabling an autoregressive robot–command policy to coordinate cargo dispatch and team formation. We compare TAGS with adapted attention-based learning, mathematical optimization, neighborhood search, and rule-based scheduling on benchmarks with 15, 35, and 50 heterogeneous robots. With 50 robots scheduling 25 delivery and 25 collaborative tasks, best-of-16 TAGS completes every instance and reduces mean makespan by 6.9% and collaborative waiting by 27.1% relative to the respective best full-completion baselines. It retains the lowest mean makespan under zero-shot transfer from 50% to 75% and 100% collaboration; a three-robot demonstration illustrates physical execution.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Multi-Robot Scheduling, Heterogeneous Robot Collaboration, Reinforcement Learning

Reviews

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

The paper studies joint scheduling of capacity-limited repeated deliveries and synchronized, capability-covering collaborative tasks by heterogeneous robots on a shared travel network, with the objective of minimizing makespan. It formulates the problem as an event-driven MDP and proposes TAGS, which encodes robots, tasks, and storage nodes as a complete entity graph with a travel-time attention bias, and autoregressively selects a robot and then its command. The policy is trained with PPO and a waiting penalty, and is evaluated with best-of-16 decoding. On synthetic instances with 15, 35, and 50 robots, TAGS achieves the lowest mean makespan among full-completion methods only at 50 robots, and it keeps its ranking when the collaboration ratio is increased without retraining.

Critical strengths

Jointly scheduling deliveries and team formation over shared robots is a practically relevant problem.

Critical weaknesses
  1. Novelty relative to existing learned schedulers. The main learning components (pointer decoding, a Graphormer-style distance bias, PPO, and best-of-B sampling) are established techniques. Decoders that select a vehicle and its next node, either sequentially (Li et al., IEEE Trans. Cybern., 2021) or jointly (2D-Ptr, Liu et al., AAMAS 2024), have been proposed for the heterogeneous capacitated vehicle routing problem with a makespan objective. Robot–task pairs are also selected jointly in learned multi-robot scheduling (Wang et al., 2022). Since Li et al. (2021) and 2D-Ptr are not cited and none of these methods is compared, it is difficult to assess what the proposed policy adds beyond them. The contribution therefore appears to lie mainly in the event-driven formulation of the combined problem.
  2. Dependence of the gain on candidate sampling. On D50, TAGS with a single deterministic rollout (argmax) is behind Greedy (MS 46.28 vs. 43.63, Sec. 4.4), and the advantage appears only when multiple sampled candidates are generated and the best one is selected (best-of-B with B ≥ 8 in Fig. 4; B = 16 in the main results), whereas Greedy is run once. Since the problem is fully observable and deterministic, an optimal deterministic policy exists; the reliance on sampling therefore suggests that the learned policy is still far from optimal. The results thus seem to reflect sampling with a perfect simulator rather than the quality of the learned policy itself.
  3. Comparability of inputs with the learned baseline. Only TAGS receives the full pairwise distance tensor through the attention-distance bias (App. C). Without this bias, TAGS (MS 43.62 on D50) performs similarly to HeteroMRTA (43.68), which suggests that much of the gain comes from this additional input.
Questions for authors
  1. Greedy with the same sampling budget. How does a randomized Greedy (e.g., selecting randomly among the top-ranked commands, as in the construction phase of GRASP) perform under the same best-of-16 budget as TAGS?
  2. HeteroMRTA with the same distance input. How does HeteroMRTA perform when given the same pairwise distance bias, on D15, D35, and D50?
  3. Comparison with decoders that select a vehicle and a node, sequentially or jointly. How does TAGS compare with Li et al. (2021), 2D-Ptr (Liu et al., 2024), and Wang et al. (2022), adapted to the same states, commands, masks, and distance inputs?
  4. Quality of the learned policy. Please report argmax (currently shown only for D50 in Fig. 4) and mean-sample performance alongside best-of-B for each problem size, together with learning curves (MS and policy entropy per seed), to show whether training has converged.
  5. What is new in the formulation (clarification). Beyond combining capability-covering teams, synchronized execution, and multi-trip deliveries, which modeling or algorithmic difficulty does the formulation address that prior work (e.g., Bischoff et al., 2020, which is not cited; Drexl, 2012) does not?
5 comments
AuthorsOpenReview ↗

Follow-Up: Request for Your Response Before the Discussion Deadline

Dear Reviewer Tjbt,

Thank you for reviewing our paper and providing your comments and suggestions. Of the five related papers mentioned in your initial review, four were cited without titles or method names, possibly due to an inadvertent omission of the full references. Based on the information provided, we independently located and read the papers that appeared to match your references, although we are not certain that they are exactly the studies you intended; we would appreciate any further clarification. We have carefully considered your suggestions, conducted additional experiments, and provided constructive, point-by-point responses. Please refer to our seven-part response above for details. As the discussion period approaches its conclusion, we would appreciate your feedback on these responses and would welcome any remaining questions requiring clarification. Your comments have greatly helped us improve the paper and strengthen its quality. Thank you again for your time and suggestions.

Best regards,
The Authors of Submission 58654

Reviewer_TjbtOpenReview ↗

Response to Authors

Thank you for answering my questions and for the additional experiments. The results show that the gains come mainly from the distance bias and from sampling during decoding. Although training maximizes the expected return, the sample mean is worse than the handcrafted Greedy at D15 and D50. Even though the entropy weight is 0, the policy’s entropy remains high, so the training may be insufficient. Therefore, it is unclear whether the results and the ablation comparisons reflect the actual performance of the method. The main contribution of this paper lies in the problem formulation, which is solved by combining existing methods. I suggest a major revision and resubmission to a conference or journal. A quantitative evaluation with physical robots would also be helpful. I maintain my rating.

AuthorsOpenReview ↗

Errors in the Assessment of Return, Training, and Ablation Evidence

1. HeteroMRTA shares the 39-dimensional entity features. Its inputs include shortest-path topological reference-distance features, and its command readout uses robot-to-target distances. Its action space, feasibility masks, reward, training budget, and evaluation protocol were also adapted to match ours, retaining its separate robot/site encoders and cross-attention architecture.

See Sec. 4.1, App. C.4, and our November 8 response. Our ablation establishes the benefit of distance bias. You recast this evidence of a component's effectiveness as a weakness of the method.

2. Best-of-KK sampling is standard in neural combinatorial optimization; Li et al. and 2D-Ptr, cited in your review, use up to 12,800 samples per instance. You wrote:

"Although training maximizes the expected return, the sample mean is worse than the handcrafted Greedy at D15 and D50."

Under the return actually optimized during training, argmax and best-of-16 outperform Greedy at all three sizes, and mean-sample outperforms Greedy at D35 and D50.

The paper’s reward definition gives the following return upon successful task completion:

R=−MS−βWfinal=−MS−βN⋅AWT,β=0.1R=-MS-\beta W_{\mathrm{final}}=-MS-\beta N\cdot AWT,\quad\beta=0.1.

Returns from unrounded MSMS and AWTAWT (higher is better):

SizeGreedyTAGS argmaxTAGS mean-sampleTAGS best-of-16
D15−58.24−58.08−60.35−45.20
D35−54.87−50.20−50.15−42.52
D50−58.22−56.37−57.12−49.64

Best-of-16 reduces the composite cost versus Greedy by 22.4%, 22.5%, and 14.7% at D15, D35, and D50, respectively.

Mean-sample is a supplementary diagnostic of ordinary sampling performance; the paper evaluates the complete best-of-16 solver.

Table 3 reports frozen-policy zero-shot results at 75% and 100% collaboration on D50. At 50% (reference), 75%, and 100%, TAGS reduces makespan versus Greedy by 6.9%, 15.9%, and 19.7%, respectively. Your final assessment does not account for this growing advantage.

3. We report joint entropy for robot selection and conditional command selection:

H(π)=H(πrobot)+Ei∼πrobot[H(πcommand∣i)]H(\pi)=H(\pi_{\mathrm{robot}})+\mathbb E_{i\sim\pi_{\mathrm{robot}}}[H(\pi_{\mathrm{command}\mid i})].

Each seed has 107 records over 1,500–160,500 environment transitions:

SeedInitial HHFinal HHDropFinal eHe^H
202607062.0271.24038.8%3.46
202607071.9761.24636.9%3.48
202607082.0961.40533.0%4.08

For the final recorded mean joint entropy in nats, eHe^H gives an effective branching scale of 3.5–4.1 equally likely joint actions.

First versus last 20 records (mean ± population SD):

SeedFirst 20Last 20
202607061.742 ± 0.1391.308 ± 0.094
202607071.731 ± 0.1241.134 ± 0.065
202607081.834 ± 0.1431.430 ± 0.053

All seeds show an overall decline and smaller late-training fluctuations. Across the final two consecutive 20-point windows, mean joint entropy changes by only 1.21%, 2.97%, and 1.04%. Your final assessment does not account for this evidence.

4. All four component ablations in Figure 3 show positive contributions. Learned robot selection, the graph encoder, attention-distance bias, and the waiting reward reduce makespan by 3.4%, 12.0%, 6.9%, and 6.2%, respectively, versus their ablated variants. All four also improve AWTAWT. These experiments use three seeds, matched training budgets, common evaluation instances, and best-of-16. How did you conclude that the ablation results are "unclear"?

5. Delivery and partial-team commitments are bidirectionally coupled: deliveries can delay collaboration, while partial teams reserve robots that could serve deliveries. Decisions can change other robots' availability and feasible actions. We explicitly decompose and handle these constraints through:

  • Coupled state tracking: remaining demand, in-transit cargo, partial teams, missing capabilities, and occupancy.
  • Constrained robot–command decisions: robot selection, delivery quantities, collaborative commitments, storage moves, and updated feasible actions.
  • Constraint propagation and event execution: in-transit cargo deduction prevents duplicate allocation; assembly-storage locks and incremental capability coverage organize teams; synchronized departure, common completion, and resource release advance execution.

You reduce this to problem formulation and existing methods, ignoring our decomposition and handling of coupled constraints. Listing Pointer Networks, Graphormer, and PPO does not assess these contributions.

6. You provided no response for ten days after our November 8 rebuttal, then stated less than 24 hours before the deadline:

"A quantitative evaluation with physical robots would also be helpful."

Do you expect us to complete additional experiments in less than one day?

Reviewer_WrveOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduced Topology-Aware Graph Scheduling (TAGS) as a learning framework for capacity-limited delivery tasks with collaboration for shared robot tasks. The paper presents capacity constraint delivery tasks with unique capabilities and collaboration modeled as a shared delivery task containing multiple robots. TAGS couples delivery progress and partial team commitments throughb an event-driven representation of shared robot availability. The algorithm is tested on 15, 35 and 50 robots, using the best of an ensemble of schedules, reducing the makespan and collaborative waiting compared to the best baselines. It also shows zero-shot transfer from 50% to 75 and 100% collaboration, along with a 3 robot demonstration.

The paper presents a learning based model for an open problem in multi-robot collaboration. The experimental, baselines and metrics provide a solid empirical justification of the contributions of the paper.

Critical strengths
  1. Technical contribution: This paper models it as a constraint satisfaction problem and introduces a graph neural network (GNN) to solve it.
  2. Empirical strength: Paper compares their model against 2 exact solvers, 2 heuristics and one learning based model. Paper also shows zero-shot capabilities to larger set of collaboration tasks that are out of distribution.
  3. Relevance and impact: Collaboration is an open-problem where learning based models can provide improved performance over existing methods.
Critical weaknesses
  1. The training time is not fully discussed. Learning models also incur a cost on the training time which is a weakness that needs to be addressed. Furthermore, the percentage improvement over Greedy Heuristic leave the question of how significant the contribution is compared to existing baselines.
  2. While ability to scale to OOD collaboration scales is impressive, how does the model perform when scaled up to larger problem than what the model is trained on? Could you clarify how the problem is different from a standard task allocation and scheduling using GNNs per cited Wang et al. 2022 [1] or more recent work that follow up on Wang et al. such as Altundas et al 2025 [2], where GNNs are shown to have zero-shot scalability to larger problems, which justifies the incurred cost of training time. A small set of larger scale problems evaluated would further improve the conclusions of the paper.
  3. While Trade-offs are discussed, a dedicated Limitations section would be helpful in clarifying what the true contributions are.

[1] Wang, Z., Liu, C., & Gombolay, M. (2022). Heterogeneous graph attention networks for scalable multi-robot scheduling with temporospatial constraints. Autonomous Robots, 46(1), 249-268.

[2] Altundas, B., Chen, S., Singh, S., Deo, S., Cho, M., & Gombolay, M. (2026). Heterogeneous Graph Transformers for Simultaneous Mobile Multi-Robot Task Allocation and Scheduling under Temporal Constraints. Advances in Neural Information Processing Systems, 38, 90611-90648.

Questions for authors
  1. How does the Makespan and Average Waiting Time (AWT) differ? Would Makespan also account for the AWT or is this an independent metric?
  2. Could the author's clarify how many training seeds were used in the evaluation of the learning based models?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.