It Costs to Get Costs! A Heuristic-Based Scalable Goal Assignment Algorithm for Multi-Robot Systems

摘要

The goal assignment problem for a multi-robot application involves assigning a unique goal to each robot to minimize the total cost of movement for all the robots. A significant step in the state-of-the-art algorithms solving this problem is to find the cost associated with each robot-goal pair. For a large multi-robot system with many robots and many goals in a complex workspace, the computation time required to find the paths for all robot-goal pairs may become prohibitively large. We present an algorithm that solves the optimal goal assignment problem without computing the paths between all the robot-goal pairs. Instead, our algorithm computes the obstacle-free optimal path for any robot-goal pair in a demand-driven way, i.e., if it is absolutely required to ensure the optimality of the goal assignment. We evaluate our algorithm extensively on both randomly generated and standard workspaces for hundreds of robots. Our experimental results demonstrate that the proposed algorithm achieves an order-of-magnitude speedup over the state-of-the-art baseline algorithm. To the best of our knowledge, our algorithm is the first one to solve the multi-robot optimal goal assignment problem without computing the paths for all robot-goal pairs explicitly, guaranteeing high scalability.