  We propose a novel algorithm to solve multi-robot motion planning (MRMP)
rapidly, called Simultaneous Sampling-and-Search Planning (SSSP). Conventional
MRMP studies mostly take the form of two-phase planning that constructs
roadmaps and then finds inter-robot collision-free paths on those roadmaps. In
contrast, SSSP simultaneously performs roadmap construction and collision-free
pathfinding. This is realized by uniting techniques of single-robot
sampling-based motion planning and search techniques of multi-agent pathfinding
on discretized spaces. Doing so builds the small search space, leading to quick
MRMP. SSSP ensures finding a solution eventually if exists. Our empirical
evaluations in various scenarios demonstrate that SSSP significantly
outperforms standard approaches to MRMP, i.e., solving more problem instances
much faster. We also applied SSSP to planning for 32 ground robots in a dense
situation.
