Coordination of Heterogeneous Teams with Uncertain Task Requirements
Organizations: University of Illinois Urbana-Champaign, Urbana, IL, USA, 61801
Abstract
Coordinating a team of heterogeneous agents to complete tasks with unknown requirements is a challenging multi-agent planning problem. Agents differ in their ability to discover task requirements and in their ability to engage tasks, so the planner must coordinate task discovery, execution, and staging. This paper introduces a hierarchical planner that uses a graph neural network policy to assign actions to agents, then finds a path to the action's location using a shortest-path algorithm. The central part of our approach is the CAAT graph, which is a graph representation of the planning context consisting of the agents, tasks, capabilities, and actions. We demonstrate that our learned planner can jointly coordinate a heterogeneous team to simultaneously discover task requirements and complete tasks in a shorter time compared to baselines that optimize task discovery and task engagement independently. Furthermore, we show that our policy can zero-shot plan on out-of-distribution settings by training only on an outdoor map then transferring without finetuning to an indoor map with more agents, tasks, and capabilities than seen during training.
Figures & tables
| Map | Default | Dot-product score | Max normalization | No position | Single-task staging | Single-task staging + No position | No staging |
|---|---|---|---|---|---|---|---|
| WV | 1.43 | 1.65 | 1.42 | 1.51 | 1.63 | 1.46 | 1.74 |
| WA | 1.37 | 1.59 | 1.40 | 1.51 | 1.57 | 1.38 | 1.68 |
| KTH | 1.90 | 2.99 | 1.96 | 2.11 | 2.10 | 2.08 | 2.19 |
| Edge type | Neighbor weight | Message from |
|---|---|---|
| Travel Time | ||
| Task Semantic | ||
| Capability–Agent | ||
| Capability–Task |
| Component | Specification |
|---|---|
| Hidden node dimension | |
| Message-passing layers | |
| Attention heads | per attention relation; |
| Agent input encoder | |
| Task input encoder | |
| Action input encoder |
| Parameter | Value |
|---|---|
| Optimizer | Adam |
| Learning rate | |
| Episodes per optimizer update | |
| Number of simultaneous simulations | |
| Entropy coefficient | |
| EMA baseline decay |
| Agent profile | Design |
|---|---|
| Specialist | Agents with few capabilities. |
| Balanced hybrid | Agents with 2–3 capabilities, including hybrid scouts that can both observe and execute tasks. |
| Scout redundant | Approximately half the agents have , more than the other profiles which have . |
| Task profile | Design |
|---|---|
| Balanced | Spatially dispersed tasks with approximately balanced requirement counts. |
| Skewed | Spatially dispersed tasks with requirements dominated by one capability on WV and WA, and two on KTH. |
| Clustered | Tasks concentrated in multiple spatial clusters, with balanced requirements. |
| Agents | Tasks | Scout then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| 3 | 5 | |||
| 6 | ||||
| 7 | ||||
| 8 | ||||
| 9 | ||||
| 4 | 5 |
| Agents | Tasks | Scout Then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| 3 | 5 | |||
| 6 | ||||
| 7 | ||||
| 8 | ||||
| 9 | ||||
| 4 | 5 |
| Agents | Tasks | Scout Then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| 8 | 14 |
| Agent profile | Task profile | Scout Then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| Specialist | Balanced | |||
| Skewed | ||||
| Clustered | ||||
| Balanced hybrid | Balanced | |||
| Skewed | ||||
| Clustered |
| Agent profile | Task profile | Scout Then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| Specialist | Balanced | |||
| Skewed | ||||
| Clustered | ||||
| Balanced hybrid | Balanced | |||
| Skewed | ||||
| Clustered |
| Agent profile | Task profile | Scout Then Engage | Engage While Scout | CAAT Graph + HGT |
|---|---|---|---|---|
| Specialist | Balanced | |||
| Skewed | ||||
| Clustered | ||||
| Balanced hybrid | Balanced | |||
| Skewed | ||||
| Clustered |
Multi-Agent Planning
Multi-Agent Planning coordinates multiple decision-makers to assign tasks, plan actions and paths, and resolve conflicts under shared constraints.
See all 129 papers