Centralized and Decentralized Algorithms for Multi-Robot Trajectory Coordination

摘要

One of the standing challenges in multi-robot systems is how to reliably avoid collisions among
\nindividual robots without jeopardizing the mission of the system. This is because the existing collisionavoidance
\ntechniques are either prone to deadlocks, i.e., the robots may never reach their desired goal
\nposition, or computationally intractable, i.e., the solution may not be provided in practical time. We
\nstudy whether it is possible to design a method for collision avoidance in multi-robot systems that is
\nboth deadlock-free and computationally tractable. The central results of our work are 1) the observation
\nthat in appropriately structured environments deadlock-free and computationally tractable collision
\navoidance is, in fact, possible to achieve and 2) consequently we propose practical, yet guaranteed,
\ncentralized and decentralized algorithms for collision avoidance in multi-robot systems.
\nWe take the deliberative approach, i.e., coordinated collision-free trajectories are first computed
\neither by a central motion planner or by decentralized negotiation among the robots and then each robot
\ncontrols its advancement along its planned trajectory. We start by reviewing the existing techniques in
\nboth single- and multi-robot motion planning, identify their limitations, and subsequently design new
\ncentralized and decentralized trajectory coordination algorithms for different use cases.
\nFirstly, we prove that a revised version of the classical prioritized planning technique, which may
\nnot return a solution in general, is guaranteed to always return a solution in polynomial time under
\ncertain conditions that we characterize. Specifically, it is guaranteed to provide a solution if the start and
\ndestination of each coordinated robot is an endpoint of a so-called well-formed infrastructure. That is,
\nit can be reliably used in systems where the robots at start and destination positions do not prevent other
\nrobots from reaching their goals, which, notably, is a property satisfied in most man-made environments.
\nSecondly, we design an asynchronous decentralized variant of both classical and revised prioritized
\nplanning that can be used to find coordinated trajectories solely by peer-to-peer message passing among
\nthe robots. The method inherits guarantees from its centralized version, but can compute the solution
\nfaster by exploiting the computational power distributed across multi-robot team.
\nThirdly, in contrast to the above algorithms that coordinate robots in a batch, we design a decentralized
\nalgorithm that can coordinate the robots in the systems incrementally. That is, the robots may
\nbe ordered to relocate at any time during the operation of the system. We prove that if the robots are
\ntasked to relocate between endpoints of a well-formed infrastructure, then the algorithm is guaranteed
\nto always find a collision-free trajectory for each relocation task in quadratic time.
\nFourthly, we show that incremental replanning of trajectories of individual robots while they are
\nsubject to gradually increasing collision penalty can serve as a powerful heuristic that is able to generate
\nnear-optimal solutions.
\nFinally, we design a novel control law for controlling the advancement of individual robots in the
\nteam along their planned trajectories in the presence of delaying disturbances, e.g., humans stepping in
\nthe way of robots. While naive control strategies for handling the disturbances may lead to deadlocks,
\nwe prove that under the proposed control law, the robots are guaranteed to always reach their destination.
\nWe evaluate the presented techniques both in synthetic simulated environments as well as in realworld
\nfield experiments. In simulation experiments with up to 60 robots, we observe that the proposed
\ntechnique ge