Centralized and Decentralized Algorithms for Multi-Robot Trajectory Coordination

Doctoral Thesis

Michal Čáp, Msc.
Artificial Intelligence Center,
Dept. of Computer Science,
Faculty of Electrical Engineering,
CTU in Prague

Supervisor: Prof. Dr. Michal Pěchouček, MSc.
Co-supervisor: Dr. rer. nat. Peter Novák

Fultext: [PDF] Download as PDF


One of the standing challenges in multi-robot systems is how to reliably avoid collisions among individual robots without jeopardizing the mission of the system. This is because the existing collision-avoidance techniques are either prone to deadlocks, i.e., the robots may never reach their desired goal position, or computationally intractable, i.e., the solution may not be provided in practical time. We study whether it is possible to design a method for collision avoidance in multi-robot systems that is both deadlock-free and computationally tractable. The central results of our work are 1) the observation that in appropriately structured environments deadlock-free and computationally tractable collision avoidance is, in fact, possible to achieve and 2) consequently we propose practical, yet guaranteed, centralized and decentralized algorithms for collision avoidance in multi-robot systems.

We take the deliberative approach, i.e., coordinated collision-free trajectories are first computed either by a central motion planner or by decentralized negotiation among the robots and then each robot controls its advancement along its planned trajectory. We start by reviewing the existing techniques in both single- and multi-robot motion planning, identify their limitations, and subsequently design new centralized and decentralized trajectory coordination algorithms for different use cases.

Firstly, we prove that a revised version of the classical prioritized planning technique, which may not return a solution in general, is guaranteed to always return a solution in polynomial time under certain conditions that we characterize. Specifically, it is guaranteed to provide a solution if the start and destination of each coordinated robot is an endpoint of a so-called well-formed infrastructure. That is, it can be reliably used in systems where the robots at start and destination positions do not prevent other robots from reaching their goals, which, notably, is a property satisfied in most man-made environments.

Secondly, we design an asynchronous decentralized variant of both classical and revised prioritized planning that can be used to find coordinated trajectories solely by peer-to-peer message passing among the robots. The method inherits guarantees from its centralized version, but can compute the solution faster by exploiting the computational power distributed across multi-robot team.

Thirdly, in contrast to the above algorithms that coordinate robots in a batch, we design a decentralized algorithm that can coordinate the robots in the systems incrementally. That is, the robots may be ordered to relocate at any time during the operation of the system. We prove that if the robots are tasked to relocate between endpoints of a well-formed infrastructure, then the algorithm is guaranteed to always find a collision-free trajectory for each relocation task in quadratic time.

Fourthly, we show that incremental replanning of trajectories of individual robots while they are subject to gradually increasing collision penalty can serve as a powerful heuristic that is able to generate near-optimal solutions.

Finally, we design a novel control law for controlling the advancement of individual robots in the team along their planned trajectories in the presence of delaying disturbances, e.g., humans stepping in the way of robots. While naive control strategies for handling the disturbances may lead to deadlocks, we prove that under the proposed control law, the robots are guaranteed to always reach their destination.

We evaluate the presented techniques both in synthetic simulated environments as well as in real-world field experiments. In simulation experiments with up to 60 robots, we observe that the proposed technique generates shorter motions than state-of-the-art reactive collision avoidance techniques and reliably solves also the instances where reactive techniques fail. Further, unlike many proposed coordination techniques, we validate the assumptions of our algorithms and the consequent practical applicability of our approach by implementing and testing proposed coordination approach in two real-world multi-robot systems. In particular, we successfully deployed and field tested asynchronous decentralized prioritized planning as a collision avoidance mechanism in 1) a Multi-UAV system with fixed-wing unmanned aircraft and 2) an experimental mobility-on-demand system using self-driving golf carts.

Selected Results


  • Characterization of a polynomially-solvable fragment of otherwise intractable multi-robot trajectory coordination problem.
  • Notion of well-formed infrastructures: One can design the operational environment of a multi-robot system such that the coordinated trajectories for the robots can be always effeciently computed.
  • Design of new centralized and decentralized trajectory coordination algorithms. Rigorous analysis of their computational complexity and proof of completeness in well-formed infrastructures.
  • Synthesis of a provably deadlock-free policy for execution of multi-robot trajectories in environments shared with people, or with other disturbances that may delay the robots' progress along the computed plan.


  • The proposed algorithms are more scalable than existing complete techniques.
  • The proposed algorithms are more relibable and generate higher-quality trajectories than existing reactive (incomplete) techniques.

Advancement over State of the Art

A practically-applicable multi-robot coordination method should be general, guaranteed, tractable, provide solutions of acceptable quality, and suit decentralized systems. The following table summarizes the properties of existing multi-robot coordination methods - note that there is no method that offers all those desirable properties. We advance the state of the art by designing a method that, in appropriately structured environments, exhibits all the desirable properties:


The proposed method has been successfully applied as a multi-robot coordination technique in two field-deployed autonomous robotic systems:

An experimental mobility-on-demand system with self-driving vehicles.

Watch video

A multi-UAV system providing situational awareness in tactical missions.

Watch video


Below, we list the publications of the author that are relevant to the topic of the thesis. The citation counts were obtained using Google Scholar on Feb 16, 2018.


  • [DOI]J. Gregoire*, M. Čáp*, and E. Frazzoli, “Locally-optimal multi-robot navigation under delaying disturbances using homotopy constraints,” Autonomous robots, 2017.
    IF: 2.7, in press; Video Codebase
    * equal contribution
  • [PDF] [DOI] B. Paden*, M. Čáp*, S. Z. Yong, D. Yershov, and E. Frazzoli, “A survey of motion planning and control techniques for self-driving urban vehicles,” IEEE transactions on intelligent vehicles, vol. 1, iss. 1, pp. 33-55, 2016.
    77 citations
    (Published as an opening article in the first issue of a newly estabilished IEEE journal. It has not been assigned impact factor yet.)
    * equal contribution
  • [PDF] [DOI] M. Čáp, P. Novák, A. Kleiner, and M. Selecký, “Prioritized planning algorithms for trajectory coordination of multiple mobile robots,” IEEE transactions on automation science and engineering, vol. 12, iss. 3, pp. 835-849, 2015.
    IF: 3.50, 28 citations; Webpage Video Codebase
  • [PDF] A. Komenda, J. Vokřínek, M. Čáp, and M. Pěchouček, “Developing multiagent algorithms for tactical missions using simulation,” Intelligent Systems, IEEE, vol. 28, iss. 1, pp. 42-49, 2013.
    IF: 2.37, 17 citations
  • [PDF] [DOI] M. Jakob, M. Pechoucek, M. Cap, P. Novak, and O. Vanek, “Mixed-reality testbeds for incremental development of HART applications,” Intelligent Systems, IEEE, vol. 27, iss. 2, pp. 19-25, 2012.
    IF: 2.37, 19 citations

Book chapters

  • [PDF] P. Novák, A. Komenda, M. Čáp, J. Vokřínek, and M. Pěchouček, “Simulated multi-robot tactical missions in urban warfare,” in Multiagent systems and applications, Springer, 2012, pp. 147-183.
    2 citations


  • [PDF] L. Paull, J. Tani, H. Ahn, J. Alonso-Mora, L. Carlone, M. Cap, Y. F. Chen, C. Choi, J. Dusek, D. Hoehener, S. Liu, M. Novitzky, I. F. Okuyama, J. Pazis, G. Rosman, V. Varricchio, H. Wang, D. Yershov, H. Zhao, M. Benjamin, C. Carr, M. Zuber, S. Karaman, E. Frazzoli, D. D. Vecchio, D. Rus, J. How, J. Leonard, and A. Censi, “Duckietown: an open and inexpensive and flexible platform for autonomy education and research,” in IEEE International Conference on Robotics and Automation (ICRA 2017), Singapore, 2017.
    8 citations; Webpage
  • [PDF] M. Čáp*, J. Gregoire*, and E. Frazzoli, “Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances,” in Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2016), 2016.
    2 citations; Video Codebase
    * equal contribution
  • [PDF] M. Čáp, J. Vokřínek, and A. Kleiner, “Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures,” in Proceedings of the twenty-fifth international conference on automated planning and scheduling, ICAPS 2015, jerusalem, israel, june 7-11, 2015., 2015, pp. 324-332.
    6 citations; Webpage Video Slides Codebase
  • [PDF] P. Janovský*, M. Čáp*, and J. Vokřínek, “Finding coordinated paths for multiple holonomic robots in 2d polygonal environment,” in International conference on autonomous agents and multiagent systems, AAMAS’14, 2014.
    4 citations; Webpage
    * equal contribution
  • [PDF] M. Čáp, P. Novák, M. Selecký, J. Faigl, and J. Vokřínek, “Asynchronous decentralized prioritized planning for coordination in multi-robot system,” in Intelligent robots and systems (IROS), 2013, 2013.
    15 citations; Webpage Video Slides
  • [PDF] M. Selecký, M. Štolba, T. Meiser, M. Čáp, A. Komenda, M. Rollo, J. Vokřínek, and M. Pěchouček, “Deployment of multi-agent algorithms for tactical operations on uav hardware (demonstration),” in Proceedings of the 12th international conference on autonomous agents and multiagent systems, AAMAS’13, 2013.
    6 citations
  • [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.
    16 citations


  • [PDF] M. Čáp, P. Novák, and A. Kleiner, “Finding near-optimal solutions in multi-robot trajectory planning,” in Principles of multi-robot systems workshop at robotics: science and systems (RSS) 2015, rome, italy, july 13-17, 2015., 2015.
    Video Poster Codebase
  • [PDF] 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.