Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures
Proceedings of the International Conference on Automated Planning and Scheduling · 08.04.2015 · 25 · 324-332
DOI: 10.1609/icaps.v25i1.13696 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.04.2015. Verfasst von Michal Čáp und 2 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref).
Abstract (Originalsprache)
We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if the destination of each task is an endpoint in a so-called well-formed infrastructure, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without any collisions. The time-complexity of the approach is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that reach the goal significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.
Zitieren
APA
Čáp, M., Vokřínek, J., & Kleiner, A. (2015). Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures. Proceedings of the International Conference on Automated Planning and Scheduling, 25, 324-332. https://doi.org/10.1609/icaps.v25i1.13696
Vancouver
Čáp M, Vokřínek J, Kleiner A. Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures. Proceedings of the International Conference on Automated Planning and Scheduling. 2015;25:324-332. doi:10.1609/icaps.v25i1.13696
BibTeX
@article{p2015,
author = {Čáp, Michal and Vokřínek, Jiří and Kleiner, Alexander},
title = {Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2015},
volume = {25},
pages = {324--332},
doi = {10.1609/icaps.v25i1.13696}
}
EUVIMED