Heterogeneous Graph Transformers for Simultaneous Mobile Multi-Robot Task Allocation and Scheduling under Temporal Constraints
Authors: Batuhan Altundas
Shengkang Chen
Shivika Singh
Shivangi Deo
Minwoo Cho
Matthew Craig Gombolay
Venue: NeurIPS 2025 poster ()
Keywords: Task Allocation and Scheduling
Multi-Agent Coordination
Graph Neural Networks
Primary area: optimization
TL;DR: We propose a fast, scalable Simultaneous Decision-Making model for multi-agent task allocation using a Heterogeneous Graph Transformer with edge attention, outperforming heuristics and solvers and generalizing from small to large-scale problems.

Abstract: Coordinating large teams of heterogeneous mobile agents to perform complex tasks efficiently has scalability bottlenecks in feasible and optimal task scheduling, with critical applications in logistics, manufacturing, and disaster response. Existing task allocation and scheduling methods, including heuristics and optimization-based solvers, often fail to scale and overlook inter-task dependencies and agent heterogeneity. We propose a novel Simultaneous Decision-Making model for Heterogeneous Multi-Agent Task Allocation and Scheduling (HM-MATAS), built on a Residual Heterogeneous Graph Transformer with edge and node-level attention. Our model encodes agent capabilities, travel times, and temporospatial constraints into a rich graph representation and is trainable via reinforcement learning. Trained on small-scale problems (10 agents, 20 tasks), our model generalizes effectively to significantly larger scenarios (up to 40 agents and 200 tasks), enabling fast, one-shot task assignment and scheduling. Our simultaneous model outperforms classical heuristics by assigning 164.10\% more feasible tasks given temporal constraints in 3.83\% of the time, metaheuristics by 201.54\% in 0.01\% of the time and exact solver by 231.73\% in 0.03\% of the time, while achieving $20\times$-to-$250\times$ speedup from prior graph-based methods across scales.

Heterogeneous Graph Transformers for Simultaneous Mobile Multi-Agent Task Allocation and Scheduling under Temporal Constraints
Batuhan Altundas*
Shengkang Chen
Georgia Institute of Technology Atlanta, GA 30332 baltundas@@gatech. edu
Georgia Institute of Technology Atlanta, GA 30332 schen7540gatech. edu
Shivika Singh
Shivangi Deo
Georgia Institute of Technology Atlanta, GA 30332
Georgia Institute of Technology Atlanta, GA 30332 sdeo338gatech, edu
esingh794@@atech.cmm com
Minwoo Cho
Matthew Gombolay
Georgia Institute of Technology Atlanta, GA 30332 mcho3188gatech.. edu
Georgia Institute of Technology
Atlanta, GA 30332
mat thew got.eww.ombblayycc.oommmm gatech. edu
Abstract
Coordinating large teams of heterogeneous mobile agents to perform complex tasks efficiently has scalability bottlenecks in feasible and optimal task scheduling, with critical applications in logistics, manufacturing, and disaster response. Existing task allocation and scheduling methods, including heuristies and optimization- based solvers, often fail to scale and overlook inter-task dependencies and agent heterogeneity. We propose novel Simultancous Recision-Making model for Heterogeneous Multi-Agent Task Allocation and Scheduling (HM-MATAS), built Residual Heterogeneous Graph Transformer with edge and node-level attention. Our model encodes agent capabilities, travel times, and temporospatial constraints into rich graph representation and trainable via reinforcement learning. Trained on small-scale problems (10 agents, 20 tasks), our model generalizes effectively to significantly larger scenarios (up to 40 agents and 200 tasks), enabling fast, one-shot task assignment and scheduling. Our simultaneous model outperforms classical heuristics by assigning 164. 10% more feasible tasks given temporal constraints in 3.83% of the time, metaheuristics by 201.54% in 0.01% % of the time and exact solver by 231.73% in 0.03% the time, while achieving 20x-10-250 speedup from prior graph-based methods across scales.
Introduction
Multi-Agent Task Allocation and Scheduling (MATAS) seeks determine the optimal assignment of tasks to agents, e.g., drones delivering supplies across disaster zones [1], and establish a corresponding schedule for each agent, accounting for both temporal and spatial constraints. Generation of optimal plans is essential in multi-agent systems, with applications ranging from search and rescue [2-5].
These authors contributed equally this work
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

HM-MATAS Problem
TARGETNET
Plan Execution
Task
T0D0
Hatarogensilyy
Allocation
Ayee
Exwastion Times
Travel Tines
PLAN
Obstacia
10.00
Constraints
Scheduling
Order Constraints
Windows
Obslacle
Figure 1: Simultaneous Task Allocation and Scheduling for Mobile Multi-Agent Teams with Hetero- geneous Travel Time and Task Execution Time under Temporal Constraints. TARGETNET takes in observation and outputs task assignment and schedule. The environment executes and evaluates the optimality and feasibility.
warehouse automation [6. 7], transportation systems [8-11] and satellite coordination in space [12- 14]. The simplest MATAS problem is the Multpple Travelling Salesman Problem (mTSP), optimizing the travel cost of multiple agents, making it an NP-hard problem that can become more complex with the addition of complex dependencies and constraints such as task coupling, time windows and heterogeneity in tasks and agents based on physical capabilities [15-24].
We aim develop generalized approach that integrates these subproblems within unified model, considering task and agent heterogeneity.
While constraint satisfaction methods can provide exact solutions to MATAS by handling temporal and spatial constraints [25, 26]. search-bace based optimizers scale poorly with increases in the number of tasks, agents, and constraints, and require handcrafted encodings and hand-tuned parameters, making them brittle for new domains. Metaheuristics, like Genetic Algorithms (GA) [27-30], and market-based approaches [31, 32] offer alternatives but rely domain-specifee knowledge and can provide suboptimal results.
Neural Network (GNN)-based solvers [23, 24, 33-38] show that learning based approaches can provide near-optimal results while remaining scalable by learning from data instead of relying hand-crafted solvers. However, GNNs face limitations in capturing dynamic, heterogeneous relations essential MATAS for heterogeneous agents due to the method of aggregation messages from multiple sources. Attention-baat based methods have been proposed to address these limitations [39], which are further expanded in Heterogeneous Graph Transformers (HGT) [40, 41] leverage attention mechanisms that allow effective modeling of heterogeneous and pairwise dynamics, making them suitable for MATAS tasks with complex relations.
Recent Graph
We tackle the challenge of Heterogeneous and Mobile MATAS (HM-MATAS) problems using scalable learning- based models. We introduce Task-Agent Relational Graph Encoding for Team- based Navigation and Execution of Tasks (TARGETNET), modeling framework that represents the Optimization Problem as a graph. TARGETNET assigns an agent to each task and schedules the tasks in the presence of order and time-window constraints. By leveraging relational representations, our method learns to generate closer-to-optimal policies than the baselines while allowing for deployment larger-scale problems. TARGETNET generates schedules in a fraction of the time it takes for the optimizer to find optimal solutions larger scales. Our results show that leveraging the expressiveness of Graph Transformers with edge attention and residual networks can allow for the creation fast and scalable policy, delivering robust and fast scheduling solutions for real-world multi-agent systems.
approach that leverages relational
summary, these are main contributions:
1. We present TARGETNET for modelling and solving HM-MATAS problems, enabling fast and scalable multi agent task planning. allowing training small instances and deployment on larger problems.
2. We propose a novel Node and Edge Awaee Heterogeneous Graph Transformer with Residuals for improved performance in modeling heterogeneous and dynamic rela- tions present in edge features. By leveraging the attention mechanism our method learns generalized policies that scale to larger problems without retraining.

---

3. We compare our model against tfate-of-the-arr models, showing that our model is able to generate schedules that are 13.26% better than the best performing metaheuristics 0.73% of the time, and 36.34% better performance than state-of-the-e GNN-based schedules in 4. 4.75% the time 10 agent-20 20 task problems, while generating 231.73% better than partial schedules generated by exact solvers after 12 hours in less than 12 seconds, in 40 agent-200) task problems.
2 Related Works
2.1 Multi-Agent Task Allocation
Gerkey and Mataric [15] proposed a taxonomy of the MRTA based on agent types (single-task vs. multi-task agents), task types (single-agent vs. multi-agent tasks), and assignment type (instantaneous assignment vs. time-extended assignment). In this work, we focus on single-task agents, single-agent tasks, and time-extend assignment (SR-ST-TA) problems which is combinatorial optimization problem known to strongly NP-hard. Unlike prior work [33, 24), we further account for Hetero- gencous Travel Time of agents along with interrelated constraints. The location of the other agents and the tasks that they are able to complete influence the performance of other agents, leading to Complex-Schedune Dependencies (CD) [16].
2.1.1 Non-learning-base Approaches
Researchers have developed different types of approaches to address the MATAS problem. Market- based approaches [31, 42, 43] and game-theoretical approaches [44, 45] are decentralized methods that enable distributed decision-making, but they typically yield worse performance compared to centralized approaches. Metaheuristics methods, including Ant Colony Optimization (ACO) [46, 47, 36] and Genetic Algorithm (GA) [30] rely search-based heuristics without any optimality guarantees. Since the MATAS problem is an optimization problem, it can be represented as Mixed Integer Linear Programming (MILP) problem [26], allowing for exact solvers [48, 49] generate solutions. Chakraa et al. [50] provides a detailed survey of existing optimization-based methods. However, most of these optimization-base approaches are computationally expensive and scale poorly with problem size.
To handle complex time constraints in task allocation and scheduling, various search-based methods have been proposed. Nunes and Gini [26] developed an auction-based method considering time- window constraints. Whereas Kartal et al. [51] used Monte Carlo Tree Search (MCTS) address MATAS with time-window constraints as well. Choudhury et al. [52] applied conflict-based search to find solutions under complex temporal constraints. However, these methods require expert domain knowledge to adapt to different problems, while our method of graph representation can encode the problem features and learn based given objective function through trial and error, making it more versatile for different objective functions.
2.1.2 Learning-based Approaches
Learning-basee MATAS methods model are function approximators [53] that trade-off training time to learn heuristic policies allow fast deployment without the need for experts [25]. Multi-Agent Reinforcement Learning (MARL) is used to train different models, such as Decision Trees [54], Neural Networks [55-57, 38, 58] and Recurrent Neural Networks (RNN) [55, 59]. The models were trained using different reinforcement learning algorithms, such as value-based [60, 61], policy- based [24, 33, 62], and actor-critic based [63, 64) learning. However, these approaches are limited in their modeling capabilities, only addressing subset of MATAS problems, such as Vehicle Routing Problems [65, 66), multiple Travelling Salesman Problems [67, 68), homogeneous agents, no travel time [33, 24], and struggling to scale effectively to larger, complex environments providing interpretability [69].
2.2 Graph Neural Networks
GNNs provide scalable approach to solving problems in multi-agent coordination [35, 70-72], adversarial agent modelling [73], and human-agent teaming [74]. Wang and Gombolay [33] proposed
3

---

a new type of Heterogeneous Graph Attention Networks (HetGAT) [75] with Edge Features [76] representing heterogeneous relational information for multi-agent task scheduling problems by se- quentially assigning agents to tasks. Transformer Attention mechanism has been used to solve limited scale constraint satisfaction problems such as Sudoku, however these methods do not scale up to larger problem sizes, and require a dense attention matrix to represent the constraints [77]. Heterogeneous Graph Transformers (HGTs) have been shown to outperform other attention based graph models in optimization problems while allowing for scalable and sparse relational representation [40], and they have been used for the Task Allocation for mTSP problems, followed by using an optimizer for solving the scheduling per agent without temporal constraints [62, 68]. However, existing HGT architectures lacks the ability to process relational information encoded within edge features. Our work leverages the capabilities of Heterogeneous Graph Transformers (HGTs) to address MATAS problems, effectively accounting for heterogeneous travel times and task completion durations.
3 Methodology
In Section 3.1 we present the HM-MATAS problem as an Optimization Problem, and in Section 3.2 present a Markov Decision Process (MDP) to simulate the movement of agents as they complete the tasks, allowing for a framework that can be used to train learning-bast baasid models using Reinforcement Learning [78]. In Section 3.3 present method of encoding the CSP problem in graph framework that can be adapted for single-step Task Allocation and Scheduling. In Section 3.4 we present a new method of integrating Edge Features into GNNs, which combine with the graph representation and train to solve HM-MATAS problems.
3.1 Problem Setup
Task Allocation and Scheduling under Temporal Constraints: We consider HM-MATAS prob- lem for mobile team of agents .A = [1,2... [A] and a set of tasks T = 21.2....,
Agents start in random locations and must travel to the location of the task to start the execution of the task. The heterogeneous execution time is the time it takes for agent to start a task j. 15) and finish it, thy, presented as t.y = tf t.y We also account for order constraints, where Wj is the minimum required wait-time between the completion of task j and start of task k and every task has a time window, [sk, ex]. where 8y is the carliest start time, and end before the deadline constraint, eg. The objective function is to minimize the maximum time it takes to complete all tasks, denoted as the makespan, while satisfying the temporal constraints. The MILP representation of the Optimization Problem can be found in the Appendix A.
Heterogeneous Trave Times using Precomputed Motion Plan: Physical heterogeneity of agents include heterogencous velocities which impact the travel time from one task to another [22]. We use Rapidly-exploring Random Graph Algorithm [79] compute the travel distances between agent start locations to task locations and the locations of pairs of tasks in the presence of obstacles. The heterogeneous velocities of each agent i, lead to having distinct travel times along the same path, represented as foo. for travel time from initial location to task j. and tT for travel time of agent Eiy i, from the location of task j. to task k. Abstracting the motion-planning enables integration with diverse planners [80-82], while preserving downstream optimization tractability [83].
3.2 Markoy Decision Process
We present the HM-MATAS problem in the form of a five-tuple Markov Decision Process < S, P, R, > that simulates the movement of agents through the map to complete the assigned tasks in a given ordered schedule. The state space, S, captures the state of the environment based on the current location of agents and tasks, when the agents will be available, a list of assigned and unassigned tasks, along with temporal constraints. The action space, A, consists of all possible agent-task pair selections, where each single action at time step t E [T, a, = (a,, Ty). represents assigning agent, as, to task, Ty. Each task is only assigned to an agent once, limiting the time horizon to number of tasks, [ The Transition Function, P. updates the state of the model, moving agents to new assigned task locations and generates new graph representation after assignment. The reward function, R, maximizes the number of feasible decisions, represented by boolean function feasible (st, ae), at every time-step, t, while minimizing the maximum makespan, tms, normalized

---

Simultansous Dacision Making Model Agenk
TARGETNET Layer Node and Edge Update
Assignment
Assggmeet
Reardual
Agent Edéga Atlention Agant Edge Message
Apent
Agent Noce Allention
Agant
-Tttto (Tady!
Message
of
Task Edge Attantion
Cihee (Tain))
Task Edge Message
Noxia
f
Tack Node Message
TJ
(a) Sample graph representation of simple agent-2 task problem, showing the heterogencous nodes, and relation- ships for Task Allocation and Schedul- ing using TARGETNET.
(b) Graph Aggregation using Edge and Node Attention and Mes- sage Passing with Residuals. Assignment node is updated using the combined Messages from agent and task nodes and edges based on Attention.
Figure 2: Graph- Task Allocation and Scheduling using GNNs with node and edge features.
to maximum deadline time, taa.. The constraint feasibility and optimality are combined using hyperparameters and B, for a total reward as shown in Eq. 1. To balance the short-term feasibility with long-term term plan quality and clarify credit assignment, we combine dense feasibility reward, +1 feasible, otherwise, with sparse reward at final timestep, t [T], that combines number and optimality of feasible assignments as shown in Eq. 1. I is the discount factor.
a(1
fma Laa
+ +BΣ²
reasible (s;, a;))
ift [
R(8t, 0z)
=
+1
if I feasible (8t, as) otherwise
3.3 Graph Modelling of Heterogeneous Task Allocation and Scheduling with Travel Times
We represent the HM-MATAS problem as a heterogeneous graph model G = (V, E) with vertices V describe Agent, Task, Assignment of an agent task, global State and Task Order nodes. Heterogeneous edges E that encode the relations between different heterogeneous elements of the graph. Each heterogeneous node encodes information unique the node type, such velocity and earliest available time for agents and time window constraints for tasks. Edges encode relational information between the two node types, representing travel time from agent's current location to tasks, and travel time and distance between tasks. We further augment our graph representation with the Assignment node simulate the assignment an agent task and explicitly model heterogeneous task execution time [84]. The Asxignment nodes representing a specific agent have edges between each other to encode the heterogeneous travel time from one task to another for the specific agent. Consequently, there are O([4[IT) ) Assignment nodes in the graph for |A] agents and [I'l tasks, with O(AA][T)) edges between the assignment nodes in total. Full details of the node and edge features can be found in Appendix B.
3.4 Graph Transformer Network with Edge Attention
GNNs were used to some MATAS problems represented graphs [33, 61, 62, 68] with Attention mechanisms [39, 40] showing higher performance by accounting for the relational importance of each edge. HGTs outperform other attention- based graph networks by leveraging the Transformer Attention mechanism [40, 85) in standard benchmarks. However, HGT's support node-tye--pppeciiiiiiie eype-specific attention, but does not innately support edge features, which crucial for MATAS [77].
augment each message-passing step HGTs, as described Appendix B, with edge- attention and messaging leveraging the distributive property of attention [86]. The node and edge features combine to update of target node feature, h [1], and edge features, [e(e). for the next layer, 1, for edge, connecting source node, s, to target node, t, as shown in Eq. and 3 respectively.
5

---

h t
Aggregate (eEN()))
(Atty(s,t) t) M (s) (tt Msga(e)
(2)
N'[c] f- (t) Ms
We pass information from edge features to target nodes using message passing. For multi attention, use MM W M h/-! to calculate message vectors for head i. WMe and W MSG along with the standard HGT weights [40] described in Appendix B, trainable.
((e)
(sg =
We) 6(c)
i=1
The edge attention, Eq. determines how important each edge message the target node, using edge features, h6-1, and target features, 1 The key values of the edge, K W 16-1, and query values for target node, (t) = W Q hi are used to compute the attention, normalized using the vector dimension of d, and the learned prior tensor P (()()).r(1))) The multi-head attention allows for the learning of multiple weights for the same features that are combined to increase the descriptive power of attention [85]. While the standard attention mechanism applies a softmax across multi-head attention, this formulation enforces that the policy always accounts for both edge and node features, even when some policies may not require them. By omitting the softmax, we allow attention weights reach zero, enabling the model learn policies that selectively ignore certain components of the graph. This flexibility improves the representational capacity of the model [87]. Key, query and attention weights, W Ke. W and WATT respectively, are learned and used to compute the attention used update both edge and target features.
N
o(e)
=
-L i=1
K ()) o(e) (2)))) ((o(e).r())
(e
(S)
Va
By accounting for both node and edge features, we present GNN algorithm that can be used for problems where relational information is vital for decision making, such as MATAS problems.
Residual Graph Neural Networks: We adopt specific type of residual network based upon the graph-raw residual [41] concept, where the initial input of the graph node and edge features are appended to each layer, to mitigate vanishing gradients in deep GNNs [88].
3.5 Simultaneous Decision Making Policy Training
We process the input features, represented as graph model in Section 3.3, using the edge-fcature augmented HGT, described in Section 3.4, to generate output predictions for Task Allocation and Scheduling policies. Our model takes in the initial state, Sp, and generates a Task Allocation, TA, and Task Scheduling, Sch, without iteratively interacting with the environment, allowing a significant boost computation speed.
Task Allocation:
We leverage the output features of the Assignment nodes, which represent the pairwise assignment of |A| agents to |T] tasks with total of [ nodes. The Assignment node features of the output reshaped into a [A] [T] matrix, and single agent is sampled for each task to achieve Task Assignment for single-agent tasks.
Scheduling:
We sort the Tasks using the output of the Task Order nodes connected to each task. During training, scheduling is performed by sampling tasks sequentially from Probability Mass Function over Task Order node outputs. Sampling proceeds without recomputing weights, requiring only single GNN forward pass.
Training: Our policy computes the Task Allocation and Scheduling in a single forward pass. However, we leverage the sequential nature of scheduling to train our models using REINFORCE [78, 89, 90] with log probabilities based on prior work for numerical stability [24]. We use the discounted reward, combining sparse final performance for optimization and dense feedback on individual task

---

constraint satisfaction. At any given time-step, t, the Task Assignment policy, ттA assigns an agent, a,, task, T, T. Simultaneously, the Scheduling policy, Tech determines which task, Tr, occupies the 8th position in the plan. This scheduling decision is conditioned on the history of assigned tasks, T<t., the complete set of agent-task pairings, (a, T)alt. and the initial state, 8p- We compute the gradient of the model using Eq. 6:
VaJ(0) Eeenp (Ereurr)>" ( r.), Vo (logTrA(aa so) log (TilTee, (a, than, than,,))) so)) (6)
4 Experiments
4.1 Experiment Setup
We generate our problems using the constraints described in Section 3.1, validated have optimal solution using exact solvers based on the MILP described in Appendix A. All learning-batt policies are trained on 200 small-scale problems (10 agents-20 tasks), with the configuration outlined in Table I of Appendix E. Three instances are initialized per model with different random seeds and trained in parallel. For testing, 200 problems are generated for small and medium scales (10 agents-50 tasks), 30 for large scale (20 agents- 100 tasks), and 10 for extra-large scale (40 agents-200 tasks). Due to the complexity of large and extra-large-scall problems, we generate and medium- scale problems, respectively, and combine them into a single map with shared obstacles. For each learning- based model, we train three instances with different random seeds and, for each test problem, report the performance of the best-performing instance. We then compute the mean and standard deviation of these best-case results across the problem set. Time performance calculated by solving 10 problems of the given scale using the models. Exact details of problem generation and reproducibility of our experiments can be found in Appendix E.
The following metrics are used to evaluate the performance of the policy. These capture quality (optimality), feasibility, and practical utility (training and inference speed):
Optimality Rate:
The Optimality Rate of the Final Reward is acquired using the reward for the total schedule at time [T), as described in Eq. I, normalized to the reward of the MILP Solver, o R R LP
Feasibility Percentage: The Percentage of Feasible Task Assignments is acquired by normalizing the number of feasible assignments the total number of tasks for each problem, (7 feasiblel///
Training Speed:
The mean training time per episode using a training dataset using small
scale problems, relevant for learning-based models.
Inference Speed:
Mean wall-clock time it takes generate the schedule in seconds.
4.1.1 Models and Baselines
We compare TARGETNET using Edge Enhanced HGT with Residuals against Heuristic and Metaheuristic schedulers, and compare the model performance against existing Graph- Learning Models, that leverage the Task Allocation Graph Representation Model presented in Fig. 7.
MILP Solver:
Exact solver using the MILP formulation described in Appendix A to solve the
problem [48].
We compare our model against greedy heuristic solvers, Earliest Deadline First (EDF) that prioritizes tasks with earlier deadlines and assigns them agents with earlier completion times [91] and Constraint-Aware EDF (CA-EDF) that accounts for precedence in task order dependencies [26, 51].
Heuristics:
A metaheuristic that improves a population of schedules over several generations by applying mutations and selecting the best schedules based on an initial seed [30, 29]. We utilize Genetic Algorithm to improve the performance of starting scheduling generated randomly, Gen- Random, and generated using EDF heuristic, Gen-EDF. Given the high time complexity of the Genetic Algorithm, we limit the evaluation the best best-performing schedules after and 3 generations
Metaheuristics:

---

NILP Solver
Optimality Rate (%
350
CA-EDF
300
Random
Gen-EDr
250
Gen-Randam
HerGAT
150
5008
Seq TERG-TARLIIA MER
100
Seq TARGETNETIE
PRR-IARGETNE
TARGETNETIER
Small
Medium
Large 20 Agents
XLarge Agents 200 Tasks
TARGETNETVE
TARGETNETYA
Agents
10 Agents
(Ours)
20 Tasks
50 Tasks
100 Tasks
Figure 3: Mean optimality rate the final reward on different scales, with standard deviation as error
bonee Lichar hattar
100
EDI
GA-EDF
Feasible (%)
80
Gen Random
Gen-EDr
Gen-Random
Gon EDF 3
HetGAT
Ros HetGAT
TAGGERGET
Seq TARGETNETIR
TARGETNETIER
Small 10 Agents
Medium
Large 20 Agents
XLarge 40 Agents 200 Tasks
TARGETNETIE
TARGETNETVA
10 Agents
TARGETNET (Ours)
20 Tasks
50 Tasks
100 Tasks
Figure 4: Mean percentage of feasible task Assignments on different scales, with standard deviation as error bars. In extra-large scales, graph-based models are shown to be able to outperform the optimizer. Higher is better.
of mutations based on computation time to be comparable to the optimal solver, with a population size of 100 and survival rate of 10% for the next generation.
GNN-Baselines: We evaluate GNN-based models that take in the Graph Model described in Section 3.3 as input to generate sequential agent-task assignment policies as described in prior work [24]. Our baselines include HetGAT [61], which employs graph-attention mechanism with edge-level attention for sequential decision making, and its residual-enhanced variant, Res-HetGAT, based on the wraph-raw-residuall [88]. Additionally, we benchmark our Simultaneous Decision Making model against Sequential Decision Making variant, referred to as Seq- Seq-TARRETNET We also consider two simplified versions: Seq- TARGETNET R, which excludes residual connections, Seq-TA -A AGETNNTT E, which excludes edge features and Seq-TARGETNET ER, which omits both edge features and residuals.
Ablation: To isolate the contributions residual connections and edge features, we conduct an abla- tion study our simultaneous decision-making model. Specifically, evaluate TARGETNET', R, which removes residuals, TARGETNET E which omits edge features and TARGETNET, ERR which removes both residuals and edge features, allowing assess their individual and combined impacts on performance.
Results & Experiment Analysis
evaluate performance of our proposed TARGETNET model across a range of problem sizes, comparing it with rule-based heuristics, metaheuristics, GNN-based sequential policies, and an MII-P-based optimal solver. Our primary focus on the trade-off between computational efficiency and solution quality, specifically feasibility and optimality of task assignments.

---

400
HetGAT
Res-HetGAT
SeQ-TARGETNETTER
Optimality Rate (%)
Seq-TARGETNETE
300
Seq-TARGETNETTR
SeQ-TARGETNET
TARGETNETIER
200
TARGETNETIE
TARGETNETVR
TARGETNET (Ours)
Small
Medium
Large
XLarge
10 Agents
10 Agents
20 Agents
40 Agents
20 Tasks
50 Tasks
100 Tasks
200 Tasks
Figure 5: Mean optimality rate of the final reward for 3 seeds of the learning-basee models different scales, with standard deviation as error bars. Higher is better.
TARGETNET consistently delivers near-optimal performance while significantly reducing computa- tion time. In small-scale problems, achieves a 13.27% improvement in feasible task assignments the rule-based CA-EDF policy and 36.35% improvement over HetGAT [61], generating sched- ules in under 0.20 seconds, the only model besides heuristics capable of sub-second scheduling at small scale.
As problem size increases, the computational benefits of TARGETNET become more pronounced. In extra-large scale settings, where the MILP solver fails to return fully-feasible solutions within 12 hours (producing partial schedules in all 10 cases). TARGETNET generates schedules with 70.80% more feasible tasks than the MILP solver and 47.05% more than HetGAT in 0.37% the computation time as while sequential models benefit from per-decision re-optimization but suffer cubic complexity, taking 538.56x more time generate schedules. While TARGETNET", E achieves similar performance to TARGETNET for the best performing seed, on average across 3 seeds, TARGETNET performs from 16.91% to 34.75% across different problem scales.
The inductive gencralization ability of our graph-based encoding combined with simultancous Task Allocation and Scheduling of TARGETNET allows model to be trained small-scale instances, and deployed directly to significantly larger problem sizes without retraining, still maintaining com- petitive performance. As shown in Fig. 5, TARGETNET consistently outperforms both baseline methods and ablation variants across all three random seeds. Although the TARGETNET E variant achieves performance comparable to the full model in seed (seed 10), the overall results demon- strate that TARGETNET maintains superior robustness by effectively representing policies both with and without explicit edge feature conditioning through the attention mechanism. Our empirical results suggest that incorporating edge-level information contributes to more stable generalization and reduced brittleness across varied problem configurations.
From a computational complexity perspective, TARGETNET operates with time and space com- plexity of (( for number of agents, |A|, and number of tasks, (T). This contrasts with the ( complexity of sequential models such as HetGAT and Seq- Eeq-TARGETNET leveraging the same graph structure, which require repeated environment updates and forward passes for each decision step. Our single-step schedule generation framework allows for significant reduction in computational load, making TARGETNET suitable for real-time deployment scenarios where optimal solvers and sequential GNNs become impractical.
The training time for the Simultancous model yields up 20x improvement sequential methods per episode as shown Fig. 6b. Furthermore, while the model trained only on the small scale, empirical results show that training in small scale is sufficient enough to learn policies that can generalize to larger problem sizes.
Empirical timing results shown in Fig.6b confirm the advantages highlighted in computational complexity. TARGETNET is consistently faster than all non-heuristic baseline methods across scales and remains the only graph-based model capable of combining low-latency inference with near-optimal task assignment performance. medium to extra-large scales, TARGETNET is 3.90 to 26.18 times faster than heuristics.

---

Training Time (s episode)
101
Computation Time (s)
101
Gen-EDI
10
HeISAT
Seg THAGETHETTR
Selp TAAGETMETIC
Sea SAAGETEETA
Sea TRAGETNET
Small
Medium
Large
XLarge 40 Agents
10 Agents
10 Agents
10 Agents
20 Agents
20 Tasks
20 Tasks
50 Tasks
100 Tasks
200 Tasks
Figure 6: (a) Mean Training Time episode and (b) Mean Computation Time during Testing, with standard deviation as error bars. Lower is better.
TARGETNET
achieves comparable or better performance while maintaining orders-of-mann of-magnitude faster runtime, offering 20x-250x speedup over state-of-the-art sequential GNN-based models. These results underscore its capacity to produce high-quality schedules under tight runtime constraints.
We further conduct sensitivity analysis subset of constraints and agent heterogeneity that our policies are trained on, and analyze the training stability across models initialized with three random seeds three in Appendix G.
Limitations and Future Work
One of the key limitations of solving mobile task allocation and scheduling problems with pre- computed motion plans is that represented model of the problem does not account for dynamic environment and agent-to-agent collision avoidance. The forecasting travel time our experiments assumes static path planning, which may lead to inaccuracies in scheduling when faced with unex- pected changes in the environment. Future work should account for agent-to-agent collision during multi-agent path finding to allow for higher fidelity solutions in real world applications [38, 83].
Our experiments show that simultancous methods consistently outperform non-exact solvers and run faster across scales, while sequential models yield superior results at larger scales but are significantly slower. We propose hybrid sequentill-smmulanee simultaneous architecture that merges the speed of simultaneous models with the scalability of sequential approaches. By integrating both through metaheuristic that selects the best output based on performance and computation time, we deliver robust, scalable solution for optimization and constraint satisfaction. Furthermore, TARGETNET provides schedules that can used to warm-start optimizer, reducing the time that the optimizer takes to return an exact solution by providing better solution [92].
While TARGETNET learns a scalable policy, the graph-based based models are not inherently interpretable. and the learned policy is hard to validate by humans [93]. While existing graph-based explainability methods, such saliency maps or counterfactuals [93], provide insight into learned policies, graph model that has full tull-transparency in its structure [94] is essential for safety-critical MATAS.
Conclusion
In this paper, we present TARGETNET. scalable, generalizable, and one-shot framework for Multi-Agent Task Allocation and Scheduling (MATAS) that integrates relational graph reasoning through Heterogeneous Graph Transformers with edge-specific attention. By capturing dynamic agent-task relationships and modeling the combinatorial nature of scheduling problems via novel graph representation, TARGETNET enables scalable simultaneous decision-makinn learning policies that enable inference an order of magnitude faster than graph- based sequential solvers. Our approach outperforms both heuristic baselines and genetic metaheuristics across problem scales-from small to extra-large- large-whilee while remaining computationally efficient and achieving near-optimal performance in scenarios where exact solvers fail. We show that TARGETNET learns nigh-performing generalizable policies that break the trade-off between speed, accuracy, and scalability.
10

---

Acknowledgments and Disclosure of Funding
This work was sponsored by Naval Research Laboratory (NRL) under grant numbers N00173- 21-1-G009 and N00173-25-1-0025 and by Office of Naval Research (ONR) under grant number N00014-23-1-2887
References
[1] Lijun Sun, Yijun Yang, Qiqi Duan, Yuhui Shi, Chao Lyu, Yu-Cheng Chang, Chin-Teng Lin, and Yang Shen. Multi-Agent Coordination across Diverse Applications: A Survey. arXiv preprint arXiv:2502. 14743, 2025.
[2] Jean Berger and Nassirou Lo. innovative multi-agent search-and-rescue path planning approach. Computers & Operations Research, 53:24-31, January 2015. ISSN 03050548. doi: 10. c0.1011/j.corr2144.4 pi1/S03305044840007775
URL
www.ghhhu..elleee...eerreee.eeee elsevier com/retrieve/
[3] Sarvapali D. Ramchur,, Trung Dong Huynh, Feng Wu, Yukki Ikuno, Jack Flann, Luc Moreau, Joel Fischer, Wenchao Jiang, Tom Rodden, Edwin Simpson, Steven Reece, Stephen Roberts, and Nicholas R. Jennings. A Disaster Response System based Human-Agent Collectives. jair, 57:661-708, December 2016. ISSN 1076-9757. doi: 10.1613/jairr5099 URL https: //jair. org/ index. sodde.pppp/ae phppppatpaaapaeaaa http://aaaaarraace//eeee////////
[4] Mattia Serra, Pratik Sathe, Irina Rypina, Anthony Kirincich, Shane D. Ross, Pierre Ler- musiaux, Arthur Allen, Thomas Peacock, and George Haller. Search and rescue at sea aided by hidden flow structures. Nat Commun, 11(1):2525, May 2020. ISSN 2041- 1723. doi: 10.1038/s41467-020 16281-x. URL https: http::://www.eee http://www...eeee//////////// com/ artiicettcc 941467-020-16881
[5] Daniel S. Drew. Multi-Agent Systems for Search and Rescue Applications. Curr Robot Rep, 189-:189, March 2021. ISSN 2662-4087.
doi: 1001007//43154--21-0000044 URL
attps://1inkksppiingg wwwpl/ngrr.....ooo//// cwm/10.m/////// http://.100///311-0011-0000000
[6] R.-S. Chen, K.-Y. Lu, and C.C. Chang. Intelligent warehousing management systems using multi-agent. ISCAT, 16(4):194, 2003. ISSN 0952-8091, 1741-5047. doi: 10.1504/JCCAT.20003 000325. URL.nttp//mw...dderrreeeee. http://iiiinnc.cmmm/iiiiiii. www.wick...nn///..............l. commmiinkppppp1dd32555. php?id=325.
//w::////wwwww/ www.:iinddeeeinnc..mmm
[7] Massimo Cossentino, Carmelo Lodato, Salvatore Lopes, and Patrizia Ribino. Multi agent simulation for decision making in warehouse management, pages 61 1-18... IEFE, 2011. ISBN 83-60810-39-1
[8] P.G. Balaji, Gaurav Sachdeva, D. Srinivasan, and Chen-Khong Tham. Multi-agent System based Urban Traffic Management. In 2007 IEEE Congress on Evolutionary Computation, pages 1740-1747, Singapore, September 2007. IEEE. ISBN 978-1-4244-1339-33 doi: 10. 100CCCCC 2007 44007844 URL https: /tieee/:////eee/////e ieee org//ocument/4424655
[9] C. Desjardins and B. Chaib-draa. Cooperative Adaptive Cruise Control: A Reinforcement Learning Approach. IEEE Trans. Intell. Transport. Syst., 1244):1248- 1260, December 2011. ISSN 1524-9050, 1558-0016. doi: 10.1109/TTS URL http://eeeexplore. ieee. beee.org//ee /ttp://cccmment/776/2//////
[10] Kuo-Yun Liang. Jonas Martensson, and Karl H. Johansson. Heavy-Duty Vehicle Platoon Formation for Fuel Efficiency. IEEE Trans. Intell. Transport. Syst. 17(4):1051-1061, April 2016. ISSN 1524-9050, 1558-0016. doi: 2011 2492243. URL 1Rt.ettp///eeeepporrr ieee. /ieee.orrg/occmmm///3/4995555
[11] Shai Shalev-Shward Shaked Shammah, and Amnon Shashua. Safe, Multi-Agent, Reinforce- ment Learning for Autonomous Driving, October 2016. URL. 03295. arXiv: 1611:0610003299 [cs].

---

[12] Xiang Zhang, Yuan Yang. Mingwei Xu, and Jing Luo. ASER: Scalable Distributed Routing Protocol for LEO Satellite Networks. In 2021 IEEE 46th Conference on Local Computer Networks (I.CN), pages 63-72, Edmonton, AB, Canada, Octoher 2021. IEEF. ISBN 978-1- 66541-886-7. doi: 10.1 11099.CCN52119922211559499999999 URL htt/ddocumenn/95229990
[13] Zhiyuan Lin, Zuyao Ni, Linling Kuang, Chumxiao Jiang, and Zhen Huang. Dynamic Beam Pattern and Bandwidth Allocation Based on Multi-Agent Deep Reinforcement Learning for Beam Hopping Satellite Systems. IEEE Trans. Veh. Technol. 71(4):3917-39300 April 2022. ISSN 0018-9545, 1939-9359. doi: 10.1109/TWT:2222.114552 ieee. org dowgmenttttt////// /9992899/
URL https: //ieexxxleoeee
[14] Yifeng Lyu, Han Hu, Rongfei Fan, Zhi Liu, Jianping An, and Shiwen Mao. Dynamic Routing for Integrated Satellite-Terrestrnn Networks: A Constrained Multi-Agent Reinforvement Learning Approach, December 2023, URL http:://axtt [es].
09455. arXiv:4401.09555
[15] Brian P Gerkey and Maja J Mataric. A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23:939-954, 2004.
[16] G. Ayorkor Korsah, Anthony Stentz, and M. Bernardine Dias. A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research, 12:1455-1512, 10 2013, ISSN 0278-3649. doi: 10. 10.1177/0278364413496666 URL htLp:tp///jouuii sagepub. com/doi/10 1177 117770007737911199668888
[17] Juntong Peng. Hrishikesh Viswanath, Kshitij Tiwari, and Aniket Bera. Graph-based De- centralized Task Allocation for Multi-Robot Target Localization, September 2023. URL arXiv:2309.0855 0998999999999 [cs].
http://arxiv. www.aarwww..ooraaaaaaaaaaa hrwggaas//309... 028.990999.9.......
[18] Yi Zhang, Haihua Zhu, Dunbing Tang, Tong Zhou, and Yong Gui. Dynamic job shop scheduling based on deep reinforcement learning for multi-agent manufacturing systems. Robotics and Computer-Integraat Manufacturing, 78:102412, 2022. ISSN 0736-5845. Publisher: Elsevier.
[19] Long Le, Dana Hughes, and Katia Sycara. Multi-agent Hicrarchical Reinforcement Learning in Urban and Search Rescue. Technical report, Working Papers Journal, 2021.
[20] Byung In Kim. Intelligent agent based planning, scheduling, and control: warehouse manage- ment application. Rensselaer Polytechnic Institute, 2002. ISBN 0-493-59362-4.
[21] Jose IIdefonso U Rubrico, Jun Ota, Toshimitsu Higashi, and Hirofumi Tamura. Metaheuristic scheduling of multiple picking agents for warehouse management. Industrial Robot: An International Journal, 35(1):58-68, 2008. ISSN 0143-991X. Publisher: Emerald Group Publishing Limited.
[22] Matteo Bettini, Ajay Shankar, and Amanda Prorok. Heterogeneous Multi-Robot Reinforcement Learning, January 2023. URI. [es].
wwwpa/wwwwwwggb////...oooo 2201../0177... arXiv:2301.07137
[23] Zheyuan Wang and Matthew Gombolay. Learning Scheduling Policies for Multi-Robot Co- ordination With Graph Attention Networks. IEEE Robot. Autom. Lett., 5(3):4509-455 4516, July 2020. ISSN 2377-3766, 2377-3774. doi: 10.11000LRA URL https: //ieeexplore ieee httgg//ocumee//11199//
[24] Batuhan Altundas, Zheyuan Wang. Joshua Bishop, and Matthew Gombolay. Learning Coor- dination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation. In 2022 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1 11679-11686 1686. Kyoto, Japan, October 2022. IEEE. ISBN 978- 18-1--66577- 927-1. doi: 10. 1w1.1/004770...02220000 2928 URL nttps://ieeexplooe ieee. ieee, org/ document/9981748//
[25] Matthew C. Gombolay, Ronald J. Wilcox, and Julie A. Shah. Fast Scheduling of Robot Teams Performing Tasks With Temporospatial Constraints. IEEE Transactions on Robotics, 34(1): 230, February 2018. ISSN 1941-0468. doi: 10. 10.1109/TRO.2211.2775550
12

---

[26] Ernesto Nunes and Maria Gini. Multi-robot auctions for allocation of tasks with temporal constraints. volume 29, 2015. ISBN 2374-3468. Issue: 1.
[27] Hengwei Guo, Zhonghua Miao, JC Ji, and Quanke Pan, An effective collaboration evolutionary algorithm for multi-robot task allocation and scheduling in a smart farm. Knowledge-Bol -Bssed Systems, 289:1 1474, 2024. ISSN 0950-7051, Publisher: Elsevier.
[28] PM Rekha and M Dakshayini. Efficient task allocation approach using genetic algorithm for cloud environment. Cluster Computing, 22(4): 2019. ISSN 1386-7857. Publisher: Springer.
[29] Yannick Monnier, J-P Beauvais, and A-M Deplanche. A genetic algorithm for scheduling tasks in real-time distributed system. volume pages 708-714, IEEE, 1998. ISBN 0-8186-864464.
[30] Ruisen Liu, Manisha Natarajan, and Matthew C. Gombolay. Coordinating Human-Robol Teams with Dynamic and Stochastic Task Proficiencies. ACM Transactions on Human-Robo Interaction, 11(1):1-42, March 2022. ISSN 2573-9522, 2573-9522. doi: 10.1145/3477391.
URL https: //dl. /d1.
acm. org//oi/o/////oo/oo//oooooo//
[31] Han Lim Choi, Luc Brunet, and Jonathan How. Consensus- based decentralized auctions for robust task allocation. IEFE Transactions on Robotics, 25:912- 926, 2009. ISSN 15523098. doi: 10. NT..TRO...0090222222
[32] Michael M. Zavlanos, Leonid Spesivtsev, and George J. Pappas. A distributed auction algorithm for the assignment problem. Proceedings of the IEEE Conference on Decision and Control, pages 1212-1217, 2008. ISSN 25762370. doi: 10.1 109/CDCC.000..773990 4739998.
[33] Zheyuan Wang and Matthew Gombolay. Stochastic Resource Optimization over Heterogeneous Graph Neural Networks for Failure-Predictive Maintenance Scheduling. ICAPS, 32:527-536, June 2022. ISSN 2334-0843, 2334-0835. doi: 10. 10.1609/scass... wttpppps..21...18333 URL https: /lojs.aaai wtwp/ooe...iiiipoooeoooo
[34] Hanqi Dai, Weining Lu, Jun Yang, and Bin Liang. Cooperative Path Planning of Multi-Agent Based on Graph Neural Network. In 2022 34th Chinese Control and Decision Conference (CCDC), pages 5620-5624, Hefei, China, August 2022. IEEE. ISBN 978- 100---16647-89--61 doi: 10. (0010999CDCS55522222.0000 10033322. URL http:: 10034322/
https://ieeexplorrs /eeeeeeeeeeeeeeeeeeeeeee Leee. otto/ogg/oo/eeeeoooo /ocument/
[35] Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph Neural Networks for Decentralized Multi-Robot Path Planning, July 2020. URL. 1Xii:1912.06099 [cs].
abs/
[36] Ziyuan Ma and Huajun Gong. Heterogeneous multi-agent task allocation based graphneural- network antcolony optimizatiinaalgoritnns.. Intelligence Robotics, 3:581-95, 2023.
[37] Xinyi Yang, Xinting Yang, Chao Yu, Jiayu Chen, Huazhong Yang, and Yu Wang. MASP: Scalable GNN-based Planning for Multi-Agent Navigation, December 2023. URL http: // //arxiv. org/ /ttp/212..ae 02522. arXiv:2312.02522 [cs].
[38] Brandon Ho, Batuhan Altundas, and Matthew Gombolay. Towards learning scalable agile dynamic motion planning for robosoccer teams with policy optimization. RoboLetics: Workshop Robot Learning in Athletics @ CoRL 2023, 2023. URL ptttps://openrevieet pet/fforum?idd=VVgFFn2Z77
[39] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
[40] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. pages 2704-27111 2710, 2020.
[41] Shaowei Yao, Tianming Wang, and Xiaojun Wan. Heterogeneous Graph Transformer for Sraph-to-Sequence Learning. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7145-7154, Online, 2020. Association for Computa- tional Linguistics. doi: 10. wt..1865311//2200... http//2222..22mmiiiaaaa main.640. URL https: //www//www//a/// aclweb org/ 1 anthology/2085 20000 acw-main 640.
13

---

[42] M Bernardine Dias. Traderbots: A new paradigm for robust and efficient multirobot coordination in dynamic environments. 2004.
[43] Sofia Amador, Steven Okamoto, and Roie Zivan. Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints. AAAI, 28(1), June 2014. ISSN 2374-3468, 2159-5399. doi: 10.1669/aaai.v225 v28.1.8889. URL Stttps///oj. http:///ssaaaaa..a.aaaaaaaaaaaa. w oot.ooogg/eeeeee.e pbtppp//pp//AAArttaaa.llloo view/8889.
[44] Inmo Jang, Hyo Sang Shin, and Antonios Tsourdos. Anonymous hedonic game for task allocation in large-scale multiple agent system. IEEE Transactions on Robotics, 34:1534 1548, 12 2018. ISSN 15523098. doi: 10.
[45] Shengkang Chen, Tony X. Lin, and Fumin Zhang. Game-theoretical approach to multi-robot task allocation using a bio-inspired optimization strategy. In IEEE International Conference on Intelligent Robots and Systems, pages 5388-5393. Institute of Electrical and Electronics Engineers Inc., 10 2023. ISBN 9781665491907. doi: 10.::10.111/////... 10.1109//005555522023.. 103419977
[46] Lu Wang, Zhiliang Wang, Siquan Hu, and Lei Liu. Ant colony optimization for task allocation in multi-agent systems. China Communications, 10(3): 2013. ISSN 1673-5447. Publisher: JEEE
[47] Yingying Su, Zhichao Bai, and Dongbing Xie. The optimizing resource allocation and task scheduling based on cloud computing and Ant Colony Optimization Algorithm. Journal of Ambient Intelligence and Humanized Computing, pages 1-9, 2021. ISSN 1868-5137. Publisher: Springer.
[48] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www gurobi. com.
[49] Laurent Perron and Vincent Furnon. Or-tools. URL httpss://ddeeelopprrssssss/// www.geee....ooo...oo.oooooo
optimization/.
[50] Hamza Chakraa, François Guérin, Edouard Leclereg, and Dimitri Lefebvre. Optimization techniques for multi-robot task allocation problems: Review the state-of-the-art. Robotics and Autonomous Systems, 108:10,49,, 10 2023. ISSN 0921-8890. doi: 10.1016/1.ROOT. 2023.104492.
[51] Bilal Kartal, Ernesto Nunes, Julio Godoy, and Maria Gini Monte Carlo tree search for multi- robot task allocation. volume 30, 2016. ISBN 2374-3468. Issue: 1.
[52] Shushman Choudhury, Jayesh K. Gupta, Mykel J. Kochenderfer, Dorsa Sadigh, and Jeannette Bohg. Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints, July 2020. URL http:://arxii org/ abs5 13109. 13Xiv:2005.13000 [cs].
[53] Giuseppe Alessio I'vvvro,,, Monica Bianchini, Maria Lucia Sampoli, and Franco Scarselli. On the approximation capability of GNNs in node classification/reerrssiio tasks. Soft Com- puting, 28(13-14):8527-854) July 2024. ISSN 1432-7643, 1433-7479. doi: 1007/ 500500-024-09676-1 URL http: //axxiv.aaiivva//a org/ abaaaaas//111 .2t.//........2....22 arXiv:2106.08992 [cs].
[54] Rohan Paleja, Andrew Silva, Letian Chen, and Matthew Gombolay. Interpretable and personal- ized apprenticeship scheduling: Learning interpretable scheduling policies from heterogeneous user demonstrations. Advances in neural information processing systems, 33:6417-6428, 2020.
[55] Renyu Yang, Xue Ouyang. Yaofeng Chen, Paul Townend, and Jie Xu. Intelligent Resource Scheduling at Scale: A Machine Learning Perspective. In 2018 IEEE Symposium on Service- Oriented System Engineering (SOSE), pages 132-141, Bamberg, March 2018. IEEE. ISBN URL
978-1-5386-5207-7. doi: 10. 10.100000EE...0 org/doccueent/835915...
ieee
[56] Johann Schmidt and Sebastian Stober. Approaching Scheduling Problems via a Deep Hybrid Greedy Model and Supervised Learning. IFAAC-PupesSOntLine, - 2021. ISSN 24058963. doi: 10. 10. 20..200.......... .08.095. URL. htttttts://iikiigghhiiii www.:/imiiiinuuu.eeeeeeeerr... elsevier com/
14

---

[57] Haoyu Wang, Zetian Liu, and Haiying Shen. Machine Learning Feature Based Job Scheduling for Distributed Machine Learning Clusters. IEEE/ACM Transactions on Networking, 31(1):
58-73, February 2023. ISSN 1063-6692, 1558-2566. doi: 10. 10.1199/TMET:302223197999 URL
https://ieeexploree ieee...eeeee....................
ieee. org//occumett/9843925
[58] Byeolyi Han, Minwoo Cho. Letian Chen, Rohan Paleja, Zixuan Wu, Sean Ye, Esmaeil Seraj, David Sidoti, and Matthew Gombolay. Learning Multi-Agent Coordination for Replenishment At Sea. IEEE Robotics and Automation Letters, 10(2):1018-100 February 2025. ISSN URL httts:://eeeepppeeet
2377-3766, 2377-3774. doi:
ieee.
org/document/ 10803076/-
[59] Cristina Morariu, Octavian Morariu, Silviu Räileanu, and Theodor Borangiu. Machine learning for predictive scheduling and resource allocation in large scale manufacturing systems. Computers in Industry, 120:103244, September 2020. ISSN 01663615. doi: 10.
103244. URL wtt.thttt////kiiigtteeet http///nnnninnhbb/e/ elsevier. www./ootreeeeee.eeeeeeeee p11/S0066336119811555
allevvierr.com/rerrireee.
[60] Pengxing Zhu and Xi Fang. Multi-UAV Cooperative Task Assignment Based on Half Random Q-Learning. Symmetry, 13(12))2417, December 2021. ISSN 2073-8994,
doi: 10.3390/
sym13122417. URL http:: http::/wwwwwwwppppppe/ com//073--//999/11111330 12/22//
[61] Zheyuan Wang, Chen Liu, and Matthew Gombolay. Heterogeneous graph attention networks
for scalable multi-robot scheduling with temporospatial constraints. Autonomous Robots, 46
(1):249-268, January 2022. ISSN 1573-7527.
doi: 10.10077110514-021-9999999 https://doi. orgii.org/11.. 110000//100111001-000990000
URL
[62] Yujiao Hu, Yuan Yao, and Wee Sun Lee. reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge- Based Systems, 204:106244 September 2020. ISSN 09507051. doi: 10.1016/j.kmooss.... 106244. URL https://
linkinghub. elsevier http://reeeeep11///5/00/565
[63] Hengliang Tang, Anqi Wang, Fei Xue, Jiaxin Yang. and Yang Cao. A Novel Hierarchical Soft Actor-Critic Algorithm for Mugti-Logistics Robots Task Allocation. IEEE Access, 2021. ISSN 2169-3536. doi: 10.1009ACCESS.2222..00000 //ieeexplore ieee. wtg/doccment/9863555
URL https:
[64] Gaoqiang Dong. Jia Wang, Mingjing Wang, and Tingting Su. An Improved Scheduling with Advantage Actor-Critic for Storm Workloads, December 2023. URL http://arxixa org/ 2as/2331.04122 arXiv:2312.04122 [cs].
[65] Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Daulet- bayev. Learning to solve vehicle routing problems: A survey, URL http: /tattp///rxiv.... wwwiiiiiorr////aa abs/
[66]
Lászıó Kováes and Ali Jlidi. Neural networks for vehicle routing problem. URL http: / //arxiv.. wawxii..rgg/be////e. arg/abs/2409 11290.
[67] Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. 210:33:1-33:22 ISSN doi: 10.4230/LIPIcs. CP.2021.33. URL http: //trxivaa.ii////aa//aa wwwg/bs//////e/ooooe/....ee.eeet abs /206 07054.
[68] Yujiao Hu, Zhen Zhang, Yuan Yao, Xingpeng Huyan, Xingshe Zhou, and Wee Sun Lee. A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs. Engineering Applications of Artificial Intelligence, 97:104061, January 2021. ISSN 09521976. doi: 10. 10111//6.j... wttp::/...a.p.......... 2020. 104061. URL htttt::://iikiinaaeeee elsevier. com/retriieveppii/SSS http:///...///002220000033333230
[69] Ethan Schneider, Daniel Wu, Devleena Das, and Sonia Chernova. CE-MRS: Contrastive explanations for multi-robot systems. 9111):01111-0012, ISSN 2377-3766. doi: 10.1109/LRA. 2024.3469786. URL htRphttts::/ieeexploore ieee. otw.....g/aassssstccccaaaaaa///e 20t.0/66020mmm111/672222.
[70] Esmaeil Seraj. Zheyuan Wang, Rohan Paleja, Matthew Sklar, Anirudh Patel, and Matthew Gombolay. Heterogeneous Graph Attention Networks for Learning Diverse Communication, October 1021. URL http: //txxiv.vvv////////////////aaavl org/ www.aa///....eeeeeee..ee.eeeetee 09568. McXiv:2108.09565 [cs].
15

---

[71] Tong Zhou, Dunbing Tang, Haihua Zhu, and Zequn Zhang, Multi-agent reinforcement learning for online scheduling smart factories. Robotics and Computer-Integrated Manufacturing. 72: 102202, December 2021. ISSN 07365845. doi: 10. www.100//...iim.2222..... 000...11122222 URL. https: //linkinghub. elsevier. httpa//ww..cooaeaeeeee/a//////aa
[72] Steve Paul and Souma Chowdhury. scalable graph learning approach capacitated vehi- cle routing problem using capsule networks and attention mechanism. volume 86236, page V03BT03A045. American Society of Mechanical Engineers, 2022. ISBN 0-7918-8623-9,
[73] Sean Ye, Manisha Natarajan, Zixuan Wu, Rohan Paleja, Letian Chen, and Matthew C. Gombolay, Learning Models of Adversarial Agent Behavior Under Partial Observability. In 2023 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pages 3688-3695 Detroit, doi: 10.1 109/000055555552202233 10341378. URL hts.sstts::/ieeexp..o.o ieeeeiieeee ieee wwtp/oocummnt//004555000
MI, USA, October 2023. JEEE. ISBN 978- 778-1-66549-19--7
[74] Manisha Natarajan, Esmaeil Seraj, Batuhan Altundas, Rohan Paleja, Sean Ye, Letian Chen, Reed Jensen, Kimberlee Chestnut Chang, and Matthew Gombolay. Human-Robot Teaming: Grand Challenges. Curr Robot Rep, 4(3):81-100, August 2023. ISSN 2662- 4087. doi: 10.
URL pestps://iimg springer. com 10. 1007/
843154-023-00108-11
[75] Xiao Wang, Houye Chuan Shi, Bai Wang, Peng Cui, P. Yu, and Yanfang Ye. Heteroge- neous Graph Attention Network, January 2021. URL http:t/////ax: httppp://aaxi...r/aabba/s/s/ arggabs/1903.. 07293. arXiv:1903.07293 [cs].
[76] Xiaoyu Mo. Yang Xing, and Chen Lv. Heterogeneous Edge-Enhanced Graph Attention Network For Multi-Agent Trajectory Prediction, June 2021. URL http: http:://axxvvvrreoeee hwgggabb//100... 07161. MxXiv:2106.0716) [es].
[77] Zhun Yang, Adam Ishay, and Joohyung Lee. Learning Solve Constraint Satisfaction Prob- lems with Recurrent Transformer, July 2023. URL http: peattp://rxiv.. aarxiv.vvvv. wwwg/bs/g////eeooeeoo..ooee 2tbbb//237704899 04895. arXiv:2307008895 [es].
[78] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. Issue: 1.
[79] Sertac Karaman and Emilio Frazzoli. Sampling-based Algorithms for Optimal Motion Planning, May 2011. URL http: wwwp:/s.//aaab/ea/ /atp:.1155.... 1186. arXiv: 105. 1 1186 [cs].
[80] František Duchoñ, Andrej Babinec, Martin Kajan, Peter Beño, Martin Florek, Tomás Fico, and Ladislav Jurišica. Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96:59-69, 2014. ISSN 1877-7058. Publisher: Elsevier.
[81] Paolo Verbari, Luca Bascetta, and Maria Prandini. Multi-agent trajectory planning: A decentral- ized iterative algorithm based on single-agen dynamic RRT. pages 1977-1982, IEEE, 2019. ISBN -53386-992-44
[82] Rahul Kala. Rapidly exploring random graphs: motion planning of multiple mobile robots. Advanced Robotics, 27(14):113-11222 October 2013. ISSN 0169- 1864, 1568-5535. doi: 10.
01000099986422013888544444 01691864 20091866.2013..00 201...85477.8
URL http:///wwtt tandf fondffnlingg ine.
[83] Andrew Messing, Glen Neville, Sonia Chernova, Seth Hutchinson, and Harish Ravichandar. GRSTAPS: Graphically Recursive Simultaneous Task Allocation, Planning, and Scheduling. The International Journal of Robotics Research, 21(2):232-256, February 2022. ISSN 0278- 3649, 1741-3176. doi: (001177702783669221102222 com/doi/100 /11..111770000223492100000000000
URL
sagermaaassssegu....... sagepub.
[84] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE transactions neural networks and learning systems, 33(2):994-544, 2021. ISSN 2162-237X. Publisher: IEEE.
[85] Vaswani. Attention all you need. Advances Neural Information Processing Systems,
2017.
16

---

[86] Narayanan Srinivasan, Priyanka Srivastava, Monika Lohani, and Shruti Baijal. Focused and distributed attention. In Progress Brain Research, volume 176, pages 87-100. Elsevier, 2009. ISBN 978-0-444-53426-2. doi: 10.10016650077--6220000111666660 URL https://
[87] Evan Miller. Attention Off By One - evanmiller.org. attps://wwin httpp:://ww.eevammleee.. evanmi org/
iestentionnis-oie off-offf------o by--oby-eee html. [Accessed 21-10-2025].
[88] Jiawei Zhang and Lin Meng. GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation, September 2019. URL http:://arizzi httt:://aaxiv.or//bbbbb.b arg/abs/1900 15799/9999599 arXiv:190.005229 [es, stat].
[89] Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine Learning. ((3344):29922666 May 1992. ISSN 0885-6123 1573-0565. doi: 10.1007/BP00992666 URL http: //tp::///nnkk sprringer com/ 10. 1000//9999009
[90] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neu- ral Combinatorial Optimization with Reinforcement Learning, January 2017. URL http:
/ //arxiv. www.oogg///a//eeeeeooeo.oeeeeeee aaaaab///161 /611. 09940. urXiv:161..0994 [cs].
[91] Mehdi Kargahi and Ali Movaghar. method for performance analysis carliest-deallnn- scheduling policy. The Journal of Supercomputing, 37:197-222, 2006. ISSN 0920-8542.
Publisher: Springer.
[92] Zhaoxin Li, Letian Chen, Rohan Paleja, Subramanya Nageshrao, and Matthew Gombolay. Faster Model Predictive Control via Self-Supervised Initialization Learning, August 2024. URL http: arxiv...vvvvv/
htrg/abs/2408. 03394. urXiv:2408.03320 [cs].
[93] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in Graph Neural Networks: Taxonomic Survey, July 2022. URL http: org/abs/2012. 2XXi:2012.155455 [es].
http::///aarii.orgraa///000/// 15445.
[94] Zachary C. Lipton. The Mythos of Model Interpretability, March 2017. URL http://arxivy org/abs/1606 03490. 11Xvv:1606.03490 [cs].
[95] Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning Implicit Credit Assignment for Cooperative Multi-Agent Reinforcement Learning, October 2020. URL org/ /twp///////////aae/////eeeeeee 2007 02529. arXiv:2007.02529 [cs].
http://arxiv.orrt
[96] Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. pages 1861-1870. PMLR, 2018. ISBN 2640-3498.
[97] Daniel Pickem, Paul Glotfelter, Li Wang, Mark Mote, Aaron Ames, Eric Feron, and Magnus Egerstedt. The robotarium: remotely accessible swarm robotics research testbed. pages 1699-1706. IEEE, 2017. ISBN 1-5090-4633-X.
[98] Sean Wilson, Paul Glotfelter, Li Wang. Siddharth Mayya, Gennaro Notomista, Mark Mote, and Magnus Egerstedt. The robotarium: Globally impactful opportunities, challenges, and lessons learned in remote-access, distributed control of multirobot systems. IEEE Control Systems Magazine, 40(1):26 2020. ISSN 1066-033X. Publisher: IEEE.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims made in the abstract and introduction are shown in the Fig. 3, 4, 6 as well as the exact values that can be found in Appendix G.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 6 present the limitations and future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
18

---

Justification:
The paper does not have theoretical results based on assumptions. The empiri- cal results were used verify the theoretical computational complexity of the presented method.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification; Appendix E provide full information required to reproduce the specific datasets, and neural network architectures. Supplementary Materials include the access to used datasets, code used to generate the datasets, the training and evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
19

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The fully anonymized code and data are shared with the supplementary works along with instructions the reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. pppullccgguice httee//odSuuueiiieeeeeee www.bbmiisiooPooooyyy.. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4.1 and Appendix E provides details on the training and test sets, necessary understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In Fig. error-bars represent one standard deviation. The exact values are also reported in the tables found in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Appendix E provide full details of the compute resources used to run the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurlPS Code of Ethics https: : htt////eurrrp.eeeee cc httppp/icccchcccccuueeeeeiieeeee
didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Our paper explores the broader effects of our method both beneficial im- pacts, such as in deployment for search and rescue, and negative impacts such as lack of interpretability leading increased risk in safety in dangerous applications.
21

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not contain data models that have a high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All methods presented are cited and credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
22

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com dataetts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
All new assets are introduced with documentation in the supplementary work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not contain Crowdsourcing or human subject experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurIPS Code of Ethies, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not contain human subject research crowdsourcing. The paper does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The paper does not present the usage of LLMs as part of the core methods of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https / htops://neerips. for what should or should not be described.
www.rrpp.cc/ooofeeeeeececccc wwc/oc//////ceeeeeeeeee ec/conferrences/2222//L
24

---

Appendix A Mixed Integer Linear Program Solver for Task Allocation and Scheduling
The Heterogeneous Mobile Multi-Agent Task Allocation and Scheduling Problem can be formulated as Mixed Integer Linear Program (MILP). This formulation enables the joint optimization of task assignments and their execution schedule.
We adopt the MILP formulation presented in Eq. where the objective is to optimize the schedule according to a predefined cost function. We build on prior work [16, 25], with the key extension of incorporating heterogeneous travel times. These travel times are derived from varying agent velocities and precomputed distances between the agents' initial positions and task locations.
min S(A,S) ,...,, SMA)
s.t.
Σ Auj =1
VjET (C1)
iEA
Sj + Sk I M(2 Aij A1k) +
ViEAET (C2)
Sy + Sk 2 -M(2- - Aú - Aix) +1
NjiKET,iEA (C3)
$ - M (3 (Ai + AAx + S)x) + ts + tyg
TiEK (C4)
$ 2 -M(1 - AAa) + tik
T (C5)
& 2 t
TkET (C6)
t Z M(Osk 1) WS
Vj (C7)
t Z 8k
YkET (C8)
& 2 the + Aut
VKET,iEA A (C9)
th S ek
VKET (C10)
In this formulation, M denotes large constant used to model conditional constraints. The constraints are interpreted as follows:
(CI) ensures that each task is assigned to exactly one agent.
(C2) and (C3) enforce mutual exclusivity and sequencing when two tasks and are assigned to the same agent i.
(C4) sets the arrival time, tg. of an agent, i, to task, k ensuring occurs only after completing the preceding task, and arriving in the location of task, k, after travel time, Uyz-
(C5) ensures that the agent's arrival its first assigned task considers its initial location.
(C6)-(C8) ensure that task start times respect agent arrival times, required wait times between dependent tasks, and task time windows.
(C9) accounts for heterogeneous task durations depending on the assigned agent.
(C10) enforces task completion within the designated time window.
The objective function is defined as:
SA..,,,.,,SNNN = max (ty))
(8)
JET
which minimizes the makespan, i.c., the maximum task finish time across all tasks.
25

---

Appendix B Graph Neural Networks
B.1 Node Attention and Message Passing in Heterogeneous Graph Networks
Hu et al. [40] describes the attention and message passing mechanisms for the nodes based on their relations. For each node, we compute key and query projections specific to attention head i follows:
(*)()) Wkx 1 (v((1) Wax A--1
where n and h denote the input features of source node and target node t from the previous layer, respectively. The matrices Wxx and W are learned projections for the i-th attention head.
The multi-head attention from source node 8 to target node is computed as:
K (M (ty) ((((())7(1))
(s,
(9)
Vd
where r(s) and r() denote the node types of and WATT is type-specific transformation matrix, N and p (())) is learned scaling factor modulating attention between node types.
r(e)
The corresponding message passed from node to t is computed as:
Msg (s,
(s)(W)
(10)
r(a)
;=1
where (s) the value vector for node head i, and W is the type-specific transformation for message projection.
r(s)
Graph Features
In the graph representation, the Agent node includes features such Earliest Time Available, indicating the soonest the agent can begin a task, and Number of Tasks Assigned, reflecting current workload. The Task nodes contains temporal constraints and scheduling information, including Start Time Constraint, End Time Constraint, Expected Completion Time if assigned previously, and a binary feature indicating whether the Agent Assigned. The State node captures high-level planning metrics such as the Number of Tasks Assigned, Maximum Makespan, the current Assignment state, and total Duration of scheduled activities.
Node Features:
Edge Features: The relationships and transitions between nodes are encoded in the Edge fea- ture. Each edge connection source node target node represented as (Source, Edge, Target) and annotated with task-relevant attributes. The edge (Agent, Duration, Task) captures task ex- ecution time, while (Agent, Travel Time, Task) represents the movement cost. Inter-task de- pendencies are modeled with (Task, Distance, Task) and (Task, Wait Time, Task), encoding spa- tial separation and required wait periods, respectively. Assignment-specific relations are de- fined by (Agent, Travel Time, Assignment) and (Agent, Task Duration, Assignment), which record travel and execution times per assignment. Finally, inter-assignment transitions are denoted by (Assignment, Travel Time, Assignment), representing temporal costs between consecutive assign- ments.
Appendix C Sequential Decision Making Models
In the sequential task allocation setting, decision-maie making unfolds over series of timesteps, each corresponding to the assignment of a single agent to a task. We employ a two-step actor mechanism with dedicated output nodes for Agent Selection and Task Selection, seen in Fig. 8. The state of the environment is encoded as a graph and processed through a Graph Neural Network (GNN). The outputs are passed through softmax functions produce probability mass functions (PMFs).
The agent selection policy, π (ar])s)) first selects an agent, Or. from the state, 8t, at time step, l. Subsequently, task, is assigned to agent, 0s, using the conditional policy x (Tz/ 8t). Each task assigned exactly once and removed from the pool of unassigned tasks upon completion. The joint action (aa, Tt) updates the environment to yield the next state $t+1
26

---

Task Allocation and Scheduling Environment
Seq-TARGETNET
Hervingtouu Tass Durbonn
Robst Selector
Actor
Agert
Tack
Durition
Olaerration:
HOT Erle
HOS
Agenn
Precongubed Tooel Times
Orter
HOX Stor
H+S Sagn
HOST Caga
Agai to
Crile
(Ptu
Evulation
mahcspas
Orlo Tharte
deadios
Figure 7: The training and policy pipeline for multi-agent task allocation environment with obstacles and sequential decision-man makiin using the Seq- TARGETNGT baseline. The architecture comprises agent and task selection modules followed by a graph-based critic that evaluates each assignment. This pipeline allows for ordered assignment of agents to tasks and simulates their movement pre-computed motion planning map. Seq-TARGETNET uses a 4-layer Graph Neural Network with residual connections to enable robust sequential reasoning.
Unlike simultaneous assignment methods (e.g., TARGETNET), where assignments are computed from single initial observation, the sequential formulation requires updating the environment iteratively after each decision. This enables more granular evaluation and dynamic response to partial assignments at the cost of added computational complexity [40, 24].
C.1 Graph-based Critic for Sequential Training
Sequential Multi-Agent Task Allocation and Scheduling (MATAS) problems are characterized by sparse and delayed rewards, creating significant challenges for effective policy learning due to the well-known credit assignment problem [95]. sequential settings, the decisions made by agents unfold over time, with each decision potentially influencing future states and the overall outcome of the schedule. The temporal dependency eventual success failure of the complete schedule to individual agent-task decisions. While the combined reward function defined in Eq. incorporates both dense penalties for constraint violations and sparse terminal reward for overall performance, the feedback remains insufficient for learning optimal intermediate actions in a long-horizon task.
sequential policies makes nontrivial to attribute the
In our framework, we adopt REINFORCE [89] for Simultaneous Task Allocation and Soft Actor- Critic (SAC) [96] for Sequential Task Allocation. Simultaneous task allocation presents a single-shot, static decision process where the complete task-agent assignment and ordering are generated in one step and evaluated holistically. REINFORCE is particularly effective in single-shot decision making, as it directly optimizes the expected return from full allocation decisions, using Monte Carlo estimates without requiring a value function or temporal credit propagation. Conversely, sequential allocation involves temporally extended decision-makee making with interdependent assignments and sparse, delayed rewards, making credit assignment a critical challenge [95]. To address this, we employ SAC, an off-policy actor-critic method that leverages value estimation and entropy-regularized learning to balance exploration and exploitation across long- horizon trajectories. This division enables each component to exploit the inductive biases of its underlying problem structure, leading to improved sample efficiency, learning stability, and policy performance [89, 96, 78].
The critic is trained to approximate the state-action value function, Qo(st, at), which estimates the expected cumulative return when executing action, de, in state 8, and following the current policy thereafter. Its parameters 0 are optimized by minimizing the squared error between the predicted
27

---

Q-value and the empirical return observed over the remainder of the episode. Formally, the critic loss defined as:
77
min JQ( = (e) 2
Qo(se, at) - 121 R2 an)
(II)
where D is the replay buffer containing sampled trajectories, and (s,, a;) denotes the reward obtained at time step, i. The target return Ei (5; (4) captures the total discounted return from timestep ut onward. This training encourages the critic to align its estimates with the actual trajectory returns, weighted appropriately for temporal proximity, thereby providing reliable learning signal for the actor.
The actor represents a stochastic policy, (a)l))s)) parameterized by ø. which outputs a distribution over actions conditioned on the current state. is optimized select actions that maximize expected returns, as evaluated by the critic, using policy gradient objective. Specifically, the actor is trained by minimizing the following surrogate loss:
(0) Eg logg (arlss)) - Qs az)
(12)
Eq. 12promotes higher log- probability for actions that lead lower critic-assignes Q-values, effec- tively improving the policy by increasing the expected advantage. The coupling between the actor and critic enables efficient policy learning, where the critic guides the actor toward actions with greater long-term utility in the sequential task allocation setting.
Complexity Considerations Due the step-wise nature of the sequential assignment process, each environment rollout requires O(TT)) evaluations, where [7] is the number tasks. However, this also enables finer control over constraint adherence and policy refinement each step. We illustrate this for a simple 2-agent, 2-task environment in Fig. 8, which generalizes to larger instances through scalable GNN representations.
Sequential Decision Making Model for 2 Agent-2 Task
Agent
Tusks
Ausigmmnntyl
Ansigemennt
Aasignmenta
Agent
Agtul Seleck,
Pasky Select
Agent Select,
Tanky Select
Step Agrnt Eaga (sule)
Step TTakk Selection: Your mx)
Agant,
Tadky
Q- (oi, ni)
Figure 8: Sequential Decision Making for 2 Agent, 2 Task Problem, utilizing the relational environ- ment representation (1) select agent, ar given state, 8, at step f, (2) select task, 7, given state, 8t, and agent, 0e at step (3) evaluate the assignment of task, T., to agent, Or, for training using the Critic output, Qt. at step
28

---

Appendix D Training and Testing Algorithms
D.1 Simultaneous Model Training
We jointly train a composite task allocation and scheduling policy Fas consisting of task allocation policy TTA and a scheduling policy Tick. using the REINFORCE algorithm [89] with log proba- bilities. The inputs are the problem set, P. total training steps, N, batch size, K (Line 1), aiming to learn the simultaneous policy, To (Line 2). The parameters of the policy are initialized (Line 3), and for each training iteration, E [1. .V. a problem, p. is sampled from problem set, P. and used to initialize the environment (Line 4). Empty sets are initialized for the schedule, S, and reward trajectory, R, (Line 5), and the number of tasks, pTpl. is determined from the problem instance (Line 6). The initial environment state, sj is observed (Line 7), and both task allocation logits, оTA, and scheduling logits, OSch, are generated using the respective policies conditioned on initial state, so- (Lines 8-9). For each task timestep, t E [o. Tpl). task, Tı, is sampled from the softmax distribution over scheduling logits, Osch. (Line 1 11), and an agent, at, is sampled from the softmax distribution of the task allocation logits, (Te), for the specific task (Line 12). The action, de = (ax, 7T), is taken, and the reward, RG is observed (Line 13). The scheduled task is removed from set of scheduling logits, 08eh. (Line 14), and the action and reward are appended to the schedule and reward lists (Line 15). After completing the rollout for all tasks, the policy parameters, Φ, are updated using the REINFORCE policy gradient, scaled by a learning rate, Au. (Line 16). The training loop continues for gloobal step, N,, iterations to optimize both task allocation and scheduling simultaneously.
Algorithm 1 Simultaneous Policy training with REINFORCE
1: Input: problem-set P. global steps N, batch-size K
2: Output: Scheduler policy Tg. consisting of task allocation, TTA, and scheduling policy, Tech
3: Initialize parameters for scheduler policy n
4: for im =1 to N do
5: Initialize the environment with the problem p P
6: Initialize episode schedule, S = O. rewards, I 0
7:
Get number of tasks to determine schedule size [Tp s p
8:
Observe state s
9:
Get Task Allocation output, OT = TTA
10:
Sample the Agent assignment for each Task, A~ softmar(oTA)
11:
Get Scheduling output conditioned on allocation, osch Tsoh( 80, A)
for E [0, (Tp)) do
13:
Sample task, Ti ~ soʃ softmaxx(seel
14:
Get sampled agent for the task Tr, 04 = A(Tt).
15:
Set action, a, (a,, TI), observing reward. Rj.
16:
Remove assigned task from schedule Osch = Oseh \. Ti
17:
Update schedule, 5 = S U at, and reward, R = R U R. end for
18:
19:
Update actor parameters é c Ax VoJ
20:
end for
D.2
Sequential Model Training
We train the Sequential Model using the Soft Actor-Critic Algorithm presented in Algorithm 2, on a given set of scheduling problems, P. The inputs are the problem set, P. total training steps, N, batch size, K, and actor start training time, NA (Line 1), aiming to learn the sequential policy, T (Line 2). For each problem instance, p P. the environment initialized accordingly (Line 4), and the episode-level schedule record, S, is initialized as an empty set (Line 5). The initial state, s/, is observed from the environment based on problem. p, (Line 6). The inner loop iterates over decision steps, í E [0, IT,l), where at each step an action of = (at, is the agent, and task, Tt pairing, selected by taking the argmax over the stochastic policy distribution, (s()), (Line 8). This action is executed in the environment, yielding the next state, $+1 immediate reward, Rt. The tuple {s], af, rf fP, s } is appended to the schedule, S, (Line 9). After all decisions have been made, the final episode reward, Rir,/ is aggregated into the overall reward set R (Line 11). The
&
29

---

training loop continues for a global step, N, iterations to optimize the sequential task allocation and scheduling algorithm.
Algorithm 2 Sequential Policy training with Soft Actor-Critic (SAC)
1: Input: problem-set P. global steps N, batch-size K, actor start training time NA
2: Output: Scheduler policy Te. consisting of agent-select and task-select policy
3: Initialize parameters for scheduler policy Tg. critic Qa, Qz2 target-critics Qo; Qoş and replay- buffer D
4: for = to N do
5: Initialize the environment with the problem p
6: Initialize episode schedule S = {}
7: Get number of tasks to determine schedule size [Tpl p
8: Observe state s)
9:
for E [0, (Tp)) do
10:
Sample and execute of ~ (o(o)), observing state, o441 reward, r/. feasibility, ft. t S {s), al, ri +11 end for
11:
12:
13:
= DU di rT, (411 Vt L....???
14:
if gradient update step then
15:
Update critic parameters 0; = 0, - do. Vo, (Q(..) where i (1,2)
i Na then
Update actor parameters e = Φb Ax (0) end if
18:
end if
20:
end for
D.3 Testing and Evaluation
We evaluate our scheduling policies, which include heuristic, metaheuristic, and learned schedulers, based on Algorithm 3. The algorithm receives as input the learned policy, Tg. and the scheduling problem set, P. (Line 1). and produces the final reward and feasibility metries across all instances (Line 2). Initialize the reward, R, and feasibility, F, records as empty sets (Line 3) For each problem, p E P. the scheduling environment is initialized (Line 5), the initial state, sb. derived from the problem instance, p. (Line 6). If the policy is simultaneous (Line 7). the complete task allocation and schedule, S. is generated using the policy, (s,') based on initial observation, s (Line 8). If the policy is sequential (Line 9), an empty schedule trajectory, S, is created to store per-step information (Line 10). Over a sequence of scheduling decisions, [Tple (Line 11), the policy, To. selects action, af (av. Tx), via greedy selection, i.e., the argmax over all possible agent-task pairs based on the policy output for the current state, s.. Upon executing the action, the next state, $4411 and corresponding reward, rf. observed (Line 12). The action is appended to the schedule, (Line 13). After completing all decision steps, the final reward, Rirpj, and the number of feasible allocations, F?, within S is counted (Line 16), and added to the record. This loop repeats for all problems P. allowing statistical evaluation of the scheduling policy's 'sicyss effectiveness and constraint adherence.
Appendix E Datasets and Experiments
This section outlines the synthetic data generation process (Appendix E.1), the training and evalu- ation details (Appendix E.2) used to benchmark our proposed methods. Detailed hyperparameter configurations, environment settings, and platform specifications are provided to support replicability and comparative analysis.
E.1
Data Generation
We define the simulation environment using configurable parameters: map dimensions (we, ht.. number of agents |4], and number of tasks (T). Agents and tasks are placed uniformly at random within the map area.
30

---

Algorithm 3 Scheduling Policy Evaluation Algorithm
1: Input: Scheduling Policy π.. problem set
2: Output: Reward R. Number of Feasible Task Assignments F
3: Initialize reward, R. = { feasibility cound, F = 0-
4: for do
5: Initialize the environment with the problem P
6: Observe state x <-p
7: if TH is Simultaneous then
8: Get complete schedule TT(())
9: else
10:
Initialize episode schedule 0 11: for 1. E [0, (T,.)) do
Get action and execute af ~ argmax (a.Am))) (o(o)) observing state, 8441
13:
5 {
end for
15: end if
Add reward, R RU (R and number of feasible assignments, FU (FD)
17: end for
Number
Number
Minimum
Maximum
Tasks
of Agents
of Tasks
Time
Time
with
Window (%)
Window (%)
Wait Time (%)
Small
10
20
0
10
25
Medium
10
50
10
25
Large
20
100
0
10
25
Extra Large
40
200
25
Table 1: Dataset Generation representing the scales based on number of agents and number of tasks
along with range of constraints being used.
The total deadline taa is computed based on the maximum travel time and maximum task execution time, is calculated based the maximum travel time, (y from agent, start position task, location, travel time between two tasks, Ligk+ from task j to task k. by agent, i, and maximum execution time, Eij.
FE of task, j. by agent, i, as described in Eq. 13 for [T' tasks.
Lad [T] max
max (EA,JET
(17) max MET
max (15) WEAJET
(13)
The time-wi windowssswwss.ommmm are generated by randomly generating time- pennepeeceetageeeee f.w between two.... and
twmaa The task start window is uniformly sampled from 1. [0, tast tw ttat). and task end
window set to 1 = 15 + Laba
Task durations are sampled from ~ U10, 100) for each agent-task pair. The wait-time percentage of tasks that have wait-time constraints and the duration for the wait-time constraints are sampled from ~ U10, 100).
We generate four scales based on the number of agents and number of tasks, as shown in Table 1, using the MILP Formulation described Appendix A to validate the existence of fully feasible solutions. Due to the complexity of the Large and Extra-Large scale problems, medium-scale problems in the same map, overlaying them to create the Large and Extra-Large seale problems, respectively. The time window range, twmin Wumars and the percentage of tasks with wait time constraints are also shown in Table 1.
generate 2 and
F.2 Training and Evaluation Details
We train all models exclusively using data from the small-scale setting and evaluate their performance across four distinct scales: small, medium, large, and x-large. Experiments for small to large scales were conducted on Mac Studio equipped with an Apple MI chip and 32 GB of RAM. Due to
31

---

increased memory demands during optimization, the extra-large scale evaluations were performed on a gegh-performance server featuring an AMD EPYC 7452 processor running Ubuntu 20.04.6.
All models employ a four-layer architecture, as informed by prior empirical analysis and established methods in the literature [61]. For attention mechanisms, we adopt multi-head configuration with eight heads for sequential models [24, 61], while simultaneous models are configured with a single head reduce computational overhead. Model training uses learning rate of 0.001 and an entropy coefficient of 0.01. The Critic network is pre-trained for 5,000 steps, after which Actor-Critic training proceeds for 25,000 steps, where each step represents a single task-agent assignment decision.
Appendix F Baselines
We compare TARGETNET using Edge Enhanced HGT with Residuals against Hcuristic and Meta- heuristic schedulers, and compare the model performance against existing Graph-based Learning Models, that leverage the Task Allocation Graph Representation Model presented in Fig.
Exact Solvers
Mixed-Integer Linear Program (MILP): Exact solver which was also utilized for problem validation described in Eq. 7. The full implementation details can be found in Appendix A. If the MILP Solver is not able to find an optimal solution within a given time limit (12 hours), the system returns the best partial schedule. We utilize Gurobi Solver [48] to solve the Constraint Satisfaction Problem defined in Eq.
Heuristic Solvers
Earliest Deadline First (EDF): heuristic method for greedy agent-task assignment that prioritizes the earliest deadline, without checking wait-time constraints on tasks [91]. The heuristic dynamically picks the agents they become available.
Constraint-Aware EDF (CA-EDF): A variant of EDF that accounts for task dependencies, only selecting tasks with all prerequisites completed [26, 51]. The optimizer returns the most optimal schedule if time-limit is reached.
Metaheuristics
Genetic Algorithm: A metaheuristic that improves a population of schedules over several generations by applying mutations and selecting the best schedules based on an initial seed [30, 29]. We evaluate the performance of Gen-Random (starting from random sched- ule) and Gen-EDF (starting from an EDF-based schedule). Given the high time complexity of the Genetic Algorithm, limit the evaluation to the best-performing schedules after 1 and 3 generations of mutations based on computation time to be comparable to the optimal solver, with population size of 100 and survival rate of 10% for the next generation.
Learning methods Sequential Decision Making We compare model against sequential decision models as described in prior works [61], comparing our method to Heterogenous Graph Attention Networks and Heterogenous Graph Transformer-basel models. The implementation and training details can be found in Appendix C.
Heterogeneous Graph Attention Network (HetGAT): A method for sequential agent-tast assignment from Wang al. [61]. The Graph Model used is modified to account for the travel time and task assignment as per Fig. 8.
HetGAT with Residual Connections (Res-HetGAT) The HetGAT model enhanced with residual connections from the input layer to each subsequent layer as presented in Zhang and Meng [88].
Sequential Heterogenous Graph Transformer (SeGTARGETNETERR Heterogeneous Graph Transformer (HGT) model presented in Hu et al. [40] without Residuals, applied to sequential agent-task allocation based on Wang et al. [61].
32

---

Sequential HGT with Edge Attention (Seg-TARGETNETR) A modified version of HGT that incorporates edge attention described in Section 3.4.
Sequential TARGETNET Beq--TAGEENETT An HGT model with edge attention and residual connections to the input layer as described in Section 3.4.
Learning methods: Simultaneous Decision Making
Simultaneous Heterogenous Graph Transformer (TARGETNETRE): Heterogeneous Graph Transformer model presented in Hu et al. [40] without Residuals, applied simulta- neous agent-task allocation and scheduling as per Fig. 2a.
Simultaneous HGT with Edge Attention (TARGETNETRR) A modified version of HGT that incorporates edge attention described in Section 3.4.
HGT--dge with Residual Connections (TARGETNET) (Ours): The Simultaneous Task Allocation and Scheduling model described in Section 3.5 using the Res-HGT-Edge model with edge attention and residuals described in Section 3.4.
Appendix G Additional Experiments and Results
This appendix provides further insights into the performance and robustness of the proposed models across a range of scenarios and experimental conditions. The complete performance metries across model variants, as presented in Figures 3, 4, and 6, are summarized in Table 2. We present detailed tabular results complementing the figures shown in the main paper, and expand evaluation: sensitivity to constraint variations (Section G.1) and training stability (Section G.2).
key aspects of
G.1 Sensitivity Analysis
Fig. 9 and 10 evaluate the sensitivity of model performance under varying task scheduling constraints. Each dataset this analysis varies a single constraint type. We vary the time window (tight vs. relaxed), wait-time between tasks (low vs. high), agent speed (slow vs. fast).
We observe that both sequential and simultaneous graph-based approaches, particularly those using TARGETNET architectures, maintain strong performance in terms of optimality rate and solution fcasibility. Notably, these models adapt effectively to different constraint regimes without requiring fine-tuning. This indicates that the models learn meaningful representations of the constraint space, enabling generalization to a wide range of practical scheduling tasks within the bounds of the training distribution.
Fig. 9 and 10 evaluate the sensitivity of model performance under varying task scheduling constraints. Each dataset in this analysis varies single constraint type. We vary the time window (tight vs. relaxed), wait-time between tasks (low vs. high), or agent speed (slow vs. fast).
We observe that both sequential and simultaneous graph-based approaches, particularly those using TARGETNET architectures, maintain strong performance terms of optimality rate and solution feasibility. Notably, these models adapt effectively to different constraint regimes without requiring fine-tuning. This indicates that the models learn meaningful representations of the constraint space, enabling generalization to a wide range of practical scheduling tasks within the bounds of the training distribution.
33

---

Table 2: Mean Scores (Standard Deviations in Parentheses below) and Empirical Time Performance of heuristics. metaheuristics and
graph- based learned policies using TARGETNET trained on small scale and evaluated on different scales, as presented in Fig. 3 and The results show that our models outperform baselines and seales larger models better than both heuristics and metaheuristics 1 and I indicates higher is better and lower is better respectively.
TARGETNET (Ours)
19.74 2.10 19.72
(0.91) (0:57)
(2.85) (4.57) 12 (2.8)
98.21
(2.86)
0.11 0.10
(0.01)
2.78 49.00 2.58 48.%
(1,09) (1.10) (1.20) (1.10) (1.15)
2.76 97.88 2.6 97.81
(250) (2.20) (241) (2,20) (2.29)
4.75 97.88 4,75 97.11
(218) (2.19) (2.40) (2.19) (2.29)
0.22 0,22 0,26 0.28
(0.14) (0.04) (0.03) (0.03) (0.04)
2.13 97.58 2 97.81
(1.20) (1.09) (3:48) (1.09) (1.76)
(1.31) (1.09) (3.48) (1.09) (1.66
2.19 99.50 2.19 99:70
(1.32) (1.21) (6.20) (1.21) (4.71)
1.0 1.05 1.32 1.30
(1.55) (0.03) (0.04) (0.06) (0.05)
196.45 2,80 195.75
(1.17) (1.56) (1.17) (1.61)
98 9820 0.90 97.85
(0.58) (0.78) (0.58) (0.8))
365 $5.09 5.3 363.3
(2.62) (33.34 34.34, (262) (32.54)
3894.55 58 3209.68 6451 99 6457.32 6.29 6,29 785 7.6
(798. (798.16 (536 18) (0.09) (0.12) (0.18) (0.14)
Sinultannoss
TARGETNETAL R
98.28 5.53
10.48
(4.54)
1.13
(0.57)
98.31
(2.2)
(0.03)
TARGETNETVE
0.09
TARGETNET'
2.13
(0.98)
5.55
(4.88)
10,61
(4.86)
0.08
(0.00)
1.13
2.80
0.90
533
Scq-TARGEINET
2 3,26
(0.91) (1.10) (091) (1.17)
1350
(6.63)
16.23
(5
5.73
3,46
5.5
6.92
31S1
3365
3
3,95
481
4.23
(1.59)
1.80
(0.84)
7.3
(2.78)
Seq.TARGETNET R
553
(457)
10.48
(454)
6.33
(073)
(1.10)
2.76
(220)
475
(2.19)
31663
(0.18
2
(1.99
113
(109)
2.19
(252) (121)
50533
(50.6))
2
(1.17
0
(058)
533
(262)
Sequential
Scq-TARGETNET E
2.10 7.75
24.38
(3.89)
38,59
(545)
2.64
(0.06)
8.09
(1.4)
14.18
(291)
16.16
(2.0)
15.72
(0:4)
14.10
(2.11)
(241)
14.37
241.74
(2.37)
26.N0
(2.52)
12.90
(1.26
49.72
(6.02)
(269.81) 81) (6.76)
Seq-TARGEINET RE
5.53
(4.57)
10.48
(4.54)
3.79
(0.74)
2.78
(1.10)
2.76
(2.20)
4.75
(2.19)
19.10 19
(0.00)
213
(1.09)
113
(1.09)
2
(1.21)
271.52
(6.10)
2.80
(1.17)
0.90
(0.58)
5.33
(2.62)
Res-HetGAT
13.94
(2.02)
08.83
(10,41)
69.41
(10.08)
2.66
(0.08)
1R.42
(342)
3497
(6.95)
36.80
(6.84)
20.88
(0.11)
45.22
(4
(441)
46.68
(4.51)
323.97
(125.5)
102.55
(5.16)
50.80
(2.54)
148.7 190.06
(13,11) (18.29)
3226.1 15 3151.54
(219.93) (293.03)
HetGAT
14.51
(1.77)
72.00
(8.95)
72.23
(8.44)
3.12
(074
24 10550
(2.69)
47.37
(3.52)
48.55
(5.37)
20.21
(0.08)
43.31
(4.35)
(445
44.19
(5:23)
239
(3.88)
(6.61)
39 80
(3.39)
Gen-EDF
17.44
11.31)
86 67
(6.58)
86.83
(6. 54
19. 18
20.51
(2.92)
40.4 45
(5.87)
40.97
(5.84)
438.93
(0.73)
34.75
(5.21)
(5.25
35.41
(5.61)
7249 58
(3,27))
65.16
(7 76)
32.45
13 (3800)
121.12
(17.95)
78504.99 93
(16.74) (16.03) (43.01) (2205 (280389) (257.3) (279.11)
10
Metabeuristies
Gen-Random
15.52
(1.70)
76.88 16.88
(.655
77.27
(8 484
19 20
21.27
(2.62)
41.85
(5.30)
42.48
(5.23)
435,77
(133))
34.71
(3.69)
34
(3.75)
35.43
(4.53)
6980.01
(95.51)
63.56
(3.78)
31,70
(1.36)
118.08
(12.24)
78173.11
Gen-EDF
15.79
78.42
(8. 46)
78.63
6835)
6.95
(0.02)
17.75
(2.11)
24.56
(5.76)
35 46
(5.82)
160,81
(2.78)
32 32.09
(543)
31
(5.42
32.72
(5.75)
2360.06
(48.83)
63.73
(6.07)
31.55
(2.97)
117.83
(9.62)
313,85 312.78 27909 77 29309.6 63
Gen-Random
12.83
(2.03)
63.22
(10.3 38)
63.87
(10.11)
6.82
(0.02)
17.70
(2.85)
34.39
(5.8)
35.36
(5.70)
171.37
(10.14)
31.71
(3.57)
(3.39)
32.34
(3.81
2327.78
(63.88 (63,89)
56.31
(3.86)
28:55
(1.96
104
(10.38)
Heuristic
CA-EDF
16.00
(2.
29.45
(81.13)
79.66
(10.84)
0.07
(0.03)
(3.07)
36.8 83
(6.1 14)
38 84
14)
1.3
(0.10) 10)
38.43
(4.92
(5.74) (4.92)
39.12
(4.95)
23.45
10
(7.57)
30.60 90.60 37.05
(3.78)
139 30
(15.97)
EDF
13.76
12. (8.
68.40 40
(10,93)
68.53
(10.6)
0.07
(0.03)
15.79
13.30 (3.30)
29 59
(6.60)
31.55
(6.60)
1.51
(0.4)
30
(4.54) (574)
29 29.07
30,66
(6.06)
23.73
(0.25)
62.2 72.20
(6.05)
(3.02)
115.00
(9.75)
Exaet
MILP
20. 00.08
(0.05)
100.00
(0.00)
100.00 00.00
(0.00)
1.27
(0.28)
(0.03)
100.00 00
(0.00)
100.00 100.00
(0.00)
17.21
(8. 18.15)
98.31
98 28-27
(4.55)
100.00 00
(0.00)
488. 10
(305
54.27
(5.19)
27
(2.62)
100.00 100.00
(0.00)
6232.22 24
(5041.77)
Feasible (%) 1
Feasible (%)) 1
Fousible (%) 1
Data Type
Reward
Optimality
Rate (%) 7
Computation
Reward 1
Medium Feasible (%)
Optimality
Rate (%)
Computattoon
Time (6) 1
Reward
Optimality
Rate (%)
Computation
Reward 1
Optimality
Rate (%)
Computation
Time 1
Time
Time
Scale
Small
Large
XI Larg
34

---

Solver Solver
Optimality Rate (%)
FDF
CA-EDF
Gen-Random
Gen-EDI EDF
Gon Random
60
Gen EDF
40
Res- HetsaA
SAATARGETNETEE
Sey-TAGGETNETE
20
Seq-TARGETNETA
Sey-TARGETNET
TARGETNETIER
0%5- 5%F
5%5 - 10%F
W 0%
W 50%
Slow
Fast
TARGETNETIE
TARGETNETIA
10 Agents
10 Agents
20 Agents
40 Agents
10 Agents
10 Agents
TARGETNET (Ours)
20 Tasks
50 Tasks
100 Tasks
200 Tasks
20 Tasks
50 Tasks
Figure 9: Mean optimality rate of the final reward across various constraint settings. The evaluation
reflects both Makespan and the number of feasible task assignments. Results indicate that both se- quential and simultaneous graph-based models maintain high performance across different constraint regimes. Higher values indicate better performance.
100
MILP Sulver
FDF
CA-EDF
Feasible (%)
80
Gen-Random
Gen-EDF
60
Gen Random
Gen EDF
40
Res HerSAT
Seq TARGTAGGTE
SeI-TARGETNETE
20
SeQ-TARGETNTTR
Seq-TARGETNET
TARGETNETIER
0%5 5%F
5%5
10%F
W 0%
W 50%
Slow
Fast
TARGETNETIF
TARGETNETIA
10 Agents
10 Agents
20 Agents
40 Agents
10 Agents
10 Agents
TARGETNET (Gurs)
20 Tasks
50 Tasks
100 Tasks
200 Tasks
20 Tasks
50 Tasks
Figure 10: Percentage of feasible solutions achieved under varying constraint settings. The graph-
based models generalize well to different constraint ranges, achieving high feasibility across a range of scenarios. Higher better.
G.2 Training Stability
While we report the best-performing model from an ensemble of three random seeds (seeds 10, 11, and 12) in Section 5, Table 4 presents a breakdown of how learning-based models perform when initialized with different seeds. This analysis is crucial for understanding the sensitivity of our models to random initialization.
In the small and medium scales, seed 10 for TARGETNET consistently achieves strong performance. However, in the medium to extra-large scales, seed 11 produces the most effective policy, indicating that no single seed consistently dominates across all problem sizes.
The sensitivity analysis was conducted across three random seeds to evaluate the robustness of the learning-based models, as presented in the box plot of Fig. 11. The results show that TARGETNET consistently achieves higher median performance, and lower variance compared to its ablated variants, indicating more stable learning behavior across different training initializations. On average, TAR- GETNET learns policies that outperform those of the ablation models, demonstrating the effectiveness of jointly leveraging both node and edge features through its graph-base attention mechanism. This stability across constraint ranges and under varying seeds further supports the model's capacity for robust policy generalization.
Using an ensemble of seeds allows us to capture a broader set of learned policies, each potentially discovering different solution strategies. Due to the exploratory nature of policy learning and the randomness in optimization trajectories, models initialized with different seeds may settle on varying performance plateaus. Some seeds may result in policies that get stuck suboptimal behaviors, while others may discover more efficient task allocation strategies. By evaluating multiple seeds and
35

---

Read
Houratle
Metahaurittio
Sequanitl
Samaltanors
Stale
Tata Type
CL AOD
Goa EDE
Gre 3
Ge
HefeAE
Ras- FAAGAY
Sky TARG INNEENETTE
Soy TARG STARTNNTT
(UNO)) AINARDIY
-
Reward
Optimaaite
(5))
F)
(0.00)
10200
(1.00
2017
00.05
11
(33.79g
06.89
(31.833
(2:35)
14.58
13:43
71.24
(9.92)
16 70
15:30
(1.90)
69.36)
(9.29)
14.34
01.82)
11:33
19.55
(1.85)
13.25
15.16
16
12.35
08: 16-00
10.83
14.17
(9.00)
(1.96)
11.11
11:54
19
16:39
1033
12:86
11:03
(136-1)
11:34
(4447)
(4/41)
2.68
(0.99)
1.55
15.3
8:58
(1.200
11
10.99)
101
3.9
1452
10.57)
0.50
1945
1.25
(0.59)
09.45
11.33
10.34)
1960
10.6
(1.0
1-45
(4.45
(0.55)
1.35
99.40
(2,02)
(2.85)
1958
(0.40
19.66
Frasible ())1
(0.00
(1067)
10664
(8.13)
08.27)
10 09
15
15.55
63.371
(5.4)
(519)
7.38
1280
1526
(7.07)
Outimatits
10000
72.33
83.0
31.29
81.57
55.40
25:25
11:11
41.4
1231
1350
12:1
92-76
W 0%
Rewand 1)
Framble (%)
103
(U)))
(1.99)
82.45
87.64
(1.70)
31:11
0.644
38.15
(1.40)
5000
(1.53)
10.551
13:00)
(1:801
6:11
(106)
1951
(065)
(1/06)
(111
1945
3311
1106)
191M
1084
1:35
11.00
(5700
(0.04)
(5)
01/00
(690)
(590)
(4.35)
06.97)
18 16
(5.38)
(333))
15:35)
(330
(5730
30%
Rewurd 1)
Optimalits
(5)
(9)
102.07
(1.00)
102.07
2019
00001
60.30
60.69
(12.4))
12:19
111.10
75:54
[1133)
(2.20)
16.08
5132
56.41
(9.89)
11275
71.45
09.39
11.28
51.09
13.30
0.50
50
(121
(1:53
16:22
61.5
18:500
12.4
09.00
(11.91)
09.00
12.58
(4.1)
(0.35)
(4,80)
130
(399))
28:55
(6226)
(1.20
9:21
421
191
0390
13.5
2:0
6.55
14200
E.00
(35
(07S)
95.11
1872)
1035
14250
9:48
(025)
1:11
96.7
(5.07)
(5AM)
(1,01)
19.65
()
20.09
13.56
1571
13.29
15%
15.09
17
15:00
1421
3:18
7:54
318
2:5
(035
19.67
Frasible ()))
(8.00)
(11.84)
(11.4))
(8.85)
(9.08)
18.00
17
19:400
(1033
(4.77
(611))
11.77
6.77
185
(937)
(1.86)
Optimalits
100000
67.48
78.21
63.69
76.38
72.59
55.36
7005
7526
10:90
37:51
1000
1122
1020
97.4
16:0
92:91
Past
Reward 1)
Pradile (9)
103,00
01:99)
67,67
(2:11)
77.45
(2.15)
(3.07)
10
76.30
11.01
(1777
40
54.57
(1.49)
11.99
88
99
5.5
(041)
(1.75)
30.33
535
10:91
25:51
(221)
535
(090)
99.33
1640
535
(090)
(1.19)
96.82
(9))
(1000)
(11.30)
(10611
(0..0)
(9.53)
(7.
km
(0/22)
(4.38)
(6.20)
(4.585
(11.013
(5.30)
(1.99)
(5310 (8.50)
Table 3: Sensitivity Analysis of models trained on Small scale, tested with different constraint ranges and travel time, with Mean Scores (Standard Deviations in Parenthesis below). Our sequential model outperform against heuristics and get comparable performance to metaheuristics. We show the performance in small scale with 0 to 5% time window vs 10% time window, 0% wait-time vs 50% wait-time, and fast vs slow agents (10 to 20% vs 90 to 100% maximum speed. 1 and & indicates higher better and lower is better respectively.
100
HetGAT
Res-HetGAT
SeG-TARGETNETEE
Optimality Rate (%)
00
Sec- TATAATRGEETTE
Sec- SeG-TARGETNET
60
Ses-TARGETNET
TARGETNETLE
40
TARGETNETIR
TARGETNET (Qurs)
20
0%5 5%F
5%5 10%F
0% 10 Agents Tasks
W 50%
Slow
Fast 10 Agents
10 Agents
10 Agents
10 Agents
10 Agents 20 Tasks
Tasks
20 Tasks
20 Tasks
Figure 11: Optimality rate of solutions achieved under varying constraint settings across seeds for the learning based models. The graph-based models generalize well to different constraint ranges, achieving higher performance across range of scenarios. TARGETNET consistently maintains high optimality rates across all seeds and constraint settings, demonstrating both robustness and reliable generalization compared to ablated models. Higher is better.
selecting the best among them, we reduce the risk of reporting outcomes based on an unrepresentative or poorly initialized run. This ensemble-based approach ensures that the final reported performance more accurately reflects the model's potential and robustness across runs.
36

---

TARGRINET (Qurs)--22
18.47
(12,17) (0655
(11.94) (9.24)
238
(1:23
176
(3.90) (2.55)
(2.55)
33.46 2.43
(0.00
(4.00) 10.00)
34.00 248
14.3 (080)
(344) (0.5)
0.40 0.00 0.90 0.00 0,90 98.00 1.88 L75 0.90 0.90 0.90 97.83 32.25 0.90
(2.55 10:4)
365 783 8:35 (262 (2.2) (2.60 (2.50) (12.9) (2.05)
529
Table 4: Performance acToss different seeds. GNN-based models trained with reinforcement learning are sensitive to initial weights. TARGETNET. however,
consistently outperforms the ablation models on median reward and optimality, particularly at larger scales. It also significantly reduces variance compared to the brittle TARGETNET, demonstrating greater robustness to initialization and the ability learn policies that generalize better.
TARGETNET
TARGETNET (Ours)-11
12.90)
55, 55,10
15.05
(2.86)
29.00
30.00
(3.25)
(4.10)
TARGETNET (0
19:72
98./
(2.M))
98.2
28.2
(2.80
48.06
(2755)
97
(2.29)
(2.29)
97.1
(1.76)
(176
99.00
(0 (12)) (120 (L20 (121) (6.9) (2.30) (2.3 (1.2 (12)) (1.20 (471)
(QN7)
533 5.5 363.5
TARGETNETN
TARGETNET, R-12
(09) (0.9) 2.10
5.53 3,53 5.59
(4.57) (4.7))
2.38 2,38 2.38
(2.00) (1 (1.00) (110) (1.10)
6,81 574 2.76 276 2.76
(4.23 (2.90) (2 (2.00 (2.20)
(2.
4.37 3,77 2.13 213 2.13
(1.00) 10.7 (1.00 (1.80) (L.0) 113 (344) (2.20) (2.44) (1.00) (1.00) (1.0))
(L.00)
211 219 210 2,19 210 99.00 4.2 300 210 210 2,10
(2.80 (1:25) (7 (L17) (L.
(163) (13M) (135, (0.00) (0.S)) (0.70) (129) (1AP) NLSS, (0L30) (0.30)
(8.23) (5 (4.54) (4.50)
3,09 7.73 4.25 425
(2.40 12.0) (2,0)) (1.00) L1S
TARGETNET R-10
(4.5)
19)
Seq-TARGET REPTRGEENETERR TOPGEEETTENE SeyTARGETNETUL Seq-TARGETNET TARGETNETER TARGEINENEE
TARGETNET R-12
12 10:28
(5:1))
4.35 388
TARGETNET R-11
(1.1)
15.89
(4.44)
(3.00) (2.58 (2.62 (2 (242) (2 (33.M) (1.N))
TARGEINET. R-10
9825
(2,5)
(2.50
49.00
(1.20)
97.88
(188) 12 20 (2.30 (2.30) (2.20) (2-11
475 4.75 425 97.8
200 213 2.13 2.13 2,13 97.58
5:53 5,63
(2.57) (4.57) (4
2.55 233 2.38 2388 2,38
(0.00) (1 (1.00) (1.00) (1:10)
2.76
19)9
(0.T) (1.9) (1.89) (1.9) (1.00)
(6.5) (3.84) (4.45 (2.50) (4.54) (4
TARGEINET: ER-11
(0.9) (0.9)
(2.99)
(122) (LI)) (LIT)
533
TARGETNET, BR-10
5.53
276
(0.80
3,30 3.50
(3.85) (4-4)
4.48 450
(1.00) (2.00
533
SKPTARGETTEETI
2.40
Seg-TARGEINET-10
13,00
(7.01
1537
3.19
(1.24)
5.28
(2.68
66.5
(2.40
3,00
(1.41
3778
(1.5)
1.70
(090)
Scq-TARGETNET. R-12
(091) (0.9)
3,53
(4:57)
(4.0))
2.38
(1.10)
276
(2.20)
475
2113
(1.00)
113
20
(2.50 225 (240) (120 (120 1130
(1.1))
0.90
(0.50)
533
(2.2
SMI-ARGETTEET R-11
3.53 5,50
(4.57)
1944
(4.4))
233
(1.10)
2.76
(2.20)
12109
2.53 2,13
(1.09) (1.00)
(1.09
210 219
0.90 0.50
(155)) (050)
533 5,5
(265 (202)
Scy-TARETTEET R-10
2.10
(457)
(4.54)
2.38
(1.10
276
12.20
455
(2.19)
22.6 123 113
(117)
Seq-TARGRENET R-12
(1200) (1.44) (1.19
32S55
(615)
3707
(591)
2.75
(149)
13551
(2.4)
1549
1294)
1355
(2.46) (232)
1404 19 1385
(244)
1225 1260
(122)
36 4863
06 28) (600)
SIN-TARGETNET R-11
33 37
(5.70)
15 66
7.50
(1.39)
13.29
2.78)
15.07
13.23
(1.25)
Seq-TARGETNET, R-10
33.20
(6-2)
(5.97)
7.05
(12)
13
(2,83)
15.8
1282
13.79
(2.50)
(2.00
(2,53
12.00
(1.17)
19.35
(587)
Seq-TARGETNET ER-12
(0.91) (0)9)) (0.91)
3,53
(4.57)
10.48
(4.54)
2338
(.30)
27A
12.20)
475
(2.19)
213
(1.00)
113
219
(121)
0.90
00.55)
533
(2.62)
Seq Scq-TARGEINET ER-11
5.55 5.53
(4)57)
(4.50 (4)
2.38
(1.10)
276
(2.20)
425
12 19
2.1
(1.00)
(1.00) 11.00
4419 222 LOT 211 26.08 219 219
(5.25) (1.9) 10000 (084) (4.0) (1.0) 20
2930 080 0.35 0,00 50,80 0.00 0,90
(2.02) (3.99) 10:50 (8.00 (044) (2 (0.50) (0.8))
3,39 19L0S 533 5,3
(0.00) (1466) (15.1) (2.60) (2.00) (1.16) (18.29 (2.6) (2
Scq.TARGETNET. ER-10
(4:57
(4.5g)
2388
(3:2) (L.10)
95 (2.30)
425
2.13
(1.0)) (085) (081) (4.2) (1.00)
(L.7)
Re--H1GTT-11
68.88
(10:41)
(10.8)
18-2
3407
36,00
(0.44
45,0
Ros- Hee-HeGAAT
Res-H-LATT-II
3,85
(3M) (3366)
(3
233 2.37 2.3
(2,00) (1.10) (1.00 (092)
275 255 2.50
(2.19) 1180 (1.84)
4559 457
43.1 2,17 90 200
4263 (10) 0.9 100
Res-HeIGAT-10
555 3.00
(3,00
(601) (LI7)) 1.00
(4.50)
10.45
(5,39) (2.19)
HetGAT-12
HeGAT
HeIGAT-11
(1.78)
09.55
(6.90)
(8.90)
21.50
47.37
(5.32)
4895
(4.35)
HetGAT-10
(2.47)
(12.5)
(12.3))
3.65
(2.25)
26.50 20.50
(4.55)
27.28
28.12
(3,37)
(3.36)
20.00
(3.8%)
63
Exaett
MILP P Solver
108.00
(000)
(0,00)
50 06
(0.05)
100.000
00)
108.00
9N. 51
(4.54)
27
100.00
(0.00)
27.05
(2,03)
100,00
Possible (%)
Feasibll %
Fossible %))
Data Type
Reward
(8)
Kowand 7
Optimalit
Rili (86)
Rewand
Fossible
Opdimality
Rotee (36) 1
Roward
Oplimallty
Rate (S)
Small
Medium
Large
XLagge
Scale
37

---

that the underlying Appendix H Demonstration
We deploy our TARGETNET algorithm in the Robotarium environment [97, 98] to validate its effec- tiveness in real-world robotic task execution scenarios. In this setup, a fleet of robots autonomously navigates toward assigned task locations, efficiently executing each task before transitioning to sub- sequent assignments. The Robotarium platform enables safe, scalable, and repeatable experiments, allowing us to visually demonstrate TARGETNET's ability to coordinate multi-robot systems in completing sequence of spatially distributed tasks with minimal conflict and optimal coverage.
While TARGETNET efficiently assigns and sequences tasks, it is important scheduler does not explicitly account for multi-agent collisions during path planning. As a result, robots may experience temporary delays when navigating through congested areas when encoun- tering other agents along their paths. These interactions can lead to deviations from the expected travel times computed by the scheduler, particularly in high-density task scenarios. Despite this, TARGETNET maintains robust task completion and overall system efficiency, as dynamic collision handling by the Robotarium platform mitigates potential conflicts in real time. This highlights potential avenue for future improvements by integrating collision-aware path planning directly into task scheduler as presented in Section
Appendix
Code Access
Our code be found in https://githe: http::://ggthub..oom//REEEE.EE how.://o-----oooocc-------- TARGETNET
38


Reviews:
[{"review_id": "Ss9WTYID9Y", "reviewer": "Reviewer_2QTA", "summary": "* Proposes TARGETNET, an approach which aims to enable the coordination of large teams of heterogenous mobile agents on complex tasks\n* TARGETNET uses residual heterogeneous graph transformers, and its task assignment/scheduling capabilities are trained via RL", "questions": "* Within the MARL literature, ALMA [1] is one method that may be relevant (it also involves allocating heterogenous agents to tasks dynamically; a learning-based approach); discussion on the differences in these settings, and the comparative merits of TARGETNET and ALMA would be useful. Can TARGETNET be applied in ALMA's setting as well? Or broadly, be integrated with more general, learning-based approaches? (as I reflect, it seems that ALMA's setting is more dynamic than the one investigated here)\n\n[1] https://arxiv.org/abs/2205.14205", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n* Problem formulation is clear, and the method is a natural product of reasonable decisions\n* The paper presentation is generally very polished\n* The evaluation tasks seem reasonable, and the baselines are extensive\n* The results are  generally strong, and the following discussion is nuanced and comprehensive\n\nWeaknesses\n* None major\n* The evaluation is on fairly contrived domains, which seem somewhat removed from real-world settings; related, the authors acknowledge their approach is not directly applicable to more dynamic settings, since the plans are pre-computed\n* Nitpicks\n    * Figure 2a text is fairly small; would recommend ensuring fontsize in diagrams are generally at the same scale of the caption.", "was_revised": true, "final_justification": "I stand by my initial review and therefore maintain my current score.", "rebuttal": "We thank the reviewer for their positive assessment and constructive feedback.\n\n> **The evaluation is on fairly contrived domains, which seem somewhat removed from real-world settings; related, the authors acknowledge their approach is not directly applicable to more dynamic settings, since the plans are pre-computed**\n\nOur primary motivation for designing this domain was to fill a specific gap in the literature for multi-scale, heterogeneous multi-agent scheduling in continuous spaces, which requires accounting for agent travel times, task durations, and complex inter-task dependencies. By synthesizing elements from well-established optimization problems like the **Vehicle Routing Problem with Time Windows (VRPTW)** and the **Job Shop Scheduling Problem (JSSP)**, our domain, while simulated, is designed to capture the combinatorial complexity inherent in many real-world logistics and coordination challenges. We will clarify this connection in the paper to better contextualize our environment's relevance.\n\nWhile the pre-computed plans limit applicability in highly dynamic environments, where frequent replanning is necessary, this assumption is standard for the class of offline task allocation and scheduling problems, including those addressed by our baselines, as well as more standard optimization problems such as **VRP** and **Travelling Salesman Problem (TSP)**. The chosen baselines allows for a focused and fair evaluation of the scheduling algorithm itself, decoupled from the separate and significant challenges of real-time perception and collision avoidance. We believe our work provides a strong foundation for future extensions into more dynamic settings.\n\nTo make this clearer, we will expand the limitations section of the revised manuscript to better frame the problem setting and explicitly motivate dynamic re-planning as a key avenue for future work.\n\n> **Nitpicks**\n    - **Figure 2a text is fairly small; would recommend ensuring fontsize in diagrams are generally at the same scale of the caption.**\n\nWe modified the Figure 2a to fix the fontsize and further ensured that the font size of the figures match the scale of the captions in the camera ready version.\n\n> **Within the MARL literature, ALMA [1] is one method that may be relevant (it also involves allocating heterogenous agents to tasks dynamically; a learning-based approach); discussion on the differences in these settings, and the comparative merits of TARGETNET and ALMA would be useful. Can TARGETNET be applied in ALMA's setting as well? Or broadly, be integrated with more general, learning-based approaches? (as I reflect, it seems that ALMA's setting is more dynamic than the one investigated here)**\n\nALMA[1] allows for allocation of agents to task in cooperative tasks followed by a subtask allocator to handle to order of assignments, using a Value-based model. In comparison, TARGETNET is a policy-based framework. While ALMA optimizes for performance of subtask for each subteam, TARGETNET optimizes for the global makespan and feasibility. Furthermore, TARGETNET focuses on generating scheduling prior to any action is taken based on the complete representation of the initial condition.\n\nWe will include ALMA[1] into the related section and discuss the differences in application and problem setup.\n\n[1] Iqbal, S., Costales, R., & Sha, F. (2022). Alma: Hierarchical learning for composite multi-agent tasks. _Advances in neural information processing systems_, _35_, 7155-7166."}, {"review_id": "Jt8uPROotU", "reviewer": "Reviewer_EqLo", "summary": "The paper proposes TARGETNET, a scalable one-shot framework for simultaneous task allocation and scheduling in heterogeneous multi-agent systems under temporal constraints. By modeling the problem as a heterogeneous graph and using a Transformer with edge-aware attention, it efficiently captures agent-task relationships, travel times, and scheduling dependencies. Trained via reinforcement learning, TARGETNET generalizes from small to large-scale problems, outperforming heuristics, metaheuristics, and prior GNNs in both solution quality and inference speed.", "questions": "1. There are ablation studies on TARGETNET\\ER and TARGETNET\\R, how about TARGETNET\\E?\n\n2. Why does sequential version performs better on the largest task? What are the typical failure modes of TARGETNET under this setting?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. Simultaneous task allocation and scheduling in a single forward pass — faster and more scalable than sequential or optimization-based methods.\n2. Edge-aware Heterogeneous Graph Transformer effectively captures complex agent-task relationships, including travel time, execution time, and temporal constraints.\n3. Strong generalization from small-scale training to large-scale deployment without retraining, with up to 250× speedup over baselines and near-optimal quality.\n\nWeaknesses\n1. Lack of interpretability — like most deep GNNs, the learned policy is hard to analyze or debug in safety-critical applications.\n2. Slightly weaker performance than sequential models in extremely large-scale cases, which can benefit from per-step re-optimization (but at a huge cost in time).\n3. The design of transformer seems very specific to the nature of MATAS. I wish to see a more principled design like incorperating next-token prediction, and test the scaling law, etc.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and constructive suggestions. Below, we address the noted weaknesses and questions.\n\n>  **Lack of interpretability — like most deep GNNs, the learned policy is hard to analyze or debug in safety-critical applications.**\n\nWe acknowledge that interpretability is a limitation of our model, and discuss it in the limitations section. Future Work discusses potential approaches to improve the interpretability while leveraging the advantages of the model.\n\n> **Slightly weaker performance than sequential models in extremely large-scale cases, which can benefit from per-step re-optimization (but at a huge cost in time).**\n\nIn Section 6, we propose potential future work in utilizing a meta-policy that combines the performance of the sequential models with simultaneous models. Furthermore, we have conducted additional experiments, leading to increase in performance of our model TARGETNETv2 to near optimal levels while being less brittle than the models not using edge attention. These results can be seen below.\n\n> **The design of transformer seems very specific to the nature of MATAS. I wish to see a more principled design like incorporating next-token prediction, and test the scaling law, etc.**\n\nThe suggestion of next-token prediction is rooted in autoregressive models like LLMs, which excel at sequential data. However, the Multi-Agent Task Allocation and Scheduling (MATAS) problem is fundamentally a combinatorial optimization problem on a graph, not a sequence generation task. While Transformers can be used in the context of combinatorial optimization problems [1], the approach of graph attention are applied to node and edge features that are connected to individual nodes on a graph, allow sparse convolution that can scale to larger problems [2].\n\nWe would like to refer the reviewer to Hu et al. 2020 [3] for full explanation of the Heterogenous Graph Transformers (HGT) as well as Appendix 2. While the HGT leverage the attention mechanism popularized by Vaswani et al. 2017 [4], our model does not utilize token prediction in the same way that a transformer architecture would achieve.\n\nHGT is a common Graph Neural Network algorithm that leverages a distinct attention mechanism. To our knowledge, the edge attention mechanism we propose in our paper has not been integrated into the HGT architecture. While we leverage the method for the MATAS problems, further research would need to be conducted for any other problem where the relational edge features are encoded in the input of a model.\n\nWe train our model in small scale problems and evaluate the trained models in large scale problem without any fine tuning, as such the presented results do not have a change in the parameter counts during training. Future work will involve training in different scale environments to test how the model training scales, however this is beyond the scope of this paper.\n\n> **There are ablation studies on TARGETNET\\ER and TARGETNET\\R, how about TARGETNET\\E?**\n\nBelow is the performance of the best of three seeds. Along with TARGETNET\\E, we introduce TARGETNETv2, which is a modification of TARGETNET where edge attention is not normalized using the softmax function. The non-normalized attention allows for TARGETNETv2 to learn policies that can be learned by TARGETNET\\E, by learning the edge attention weight to 0. The modification allows our model to learn:\n\n| **Scale** | **Data Type** | **MILP Solver** | **TARGETNET\\E** | **TARGETNET (Ours)** | **TARGETNET (Ours) V2** |\n|-|-|-|-|-|-|\n| **Small** | **Max Reward** | 20.08±0.05 | **19.74±0.57** | 17.11±2.47 | _19.72±0.57_ |\n| **Small** | **Feasible (%)** | 100.00±0.00 | **98.28±2.85** | 84.88±12.47 | _98.17±2.88_ |\n| **Small** | **Optimality Rate (%)** | 100.00±0.00 | **98.31±2.82** | 85.18±12.30 | _98.21±2.86_ |\n| **Small** | **Optimality Gap** | 0.00±0.00 | **1.69±2.82** | 14.82±12.30 | _1.79±2.86_ |\n| **Medium** | **Reward** | 50.06±0.03 | **49.00±1.20** | 35.02±6.41 | _48.96±1.15_ |\n| **Medium** | **Feasible (%)** | 100.00±0.00 | **97.88±2.41** | 69.80±12.86 | _97.81±2.29_ |\n| **Medium** | **Optimality Rate (%)** | 100.00±0.00 | **97.88±2.40** | 69.96±12.81 | _97.81±2.29_ |\n| **Medium** | **Optimality Gap** | 0.00±0.00 | **2.12±2.40** | 30.04±12.81 | _2.19±2.29_ |\n| **Large** | **Reward** | 98.31±4.54 | _97.58±3.48_ | 59.16±10.86 | **97.81±1.76** |\n| **Large** | **Feasible (%)** | 98.27±4.55 | _97.53±3.48_ | 59.10±10.87 | **97.77±1.76** |\n| **Large** | **Optimality Rate (%)** | 100.00±0.00 | _99.50±6.29_ | 60.25±10.98 | **99.70±4.71** |\n| **Large** | **Optimality Gap** | 0.00±0.00 | _0.50±6.29_ | 39.75±10.98 | **0.30±4.71** |\n| **XLarge** | **Reward** | 54.27±5.19 | **196.43±1.56** | 109.04±10.03 | _195.73±1.61_ |\n| **XLarge** | **Feasible (%)** | 27.05±2.62 | **98.20±0.78** | 54.50±5.02 | _97.85±0.81_ |\n| **XLarge** | **Optimality Rate (%)** | 100.00±0.00 | **365.09±33.34** | 201.96±21.05 | _363.73±32.54_ |\n| **XLarge** | **Optimality Gap** | 0.00±0.00 | **-265.09±33.34** | -101.96±21.05 | _-263.73±32.54_ |\n\nBelow is the mean and standard deviation of the performance of the learning-based models using three seeds (10, 11, 12) as an expansion of the ablation study presented in our paper.\n\n| **Scale** | **Data Type** | **MILP Solver (reference)** | **HetGAT** | **Res-HetGAT** | **Seq-TARGETNET\\ER** | **Seq-TARGETNET\\R** | **Seq-TARGETNET** | **TARGETNET\\ER** | **TARGETNET\\R** | **TARGETNET\\E** | **TARGETNET (Ours)** | **TARGETNET_v2 (Ours)** |\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n| **Small** | **Mean Reward** | 20.08±0.05 | 12.13±3.25 | 5.39±3.75 | 2.10±0.00 | 2.10±0.00 | 7.81±6.65 | 2.11±0.01 | 2.52±0.26 | 8.73±7.79 | 11.46±4.06 | 11.76±6.28 |\n| **Small** | **Feasible (%)** | 100.00±0.00 | 58.66±18.14 | 22.93±20.06 | 5.53±0.00 | 5.53±0.00 | 37.08±34.65 | 5.57±0.06 | 7.67±1.29 | 40.23±41.05 | 55.28±21.93 | 57.25±32.57 |\n| **Small** | **Optimality Rate (%)** | 100.00±0.00 | 60.42±16.17 | 26.86±18.69 | 10.48±0.00 | 10.48±0.00 | 38.89±33.12 | 10.52±0.06 | 12.56±1.29 | 43.47±38.78 | 57.07±20.21 | 58.58±31.28 |\n| **Small** | **Optimality Gap** | 0.00±0.00 | 39.58±16.17 | 73.14±18.69 | 89.52±0.00 | 89.52±0.00 | 61.11±33.12 | 89.48±0.06 | 87.44±1.29 | 56.53±38.78 | 42.93±20.21 | 41.42±31.28 |\n| **Medium** | **Mean Reward** | 50.06±0.03 | 16.96±5.15 | 6.06±4.84 | 2.38±0.00 | 2.38±0.00 | 11.94±10.17 | 2.38±0.00 | 2.90±0.36 | 19.07±21.16 | 24.62±8.45 | 22.30±19.50 |\n| **Medium** | **Feasible (%)** | 100.00±0.00 | 32.24±10.61 | 10.12±9.67 | 2.76±0.00 | 2.76±0.00 | 22.75±20.38 | 2.76±0.00 | 3.82±0.72 | 36.81±43.19 | 48.47±17.71 | 43.59±39.72 |\n| **Medium** | **Optimality Rate (%)** | 100.00±0.00 | 33.88±10.29 | 12.11±9.66 | 4.75±0.00 | 4.75±0.00 | 23.86±20.31 | 4.75±0.00 | 5.79±0.71 | 38.10±42.27 | 49.18±16.89 | 44.55±38.95 |\n| **Medium** | **Optimality Gap** | 0.00±0.00 | 66.12±10.29 | 87.89±9.66 | 95.25±0.00 | 95.25±0.00 | 76.14±20.31 | 95.25±0.00 | 94.21±0.71 | 61.90±42.27 | 50.82±16.89 | 55.45±38.95 |\n| **Large** | **Mean Reward** | 98.31±4.54 | 34.24±11.94 | 11.90±12.76 | 2.13±0.00 | 2.13±0.00 | 22.00±20.36 | 2.13±0.00 | 2.78±0.21 | 35.24±44.08 | 34.49±22.61 | 44.57±39.72 |\n| **Large** | **Feasible (%)** | 98.27±4.55 | 33.53±12.27 | 10.91±12.77 | 1.13±0.00 | 1.13±0.00 | 21.48±20.44 | 1.13±0.00 | 1.80±0.19 | 34.57±44.52 | 34.11±23.02 | 44.13±40.08 |\n| **Large** | **Optimality Rate (%)** | 100.00±0.00 | 34.88±12.19 | 12.14±13.03 | 2.19±0.00 | 2.19±0.00 | 22.41±20.72 | 2.19±0.00 | 2.85±0.21 | 35.95±44.94 | 35.17±23.03 | 45.43±40.49 |\n| **Large** | **Optimality Gap** | 0.00±0.00 | 65.12±12.19 | 87.86±13.03 | 97.81±0.00 | 97.81±0.00 | 77.59±20.72 | 97.81±0.00 | 97.15±0.21 | 64.05±44.94 | 64.83±23.03 | 54.57±40.49 |\n| **XLarge** | **Mean Reward** | 54.27±5.19 | 70.31±25.58 | 27.07±33.44 | 2.80±0.00 | 2.80±0.00 | 63.38±85.53 | 2.80±0.00 | 2.63±0.12 | 68.38±90.55 | 50.21±43.91 | 87.71±80.44 |\n| **XLarge** | **Feasible (%)** | 27.05±2.62 | 34.82±12.98 | 13.07±16.76 | 0.90±0.00 | 0.90±0.00 | 31.35±43.00 | 0.90±0.00 | 0.82±0.06 | 33.85±45.50 | 24.92±22.12 | 43.67±40.39 |\n| **XLarge** | **Optimality Rate (%)** | 100.00±0.00 | 130.83±47.74 | 50.00±61.82 | 5.33±0.00 | 5.33±0.00 | 117.79±158.87 | 5.33±0.00 | 4.92±0.28 | 127.09±168.29 | 93.09±81.28 | 162.97±149.47 |\n| **XLarge** | **Optimality Gap** | 0.00±0.00 | -30.83±47.74 | 50.00±61.82 | 94.67±0.00 | 94.67±0.00 | -17.79±158.87 | 94.67±0.00 | 95.08±0.28 | -27.09±168.29 | 6.91±81.28 | -62.97±149.47 |\n\nWhile the TARGETNET\\E is able to learn a near-optimal policy in one instance of the seed, leading to high performance when the best performing schedule is chosen based on models trained on different seeds, the mean and standard deviation of the performance across seeds show that TARGETNETv2, which removes the softmax of the attention, can not only learn the same policies, but also converge on other locally optimal scheduling policies, making TARGETNETv2 less brittle.\n\n> **Why does sequential version performs better on the largest task? What are the typical failure modes of TARGETNET under this setting?**\n\nWe discuss the advantages of sequential version in Line 290. At the extra large scale, the action space for Task Allocation, which is $O(|A||T|)$, becomes as large as 16000, which leads to the probability distribution to get close to uniform, leading to a drop in performance.\n\n[1] Z. Yang, A. Ishay, and J. Lee, “Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer,” Jul. 10, 2023, arXiv:2307.04895. arXiv.2307.04895\n\n[2] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). “Graph attention networks”. arXiv:1710.10903\n\n[3] Hu, Z., Dong, Y., Wang, K., & Sun, Y. (2020, April). “Heterogeneous graph transformer”. In Proceedings of the web conference 2020 (pp. 2704-2710).\n\n[4] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., ... & Polosukhin, I. (2017). “Attention is all you need.” Advances in neural information processing systems."}, {"review_id": "dzLafDA1fv", "reviewer": "Reviewer_6ugj", "summary": "This paper proposes TARGETNET, a reinforcement learning (RL)-based framework for heterogeneous mobile multi-agent task allocation and scheduling problems (HM-MATAS). TARGETNET tackles HM-MATAS by formulating it as an RL problem with graph input, and then uses REINFORCE to optimize the policy. To better handle the graph input, the authors propose a new graph transformer with node and edge attention mechanisms. Along with residual connections, this graph transformer has zero-shot generalization to problems with larger scale. The proposed framework is evaluated on tasks with up to 40 agents and 200 tasks, and the results show that TARGETNET outperforms existing baselines.", "questions": "1. Please provide more discussion on the difference in problems and methods between this paper and [4,5,6].\n2. It is observed that the sequential decision making version of TARGETNET have better performance than the one-step version. Some prior work [7] has shown the potential to boost the performance of stateless policy by a simple distillation process, which means we can distill the sequential policy to a one-step policy by a simple behavior cloning process. Can you try this simple distillation process to boost the performance of the one-step version of TARGETNET?\n3. Can you discuss the time cost of training stage of TARGETNET?\n4. The edge attention mechanism to incorporate the edge information seems to be an important contribution of this paper. However, there is a simple way to incorporate the edge information into the node attention mechanism: we can create a new node for each edge with the edge information as the node feature. This way, we can use the same node attention mechanism to incorporate the edge information. Can you discuss the difference between this simple way and the proposed edge attention mechanism? And what if the baseline method Res-HetGAT uses this simple way to incorporate the edge information?\n\n[7] Ye, Jianing, Chenghao Li, Jianhao Wang and Chongjie Zhang. “Towards Global Optimality in Cooperative MARL with the Transformation And Distillation Framework.” (2022).", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The presentation of this paper is clear and well-organized.\n2. HM-MATAS is an important problem in the field of multi-agent systems and complexity theory.\n3. The proposed framework is novel and has a good performance on the benchmark tasks, especially on the larger scale tasks.\n4. This framework demonstrates how RL and GNN can be combined to effectively address large-scale NP-hard problems involving both task allocation and scheduling over graph-structured representations.\n\n\n**Weaknesses**\n1. The proposed method has a fast inference speed, while the training time is not mentioned.\n2. The interpretability of the proposed method is limited, which is a common problem in deep RL.\n3. Using RL to solve combinatorial optimization problems (e.g. graph-based problems) is not a new idea [1,2,3]. The authors should discuss more related work in this area [4,5,6].\n\n[1] Wagner, Adam Zsolt. “Constructions in combinatorics via neural networks.” ArXiv abs/2104.14516, 2021.\n\n[2] Darvariu V A, Hailes S, Musolesi M. Graph reinforcement learning for combinatorial optimization: A survey and unifying perspective[J]. arXiv preprint arXiv:2404.06492, 2024.\n\n[3] Peng Y, Choi B, Xu J. Graph learning for combinatorial optimization: a survey of state-of-the-art[J]. Data Science and Engineering, 2021.\n\n[4] Ma, Qiang, Suwen Ge, Danyang He, Darshan D. Thaker and Iddo Drori. “Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning.” ArXiv abs/1911.04936, 2019.\n\n[5] Batuhan Altundas, Zheyuan Wang, Joshua Bishop, and Matthew Gombolay. Learning Coor- dination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation.\n\n[6] Zheyuan Wang and Matthew Gombolay. Stochastic Resource Optimization over Heterogeneous Graph Neural Networks for Failure-Predictive Maintenance Scheduling.", "was_revised": true, "final_justification": "As most of my concerns have been clarified by the authors' response, I will keep my current rating.", "rebuttal": "We sincerely thank the reviewer for their detailed feedback and insightful comments. We have incorporated revisions based on this feedback.\n\n> **The proposed method has a fast inference speed, while the training time is not mentioned.**\n> **Can you discuss the time cost of training stage of TARGETNET?**\nThe training time was not mentioned as each model is trained once in the small scale and tested on a range of different scales.\n\nWe have conducted an additional evaluation on our system for learning-based baselines for over 100 epochs. We report the mean and standard deviation of time in seconds to train each model for a single epoch below:\n\n|  | **Mean Training Time (s)** | **Stdev Training Time** |\n|---|---|---|\n| **HetGAT** | 28.310 | 1.030 |\n| **Res-HetGAT** | 29.735 | 0.972 |\n| **Seq-TARGETNET/ER** | 43.628 | 1.838 |\n| **Seq-TARGETNET/R** | 66.129 | 3.395 |\n| **Seq-TARGETNET** | 61.843 | 2.028 |\n| **TARGETNET/ER** | 2.166 | 0.085 |\n| **TARGETNET/R** | 2.998 | 0.095 |\n| **TARGETNET/E** | 2.206 | 0.080 |\n| **TARGETNET** | 3.039 | 0.103 |\n\nAs seen in the training time, the training speed of different models is consistent with the inference speed. Simultaneous decision-making models of TARGETNET are faster by a factor of x20. As the models are trained on 20 task problems, the empirical results align with the theoretical complexity of $O(|A||T|^2)$ for sequential models and $O(|A||T|) for simultaneous models. The increase in the feature space size with the presence of residuals and edge attention leads to an increase in training and evaluation time.\n\nThe training time presented above also implies that it is faster to train a simultaneous TARGETNET over the existing sequential models from prior work, leading to training and deploying models within the time frame that it takes an exact solver to produce a single suboptimal solution for the extra-large scale.\n\n> **The interpretability of the proposed method is limited, which is a common problem in deep RL.**\n\nWe agree with the Reviewer that Interpretability is a common problem in both Deep RL and Optimization Problems. We further discuss it in paragraph starting in Line 329 in Section 6.\n\n> **a. Using RL to solve combinatorial optimization problems (e.g. graph-based problems) is not a new idea [1,2,3].**\n\nWe agree that there are prior works that focus on using RL to solve combinatorial optimization problems. The method presented in TARGETNET, which uses RL for both Task Allocation and Scheduling in a single forward propagation, is novel.\n\n> **Please provide more discussion on the difference in problems and methods between this paper and [4,5,6].**\n\nWe would like to thank the reviewer for referring the related work which we will discuss more in depth. We agree that contextualizing our work within the broader field of RL for Combinatorial Optimization (CO) is crucial. We have revised our related work section to better position TARGETNET and now include a detailed discussion of the suggested papers. The key distinctions are:\n\n- **[4] Ma et al., 2019:** This work proposes a hierarchical GNN for the Traveling Salesman Problem with Time Windows (TSPTW). While related, our HM-MATAS formulation addresses a more complex problem, equivalent to a multi-agent TSP variant (m-TSPTW) with additional heterogeneity constraints for agents and tasks. TARGETNET is designed to handle the joint allocation and scheduling aspects of this multi-agent, multi-task setting in a single pass, and accounts for heterogeneous task durations along with the heterogeneous travel time.\n    \n- **[5] Altundas et al. & [6] Wang and Gombolay:** The problem formulation of both [5] and [6] assumes that travel times are negligible compared to task service durations, leading to a simpler graph representation of the problem. Our framework, TARGETNET, is explicitly designed to handle scenarios where heterogeneous travel times are a critical component of the scheduling decision and may be a key factor in success. Furthermore, [5] relies on an ensemble of policies to achieve its best performance, whereas TARGETNET generates a high-quality schedule in a single forward pass. [6] focuses on a stochastic maintenance scheduling problem, leveraging the HetGAT model we benchmark against. However, the key challenge in [6] is _when_ to dispatch agents to tasks that appear over time, which differs from our deterministic generation of complete schedules in fully observable settings.\n\nWe have incorporated these comparisons into our revised manuscript.\n\n> **It is observed that the sequential decision making version of TARGETNET have better performance than the one-step version. Some prior work [7] has shown the potential to boost the performance of stateless policy by a simple distillation process, which means we can distill the sequential policy to a one-step policy by a simple behavior cloning process. Can you try this simple distillation process to boost the performance of the one-step version of TARGETNET?**\n\nThe proposed distillation is indeed a powerful technique for creating a fast and high-performance policy. However, the primary motivation for our one-step model is to demonstrate its capability to learn through Reinforcement Learning. The goal is to provide a lightweight alternative for scenarios with limited computational budgets. The distillation process, while effective, would first require training the full sequential model, thereby negating the training-time advantages that make the one-step model appealing.\n\nOur paper's focus is on analyzing the trade-off between the computationally expensive sequential approach and the efficient one-step approach. While distilling the sequential policy is an excellent direction for future work to create a fast inference model, it addresses a different research question than the one we focus on.\n\nFurthermore, the additional experiments conducted, as presented in the rebuttal for Reviewer EqLo's comments, show that simultaneous models are able to learn policies that outperform sequential models in every scale while being more robust to initial starting weights.\n\n> **The edge attention mechanism to incorporate the edge information seems to be an important contribution of this paper. However, there is a simple way to incorporate the edge information into the node attention mechanism: we can create a new node for each edge with the edge information as the node feature. This way, we can use the same node attention mechanism to incorporate the edge information. Can you discuss the difference between this simple way and the proposed edge attention mechanism? And what if the baseline method Res-HetGAT uses this simple way to incorporate the edge information?**\n\nWe thank the reviewer for their suggested feedback. While the edge features can be represented as a node feature with the addition of new nodes for each node, the added node would lead to the need for additional layers for message passing. Furthermore, the two-hop message passing for the node features would lead to added complexities and potential for information loss. Our proposed method also combines the edge and node features when updating the node features of the next layer, leveraging the linearity of attention such that $A(B || C) = A_1 B + A_2 C$, where $A = (A_1||A_2)$, for attention vectors, $A$, $A_1$ and $A_2$ and feature vectors $B$ and $C$.\n\nFor both HetGAT and HGT, the simple way of incorporating the edge features and attention would lead to increased complexity and need for additional layers, leading to increased computation time that may surpass the method proposed in our work.\n\nBased on the feedback of the reviewer, we have also improved our model, adding TARGETNETv2 into our results. TARGETNETv2 removes the softmax of attention heads in the edge feature, allowing for our model to represent models with and without edge attention by learning the attention value. This leads to a more versatile and robust model in the presence of relational information, such as heterogeneous travel times. Again, we would like to refer the reviewer to the rebuttal for Reviewer EqLo's comments for these additional results.\n \n[1] Wagner, Adam Zsolt. “Constructions in combinatorics via neural networks.” ArXiv abs/2104.14516, 2021.\n\n[2] Darvariu V A, Hailes S, Musolesi M. “Graph reinforcement learning for combinatorial optimization: A survey and unifying perspective” [J]. arXiv preprint arXiv:2404.06492, 2024.\n\n[3] Peng Y, Choi B, Xu J. “Graph learning for combinatorial optimization: a survey of state-of-the-art”[J]. Data Science and Engineering, 2021.\n\n[4] Ma, Qiang, Suwen Ge, Danyang He, Darshan D. Thaker and Iddo Drori. “Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning.” ArXiv abs/1911.04936, 2019.\n\n[5] Batuhan Altundas, Zheyuan Wang, Joshua Bishop, and Matthew Gombolay. “Learning Coordination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation.”\n\n[6] Zheyuan Wang and Matthew Gombolay. “Stochastic Resource Optimization over Heterogeneous Graph Neural Networks for Failure-Predictive Maintenance Scheduling”."}, {"review_id": "tRukUlGdnC", "reviewer": "Reviewer_nWbH", "summary": "This paper aims to improve the scalability of the solver in multi-agent task allocation and scheduling domain under constraints. The authors follow previous GNN-based methods and propose TARGETNET, which treats agents, tasks, and allocation all as nodes in a graph and relations between them as edges. In each time step, the allocation result is decided via message passing through the graph. The authors further conducted a mass of experiments against multiple baselines to show the effect of TARGETNET.", "questions": "1. Besides the agents and tasks as nodes, the authors further include $|A||T|$ assignment nodes in the graph. When encountered with extremely large scale tasks, the complexity of the graph would increase significantly. However, the experiment results show that the computation time of TARGETNET is lower than baselines. Could the authors explain why TARGETNET maintains a high efficiency?\n\n2. As shown in Figure 3 and 4, the performance of TARGETNET is severely declined after removing the residual connections. Is this indicating that the improved performance of TARGETNET is due to the residual connections rather than the graph-based learning methodology?", "limitations": "Yes but not sufficient. Please see weaknesses and questions.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "**Strengths**: \n1. The presentation of the paper is very detailed. The authors have provided various materials to illustrate the methodology and the results, including graphs, equations, pseudo-code, and videos.\n2. The authors conducted extensive experiments, employing a variety of baselines and designing multiple metrics to evaluate the performances. All these lead to convincing results.\n\n**Weaknesses**:\n1. There are some expression and grammar mistakes in the paper (e.g., line 51, 163 and 181), which should be avoided in academic writing. \n2. Overall, the performance of TARGETNET is not outstanding enough compared to the baselines. It exhibits clear superiority in the computation time, but its optimal and successful rates are inferior to MILP solver in small, medium and large scale tasks. As MILP solver is supported by solid mathematical theory, users would prefer MILP in most cases, making the application of TARGETNET limited in extremely large cases.", "was_revised": true, "final_justification": "I have updated my assessment to ``3: borderline reject''. The authors have described a well-designed framework for multi-agent task allocation, but the experiment results indicate that the key to the improved performance is the residual connection in the network rather than the edge attention proposed in Section 3.4. This gives the impression that the proposed method looks fancy in Figure 2 but lacks practical utility. During the rebuttal period, the author modified TARGETNET and proposed an improved version TARGETNETv2, which is much stronger but needs to be properly integrated into the paper with further ablation studies.", "rebuttal": "We thank the reviewer for their detailed feedback and constructive comments. We have made revisions based on the suggestions.\n\n> **There are some expression and grammar mistakes in the paper (e.g., line 51, 163 and 181), which should be avoided in academic writing.**\n\nWe have corrected the grammar mistakes mentioned and further improved our manuscript.\n\n> **Overall, the performance of TARGETNET is not outstanding enough compared to the baselines. It exhibits clear superiority in the computation time, but its optimal and successful rates are inferior to MILP solver in small, medium and large scale tasks. As MILP solver is supported by solid mathematical theory, users would prefer MILP in most cases, making the application of TARGETNET limited in extremely large cases.**\n\nWe would like to thank the reviewer for their thorough analysis of the limitations of the Machine Learning-based approaches to optimization problems.\n\nOur primary contribution is not to replace MILP in scenarios where it is feasible, but to provide a scalable solution that delivers high-quality, near-optimal schedules in a fraction of the time for problem sizes where MILP fails entirely. For instance, our experiments show that TARGETNET finds solutions orders of magnitude faster, making it practical for real-time applications where a good solution quickly is more valuable than a perfect solution that arrives too late.\n\nDeveloping fast, high-quality approximate solvers like TARGETNET is a vital research direction that can work together with exact solvers. As noted in [1, 2], such methods can provide a high-quality \"warm start\" to dramatically reduce the search space and runtime of a MILP solver. Therefore, we believe TARGETNET is not \"limited\" but rather is a significant and practical step forward for a broad and critical class of computationally challenging optimization problems.\n\nWe have also conducted additional experiments, including TARGETNET without edge attention, TARGETNET\\E, and a modification of TARGETNET with a non-normalized edge attention. The results, presented as part of the rebuttal for Reviewer EqLo's comments, show that one of the three seeds is able to converge into a policy that is within 5% of the optimal fully feasible solution on an extra-large scale. The modification of TARGETNETv2 allows a more robust model that can, on average, converge to a policy that is better than other learning based baselines, indicating a less brittle model that depends on the initial model weights. These results will be added to the camera-ready version.\n\n[1] Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: a methodological tour d’horizon. _European Journal of Operational Research_, _290_(2), 405-421.\n[2] Kruber, M., Lübbecke, M. E., & Parmentier, A. (2017, May). Learning when to use a decomposition. In _International conference on AI and OR techniques in constraint programming for combinatorial optimization problems_ (pp. 202-210). Cham: Springer International Publishing.\n\n> **Besides the agents and tasks as nodes, the authors further include |A||T| assignment nodes in the graph. When encountered with extremely large scale tasks, the complexity of the graph would increase significantly. However, the experiment results show that the computation time of TARGETNET is lower than baselines. Could the authors explain why TARGETNET maintains a high efficiency?**\n\nTARGETNET only constructs a single graph representation of the world, including the heterogenous travel time from one task to another task for each agent, which is represented as an edge between the Assignment Nodes, with a complexity of $O(|A||T|^2)$ number of edges due to the limitation of per agent travel.\n\nUnlike baselines that still require the simulation of the agent movement to new location to update agent makespan and when they would be available to move to the next task location, the simultaneous nature of TARGETNET allow for the generation of the entire schedule without needing to interact with the environment, relying on the initial state observation, $s_0$, to generate a full schedule.\n\nFurthermore, TARGETNET scales polynomially with the number of agents and tasks while the problem itself is NP-hard. This is one of the key advantages of learning-based models, as they can learn potential heuristics that outperform existing methods.\n\n> **As shown in Figure 3 and 4, the performance of TARGETNET is severely declined after removing the residual connections. Is this indicating that the improved performance of TARGETNET is due to the residual connections rather than the graph-based learning methodology?**\n\nWe would like to refer the Reviewer to the rebuttal to the feedback of Reviewer EqLo for additional experiments for our model without edge attention, TARGETNET\\E. We agree with the reviewer that the performance of the Graph Models has a significant increase in the performance with the addition of Residual Connections, and the presence of the Edge Features makes the model less brittle, capable of learning a better mean performance across 3 different seeds (10, 11, 12).\n\nFurthermore, our additional experiments with TARGETNETv2 that allow a non-normalized edge attention encapsulate the policies that can be learned by TARGETNET\\E, as they are able to learn the same policies. This makes the addition of Edge Attention lead to a more robust model that can learn a wide range of policies that models without edge attention are not able to represent.\n\nWe are currently running the training and evaluation of the Sequential variant of the model without edge features, Seq-TARGETNET\\E. Due to the slower nature of the model, we will provide these results in the camera-ready version of our work along with a detailed discussion."}]

Author rebuttal:

Meta-review: The paper studies the use of Graph Transformers and RL for certain classes of combinatorial optimization problems. The problem, of finding polynomial time approximately optimal solutions for large-scale combinatorial optimization, is very well-motivated and significant. The proposed solution, TargetNet, is a novel synthesis of techniques from different ML areas. Experiments show that TargetNet is effective in solving several combinatorial problems, with time taken orders of magnitude faster than previous GNN baselines.

Reviewers provided constructive feedback which the authors incorporated during the discussion phase. An important outcome from the additional ablations is that the authors identified a variant, TargetNetv2, that was less brittle than TargetNet across the various problems tested in the experiments. Most of the reviewers agreed that the paper (with the inclusion of TargetNetv2) is above the bar for publication; the only dissent/concern was that including TargetNetv2 in the paper will require all ablations to be re-run with TargetNetv2 as the base, to check if the authors conclusions about the utility of different components of TargetNet remain true of TargetNetv2.
Decision: Accept (poster)