论文标题
使用基于内侧轴的卵石图嵌入的多机器人路径计划
Multi-Robot Path Planning Using Medial-Axis-Based Pebble-Graph Embedding
论文作者
论文摘要
我们提出了一种在带有多边形边界的连续平面工作区中，用于标记，磁盘形多机器人路径计划（MPP）的集中式算法。我们的方法自动将连续问题转换为一个离散的基于图的变体称为卵石运动问题，可以有效地解决。为了构建基本的卵石图，我们通过内侧轴转换工作空间中的刻有圆圈，并将机器人组织到每个刻有圆圈内的层中。我们表明，我们的分层卵石图可实现无碰撞运动，从而使所有图形限制的MPP实例都是可行的。然后，可以通过将机器人从与图形顶点路由和图形顶点进行局部导航进行求解的MPP实例。我们在具有高机器人包装密度的多种环境（最高$ 61.6 \％的工作区）上测试了我们的方法。对于通道狭窄的环境，这种密度违反了最先进的MPP计划者做出的良好分离的假设，而我们的方法的平均成功率为$ 83 \％$。
We present a centralized algorithm for labeled, disk-shaped Multi-Robot Path Planning (MPP) in a continuous planar workspace with polygonal boundaries. Our method automatically transform the continuous problem into a discrete, graph-based variant termed the pebble motion problem, which can be solved efficiently. To construct the underlying pebble graph, we identify inscribed circles in the workspace via a medial axis transform and organize robots into layers within each inscribed circle. We show that our layered pebble-graph enables collision-free motions, allowing all graph-restricted MPP instances to be feasible. MPP instances with continuous start and goal positions can then be solved via local navigations that route robots from and to graph vertices. We tested our method on several environments with high robot-packing densities (up to $61.6\%$ of the workspace). For environments with narrow passages, such density violates the well-separated assumptions made by state-of-the-art MPP planners, while our method achieves an average success rate of $83\%$.
