k-color multi-robot motion planning

摘要: We present a simple and natural extension of the multi-robot motion planning problem where robots are partitioned into groups (colors), such that in each group interchangeable. Every robot is no longer required to move specific target, but rather some target placement assigned its group. call this k-color provide sampling-based algorithm specifically designed for solving it. At heart novel technique reduced several discrete problems. These reductions amplify basic samples massive collections free placements paths robots. demonstrate performance by an implementation case disc polygonal translating plane. show successfully efficiently copes with variety challenging scenarios, involving many robots, while simplified version algorithm, can be viewed as prevalent case, fails even on scenarios. Interestingly, our outperforms well established PRM standard problem, which has distinct color.