DDM: Fast Near-Optimal Multi-Robot Path Planning Using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics
DDM: Fast Near-Optimal Multi-Robot Path Planning Using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics
复制标题
DOI：
10.1109/lra.2020.2967326
复制
发表时间：
2020-04-01
影响因子：
5.2
通讯作者：
Yu, Jingjin
中科院分区：
文献类型：
--
作者：
Han, Shuai D.;Yu, Jingjin
我们提出了一种新颖的集中式解耦算法 DDM，用于解决网格图中的多机器人路径规划问题，针对按需和自动化仓库式设置。研究了两种设置：一种是传统设置，其目标是将一组机器人尽快从各自的初始顶点移动到目标顶点；另一种是动态设置，需要频繁重新规划以适应目标配置调整。在其他技术中，DDM 主要通过利用两种创新启发式方法来实现：路径多样化和最优子问题解决方案数据库。这两种启发式攻击基于解耦的规划器的两个不同阶段：虽然路径多样化允许更有效地利用整个工作空间进行机器人旅行，但最佳子问题解决方案数据库有助于快速解决局部路径冲突。广泛的评估表明，DDM 实现了高水平的可扩展性和接近最佳的解决方案质量。
We propose a novel centralized and decoupled algorithm, DDM, for solving multi-robot path planning problems in grid graphs, targeting on-demand and automated warehouse-like settings. Two settings are studied: a traditional one whose objective is to move a set of robots from their respective initial vertices to the goal vertices as quickly as possible, and a dynamic one which requires frequent re-planning to accommodate for goal configuration adjustments. Among other techniques, DDM is mainly enabled through exploiting two innovative heuristics: path diversification and optimal sub-problem solution databases. The two heuristics attack two distinct phases of a decoupling-based planner: while path diversification allows the more effective use of the entire workspace for robot travel, optimal sub-problem solution databases facilitate the fast resolution of local path conflicts. Extensive evaluation demonstrates that DDM achieves high levels of scalability and solution quality close to the optimum.