A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems
<|reference_start|>A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems: 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.<|reference_end|>
@article{aakash2024a,
    title={A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot
  Systems},
    author={Aakash and Indranil Saha},
    journal={arXiv preprint arXiv:2402.13292},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13292},
    primaryClass={cs.MA cs.AI cs.RO}
}