CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent
  Path Planning in Continuous Spaces
  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.
