# Heterogeneous Coalition Formation and Scheduling with Multi-Skilled Robots

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2023.

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

- [Large-Scale Multi-Robot Assembly Planning for Autonomous Manufacturing](https://mlsanity.com/paper/2311.00192/) (2023)
- [Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts](https://mlsanity.com/paper/2608.21554/) (2026)
- [GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning](https://mlsanity.com/paper/2609.00577/) (2026)

## Abstract (arXiv)

We present an approach to task scheduling in heterogeneous multi-robot systems. In our setting, the tasks to complete require diverse skills. We assume that each robot is multi-skilled, i.e., each robot offers a subset of the possible skills. This makes the formation of heterogeneous teams (coalitions) a requirement for task completion. We present two centralized algorithms to schedule robots across tasks and to form suitable coalitions, assuming stochastic travel times across tasks. The coalitions are dynamic, in that the robots form and disband coalitions as the schedule is executed. The first algorithm we propose guarantees optimality, but its run-time is acceptable only for small problem instances. The second algorithm we propose can tackle large problems with short run-times, and is based on a heuristic approach that typically reaches 1x-2x of the optimal solution cost.