# CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 65 references that are in the map.
- First posted on arXiv 24 Jan 2022.

## Builds on (most cited first, 26 of 26)

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Learning Sampling Distributions for Robot Motion Planning](https://mlsanity.com/paper/1709.05448/) (2017)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Motion Planning Networks: Bridging the Gap Between Learning-based and Classical Motion Planners](https://mlsanity.com/paper/1907.06013/) (2019)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [VAIN: Attentional Multi-agent Predictive Modeling](https://mlsanity.com/paper/1706.06122/) (2017)
- [Multimodal Deep Generative Models for Trajectory Prediction: A Conditional Variational Autoencoder Approach](https://mlsanity.com/paper/2008.03880/) (2020)
- [Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning](https://mlsanity.com/paper/2011.13219/) (2020)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [LEGO: Leveraging Experience in Roadmap Generation for Sampling-Based Planning](https://mlsanity.com/paper/1907.09574/) (2019)
- [Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees](https://mlsanity.com/paper/1903.00070/) (2019)
- [Learned Critical Probabilistic Roadmaps for Robotic Motion Planning](https://mlsanity.com/paper/1910.03701/) (2019)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning](https://mlsanity.com/paper/1903.00994/) (2019)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)
- [Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning](https://mlsanity.com/paper/1305.2889/) (2013)
- [Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm](https://mlsanity.com/paper/1703.04159/) (2017)
- [Multi-agent RRT*: Sampling-based Cooperative Pathfinding (Extended Abstract)](https://mlsanity.com/paper/1302.2828/) (2013)
- [Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent](https://mlsanity.com/paper/2003.12924/) (2020)

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

- [Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models](https://mlsanity.com/paper/2502.03607/) (2025)
- [Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models](https://mlsanity.com/paper/2412.17993/) (2024)
- [Learning-based Motion Planning in Dynamic Environments Using GNNs and Temporal Encoding](https://mlsanity.com/paper/2210.08408/) (2022)
- [Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality](https://mlsanity.com/paper/2301.08451/) (2023)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization](https://mlsanity.com/paper/2604.05416/) (2026)
- [Shared-Roadmap Generation and Evaluator for Multi-Agent Path Planning Using Heterogeneous Graph Neural Network](https://mlsanity.com/paper/2610.09034/) (2026)

## Abstract (arXiv)

Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach is to first construct graphs approximating the spaces, called roadmaps, and then apply multi-agent pathfinding (MAPF) algorithms to derive a set of conflict-free paths. While conventional studies have utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored how we can construct roadmaps that work effectively for multiple agents. To this end, we propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in the time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and then uses the learned model to sample the vertices of CTRMs for new, previously unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining a success rate and solution quality comparable to conventional roadmap construction approaches.