Reinforcement Learning Based Heterogeneous Task Allocation Under Spatio-Temporal Environmental Uncertainty for Multi-Robot Teams

Xi Lin; Yaxuan Li; Paul Szenher; Brendan Englot

cs.ROOct 11, 2026

Reinforcement Learning Based Heterogeneous Task Allocation Under Spatio-Temporal Environmental Uncertainty for Multi-Robot Teams

Authors: Xi Lin, Yaxuan Li, Paul Szenher, Brendan Englot

Organizations: Department of Mechanical Engineering, Stevens Institute of Technology, 1 Castle Point Terrace, Hoboken, NJ 07030, USA

Abstract

Autonomous Surface Vehicles (ASVs) have been increasingly deployed to perform different kinds of maritime tasks in recent years, which motivates the need for a reliable task allocation policy that can adapt to heterogeneous tasks and maritime disturbances. In this work, we formulate a multi-robot task allocation problem in which a team of ASVs with heterogeneous capabilities needs to complete tasks of different types and appearance times under unknown stochastic spatio-temporal uncertainties from maritime disturbances. We propose a decentralized Reinforcement Learning (RL) based policy network that is trained to be robust towards uncertainty-induced observation deviations, and is able to perform individual decision making that leads to efficient execution behaviors toward heterogeneous task requirements. We evaluate the proposed policy and four baseline methods in simulated experiments with varied proportions of different tasks types, numbers of tasks, robot species and robots per species. Experiment results show that our proposed policy achieves the lowest makespan and can be deployed to address scenarios with 100 robots and 400 tasks.

Figures & tables

Fig. 1 : Our task allocation problem. The base station of each robot species is marked by a pink square. The capability vectors of robot species and the capability requirements of tasks are shown as color palettes in pink squares and next to robot and task icons, where each color represents a specific capability. Gray, lime and cyan arrows indicate the task location which the robot is en-route to executing, transporting items towards, and ready for (or under) execution, respectively. Background colors, from blue (low) to red (high), show local uncertainty levels that are unknown to robots. White contour lines indicate locations with the same uncertainties.

Fig. 2 : Policy network architecture. Observations of robots and tasks are passed through corresponding gated encoders to obtain robust embedded features. Then a self-attention module and a cross-attention module are used to fuse the ego robot feature with that of other robots and tasks to obtain a comprehensive understanding. The policy outputs a probability vector that reflects the attentions of the ego robot on all available tasks.

Panel of Figure 3 — Fig. 3 : Examples of initial scenes in experiment episodes. The capability requirements of active tasks at the current moment are shown as color palettes, while hexagons and pentagons with lime colors indicate the start and goal locations of transportation tasks. Markers for tasks that have not yet appeared are the same as those in Fig. 1 .

range of $m$	$[75,150]$	learning rate	$1e-5$
range of $n$	$[3,5]$	batch size	$1024$
range of $k$	$[4,6]$	eval ep num	$256$
max ep time	200	total ep num	5000

TABLE I : Training hyperparameters .

Fig. 4 : Training performance. The solid line and bandwidth represent the mean and standard deviation of evaluation results over ten models from ten different training trials.

$m$	50	100	200	200	400	400
$n$	3	4	4	6	7	10
$k$	4	5	8	8	10	10
RL (Ours)	75.92	94.72	109.50	82.10	109.26	87.25
	$\bf\pm 22.45$	$\bf\pm 30.29$	$\bf\pm 28.40$	$\bf\pm 18.59$	$\bf\pm 32.39$	$\bf\pm 25.05$
HBTA	101.78	119.54	129.20	96.38	121.33	91.44
	$\pm 40.44$	$\pm 39.43$	$\pm 31.49$	$\pm 26.12$	$\pm 36.83$	$\pm 24.72$

TABLE II : Makespan data in experiments . Each entry shows the mean and standard deviation of results from 100 experiments.

Explore similar work

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
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
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

Aug 21, 2026J/K move · Enter open · S save

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

Daniel Garces, Sara Castro, Adrian Haimovich, Byron Crowe+1

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

Multi-Robot Task Allocation Robotics Model-Based RL

Open paper AskPDF arXiv

Heterogeneous multi-robot service systems must assign requests to compatible robots, construct feasible schedules, and adapt as new tasks arrive online. Historical data can help anticipate future demand, but relying too heavily on inaccurate predictions can degrade performance under distribution shifts. We develop a prediction-aware adaptive rollout framework for heterogeneous multi-robot task assignment with scheduled and real-time requests. The problem is formulated as a finite-horizon stochastic dynamic program incorporating robot-task compatibility, ordered service requirements, routing constraints, service windows, and end-of-horizon return requirements. The proposed policy evaluates current assignments using sampled future request scenarios while restricting immediate commitments to requests already observed. To enable online use, the framework combines pruned candidate controls, wait actions, and an interaction-aware base policy for efficient future-cost estimation. Robustness to forecast error is provided by adaptively reweighting predicted requests based on recent prediction mismatch and selectively re-optimizing assigned but unstarted requests. We also introduce a historical-data-driven procedure for selecting the heterogeneous fleet composition before deployment. In a case study using real nursing-task requests from hospital inpatient floors, the proposed approach achieves near-complete service and reduces serviced-request wait times relative to reactive, token-passing, prediction-positioning, and myopic greedy baselines, with the largest improvements in tail-delay metrics.

Abstract

Explore similar work

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

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

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