Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots

Abstract

In autonomous multirobot systems one of the concerns is how to prevent collisions between the individual robots. One approach to this problem involves finding coordinated trajectories from start to destination for all the robots and then letting the robots follow the preplanned coordinated trajectories. A widely used practical method for finding such coordinated trajectories is “classical” prioritized planning, where robots plan sequentially one after another. This method has been shown to be effective in practice, but it is incomplete (i.e., there are solvable problem instances that the algorithm fails to solve) and it has not yet been formally analyzed under what circumstances is the method guaranteed to succeed. Further, prioritized planning is a centralized algorithm, which makes the method unsuitable for decentralized multirobot systems. The contributions of this paper are: a) an adapted version of classical prioritized planning called revised prioritized planning with a formal characterization of a class of instances that are provably solvable by this algorithm and b) an asynchronous decentralized variant of both classical and revised prioritized planning together with a formal analysis showing that the algorithm terminates and inherits completeness properties from its centralized counterpart. The experimental evaluation performed in simulation on realworld indoor maps shows that: a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized implementation of classical and revised prioritized planning finds solution in large multirobot teams up to 2x-faster than the previously proposed synchronized decentralized approach. Note to Practitioners-Consider a large warehouse in which the goods are stored and retrieved by autonomous mobile robots. One way to deal with possible collisions between the robots is to ignore interactions between the vehicles during the route planning for each robot and handle the conflicts only during the route execution. However, such an approach is prone to deadlocks, i.e., to situations during which some of the robots mutually block each other, cannot proceed and fail to complete their transportation task. An alternative approach would involve planning collision-free routes for each robot before the robots start executing them. However, the current methods that guarantee ability to find a solution to any such coordination problem are not applicable in practice due to their high computational complexity. Instead, a simple and computationally efficient approach in which robots plan their routes sequentially one after another (classical prioritized planning) is often used for finding coordinated trajectories even though the algorithm is known to fail on many dense problem instances. In this paper, we show that a simple adaptation of this classical algorithm called revised prioritized planning is guaranteed to find collision-free trajectories for a well-defined class of practical problems. In particular, if the system resembles human-made transport infrastructures by requiring that the start and destination position of each vehicle must never obstruct other vehicles from moving, then the proposed approach is guaranteed to provide a solution. For instance, in our warehouse multirobot system example, the collision-free routes can be efficiently computed by the revised prioritized planning approach. This paper formally characterizes the problem instances for which the method is guaranteed to succeed. Further, we propose a new asynchronous decentralized adaptation of both classical and revised prioritized algorithm that can be used in multirobot systems without a central solver. This technique can be used to find coordinated trajectories just by running a simple asynchronous negotiation protocol between the individual robots. This paper provides an analysis showing that the asynchronous decentralized implementations of classical and revised prioritized planning exhibit desirable theoretical properties and an experimental comparison of performance of different variations of centralized and decentralized prioritized planning algorithms.