Document Open Access Logo

Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines

Authors Joshua Ani, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan Hendrickson, Jayson Lynch

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.5.pdf
  • Filesize: 1.18 MB
  • 21 pages

Document Identifiers

Author Details

Joshua Ani
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Michael Coulombe
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Erik D. Demaine
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Yevhenii Diomidov
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Timothy Gomez
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Dylan Hendrickson
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Jayson Lynch
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA

Cite AsGet BibTex

Joshua Ani, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan Hendrickson, and Jayson Lynch. Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SAND.2023.5

Abstract

We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-planning problems. While past work considers just one robot or one robot per player, most of our models allow for one or more locations to spawn new robots in each time step, leading to arbitrarily many robots. In the 0-player context, where all motion is deterministically forced, we prove that deciding whether any robot ever reaches a specified location is undecidable, by representing a counter machine. In the 1-player context, where the player can choose how to move the robots, we prove equivalence to Petri nets, EXPSPACE-completeness for reaching a specified location, PSPACE-completeness for reconfiguration, and ACKERMANN-completeness for reconfiguration when robots can be destroyed in addition to spawned. Finally, we consider a variation on the standard 2-player context where, instead of one robot per player, we have one robot shared by the players, along with a ko rule to prevent immediately undoing the previous move. We prove this impartial 2-player game EXPTIME-complete.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Gadgets
  • robots
  • undecidability
  • Petri nets

Metrics

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

References

  1. Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dyl an H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Ja yson Lynch, Irene Parada, and Vera Sacristán. Characterizing universal reconfigurability of modular pivoting robots. In Kevin Buchin and Éric Colin de Verdière, editors, Proceedings of the 37th International Symposium on Computational Geometry, LIPIcs, pages 10:1-10:20, 2021. Google Scholar
  2. Robert M. Alaniz, Bin Fu, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert Schweller, and Tim Wylie. Reachability in restricted chemical reaction networks. arXiv preprint, 2022. URL: https://arxiv.org/abs/2211.12603.
  3. Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Walking through doors is hard, even without staircases: Proving PSPACE-hardness via planar assemblies of door gadgets. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), Favignana, Italy, September 2020. Google Scholar
  4. Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing blocks via checkable gadgets: PSPACE-completeness of Push-1F and Block/Box Dude. In Proceedings of the 11th International Conference on Fun with Algorithms, pages 2:1-2:30, Island of Favignana, Sicily, Italy, May-June 2022. Google Scholar
  5. Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, and Jayson Lynch. Traversability, reconfiguration, and reachability in the gadget framework. In Petra Mutzel, Md. Saidur Rahman, and Slamin, editors, Proceedings of the 16th International Conference and Workshops on Algorithms and Computation, volume 13174 of Lecture Notes in Computer Science, pages 47-58, Jember, Indonesia, March 2022. URL: https://doi.org/10.1007/978-3-030-96731-4_5.
  6. Joshua Ani, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets. In Petra Mutzel, Md. Saidur Rahman, and Slamin, editors, Proceedings of the 16th International Conference and Workshops on Algorithms and Computation, volume 13174 of Lecture Notes in Computer Science, pages 187-198, Jember, Indonesia, March 2022. Google Scholar
  7. Jose Balanza-Martinez, Austin Luchsinger, David Caballero, Rene Reyes, Angel A Cantu, Robert Schweller, Luis Angel Garcia, and Tim Wylie. Full tilt: Universal constructors for general shapes with uniform external forces. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2689-2708. SIAM, 2019. Google Scholar
  8. David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie. Relocating units in robot swarms with uniform control signals is PSPACE-complete. CCCG 2020, 2020. Google Scholar
  9. Wojciech Czerwiński and Łukasz Orlikowski. Reachability in vector addition systems is Ackermann-complete. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 1229-1240, 2022. Google Scholar
  10. Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Computational complexity of motion planning of a robot through simple gadgets. In Proceedings of the 9th International Conference on Fun with Algorithms, pages 18:1-18:21, La Maddalena, Italy, June 2018. Google Scholar
  11. Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson, and Jayson Lynch. PSPACE-completeness of reversible deterministic systems. In Proceedings of the 9th Conference on Machines, Computations and Universality, pages 91-108, Debrecen, Hungary, August-September 2022. Google Scholar
  12. Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Toward a general theory of motion planning complexity: Characterizing which gadgets make games hard. In Proceedings of the 11th Conference on Innovations in Theoretical Computer Science, Seattle, Washington, January 2020. Google Scholar
  13. Javier Esparza. Decidability and complexity of petri net problems - An introduction. Lectures on Petri Nets I: Basic Models: Advances in Petri Nets, pages 374-428, 2005. Google Scholar
  14. Dylan Hendrickson. Gadgets and gizmos: A formal model of simulation in the gadget framework for motion planning. Master’s thesis, Massachusetts Institute of Technology, 2021. Google Scholar
  15. Jérôme Leroux. The reachability problem for Petri nets is not primitive recursive. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 1241-1252, 2022. Google Scholar
  16. Jérôme Leroux and Sylvain Schmitz. Reachability in vector addition systems is primitive-recursive in fixed dimension. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-13. IEEE, 2019. Google Scholar
  17. Jayson Lynch. A framework for proving the computational intractability of motion planning problems. PhD thesis, Massachusetts Institute of Technology, 2020. Google Scholar
  18. Marvin Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Inc, 1967. Google Scholar
  19. Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6(2):223-231, 1978. Google Scholar
  20. Larry J. Stockmeyer and Ashok K. Chandra. Provably difficult combinatorial games. Siam Journal on Computing, 8(2):151-174, May 1979. 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