  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 high
levels of solution optimality.
