cs.MANov 16, 2026

Coordination of Heterogeneous Teams with Uncertain Task Requirements

Authors: Jongann Lee, Melkior Ornik

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

Explore similar work

CardsList
  1. Discovery-Probability Graph Planning for Embodied Agents in Tasks with Hidden Cooperation Requirements

    Oct 19, 2026Zihuang Cai, Changjian Chen, Zhuo Tang +2Multi-Agent PlanningGraph-Based Planning

  2. Shared-Roadmap Generation and Evaluator for Multi-Agent Path Planning Using Heterogeneous Graph Neural Network

    Oct 6, 2026Brandon Ho, Nikola Rogers, Seung-Kyum ChoiMulti-Agent PlanningMulti-Agent Path Finding

  3. Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO

    Apr 1, 2026Matthias Rubio, Julia Richter, Hendrik Kolvenbach +1Multi-Robot Task AllocationMulti-Robot Motion Planning