We consider the following motion-planning problem: we are given m unit discs in a simple polygon with n vertices, each at their own start position, and we want to move the discs to a given set of m target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in O (n log n + mn + m~2) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.
展开▼
机译：我们考虑以下动作计划问题：我们在一个简单的多边形中给出了一个带有n个顶点的M单位光盘，每个都是在自己的起始位置，并且我们希望将光盘移动到给定的一组m个目标位置。与标准（标记）的问题相反，允许每个光盘移动到任何目标位置，只要在最后占用每个目标位置。我们表明，该问题的这个未标记版本可以在O（n log n + mn + m〜2）中来解决，假设启动和目标位置彼此至少距离至少一些。这与标准（标记）和更一般的多机器人运动规划问题呈鲜明对比，用于在简单的多边形中移动的光盘，这已知是强烈的NP-COLLE。
展开▼
