Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
复制标题
DOI：
10.1109/icra48506.2021.9561899
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Teng Guo;Shuai D. Han;Jingjin Yu
中科院分区：
文献类型：
--
作者：
Teng Guo;Shuai D. Han;Jingjin Yu
在这项工作中，我们系统地研究了应用时空分裂算法的多机器人运动规划（MRMP）问题的图论设置：一个已知的NP-难最佳解决的问题。遵循分治原则，我们设计了多个空间和时间分裂方案，可以应用于任何现有的MRMP算法，包括整数规划求解器和增强的基于冲突的搜索，在正交的方式。一个良好的基线MRMP算法与适当的分裂启发式的组合证明是非常有效的，允许解决问题的10+倍，比以前可能的，广泛的数值评估证实。值得注意的是，融合时间分割启发式和增强的基于冲突的搜索（ECBS）算法的问题的空间分区将ECBS在大型和具有挑战性的DAO映射上的可扩展性提高了5-15倍，对解决方案的最优性的影响可以忽略不计。
In this work, we systematically examine the application of spatio-temporal splitting heuristics to the Multi-Robot Motion Planning (MRMP) problem in a graph-theoretic setting: a problem known to be NP-hard to optimally solve. Following the divide-and-conquer principle, we design multiple spatial and temporal splitting schemes that can be applied to any existing MRMP algorithm, including integer programming solvers and Enhanced Conflict Based Search, in an orthogonal manner. The combination of a good baseline MRMP algorithm with a proper splitting heuristic proves highly effective, allowing the resolution of problems 10+ times than what is possible previously, as corroborated by extensive numerical evaluations. Notably, spatial partition of problem fusing with the temporal splitting heuristic and the enhanced conflict based search (ECBS) algorithm increases the scalability of ECBS on large and challenging DAO maps by 5–15 folds with negligible impact on solution optimality.