A Caltech Library Service

Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots

Čáp, Michal and Novák, Peter and Kleiner, Alexander and Selecký, Martin (2015) Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots. IEEE Transactions on Automation Science and Engineering, 12 (3). pp. 835-849. ISSN 1545-5955.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2015 IEEE. Manuscript received August 31, 2014; revised January 06, 2015, May 06, 2015, and May 20, 2015; accepted May 21, 2015. Date of publication June 29, 2015; date of current version July 17, 2015. This paper was recommended for publication by Associate Editor F. Ehlers and Editor L. Sabattini upon evaluation of the reviewers’ comments. This work was supported in part by the Czech Science Foundation under Grant 13-22125S) and in part by the Grant Agency of the Czech Technical University in Prague under Grant SGS14/143/OHK3/2T/13. The authors greatly appreciate access to computing and storage facilities owned by parties and projects contributing to the National Grid Infrastructure MetaCentrum, provided under the program “Projects of Large Infrastructure for Research, Development, and Innovations” (LM2010005).
Funding AgencyGrant Number
Czech Science Foundation13-22125S
Czech Technical UniversitySGS14/143/OHK3/2T/13
Issue or Number:3
Record Number:CaltechAUTHORS:20150821-081625348
Persistent URL:
Official Citation:Cap, M.; Novak, P.; Kleiner, A.; Selecky, M., "Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots," Automation Science and Engineering, IEEE Transactions on , vol.12, no.3, pp.835,849, July 2015 doi: 10.1109/TASE.2015.2445780
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:59802
Deposited By: Tony Diaz
Deposited On:21 Aug 2015 18:34
Last Modified:03 Oct 2019 08:50

Repository Staff Only: item control page