DISPATCH: Decentralized Informed Spatial Planning and Assignment of Tasks for Cooperative Heterogeneous Agents

1Department of EECS, University of California, Berkeley    2Department of Computer Science, University of Southern California
Facility floor plan with heterogeneous robots, weighted task stations, and a skill-compatibility matrix

Problem setting. (a) Heterogeneous robots navigate around racks and walls to weighted task stations \(S_j\); each robot senses entities within a limited radius \(r\), and workloads decrease during service. (b) Skill compatibility \(\phi_{ji}\), task weights \(w_j\), and workloads \(L_j\); outlined cells mark the fairness-aware assignment.

We train decentralized, graph-based robot policies using an exact, fairness-aware assignment as a teacher. During execution the robots do not have access to the assignment solver. Even so, they complete every task for teams of 3 to 15 robots, and their completion time and fairness show no statistically significant difference from the centralized teacher.

Abstract

Heterogeneous robot teams must coordinate spatial task service from local observations while balancing efficiency and fairness. We study a one-to-one setting with \(N\) agents and \(N\) weighted tasks, where agent–task utility combines skill compatibility with travel distance, and ask how a centralized fairness-aware assignment teacher can guide decentralized learning of task-directed navigation.

We introduce EG-MARL, a centralized-training decentralized-execution (CTDE) framework whose teacher is an Eisenberg–Gale (EG)-inspired weighted log-welfare assignment, solved exactly as a maximum-weight bipartite matching. Teacher-assigned tasks guide training through task-specific rewards. The learned actors use graph-based observations and message passing to select task-directed motion without querying the assignment solver during execution.

We evaluate EG-MARL in Multi-Agent Particle Environment (MPE) simulations for \(N = 3, 7, 10, 15\) against centralized log-welfare, minimum-completion-time (Min-Time), min–max-distance, and full-communication online references. Under the main evaluation settings, learned execution completes all tasks in every evaluated episode, with log-welfare regret growing from 0.07 to 0.22 and attributable to extra travel. We find no statistically significant differences in completion time or fairness between learned execution and the centralized teacher. On the teacher-aligned fairness metric, EG-MARL is fairer than Min-Time and min–max-distance assignments at larger team sizes; Min-Time is faster but less fair.

Decentralized Execution

Learned EG-MARL policies acting on saved evaluation scenarios in MPE for team sizes 3–15. Each robot picks its own action from local observations and its graph. The centralized solver is never queried.

\(N = 3\), all tasks completed in 2.7 s

\(N = 7\), all tasks completed in 2.7 s

\(N = 10\), all tasks completed in 2.6 s

\(N = 15\), all tasks completed in 3.0 s

Each colored disk is a robot, and its dashed trail is beaded every 0.3 s. The dotted circle around it marks its sensing radius \(r_o = 0.3\). Squares are task stations, sized by task weight \(w_j\), and they fill in gray as their workload is serviced. Dashed lines connect each robot to the task the teacher assigned it. That assignment is used only to shape rewards during training and is never part of the robot's observation. For each team size, the episode shown is a completed evaluation scenario whose log-welfare regret is closest to the median. Playback is about 0.3× real time.

Method

DISPATCH studies how a centralized, fairness-aware assignment can teach a team of heterogeneous robots to coordinate when, at execution time, each robot only sees its local surroundings. Our approach, EG-MARL, follows the centralized-training, decentralized-execution paradigm: an exact assignment solver is available during training, but the deployed policies never call it.

A spatially aware log-welfare teacher

The utility of agent \(i\) serving task \(j\) is \(u_{ji} = \alpha^{d_{ij}}\phi_{ji}\), where \(\phi_{ji}\) is skill compatibility, \(d_{ij}\) is travel distance, and \(\alpha \in (0,1)\) discounts longer trips. Following the form of the Eisenberg–Gale program, the teacher selects the one-to-one assignment that maximizes priority-weighted log welfare,

\[ \max_{x\in\{0,1\}^{N\times N}} \; \sum_{j\in\mathcal{T}} w_j \log\Big(\sum_{i\in\mathcal{A}} u_{ji}\,x_{ji}\Big), \]

subject to every agent and every task being matched exactly once. Because each feasible assignment is a permutation, the problem reduces exactly to a maximum-weight bipartite matching with scores \(w_j \log u_{ji}\), which the Hungarian algorithm solves to global optimality in \(O(N^3)\). The resulting assignment is Pareto-efficient and maximizes the weighted geometric mean of task utilities, so allocations that leave any high-priority task poorly served are strongly penalized. Having an exact optimum also lets us measure the regret of learned execution precisely.

Learning from the teacher

At the start of each training episode the teacher assigns every agent a target task \(g_i\). This target enters only through the reward: agents are rewarded for approaching and servicing their assigned task, \(r^{(i)}_{\text{fair}} = -\lVert p_i - g_i\rVert + \mathbb{1}\{\text{arrive}\}R_{\text{arr}}\), together with terms for workload progress, task completion, early task discovery, and collision avoidance. The target is never written into an agent's observation or graph, so at test time each agent must infer which task to serve on its own.

Decentralized graph-based execution

Following InforMARL, each agent builds a local graph over nearby agents, tasks, obstacles, and walls, and aggregates it with three graph-transformer (UniMP) layers before a recurrent MAPPO actor. Agents sense tasks within an observation radius \(r_o\) and exchange the set of discovered tasks with teammates within a communication radius \(r_c\). A centralized critic is used during training only.

As a point of comparison we also introduce EG-Online, a full-communication reference that alternates cooperative stochastic exploration with EG assignment over the tasks discovered so far.

Results

We evaluate in the Multi-Agent Particle Environment on 100 scenarios per team size and compare against the centralized teacher (EG-Centralized), the full-communication online reference (EG-Online), an efficiency-only Hungarian assignment that minimizes estimated completion time (Min-Time), and a min–max-distance assignment (Min–Max).

Fairness and efficiency vs team size

Fairness (normalized Jain \(\tilde J\), ↑) and completion time (↓) vs. team size. EG-MARL tracks the centralized oracle; Min-Time is fastest but loses fairness as \(N\) grows. Bands: 95% CIs.

Fairness-efficiency trade-off per team size

Fairness–efficiency plane at each \(N\). EG-MARL (blue) sits on top of EG-Centralized (green ring) in the upper-left.

Main comparison (mean ± SD over 100 episodes)

MethodTime \(T\) (s) ↓Distance \(D\) ↓\(F(\rho)\) ↑Jain \(J(\rho)\) ↑

Log-welfare regret ↓

MethodN=3N=7N=10N=15
EG-MARL0.07 ± 0.110.10 ± 0.070.15 ± 0.080.22 ± 0.10
EG-Online0.84 ± 1.050.98 ± 0.752.67 ± 15.494.56 ± 15.25

EG-MARL's remaining regret is due to extra travel; EG-Online pays for discovery and occasional timeouts.

Observation-radius sweep (success %)

\(N\)\(r_o\)=0.10.20.30.5
7919810094
10969710094
15919510095

Frozen policies (trained at \(r_o\)=0.5, \(r_c\)=0.75), \(r_c\)=0.45. Jain fairness varies by ≤ 0.010 across radii.

Across all team sizes, paired tests on shared scenarios (Holm-corrected over 24 comparisons) find no significant difference between EG-MARL and the centralized teacher in completion time or Jain fairness; the mean paired difference in Jain's index is below \(10^{-3}\) at every \(N\). Non-significance does not establish equivalence, but it is consistent with the learned policies reproducing the teacher's assignments on unseen scenarios.

Relative to the baselines, EG-MARL is fairer than Min-Time at \(N = 7, 10, 15\), although Min-Time completes faster at the two largest team sizes, and it improves on Min–Max in both fairness and completion time at every team size. In a 7-agent ablation, replacing the teacher-guided reward with a Simple-Spread coverage reward increases both completion time (3.62 s vs. 2.75 s) and travel distance, while removing the exploration bonus leaves efficiency unchanged and slightly lowers fairness.

BibTeX

@article{liu2025dispatch,
  title   = {{DISPATCH} -- Decentralized Informed Spatial Planning and Assignment of Tasks for Cooperative Heterogeneous Agents},
  author  = {Liu, Yao and Mohanty, Sampad and Ondula, Elizabeth and Krishnamachari, Bhaskar},
  journal = {arXiv preprint arXiv:2511.17915},
  year    = {2025}
}