Document Open Access Logo

Multi-Robot Motion Planning for Unit Discs with Revolving Areas

Authors Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, Erin Taylor

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.35.pdf
  • Filesize: 1.1 MB
  • 20 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Duke University, Durham NC, USA
Tzvika Geft
  • Tel Aviv University, Israel
Dan Halperin
  • Tel Aviv University, Israel
Erin Taylor
  • Duke University, Durham, NC, USA

Funding

Work by Pankaj K. Agarwal and Erin Taylor is supported by IIS-1814493, CCF-2007556, and CCF-2223870. Work by Dan Halperin and Tzvika Geft has been 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.

Cite AsGet BibTex

Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor. Multi-Robot Motion Planning for Unit Discs with Revolving Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.35

Abstract

We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R' that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1+ε)-approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O(1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O(log n log log n)-approximation algorithm for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • motion planning
  • optimal motion planning
  • approximation
  • complexity
  • NP-hardness

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. IEEE Trans Autom. Sci. Eng., 12(4):1309-1317, 2015. Google Scholar
  2. 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. Google Scholar
  3. Eric Berberich, Dan Halperin, Michael Kerber, and Roza Pogalnikova. Deconstructing approximate offsets. Discret. Comput. Geom., 48(4):964-989, 2012. Google Scholar
  4. Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 rush hour with fixed blocks is pspace-complete. In 10th International Conference on Fun with Algorithms, volume 157, pages 7:1-7:14, 2021. Google Scholar
  5. Danny Z Chen and Haitao Wang. Computing shortest paths among curved obstacles in the plane. ACM Transactions on Algorithms, 11(4):1-46, 2015. Google Scholar
  6. Dror Dayan, Kiril Solovey, Marco Pavone, and Dan Halperin. Near-optimal multi-robot motion planning with finite sampling. In IEEE International Conference on Robotics and Automation, pages 9190-9196, 2021. Google Scholar
  7. 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
  8. Guy Even, J Seffi Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  9. Tzvika Geft and Dan Halperin. On the complexity of a family of decoupled multi-robot motion planning problems, 2021. URL: http://arxiv.org/abs/2104.07011.
  10. Tzvika Geft and Dan Halperin. Refined hardness of distance-optimal multi-agent path finding. In 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 481-488, 2022. Google Scholar
  11. 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
  12. Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7):846-894, 2011. Google Scholar
  13. C O'Ddnlaing and CK Yap. A retraction method for planning the motion of a disc. J. Algorithms, 6:104-111, 1985. Google Scholar
  14. Oren Salzman. Sampling-based robot motion planning. Commun. ACM, 62(10):54-63, 2019. Google Scholar
  15. 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
  16. Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, and Kostas E. Bekris. dRRT^*: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots, 44(3-4):443-467, 2020. Google Scholar
  17. Israela Solomon and Dan Halperin. Motion planning for multiple unit-ball robots in ℝ^d. In Workshop on the Algorithmic Foundations of Robotics, WAFR, pages 799-816, 2018. Google Scholar
  18. Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. Int. J. Robotics Res., 35(14):1750-1759, 2016. Google Scholar
  19. Kiril Solovey, Lucas Janson, Edward Schmerling, Emilio Frazzoli, and Marco Pavone. Revisiting the asymptotic optimality of RRT. In 2020 IEEE International Conference on Robotics and Automation, pages 2189-2195. IEEE, 2020. Google Scholar
  20. Kiril Solovey, Jingjin Yu, Or Zamir, and Dan Halperin. Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and Systems, 2015. Google Scholar
  21. 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 Proc. 12th International Symposium on Combinatorial Search, pages 151-159, 2019. Google Scholar
  22. Matthew Turpin, Kartik Mohta, Nathan Michael, and Vijay Kumar. Goal assignment and trajectory planning for large teams of interchangeable robots. Auton. Robots, 37(4):401-415, 2014. Google Scholar
  23. Vijay V Vazirani. Approximation Algorithms. Springer, 2001. Google Scholar
  24. Chee-Keng Yap. An O(n log n) algorithm for the voronoi diagram of a set of simple curve segments. Discret. Comput. Geom., 2:365-393, 1987. 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 Imprint Privacy Contact