Abstract
We propose a novel centralized and decoupled algorithm, DDM, for solving one-shot and dynamic optimal multi-robot path planning problems in a graph-based setting. 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 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 both great scalability and a high level of solution optimality.
Abstract (translated by Google)
URL
http://arxiv.org/abs/1904.02598