# Quick Multi-Robot Motion Planning by Combining Sampling and Search

arXiv: https://arxiv.org/abs/2203.00315 · HTML: https://mlsanity.com/paper/2203.00315/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2022.

## Built on by (most cited first, 6 of 6)

- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Zero-Shot Multi-Object Scene Completion](https://mlsanity.com/paper/2403.14628/) (2024)
- [Multi-agent Path Finding for Cooperative Autonomous Driving](https://mlsanity.com/paper/2402.00334/) (2024)
- [Multi-agent Path Finding for Mixed Autonomy Traffic Coordination](https://mlsanity.com/paper/2409.03881/) (2024)
- [D4orm: Multi-Robot Trajectories with Dynamics-aware Diffusion Denoised Deformations](https://mlsanity.com/paper/2503.12204/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

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.