论文标题
在多项式时间内对网格的时间 - 最佳时间多机器人路径计划
Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time
论文作者
论文摘要
基于图的多机器人路径计划（MRPP）是最佳求解的NP-HARD。在这项工作中，我们提出了第一个用于MRPP的低多项式时间算法，以实现1--1.5的渐近最佳性能在非常高的机器人密度下的随机实例上保证，并具有很高的可能性。计算效率和解决方案最优性的双重保证表明，我们提出的一般方法有望在大量机器人仓库中显着扩大多机器人的应用程序。 具体而言，在$ m_1 \ times m_2 $ gird，$ m_1 \ ge m_2 $，我们的rth（带高速公路的rubik桌子）算法计算的解决方案可将最多可用$ \ frac {m_1m_2} {3} $ robots与均匀分布的启动和零件配置为$ _1 + M M Mak_1 + MM M.1 + 2M 1 + MM_1） 高概率。 Because the minimum makespan for such instances is $m_1 + m_2 - o(m_1)$, also with high probability, RTH guarantees $\frac{m_1+2m_2}{m_1+m_2}$ optimality as $m_1 \to \infty$ for random instances with up to $\frac{1}{3}$ robot density, with high probability. $ \ frac {m_1+2m_2} {m_1+m_2} \ in（1，1.5] $。与此关键结果一起，我们还建立了一系列相关结果，支持更高的机器人密度和环境，具有定期分布的障碍，这些障碍可以直接映射到实际的基础上，以确立的是依据的基准，从而使我们的基础有效地构建了，我们可以在我们的基准方面进行构建，从而使我们的原理构建了，我们可以在我们的基准方面进行构建，我们可以在我们的基准方面构建，我们可以在我们的基准方面进行构建，这是我们在构图中的构建。与包括ECB和DDM在内的方法相比，RTH及其变体在广泛的数值评估中的计算最佳性显示出非凡的可伸缩性，并将其扩展到450美元以上的300美元网格，$ 45,000 $ 45,000 $机器人，并且始终如一地通过$ 1.5 $ $ 1.5 $ $ $ $ $分析。
Graph-based multi-robot path planning (MRPP) is NP-hard to optimally solve. In this work, we propose the first low polynomial-time algorithm for MRPP achieving 1--1.5 asymptotic optimality guarantees on makespan for random instances under very high robot density, with high probability. The dual guarantee on computational efficiency and solution optimality suggests our proposed general method is promising in significantly scaling up multi-robot applications for logistics, e.g., at large robotic warehouses. Specifically, on an $m_1\times m_2$ gird, $m_1 \ge m_2$, our RTH (Rubik Table with Highways) algorithm computes solutions for routing up to $\frac{m_1m_2}{3}$ robots with uniformly randomly distributed start and goal configurations with a makespan of $m_1 + 2m_2 + o(m_1)$, with high probability. Because the minimum makespan for such instances is $m_1 + m_2 - o(m_1)$, also with high probability, RTH guarantees $\frac{m_1+2m_2}{m_1+m_2}$ optimality as $m_1 \to \infty$ for random instances with up to $\frac{1}{3}$ robot density, with high probability. $\frac{m_1+2m_2}{m_1+m_2} \in (1, 1.5]$. Alongside this key result, we also establish a series of related results supporting even higher robot densities and environments with regularly distributed obstacles, which directly map to real-world parcel sorting scenarios. Building on the baseline methods with provable guarantees, we have developed effective, principled heuristics that further improve the computed optimality of the RTH algorithms. In extensive numerical evaluations, RTH and its variants demonstrate exceptional scalability as compared with methods including ECBS and DDM, scaling to over $450 \times 300$ grids with $45,000$ robots, and consistently achieves makespan around $1.5$ optimal or better, as predicted by our theoretical analysis.
