# Robust Task Scheduling for Heterogeneous Robot Teams under Capability Uncertainty

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2021.

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

- [Decentralized Reinforcement Learning for Multi-Agent Multi-Resource Allocation via Dynamic Cluster Agreements](https://mlsanity.com/paper/2503.02437/) (2025)
- [Partner Capability Estimation for Task-Agnostic Adaptation in Ad-Hoc Teamwork](https://mlsanity.com/paper/2607.27177/) (2026)
- [Scalable Hierarchical Reinforcement Learning for Hyper Scale Multi-Robot Task Planning](https://mlsanity.com/paper/2412.19538/) (2024)
- [Pro-Routing: Proactive Routing of Autonomous Multi-Capacity Robots for Pickup-and-Delivery Tasks](https://mlsanity.com/paper/2503.24325/) (2025)
- [DC-Ada: Reward-Only Decentralized Sensor Adaptation for Heterogeneous Multi-Robot Teams](https://mlsanity.com/paper/2604.03905/) (2026)
- [Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts](https://mlsanity.com/paper/2608.21554/) (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)

This paper develops a stochastic programming framework for multi-agent systems where task decomposition, assignment, and scheduling problems are simultaneously optimized. The framework can be applied to heterogeneous mobile robot teams with distributed sub-tasks. Examples include pandemic robotic service coordination, explore and rescue, and delivery systems with heterogeneous vehicles. Due to their inherent flexibility and robustness, multi-agent systems are applied in a growing range of real-world problems that involve heterogeneous tasks and uncertain information. Most previous works assume one fixed way to decompose a task into roles that can later be assigned to the agents. This assumption is not valid for a complex task where the roles can vary and multiple decomposition structures exist. Meanwhile, it is unclear how uncertainties in task requirements and agent capabilities can be systematically quantified and optimized under a multi-agent system setting. A representation for complex tasks is proposed: agent capabilities are represented as a vector of random distributions, and task requirements are verified by a generalizable binary function. The conditional value at risk (CVaR) is chosen as a metric in the objective function to generate robust plans. An efficient algorithm is described to solve the model, and the whole framework is evaluated in two different practical test cases: capture-the-flag and robotic service coordination during a pandemic (e.g., COVID-19). Results demonstrate that the framework is generalizable, scalable up to 140 agents and 40 tasks for the example test cases, and provides low-cost plans that ensure a high probability of success.