The state-of-the-art algorithms for cooperative pathfinding for embodied robots typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. We proposed MA-RRT*, a novel algorithm for multi-agent motion planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm called RRT*. Initially, we focus on the case where the agents’ mobility model is a discrete graph in order to allow comparison with a state-of-the-art optimal anytime approach by Standley et al. We evaluate the performance of the proposed algorithm and its scalability with respect to the number of agents and the size of the environment. Our results show that in uncluttered environments the sampling-based approach offers better scalability than the forward-search approach.

Related publications:

• M. Čáp, P. Novák, J. Vokřínek, and M. Pěchouček, “Multi-agent RRT*: sampling-based cooperative pathfinding,” in Autonomous robots and multirobot systems workshop at AAMAS 2013, 2013.
  [Bibtex]

  @inproceedings{cap_2013_c,
  author = "Michal \v{C}\'{a}p and Peter Nov\'{a}k and Ji\v{r}\'{i} Vok\v{r}\'{i}nek and Michal P\v{e}chou\v{c}ek",
  title = "Multi-agent {RRT*}: Sampling-based Cooperative Pathfinding",
  booktitle = "Autonomous Robots and Multirobot Systems Workshop at {AAMAS 2013}",
  year = "2013",
  poster = "http://michalcap.net/wp-content/papercite-data/pdf/cap_2013_c-poster.pdf",
  }

• M. Čáp, P. Novák, J. Vokřínek, and M. Pěchouček, “Multi-agent RRT*: sampling-based cooperative pathfinding (extended abstract),” in Proceedings of the 12th international conference on autonomous agents and multiagent systems, AAMAS’13, 2013.
  [Bibtex]

  @inproceedings{cap_2013_a,
  author = {Michal \v{C}\'{a}p and Peter Nov\'{a}k and Ji\v{r}\'{i} Vok\v{r}\'{i}nek and Michal P\v{e}chou\v{c}ek},
  title = {Multi-agent {RRT*}: Sampling-based Cooperative Pathfinding (Extended Abstract)},
  booktitle = {Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, {AAMAS'13}},
  year = {2013},
  }