# Bigraph Matching Weighted with Learnt Incentive Function for Multi-Robot Task Allocation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 11 Mar 2024.

## Builds on (most cited first, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Graph Capsule Convolutional Neural Networks](https://mlsanity.com/paper/1805.08090/) (2018)
- [Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks](https://mlsanity.com/paper/1803.09621/) (2018)
- [Multi-Robot Coverage and Exploration using Spatial Graph Neural Networks](https://mlsanity.com/paper/2011.01119/) (2020)
- [Learning Scalable Policies over Graphs for Multi-Robot Task Allocation using Capsule Attention Networks](https://mlsanity.com/paper/2205.03321/) (2022)
- [Efficient Planning of Multi-Robot Collective Transport using Graph Reinforcement Learning with Higher Order Topological Abstraction](https://mlsanity.com/paper/2303.08933/) (2023)
- [Graph Learning Based Decision Support for Multi-Aircraft Take-Off and Landing at Urban Air Mobility Vertiports](https://mlsanity.com/paper/2302.05849/) (2023)
- [Fast Decision Support for Air Traffic Management at Urban Air Mobility Vertiports using Graph Learning](https://mlsanity.com/paper/2308.09075/) (2023)
- [Decentralized Dynamic Task Allocation in Swarm Robotic Systems for Disaster Response](https://mlsanity.com/paper/1907.04394/) (2019)

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

- [Learning-aided Bigraph Matching Approach to Multi-Crew Restoration of Damaged Power Networks Coupled with Road Transportation Networks](https://mlsanity.com/paper/2506.19703/) (2025)

## Abstract (arXiv)

Most real-world Multi-Robot Task Allocation (MRTA) problems require fast and efficient decision-making, which is often achieved using heuristics-aided methods such as genetic algorithms, auction-based methods, and bipartite graph matching methods. These methods often assume a form that lends better explainability compared to an end-to-end (learnt) neural network based policy for MRTA. However, deriving suitable heuristics can be tedious, risky and in some cases impractical if problems are too complex. This raises the question: can these heuristics be learned? To this end, this paper particularly develops a Graph Reinforcement Learning (GRL) framework to learn the heuristics or incentives for a bipartite graph matching approach to MRTA. Specifically a Capsule Attention policy model is used to learn how to weight task/robot pairings (edges) in the bipartite graph that connects the set of tasks to the set of robots. The original capsule attention network architecture is fundamentally modified by adding encoding of robots' state graph, and two Multihead Attention based decoders whose output are used to construct a LogNormal distribution matrix from which positive bigraph weights can be drawn. The performance of this new bigraph matching approach augmented with a GRL-derived incentive is found to be at par with the original bigraph matching approach that used expert-specified heuristics, with the former offering notable robustness benefits. During training, the learned incentive policy is found to get initially closer to the expert-specified incentive and then slightly deviate from its trend.