The fundamental goal assignment problem for a multi-robot application aims to
assign a unique goal to each robot while ensuring collision-free paths,
minimizing the total movement cost. A plausible algorithmic solution to this
NP-hard problem involves an iterative process that integrates a task planner to
compute the goal assignment while ignoring the collision possibilities among
the robots and a multi-agent path-finding algorithm to find the collision-free
trajectories for a given assignment. This procedure involves a method for
computing the next best assignment given the current best assignment. A naive
way of computing the next best assignment, as done in the state-of-the-art
solutions, becomes a roadblock to achieving scalability in solving the overall
problem. To obviate this bottleneck, we propose an efficient conflict-guided
method to compute the next best assignment. Additionally, we introduce two more
optimizations to the algorithm -- first for avoiding the unconstrained path
computations between robot-goal pairs wherever possible, and the second to
prevent duplicate constrained path computations for multiple robot-goal pairs.
We extensively evaluate our algorithm for up to a hundred robots on several
benchmark workspaces. The results demonstrate that the proposed algorithm
achieves nearly an order of magnitude speedup over the state-of-the-art
algorithm, showcasing its efficacy in real-world scenarios.

通过提出高效的冲突引导方法，避免了计算下一个最佳分配时的瓶颈，以及引入两种算法优化来提高效率和可扩展性，研究表明该算法在实际场景中取得了近一个数量级的加速效果。

多机器人系统冲突感知的最优目标分配算法

A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot  Systems

In cooperative Multi-Agent Planning (MAP), a set of goals has to be achieved
by a set of agents. Independently of whether they perform a pre-assignment of
goals to agents or they directly search for a solution without any goal
assignment, most previous works did not focus on a fair
distribution/achievement of goals by agents. This paper adapts well-known
fairness schemes to MAP, and introduces two novel approaches to generate
cost-aware fair plans. The first one solves an optimization problem to
pre-assign goals to agents, and then solves a centralized MAP task using that
assignment. The second one consists of a planning-based compilation that allows
solving the joint problem of goal assignment and planning while taking into
account the given fairness scheme. Empirical results in several standard MAP
benchmarks show that these approaches outperform different baselines. They also
show that there is no need to sacrifice much plan cost to generate fair plans.

本文介绍了两种创新方法来生成成本感知的公平计划，第一种使用优化问题预先分配目标，并使用该分配解决集中式 MAP 任务，第二种利用基于计划的编译，考虑给定的公平性方案来解决目标分配和计划的联合问题，在几个标准 MAP 基准测试中证明这些方法优于不同的基线，并表明生成公平计划无需牺牲过多的计划成本。