Selected work IEEE RA-L 2025 IROS 2025 • Hangzhou, China 🇨🇳

Heterogeneous Multi-Robot Task Allocation and Scheduling via Reinforcement Learning

Weiheng Dai, Utkarsh Rai, Jimmy Chiun, Yuhong Cao, Guillaume Sartoretti

Multi-Agent RLTask AllocationSchedulingHeterogeneous Teams
Paper Code Results Video BibTeX
100% of instances solved, in every configuration tested the exact solver drops to 0% on the hardest ones
100× faster than the mixed-integer solver, at least and at least 10× faster than ACO heuristics
150 / 500 agents and tasks, without retraining trained on 15–50 tasks and 3–5 species
< 23% worst-case makespan gap to exact solutions on a scenario it was never trained for

Abstract

Many multi-robot applications require allocating a team of heterogeneous agents to complete a given set of spatially distributed tasks as quickly as possible, such as search and rescue, area inspection/monitoring, and space exploration. We focus on tasks which can only be initiated when all required agents have arrived, such as detection involving sensor fusion or cooperative assembly requiring robots with different tools/skillsets. Robots dynamically form and disband teams based on diverse abilities needed for each task, which, however, can potentially result in extra idle (waiting) times at the task location. Robots (agents) should take into account the schedules of others to maximize their collective efficiency and reduce overall task completion time (makespan). Conventional methods such as mix-integer programming generally require centralized scheduling and long optimization time, which limits their potential for real-world applications. In this work, we propose a decentralized method that fully relies on reinforcement learning (RL) to train a generalized policy applicable to heterogeneous agents. To address the challenge of complex cooperation learning, we further introduce a constrained flashforward mechanism to guide/constrain the agents' exploration and help them make better predictions. Through an attention mechanism that reasons about both short-term cooperation and long-term scheduling dependency, agents learn to reactively choose their next tasks (and subsequent coalitions) to avoid wasting abilities and to shorten the makespan. We compare our method with state-of-the-art heuristic and mixed-integer programming methods, demonstrating its generalization ability and showing it closely matches or outperforms these baselines while remaining at least two orders of magnitude faster.

How It Works

A task cannot start until every skill it needs is standing there at once. That single constraint turns allocation into scheduling, and scheduling into a deadlock problem.

A search-and-rescue scene where drones, a removal truck and a rescue robot carry different skills, matched against task requirements.
Each robot carries a subset of skills; each site demands its own combination. A coalition forms only when the combination is covered, and everyone waits for the slowest arrival.
  1. 01

    Coalitions that must arrive together

    Tasks begin only once every required agent is present, so robots form and disband teams by capability and pay for mistimed arrivals in idle waiting. Waiting time is a first-class metric here, not a footnote.

  2. 02

    A species-traits model

    Agents belong to species that share a trait vector over a fixed skill set; tasks carry requirements over the same vocabulary. Additive tasks sum the coalition’s traits, binary tasks need each skill covered by at least one member.

  3. 03

    A constrained flashforward mechanism

    Left unconstrained, agents explore joins that strand the team in deadlock. The flashforward mechanism narrows which tasks an agent may select, letting it anticipate the consequence of joining a coalition and keeping training efficient.

  4. 04

    Attention across two horizons

    The policy attends to short-term cooperation — who is heading where right now — and to long-term scheduling dependencies, so agents reactively pick a next task and coalition that will not waste anyone’s capabilities.

  5. 05

    Trained small, run enormous

    Training instances hold 15 to 50 tasks and 3 to 5 species, with an Adam learning rate of 10−5 decaying every 2,000 episodes. The same network then handles 150 agents and 500 tasks, where makespan grows near-linearly with the task-to-agent ratio.

The task-allocation network: agent and task graphs pass through separate encoders, two cross-attention encoders, and a decoder that outputs a probability over tasks.
The source paper's encoder-decoder architecture. Agent and task context meet through two-way cross-attention before the masked decoder scores the next task.

Results

Fifty unseen instances per configuration, against an exact mixed-integer solver (CTAS-D), two ant-colony heuristics and a greedy baseline. Group labels read agents / tasks.

Five species forming and disbanding coalitions until every task is finished.

Paper Video

BibTeX

@article{dai2025heterogeneous,
  title={Heterogeneous Multi-Robot Task Allocation via Reinforcement Learning},
  author={Dai, Weiheng and Rai, Utkarsh and Chiun, Jimmy and Cao, Yuhong and Sartoretti, Guillaume},
  journal={IEEE Robotics and Automation Letters},
  year={2025},
  pages={2654-2661},
  keywords={Robots;Robot kinematics;Robot sensing systems;System recovery;Resource management;Schedules;Training;Vectors;Reinforcement learning;Search problems;Planning, scheduling and coordination;multi-robot systems;reinforcement learning},
  doi={10.1109/LRA.2025.3534682}
}

Related Project