Heterogeneous Graph Transformers for Simultaneous Mobile Multi-Robot Task Allocation and Scheduling under Temporal Constraints¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

TARGETNET is a Residual Heterogeneous Graph Transformer (HGT) that jointly solves multi-agent task allocation and scheduling (MATAS) in a single forward pass, encoding heterogeneous travel times, agent capabilities, time-window constraints, and order dependencies into a rich graph structure trained via REINFORCE. Trained on 10-agent/20-task problems, it generalizes zero-shot to 40-agent/200-task scenarios, outperforming classical solvers by 231.73% in feasible task completion at 0.03% of the compute time.

Problem¶

Existing MATAS solvers—MILP exact solvers, metaheuristics (Genetic Algorithms), and sequential GNN policies—fail to jointly handle (1) heterogeneous agent travel times/execution times, (2) time-window and order precedence constraints, and (3) scalability from small to large fleets without retraining. Sequential GNN approaches like HetGAT incur O(|A||T|³) complexity and require repeated environment interaction; exact solvers time out at large scale (12 hours for 40 agents/200 tasks with only partial solutions returned).

Method¶

Graph encoding: The problem is cast as a heterogeneous graph G = (V, E) with five node types—Agent, Task, Assignment (one per agent-task pair, total O(|A||T|)), global State, and Task Order—and typed edges encoding travel times between all pairs (O(|A||T|²) assignment-to-assignment edges).

Edge-augmented HGT: Standard HGTs lack native edge-feature support. TARGETNET augments each message-passing step with separate edge attention (AttE) and edge messages (MsgE) that update both target node features and edge features simultaneously (Eqs. 2–5). Multi-head attention omits the inter-head softmax to allow selective zeroing of edge/node contributions.

Residual connections: Graph-raw residuals append initial node/edge features at every layer to mitigate vanishing gradients.

Simultaneous decision making: A single forward pass produces (a) a |A|×|T| assignment matrix from Assignment node outputs, and (b) task ordering from Task Order node outputs—no iterative re-querying of the environment. Training uses REINFORCE with discounted reward combining dense per-step feasibility signals and sparse final makespan-optimality reward (Eq. 1).

Key Contributions¶

HM-MATAS formulation unifying heterogeneous travel times, agent capabilities, time-window and order-precedence constraints into a single MILP/MDP framework.
TARGETNET — simultaneous one-shot allocation + scheduling via edge-feature-augmented Residual HGT, reducing inference complexity from O(|A||T|³) to O(|A||T|²).
Edge-attention mechanism that integrates relational (edge-level) information into HGT message passing without breaking the heterogeneous attention structure.
Cross-scale generalization: train on 10 agents/20 tasks, deploy on 40 agents/200 tasks with no retraining.

Results¶

vs. CA-EDF heuristic (small scale, 10a/20t): +13.27% feasible assignments, sub-0.20 s inference (only model besides heuristics achieving sub-second scheduling).
vs. best metaheuristic (Gen-EDF, small scale): +13.26% better schedule quality in 0.73% of compute time.
vs. HetGAT (small scale): +36.35% feasible assignments in 4.75% of compute time.
vs. MILP exact solver (extra-large, 40a/200t): +70.80% more feasible tasks; MILP returns only partial schedules after 12 hours; TARGETNET runs in <12 seconds.
vs. sequential GNN baselines (extra-large): +47.05% feasible tasks vs. HetGAT; 538.56× faster than sequential graph models; 20×–250× speedup across scales.
Training speed: up to 20× faster per episode than sequential methods.
Ablation: removing edge features (TARGETNET\E) degrades mean performance 16.91%–34.75% across scales; removing residuals further reduces robustness across seeds.

Limitations¶

Precomputed static motion plans (Rapidly-exploring Random Graph) do not account for dynamic environments or agent-agent collision avoidance; runtime obstacles invalidate schedules.
No joint multi-agent path-finding during execution.
Graph-based policy is not inherently interpretable; learned attention weights are not human-auditable, which is problematic for safety-critical deployments.
Extra-large test set is small (10 problems), limiting statistical confidence at that scale.
Simultaneous model underperforms sequential models at large scales in optimality rate (sequential models re-optimize per step); authors propose a hybrid as future work but do not evaluate it.

Relevance to Agentic AI / LLM Agents¶

While TARGETNET operates on robotic/physical agents rather than LLM-based agents, it directly addresses the core agentic problem of coordinating heterogeneous agents across long-horizon tasks with complex temporal dependencies—the same structural challenge faced by multi-agent LLM orchestration frameworks (task decomposition, agent assignment, scheduling under deadlines). The one-shot simultaneous planning approach is architecturally relevant to LLM agent planners that must produce full execution plans without iterative environment queries, and the HGT-with-edge-attention design offers a blueprint for encoding rich relational metadata (tool capabilities, API latencies, context dependencies) in multi-agent LLM coordination graphs. The generalization from small to large problem instances without retraining parallels the scaling challenge in LLM agent fleets where plan structures must transfer across task complexities.