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.

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