On the hardness of unlabeled multi-robot motion planning
On the hardness of unlabeled multi-robot motion planning
复制标题
DOI：
10.1177/0278364916672311
复制
发表时间：
2016-12-01
影响因子：
9.2
通讯作者：
Halperin, Dan
中科院分区：
文献类型：
--
作者：
Solovey, Kiril;Halperin, Dan
在未标记的多机器人运动计划中，几个可互换的机器人在一个共同的工作区中运行。目标是将机器人移至一组目标位置，以便每个位置都会被某个机器人占据。在本文中，我们研究了在多边形障碍物中移动的单位方机器人的特定情况，并表明它是pspace-hard。我们还考虑了此问题的另外三种变体，并表明它们也是Pspace-Hard。据我们所知，这是未标记案件的第一个硬度证明。此外，我们的证据可以用来证明标记的变体（每个机器人都分配了特定的目标位置），对于单位方机器人而言，同样是pspace-hard，它设定了另一个先例，因为先前的硬度结果需要机器人的形状不同（或至少在不同的方向）。最后，我们解决了一个开放的问题，说明在具有多边形障碍的环境中，众所周知的高峰小时难题的复杂性。
In unlabeled multi-robot motion planning, several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this problem for the specific case of unit-square robots moving amidst polygonal obstacles and show that it is PSPACE-hard. We also consider three additional variants of this problem and show that they are all PSPACE-hard as well. To the best of our knowledge, this is the first hardness proof for the unlabeled case. Furthermore, our proofs can be used to show that the labeled variant (where each robot is assigned a specific target position), again, for unit-square robots, is PSPACE-hard as well, which sets another precedent, as previous hardness results require the robots to be of different shapes (or at least in different orientations). Lastly, we settle an open problem regarding the complexity of the well-known Rush-Hour puzzle for unit-square cars in environments with polygonal obstacles.