  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.
