# Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints

arXiv: https://arxiv.org/abs/2005.13109 · HTML: https://mlsanity.com/paper/2005.13109/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2020.

## Built on by (most cited first, 9 of 9)

- [DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments](https://mlsanity.com/paper/2209.02865/) (2022)
- [DeepFleet: Multi-Agent Foundation Models for Mobile Robots](https://mlsanity.com/paper/2508.08574/) (2025)
- [Learning Performance Graphs from Demonstrations via Task-Based Evaluations](https://mlsanity.com/paper/2204.05909/) (2022)
- [Graph Attention Multi-Agent Fleet Autonomy for Advanced Air Mobility](https://mlsanity.com/paper/2302.07337/) (2023)
- [Task Allocation using a Team of Robots](https://mlsanity.com/paper/2207.09650/) (2022)
- [A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation](https://mlsanity.com/paper/2407.00496/) (2024)
- [SPACE: A Python-based Simulator for Evaluating Decentralized Multi-Robot Task Allocation Algorithms](https://mlsanity.com/paper/2409.04230/) (2024)
- [ARMATA: Auto-Regressive Multi-Agent Task Assignment](https://mlsanity.com/paper/2605.04225/) (2026)
- [Reinforcement Learning Based Heterogeneous Task Allocation Under Spatio-Temporal Environmental Uncertainty for Multi-Robot Teams](https://mlsanity.com/paper/2610.15237/) (2026)

## Abstract (arXiv)

We consider the problem of dynamically allocating tasks to multiple agents under time window constraints and task completion uncertainty. Our objective is to minimize the number of unsuccessful tasks at the end of the operation horizon. We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination and addresses them in a hierarchical manner. The lower layer computes policies for individual agents using dynamic programming with tree search, and the upper layer resolves conflicts in individual plans to obtain a valid multi-agent allocation. Our algorithm, Stochastic Conflict-Based Allocation (SCoBA), is optimal in expectation and complete under some reasonable assumptions. In practice, SCoBA is computationally efficient enough to interleave planning and execution online. On the metric of successful task completion, SCoBA consistently outperforms a number of baseline methods and shows strong competitive performance against an oracle with complete lookahead. It also scales well with the number of tasks and agents. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.