Document Open Access Logo

Efficiently Reconfiguring a Connected Swarm of Labeled Robots

Authors Sándor P. Fekete , Peter Kramer , Christian Rieck , Christian Scheffer , Arne Schmidt

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.17.pdf
  • Filesize: 0.85 MB
  • 15 pages

Document Identifiers

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Peter Kramer
  • Department of Computer Science, TU Braunschweig, Germany
Christian Rieck
  • Department of Computer Science, TU Braunschweig, Germany
Christian Scheffer
  • Faculty of Electrical Engineering and Computer Science, Bochum University of Applied Sciences, Germany
Arne Schmidt
  • Department of Computer Science, TU Braunschweig, Germany

Cite As Get BibTex

Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently Reconfiguring a Connected Swarm of Labeled Robots. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.17

Abstract

When considering motion planning for a swarm of n labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, the total duration of an overall schedule can be bounded to 𝒪(d), which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots.
We resolve these major open problems by (1) establishing a lower bound of Ω(√n) for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Computing methodologies → Motion path planning
Keywords
  • Motion planning
  • parallel motion
  • bounded stretch
  • makespan
  • connectivity
  • swarm robotics

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. Transactions on Automation Science and Engineering, 12(4):1309-1317, 2015. URL: https://doi.org/10.1109/TASE.2015.2470096.
  2. Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, and Vera Sacristán. Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers. Algorithmica, 83(5):1316-1351, 2021. URL: https://doi.org/10.1007/s00453-020-00784-6.
  3. Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting squares: Input-sensitive in-place reconfiguration of sliding squares. In Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 4:1-4:19, 2022. URL: https://doi.org/10.4230/LIPIcs.SWAT.2022.4.
  4. Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated motion planning: The video. In Symposium on Computational Geometry (SoCG), pages 74:1-74:6, 2018. Video at https://www.ibr.cs.tu-bs.de/users/fekete/Videos/CoordinatedMotionPlanning.mp4. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.74.
  5. Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms. In Symposium on Computational Geometry (SoCG), pages 65:1-65:6, 2022. URL: https://doi.org/10.4230/LIPIcs.SoCG.2022.65.
  6. Gruia Călinescu, Adrian Dumitrescu, and János Pach. Reconfigurations in graphs and grids. SIAM Journal on Discrete Mathematics, 22(1):124-138, 2008. URL: https://doi.org/10.1137/060652063.
  7. Soon-Jo Chung, Aditya Avinash Paranjape, Philip Dames, Shaojie Shen, and Vijay Kumar. A survey on aerial swarm robotics. IEEE Transactions on Robotics, 34(4):837-855, 2018. URL: https://doi.org/10.1109/TRO.2018.2857475.
  8. Loïc Crombez, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks approach to low-makespan coordinated motion planning. In Symposium on Computational Geometry (SoCG), pages 63:1-63:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.63.
  9. Daniel Delahaye, Stéphane Puechmorel, Panagiotis Tsiotras, and Eric Féron. Mathematical models for aircraft trajectory design: A survey. In Air Traffic Management and Systems, pages 205-247. Springer, 2014. URL: https://doi.org/10.1007/978-4-431-54475-3_12.
  10. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane Souvaine. Staged self-assembly: Nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 7(3):347-370, 2008. URL: https://doi.org/10.1007/s11047-008-9073-0.
  11. Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6):1727-1762, 2019. URL: https://doi.org/10.1137/18M1194341.
  12. Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt. New geometric algorithms for fully connected staged self-assembly. Theoretical Computer Science, 671:4-18, 2017. URL: https://doi.org/10.1016/j.tcs.2016.11.020.
  13. Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Self-assembly of arbitrary shapes using RNAse enzymes: Meeting the Kolmogorov bound with small scale factor. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 201-212, 2011. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.201.
  14. Adrian Dumitrescu and János Pach. Pushing squares around. Graphs and Combinatorics, 22(1):37-50, 2006. URL: https://doi.org/10.1007/s00373-005-0640-1.
  15. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Formations for fast locomotion of metamorphic robotic systems. International Journal of Robotics Research, 23(6):583-593, 2004. URL: https://doi.org/10.1177/0278364904039652.
  16. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration. Transactions on Robotics, 20(3):409-418, 2004. URL: https://doi.org/10.1109/TRA.2004.824936.
  17. Sándor P. Fekete, Björn Hendriks, Christopher Tessars, Axel Wegener, Horst Hellbrück, Stefan Fischer, and Sebastian Ebers. Methods for improving the flow of traffic. In Organic Computing - A Paradigm Shift for Complex Systems. Springer, 2011. URL: https://doi.org/10.1007/978-3-0348-0130-0_29.
  18. Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected coordinated motion planning with bounded stretch. In International Symposium on Algorithms and Computation (ISAAC), pages 9:1-9:16, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.9.
  19. Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing coordinated motion plans for robot swarms: The CG:SHOP Challenge 2021, 2021. URL: http://arxiv.org/abs/2103.15381.
  20. Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently reconfiguring a connected swarm of labeled robots, 2022. URL: http://arxiv.org/abs/2209.11028.
  21. Lester R. Ford and Delbert R. Fulkerson. Flows in networks. Princeton University Press, 1962. Google Scholar
  22. Seth C. Goldstein and Todd C. Mowry. Claytronics: A scalable basis for future robots, 2004. URL: http://www.cs.cmu.edu/~claytronics/papers/goldstein-robosphere04.pdf.
  23. Stephen Kloder and Seth Hutchinson. Path planning for permutation-invariant multi-robot formations. IEEE Transactions on Robotics and Automation, 22(4):650-665, 2006. URL: https://doi.org/10.1109/TRO.2006.878952.
  24. Bernhard H. Korte and Jens Vygen. Combinatorial optimization. Springer, 2011. Google Scholar
  25. Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Coordinated motion planning through randomized k-opt. In Symposium on Computational Geometry (SoCG), pages 64:1-64:8, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.64.
  26. Austin Luchsinger, Robert T. Schweller, and Tim Wylie. Self-assembly of shapes at constant scale using repulsive forces. Natural Computing, 18(1):93-105, 2019. URL: https://doi.org/10.1007/s11047-018-9707-9.
  27. Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795-799, 2014. URL: https://doi.org/10.1126/science.1254295.
  28. Erol Şahin and Alan F. T. Winfield. Special issue on swarm robotics. Swarm Intelligence, 2(2-4):69-72, 2008. URL: https://doi.org/10.1007/s11721-008-0020-6.
  29. Michael Schreckenberg and Reinhard Selten. Human Behaviour and Traffic Networks. Springer, 2013. URL: https://doi.org/10.1007/978-3-662-07809-9.
  30. 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. International Journal of Robotics Research, 2(3):46-75, 1983. URL: https://doi.org/10.1177/027836498300200304.
  31. David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. URL: https://doi.org/10.1137/S0097539704446712.
  32. Kiril Solovey and Dan Halperin. k-color multi-robot motion planning. International Journal of Robotics Research, 33(1):82-97, 2014. URL: https://doi.org/10.1177/0278364913506268.
  33. Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. International Journal of Robotics Research, 35(14):1750-1759, 2016. URL: https://doi.org/10.1177/0278364916672311.
  34. Kiril Solovey, Jingjin Yu, Or Zamir, and Dan Halperin. Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and Systems, 2015. URL: https://doi.org/10.15607/RSS.2015.XI.011.
  35. Matthew Turpin, Nathan Michael, and Vijay Kumar. Trajectory planning and assignment in multirobot systems. In Algorithmic Foundations of Robotics X - Workshop on the Algorithmic Foundations of Robotics (WAFR), pages 175-190. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36279-8_11.
  36. Matthew Turpin, Kartik Mohta, Nathan Michael, and Vijay Kumar. Goal assignment and trajectory planning for large teams of interchangeable robots. Autonomous Robots, 37(4):401-415, 2014. URL: https://doi.org/10.1007/s10514-014-9412-1.
  37. Hyeyun Yang and Antoine Vigneron. A simulated annealing approach to coordinated motion planning. In Symposium on Computational Geometry (SoCG), pages 65:1-65:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.65.
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