publication . Part of book or chapter of book . Preprint . 2019

On Randomized Searching for Multi-robot Coordination

Jakub Hvezda; Miroslav Kulich; Libor Preucil;
Open Access English
  • Published: 26 Oct 2019
Abstract
In this chapter, we propose a novel approach for solving the coordination of a fleet of mobile robots, which consists of finding a set of collision-free trajectories for individual robots in the fleet. This problem is studied for several decades, and many approaches have been introduced. However, only a small minority is applicable in practice because of their properties - small computational requirement, producing solutions near-optimum, and completeness. The approach we present is based on a multi-robot variant of Rapidly Exploring Random Tree algorithm (RRT) for discrete environments and significantly improves its performance. Although the solutions generated...
Persistent Identifiers
Subjects
free text keywords: Computer Science - Robotics, Robot, Mobile robot, Theoretical computer science, Computer science, Completeness (statistics), Slightly worse, Rapidly exploring random tree
Funded by
EC| SafeLog
Project
SafeLog
Safe human-robot interaction in logistic applications for highly flexible warehouses
  • Funder: European Commission (EC)
  • Project Code: 688117
  • Funding stream: H2020 | RIA
Validated by funder
Download fromView all 4 versions
Open Access
http://arxiv.org/pdf/2007.1002...
Part of book or chapter of book
Provider: UnpayWall
Open Access
ZENODO
Part of book or chapter of book . 2019
Provider: ZENODO
null
Lecture Notes in Electrical Engineering
Part of book or chapter of book
Provider: Sygma
38 references, page 1 of 3

1. Bennewitz, M., Burgard, W., Thrun, S.: Optimizing schedules for prioritized path planning of multi-robot systems. In: Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on. pp. 271 - 276 vol.1 (2001)

2. van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 430-435. IEEE (2005)

3. van den Berg, J., Snoeyink, J., Lin, M.C., Manocha, D.: Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In: Trinkle, J., Matsuoka, Y., Castellanos, J.A. (eds.) Robotics: Science and Systems V, University of Washington, Seattle, USA, June 28 - July 1, 2009. The MIT Press (2009)

4. Cap, M., Novak, P., Kleiner, A., Selecky, M., Pechoucek, M.: Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots. IEEE Transactions on Automation Science and Engineering Special Is (2015)

5. Chiew, K.: Scheduling and routing of autonomous moving objects on a mesh topology. Operational Research 12(3), 385-397 (Nov 2010) [OpenAIRE]

6. DeWilde, B., Ter Mors, A., Witteveen, C.: Push and Rotate: A complete Multi-agent Pathfinding algorithm. Journal of Artificial Intelligence Research 51, 443-492 (2014)

7. Dobson, A., Solovey, K., Shome, R., Halperin, D., Bekris, K.E.: Scalable asymptoticallyoptimal multi-robot motion planning. In: 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS). pp. 120-127 (Dec 2017)

8. Doriya, R., Mishra, S., Gupta, S.: A brief survey and analysis of multi-robot communication and coordination. In: International Conference on Computing, Communication Automation. pp. 1014-1021 (May 2015) [OpenAIRE]

9. Gawrilow, E., Ko¨hler, E., Mo¨hring, R.H., Stenzel, B.: Dynamic Routing of Automated Guided Vehicles in Real-time, pp. 165-177. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)

10. Geramifard, A., Chubak, P., Bulitko, V.: Biased Cost Pathfinding. In: AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. pp. 112-114 (2006)

11. Goldreich, O.: Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron,, Lecture Notes in Computer Science, vol. 6650, pp. 1-5. Springer (2011)

12. Hopcroft, J., Schwartz, J., Sharir, M.: On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the ”Warehouseman's Problem”. The International Journal of Robotics Research 3(4), 76-88 (Dec 1984)

13. Hveˇzda, J., Kulich, M., Prˇeucˇil, L.: Improved discrete rrt for coordinated multi-robot planning. In: Proceedings of the 15th International Conference on Informatics in Control, Automation and Robotics, ICINCO 2018 - Volume 2. pp. 181-189 (2018)

14. Hveˇzda, J., Rybeck y´, T., Kulich, M., Prˇeucˇil, L.: Context-aware route planning for automated warehouses. In: 21st IEEE International Conference on Intelligent Transportation Systems (in press)

15. Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. CoRR abs/1005.0416 (2010) [OpenAIRE]

38 references, page 1 of 3
Related research
Abstract
In this chapter, we propose a novel approach for solving the coordination of a fleet of mobile robots, which consists of finding a set of collision-free trajectories for individual robots in the fleet. This problem is studied for several decades, and many approaches have been introduced. However, only a small minority is applicable in practice because of their properties - small computational requirement, producing solutions near-optimum, and completeness. The approach we present is based on a multi-robot variant of Rapidly Exploring Random Tree algorithm (RRT) for discrete environments and significantly improves its performance. Although the solutions generated...
Persistent Identifiers
Subjects
free text keywords: Computer Science - Robotics, Robot, Mobile robot, Theoretical computer science, Computer science, Completeness (statistics), Slightly worse, Rapidly exploring random tree
Funded by
EC| SafeLog
Project
SafeLog
Safe human-robot interaction in logistic applications for highly flexible warehouses
  • Funder: European Commission (EC)
  • Project Code: 688117
  • Funding stream: H2020 | RIA
Validated by funder
Download fromView all 4 versions
Open Access
http://arxiv.org/pdf/2007.1002...
Part of book or chapter of book
Provider: UnpayWall
Open Access
ZENODO
Part of book or chapter of book . 2019
Provider: ZENODO
null
Lecture Notes in Electrical Engineering
Part of book or chapter of book
Provider: Sygma
38 references, page 1 of 3

1. Bennewitz, M., Burgard, W., Thrun, S.: Optimizing schedules for prioritized path planning of multi-robot systems. In: Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on. pp. 271 - 276 vol.1 (2001)

2. van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 430-435. IEEE (2005)

3. van den Berg, J., Snoeyink, J., Lin, M.C., Manocha, D.: Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In: Trinkle, J., Matsuoka, Y., Castellanos, J.A. (eds.) Robotics: Science and Systems V, University of Washington, Seattle, USA, June 28 - July 1, 2009. The MIT Press (2009)

4. Cap, M., Novak, P., Kleiner, A., Selecky, M., Pechoucek, M.: Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots. IEEE Transactions on Automation Science and Engineering Special Is (2015)

5. Chiew, K.: Scheduling and routing of autonomous moving objects on a mesh topology. Operational Research 12(3), 385-397 (Nov 2010) [OpenAIRE]

6. DeWilde, B., Ter Mors, A., Witteveen, C.: Push and Rotate: A complete Multi-agent Pathfinding algorithm. Journal of Artificial Intelligence Research 51, 443-492 (2014)

7. Dobson, A., Solovey, K., Shome, R., Halperin, D., Bekris, K.E.: Scalable asymptoticallyoptimal multi-robot motion planning. In: 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS). pp. 120-127 (Dec 2017)

8. Doriya, R., Mishra, S., Gupta, S.: A brief survey and analysis of multi-robot communication and coordination. In: International Conference on Computing, Communication Automation. pp. 1014-1021 (May 2015) [OpenAIRE]

9. Gawrilow, E., Ko¨hler, E., Mo¨hring, R.H., Stenzel, B.: Dynamic Routing of Automated Guided Vehicles in Real-time, pp. 165-177. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)

10. Geramifard, A., Chubak, P., Bulitko, V.: Biased Cost Pathfinding. In: AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. pp. 112-114 (2006)

11. Goldreich, O.: Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron,, Lecture Notes in Computer Science, vol. 6650, pp. 1-5. Springer (2011)

12. Hopcroft, J., Schwartz, J., Sharir, M.: On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the ”Warehouseman's Problem”. The International Journal of Robotics Research 3(4), 76-88 (Dec 1984)

13. Hveˇzda, J., Kulich, M., Prˇeucˇil, L.: Improved discrete rrt for coordinated multi-robot planning. In: Proceedings of the 15th International Conference on Informatics in Control, Automation and Robotics, ICINCO 2018 - Volume 2. pp. 181-189 (2018)

14. Hveˇzda, J., Rybeck y´, T., Kulich, M., Prˇeucˇil, L.: Context-aware route planning for automated warehouses. In: 21st IEEE International Conference on Intelligent Transportation Systems (in press)

15. Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. CoRR abs/1005.0416 (2010) [OpenAIRE]

38 references, page 1 of 3
Related research
Any information missing or wrong?Report an Issue