Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots
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 trajector...
Published in: | IEEE Transactions on Automation Science and Engineering |
---|---|
Main Authors: | , , , |
Format: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
IEEE
2015
|
Subjects: | |
Online Access: | https://authors.library.caltech.edu/59802/ https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348 |
id |
ftcaltechauth:oai:authors.library.caltech.edu:59802 |
---|---|
record_format |
openpolar |
spelling |
ftcaltechauth:oai:authors.library.caltech.edu:59802 2023-05-15T17:53:56+02:00 Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots Čáp, Michal Novák, Peter Kleiner, Alexander Selecký, Martin 2015-07 https://authors.library.caltech.edu/59802/ https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348 unknown IEEE Čá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. doi:10.1109/TASE.2015.2445780. https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348 <https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348> Article PeerReviewed 2015 ftcaltechauth https://doi.org/10.1109/TASE.2015.2445780 2021-11-11T19:05:39Z 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. Article in Journal/Newspaper Orca Caltech Authors (California Institute of Technology) IEEE Transactions on Automation Science and Engineering 12 3 835 849 |
institution |
Open Polar |
collection |
Caltech Authors (California Institute of Technology) |
op_collection_id |
ftcaltechauth |
language |
unknown |
description |
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. |
format |
Article in Journal/Newspaper |
author |
Čáp, Michal Novák, Peter Kleiner, Alexander Selecký, Martin |
spellingShingle |
Čáp, Michal Novák, Peter Kleiner, Alexander Selecký, Martin Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
author_facet |
Čáp, Michal Novák, Peter Kleiner, Alexander Selecký, Martin |
author_sort |
Čáp, Michal |
title |
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
title_short |
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
title_full |
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
title_fullStr |
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
title_full_unstemmed |
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots |
title_sort |
prioritized planning algorithms for trajectory coordination of multiple mobile robots |
publisher |
IEEE |
publishDate |
2015 |
url |
https://authors.library.caltech.edu/59802/ https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348 |
genre |
Orca |
genre_facet |
Orca |
op_relation |
Čá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. doi:10.1109/TASE.2015.2445780. https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348 <https://resolver.caltech.edu/CaltechAUTHORS:20150821-081625348> |
op_doi |
https://doi.org/10.1109/TASE.2015.2445780 |
container_title |
IEEE Transactions on Automation Science and Engineering |
container_volume |
12 |
container_issue |
3 |
container_start_page |
835 |
op_container_end_page |
849 |
_version_ |
1766161649562025984 |