k-color multi-robot motion planning
k-color multi-robot motion planning
复制标题
k色多机器人运动规划
DOI：
10.1177/0278364913506268
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
D. Halperin
中科院分区：
文献类型：
--
作者：
Kiril Solovey;D. Halperin
我们提出了多机器人运动计划问题的简单自然扩展，其中机器人被划分为组（颜色），因此在每个组中，机器人都可以互换。不再需要每个机器人移动到特定目标，而是将分配给其组的某些目标放置。我们称此问题K-Color多机器人运动计划，并提供了专门设计用于解决该算法的基于抽样的算法。算法的核心是一种新颖的技术，其中k色问题将减少为几个离散的多机器人运动计划问题。这些降低将基本样品扩大到了机器人的自由放置和路径的大量集合中。我们通过在平面中翻译的磁盘机器人和多边形机器人的实现来证明该算法的性能。我们表明，该算法成功有效地应对各种具有挑战性的方案，涉及许多机器人，而该算法的简化版本可以看作是基于样本的算法的扩展，用于k-color案例，但即使在简单的情况下。有趣的是，我们的算法在标准的多机器人问题上的实施优于PRM的实现，每个机器人都具有独特的颜色。
We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k-color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it. At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots. We demonstrate the performance of the algorithm by an implementation for the case of disc robots and polygonal robots translating in the plane. We show that the algorithm successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a well established implementation of PRM for the standard multi-robot problem, in which each robot has a distinct color.