Multi-Robot Multi-Queue Control via Exhaustive Assignment Actor-Critic Learning

Mohammad Merati; H. M. Sabbir Ahmad; Wenchao Li; David Castañón

eess.SYApr 4, 2026

Multi-Robot Multi-Queue Control via Exhaustive Assignment Actor-Critic Learning

Authors: Mohammad Merati, H. M. Sabbir Ahmad, Wenchao Li, David Castañón

Organizations: Divisions of Systems Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States. · Department of Electrical and Computer Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States.

Abstract

We study online task allocation for multi-robot, multi-queue systems with asymmetric stochastic arrivals and switching delays. We formulate the problem in discrete time: each location can host at most one robot per slot, servicing a task consumes one slot, switching between locations incurs a one-slot travel delay, and arrivals at locations are independent Bernoulli processes with heterogeneous rates. Building on our previous structural result that optimal policies are of exhaustive type, we formulate a discounted-cost Markov decision process and develop an exhaustive-assignment actor-critic policy architecture that enforces exhaustive service by construction and learns only the next-queue allocation for idle robots. Unlike the exhaustive-serve-longest (ESL) queue rule, whose optimality is known only under symmetry, the proposed policy adapts to asymmetry in arrival rates. Across different server-location ratios, loads, and asymmetric arrival profiles, the proposed policy consistently achieves lower discounted holding cost and smaller mean queue length than the ESL baseline, while remaining near-optimal on instances where an optimal benchmark is available. These results show that structure-aware actor-critic methods provide an effective approach for real-time multi-robot scheduling.

Figures & tables

Fig. 1 : Block diagram of the proposed EA-AC architecture. The policy network encodes robot and queue states, models robot-queue interactions, and generates sequential assignment decisions for idle robots. The critic network uses centralized state information to estimate the value function during training.

Scenario	$(M,N)$	Policy	Discounted Cost ( $\downarrow$ )	Mean Queue Length ( $\downarrow$ )	Cost Red. (%) ( $\uparrow$ )	Queue Red. (%) ( $\uparrow$ )
S1	$(1,3)$	ESL	$410.51\pm 8.67$	$1.6133\pm 0.0214$	–	–
S1	$(1,3)$	EA-AC	$\mathbf{405.99\pm 8.64}$	$\mathbf{1.5905\pm 0.0211}$	$\mathbf{1.10}$	$\mathbf{1.41}$
S2	$(6,24)$	ESL	$1521.64\pm 14.44$	$0.6927\pm 0.0035$	–	–
S2	$(6,24)$	EA-AC	$\mathbf{1432.86\pm 13.80}$	$\mathbf{0.6381\pm 0.0033}$	$\mathbf{5.83}$	$\mathbf{7.88}$
S3	$(12,60)$	ESL	$3757.98\pm 24.87$	$0.7047\pm 0.0024$	–	–
S3	$(12,60)$	EA-AC	$\mathbf{3451.51\pm 26.29}$	$\mathbf{0.6362\pm 0.0026}$	$\mathbf{8.16}$	$\mathbf{9.71}$

TABLE I : Performance comparison between ESL and EA-AC across asymmetric scenarios. Values are reported as mean

\pm

95% CI half-width. Best values in each scenario are shown in bold. Improvement is computed relative to ESL.

Fig. 2 : Distribution of arrival rates across the six asymmetric scenarios. Each bar indicates the number of queues whose arrival rate falls at a given value on the $0.05$ grid.

Fig. 3 : Empirical convergence scaling of the proposed EA-AC policy with respect to the number of robots. Over the tested scenarios, the number of training iterations required for convergence grows approximately linearly with system size.

Scenario	$(M,N)$	Arrival rates $p$	Policy	Discounted Cost ( $\downarrow$ )	Mean Queue Length ( $\downarrow$ )
S1	$(1,3)$	$[0.10,\ 0.25,\ 0.45]$	Optimal	$\mathbf{405.8574\pm 8.68}$	$\mathbf{1.5895\pm 0.0211}$
S1	$(1,3)$	$[0.10,\ 0.25,\ 0.45]$	EA-AC	$405.9872\pm 8.64$	$1.5905\pm 0.0211$
S2	$(1,4)$	$[0.05,\ 0.10,\ 0.25,\ 0.30]$	Optimal	$\mathbf{322.3632\pm 6.27}$	$\mathbf{0.8875\pm 0.0102}$
S2	$(1,4)$	$[0.05,\ 0.10,\ 0.25,\ 0.30]$	EA-AC	$322.5075\pm 6.27$	$0.8877\pm 0.0101$
S3	$(2,4)$	$[0.15,\ 0.25,\ 0.50,\ 0.60]$	Optimal	$\mathbf{397.0253\pm 5.15}$	$\mathbf{1.0320\pm 0.0065}$
S3	$(2,4)$	$[0.15,\ 0.25,\ 0.50,\ 0.60]$	EA-AC	$399.4329\pm 5.12$	$1.0380\pm 0.0066$

TABLE II : Comparison of the proposed EA-AC policy with optimal benchmarks. For S1–S3, the reference policy is the exact optimal policy; for S4–S5, it is the ESL policy, which is optimal under symmetry.

Robot location embedding dimension	16
Actor hidden width $d$	128
Critic hidden width $d$	128
Actor queue encoder	2-layer MLP
Actor robot encoder	2-layer MLP
Actor assignment scorer	scaled dot-product $+\;$ queue bias
Actor masking	occupancy and reservation masks

TABLE III : Architecture summary of the proposed EA-AC policy and value networks.

Fig. 4 : Supplementary comparison of mean queue length for EA-AC and ESL across multiple robot–queue configurations. Each panel corresponds to a fixed number of robots, and the three bars within each panel show performance at different queue counts.

Explore similar work

FORMICA: Decision-Focused Learning for Communication-Free Multi-Robot Task Allocation
Feb 20, 2026Antonio Lopez, Jack Muirhead, Carlo PinciroliMulti-Robot Task Allocation Multi-Agent Systems
Dept. of Robotics Engineering, Worcester Polytechnic Institute, Worcester MA 01609, USA
Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach
Apr 13, 2026Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson +1Multi-Robot Task Allocation Multi-Agent Systems
Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA, United States · Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, United States · Thayer School of Engineering, Dartmouth College, Hanover, NH, United States
Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts
Aug 21, 2026Daniel Garces, Sara Castro, Adrian Haimovich +2Multi-Robot Task Allocation Robotics
John A. Paulson School Of Engineering And Applied Sciences, Harvard University, 150 Western Avenue, Boston, 02134, MA, USA · Harvard Medical School, 77 Avenue Louis Pasteur, Boston, 02215, MA, USA · Beth Israel Deaconess Medical Center, 330 Brookline Avenue, Boston, 02215, MA, USA +1

Feb 20, 2026J/K move · Enter open · S save

FORMICA: Decision-Focused Learning for Communication-Free Multi-Robot Task Allocation

Antonio Lopez, Jack Muirhead, Carlo Pinciroli

Dept. of Robotics Engineering, Worcester Polytechnic Institute, Worcester MA 01609, USA

Multi-Robot Task Allocation Multi-Agent Systems Decision-Focused Learning

Open paper AskPDF arXiv

Most multi-robot task allocation methods rely on communication to resolve conflicts and reach consistent assignments. In environments with limited bandwidth, degraded infrastructure, or adversarial interference, existing approaches degrade sharply. We introduce a learning-based framework that achieves high-quality task allocation without any robot-to-robot communication. The key idea is that robots coordinate implicitly by predicting teammates' bids: if each robot can anticipate competition for a task, it can adjust its choices accordingly. Our method predicts bid distributions to correct systematic errors in analytical mean-field approximations. While analytical predictions assume idealized conditions (uniform distributions, known bid functions), our learned approach adapts to task clustering and spatial heterogeneity. Inspired by Smart Predict-then-Optimize (SPO), we train predictors end-to-end to minimize Task Allocation Regret rather than prediction error. To scale to large swarms, we develop a mean-field approximation where each robot predicts the distribution of competing bids rather than individual bids, reducing complexity from

O(NT)

O(T)

. We call our approach FORMICA: Field-Oriented Regret-Minimizing Implicit Coordination Algorithm. Experiments show FORMICA substantially outperforms a natural analytical baseline. In scenarios with 16 robots and 64 tasks, our approach improves system reward by 17% and approaches the optimal MILP solution. When deployed on larger scenarios (256 robots, 4096 tasks), the same model improves performance by 7%, demonstrating strong generalization. Training requires only 21 seconds on a laptop, enabling rapid adaptation to new environments.

Abstract

Explore similar work

FORMICA: Decision-Focused Learning for Communication-Free Multi-Robot Task Allocation

Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts