# Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2013.

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

- [Multi-Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2410.03072/) (2024)
- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [Hypergraph-based Multi-Robot Task and Motion Planning](https://mlsanity.com/paper/2210.04333/) (2022)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [Systematic Comparison of Path Planning Algorithms using PathBench](https://mlsanity.com/paper/2203.03092/) (2022)
- [Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance](https://mlsanity.com/paper/2210.07141/) (2022)
- [Pathfinding with Lazy Successor Generation](https://mlsanity.com/paper/2408.15443/) (2024)
- [A Hybrid Evolutionary Approach for Multi Robot Coordinated Planning at Intersections](https://mlsanity.com/paper/2412.01082/) (2024)
- [Multi-Agent Pathfinding Under Team-Connected Communication Constraint via Adaptive Path Expansion and Dynamic Leading](https://mlsanity.com/paper/2501.02770/) (2025)
- [D4orm: Multi-Robot Trajectories with Dynamics-aware Diffusion Denoised Deformations](https://mlsanity.com/paper/2503.12204/) (2025)

## Abstract (arXiv)

We present a sampling-based framework for multi-robot motion planning which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.