Fast Planning for Multiple Robots


Planning is a crucial component in robotic systems. Nevertheless, the state-of-the art algorithms do not perform well in realistic conditions for robot groups. On the one hand, sampling or graph based methods which operate in joint space suffer from the dimensionality explosion. On the other hand, planners which try to avoid that effect make simplifying assumptions, limiting its practical applications.

We investigate planning algorithms which work in realistic conditions (that is kinematic constraints and imperfect plan execution) for robot groups. Because there is always the possibility that a single robot fails, such plans need to be either be computable in a very short amount of time or it needs to be possible to update them online.

The following video shows an example of a motion planning problem. The robots need to swap sides, but there is only a small corridor available. Nevertheless, we want to find a motion plan for each robot such that the overal swapping time is minimal (or within a specifiable factor away from the optimum).


In collaboration with the Intelligent Decision Making Laboratory (IDM Lab).

  • Wolfgang Hönig
  • T. K. Satish Kumar
  • Liron Cohen (IDM Lab)
  • Hang Ma (IDM Lab)
  • Hong Xu (IDM Lab)
  • Sven Koenig (IDM Lab)
  • Nora Ayanian

Related Publications

  • W. Hönig, T. K. S. Kumar, H. Ma, S. Koenig, and N. Ayanian "Formation change for robot groups in occluded environments", in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2016. Accepted, to appear.
    [ PDF Preprint, Video, BibTeX ]
  • H. Ma, S. Koenig, N. Ayanian, L. Cohen, W. Hönig, T. K. S. Kumar, T. Uras, H. Xu, C. Tovey, and G. Sharon. "Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios", in IJCAI-16 Workshop on Multi-Agent Path Finding (WOMPF), New York City, NY, July 2016.
    [ PDF Preprint ]
  • W. Hönig, T. K. S. Kumar, L. Cohen, H. Ma, S. Koenig, and N. Ayanian. "Path Planning With Kinematic Constraints For Robot Groups", in Southern California Robotics Symposium (SCR), San Diego, CA, April 2016.
    [ PDF Preprint ]
  • W. Hönig, T. K. S. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig. "Multi-Agent Path Finding with Kinematic Contraints", in International Conference on Automated Planning and Scheduling, London, U.K., June 2016.
    [ PDF Preprint, Video, BibTeX ]