Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time
Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time
复制标题
DOI：
10.15607/rss.2022.xviii.057
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Teng Guo;Jingjin Yu
中科院分区：
文献类型：
--
作者：
Teng Guo;Jingjin Yu
基于图的多机器人路径规划(MRPP)是一个NP-困难的最优解问题。在这项工作中，我们提出了第一个低多项式时间的MRPP算法，在很高的机器人密度下，以很高的概率实现了随机实例的1-1.5渐近最优性保证。对计算效率和解的最优性的双重保证表明，我们提出的通用方法在大规模扩展多机器人物流应用方面很有前景，例如在大型机器人仓库中。具体地说，在一个$m_1\x m_2$网格，$m_1\ge m_2$上，我们的RTH(Rubik Table With Highways)算法以很高的概率计算最多$\FRAC{m_1m_2}{3}$机器人的布线，这些机器人的起点和目标配置是均匀随机分布的，完工时间为$m_1+2m_2+o(M_1)$。由于这类实例的最小完工时间为$m_1+m_2-o(M_1)$，也是大概率的，对于机器人密度高达$\frac{1}{3}$的随机实例，RTH保证$\frac{m_1+2m_2}{m_1+m_2}$最优性为$m_1\to\inty$。$\frac{m_1+2m_2}{m_1+m_2}\in(1，1.5]$.除了这一关键结果，我们还建立了一系列相关结果，支持更高的机器人密度和具有规则分布的障碍物的环境，这些环境直接映射到真实世界的包裹分拣场景。在具有可证明保证的基线方法的基础上，我们开发了有效的、原则性的启发式算法，进一步提高了RTH算法的计算最优性。在广泛的数值评估中，RTH及其变体显示出与ECBS和DDM等方法相比的卓越可扩展性，使用价值45,000美元的机器人扩展到超过450美元\乘以300美元网格，并如我们的理论分析所预测的那样，始终如一地实现约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.