Document Open Access Logo

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Authors Bahareh Banyassady , Mark de Berg , Karl Bringmann, Kevin Buchin , Henning Fernau , Dan Halperin , Irina Kostitsyna , Yoshio Okamoto , Stijn Slot

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.12.pdf
  • Filesize: 0.96 MB
  • 16 pages

Document Identifiers

Author Details

Bahareh Banyassady
  • Zuse Institute Berlin, Germany
Mark de Berg
  • TU Eindhoven, The Netherlands
Karl Bringmann
  • Universität des Saarlandes, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarbrücken, Germany
Kevin Buchin
  • TU Dortmund, Germany
Henning Fernau
  • Universität Trier, Germany
Dan Halperin
  • Tel Aviv University, Israel
Irina Kostitsyna
  • TU Eindhoven, The Netherlands
Yoshio Okamoto
  • The University of Electro-Communications, Tokyo, Japan
Stijn Slot
  • Adyen, Amsterdam, The Netherlands

Funding

  • de Berg, Mark: Supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.
  • Halperin, Dan: Supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University.
  • Okamoto, Yoshio: JSPS KAKENHI Grant Numbers JP20H05795 and JP20K11670.

Acknowledgements

This research was initiated at the Lorentz-Center Workshop on Fixed-Parameter Computational Geometry, 2018. We thank Gerhard Woeginger for discussions during the workshop.

Cite As Get BibTex

Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.12

Abstract

We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end.
If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(n log n + mn + m²) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • motion planning
  • computational geometry
  • simple polygon

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Aviv Adler, Mark de Berg, Dan Halperin, and Kiril Solovey. Efficient multi-robot motion planning for unlabeled discs in simple polygons. In Algorithmic Foundations of Robotics XI, pages 1-17. Springer, 2015. Google Scholar
  2. Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, and Remco J. A. Surtel. Multi-robot motion planning of k-colored discs is PSPACE-hard. In 10th International Conference on Fun with Algorithms (FUN 2021), volume 157 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:16, 2020. Google Scholar
  3. Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia E. Kavraki, and Sebastian Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementation. MIT Press, 2005. Google Scholar
  4. Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Henk Meijer, and Christian Scheffer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6):1727-1762, 2019. Google Scholar
  5. Dan Halperin, Lydia Kavraki, and Kiril Solovey. Robotics. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 51, pages 1343-1376. Chapman & Hall/CRC, 3rd edition, 2018. Google Scholar
  6. Dan Halperin, Micha Sharir, and Oren Salzman. Algorithmic motion planning. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 50, pages 1311-1342. Chapman & Hall/CRC, 3rd edition, 2018. Google Scholar
  7. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343:72-96, 2005. Google Scholar
  8. John E. Hopcroft, Jacob Theodore Schwartz, and Micha Sharir. 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, 1984. Google Scholar
  9. Lydia E. Kavraki, Petr Svestka, Jean-Claude Latombe, and Mark H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996. Google Scholar
  10. Stephen Kloder and Seth Hutchinson. Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics, 22(4):650-665, 2006. Google Scholar
  11. Daniel M. Kornhauser, Gary Miller, and Paul Spirakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. Master’s thesis, MIT, Dept. of Electrical Engineering and Computer Science, 1984. Google Scholar
  12. James J. Kuffner and Steven M. Lavalle. RRT-Connect: An efficient approach to single-query path planning. In IEEE International Conference on Robotics and Automation (ICRA), pages 995-1001, 2000. Google Scholar
  13. Steven M. LaValle. Planning Algorithms. Cambridge University Press, 2006. Google Scholar
  14. Gildardo Sanchez and Jean-Claude Latombe. Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In IEEE International Conference on Robotics and Automation, volume 2, pages 2112-2119. IEEE, 2002. Google Scholar
  15. Jacob T. Schwartz and Micha Sharir. On the "piano movers" problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4(3):298-351, 1983. Google Scholar
  16. Jacob T. Schwartz and Micha Sharir. On the piano movers' problem: III. coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. The International Journal of Robotics Research, 2(3):46-75, 1983. Google Scholar
  17. Micha Sharir and Shmuel Sifrony. Coordinated motion planning for two independent robots. Annals of Mathematics and Artificial Intelligence, 3(1):107-130, 1991. Google Scholar
  18. Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, and Kostas E. Bekris. dRRT^*: Scalable and informed asymptotically-optimal multi-robot motion planning. Autonomous Robots, 44(3-4):443-467, 2020. Google Scholar
  19. Israela Solomon and Dan Halperin. Motion planning for multiple unit-ball robots in ℝ^d. In Marco Morales, Lydia Tapia, Gildardo Sánchez-Ante, and Seth Hutchinson, editors, Proc. 13th Workshop on the Algorithmic Foundations of Robotics, WAFR, volume 14 of Springer Proceedings in Advanced Robotics, pages 799-816. Springer, 2018. Google Scholar
  20. Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. The International Journal of Robotics Research, 35(14):1750-1759, 2016. Google Scholar
  21. Kiril Solovey, Oren Salzman, and Dan Halperin. Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. International Journal of Robotics Research, 35(5):501-513, 2016. Google Scholar
  22. Kiril Solovey, Jingjin Yu, Or Zamir, and Dan Halperin. Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and Systems XI. Robotics: Science and Systems Foundation, 2015. Google Scholar
  23. Paul Spirakis and Chee K. Yap. Strong NP-hardness of moving many discs. Information Processing Letters, 19(1):55-59, 1984. Google Scholar
  24. Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Pavel Surynek and William Yeoh, editors, Proc. 12th International Symposium on Combinatorial Search, SOCS, pages 151-159. AAAI Press, 2019. Google Scholar
  25. Petr Svestka and Mark H. Overmars. Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3):125-152, 1998. Google Scholar
  26. Matthew Turpin, Nathan Michael, and Vijay Kumar. Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In IEEE International Conference on Robotics and Automation, pages 842-848. IEEE, 2013. Google Scholar
  27. Glenn Wagner and Howie Choset. Subdimensional expansion for multirobot path planning. Artificial Intelligence, 219:1-24, 2015. Google Scholar
  28. Chee Yap. Coordinating the motion of several discs. Courant Institute of Mathematical Sciences, 1984. Google Scholar
  29. Jingjin Yu. Constant factor time optimal multi-robot routing on high-dimensional grids. In Hadas Kress-Gazit, Siddhartha S. Srinivasa, Tom Howard, and Nikolay Atanasov, editors, Robotics: Science and Systems XIV, 2018. Google Scholar
  30. Jingjin Yu and Steven M. LaValle. Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics. IEEE Transactions on Robotics, 32(5):1163-1177, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact