In this paper, we study the multi-robot task assignment and path-finding problem (MRTAPF), where a number of agents are required to visit all given goal locations while avoiding collisions with each other. We propose a novel two-layer algorithm SA-reCBS that cascades the simulated annealing algorithm and conflict-based search to solve this problem. Compared to other approaches in the field of MRTAPF, the advantage of SA-reCBS is that without requiring a pre-bundle of goals to groups with the same number of groups as the number of robots, it enables a part of agents needed to visit all goals in collision-free paths. We test the algorithm in various simulation instances and compare it with state-of-the-art algorithms. The result shows that SA-reCBS has a better performance with a higher success rate, less computational time, and better objective values.
翻译:在本文中,我们研究了多机器人任务分配和路径规划问题(MRTAPF),其中需要多个智能体访问所有给定的目标位置,同时避免彼此之间的冲突。我们提出了一种新颖的两层算法SA-reCBS,该算法串联了模拟退火算法和基于冲突的搜索来解决这个问题。与MRTAPF领域中的其他方法相比,SA-reCBS的优势在于,在不需要将目标预先绑定到具有与机器人数量相同的组的情况下,它可以使一部分智能体需要在避免与其他代理碰撞情况下访问所有目标。我们在各种仿真实例中测试了算法,并与最先进的算法进行了比较。结果表明,SA-reCBS具有更好的性能,成功率更高,计算时间更短,客观价值更好。