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.

该论文介绍了一种使用图强化学习 (GRL) 框架来学习多机器人任务分配 (MRTA) 的启发式或激励的方法，其中使用胶囊注意力策略模型来学习如何赋予任务 / 机器人配对 (边) 在将任务集与机器人集连接的二分图中的权重。该方法与使用专家指定启发式的原始二分图匹配方法性能相当，但具有显著的鲁棒性优势。在训练过程中，学到的激励策略与专家指定的激励策略初始接近，然后稍微偏离其趋势。

多机器人任务分配中带有学习激励函数的大图匹配加权

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

Task allocation using a team or coalition of robots is one of the most
important problems in robotics, computer science, operational research, and
artificial intelligence. In recent work, research has focused on handling
complex objectives and feasibility constraints amongst other variations of the
multi-robot task allocation problem. There are many examples of important
research progress in these directions. We present a general formulation of the
task allocation problem that generalizes several versions that are
well-studied. Our formulation includes the states of robots, tasks, and the
surrounding environment in which they operate. We describe how the problem can
vary depending on the feasibility constraints, objective functions, and the
level of dynamically changing information. In addition, we discuss existing
solution approaches for the problem including optimization-based approaches,
and market-based approaches.

本文介绍一个通用的、广泛涉及机器人、计算机科学、运筹学和人工智能等领域的任务分配问题，包括机器人、任务和周围环境状态的多个版本，并探讨了解决该问题的现有方法，包括基于优化和市场的方法。