Document Open Access Logo

Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard

Authors Erik D. Demaine, Dylan H. Hendrickson , Jayson Lynch

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.62.pdf
  • Filesize: 1.38 MB
  • 42 pages

Document Identifiers

Author Details

Erik D. Demaine
  • MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA
Dylan H. Hendrickson
  • MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA
Jayson Lynch
  • MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA

Acknowledgements

This work grew out of an open problem session from MIT class on Algorithmic Lower Bounds: Fun with Hardness Proofs (6.890) from Fall 2014.

Cite AsGet BibTex

Erik D. Demaine, Dylan H. Hendrickson, and Jayson Lynch. Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 62:1-62:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.62

Abstract

We begin a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget’s state. We study two general families of such gadgets within this theory, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also study a range of competitive game-theoretic scenarios, from one player controlling one robot to teams of players each controlling their own robot and racing to achieve their team’s goal. Under certain restrictions on these gadgets, we fully characterize the complexity of bounded 1-player motion planning (NL vs. NP-complete), unbounded 1-player motion planning (NL vs. PSPACE-complete), and bounded 2-player motion planning (P vs. PSPACE-complete), and we partially characterize the complexity of unbounded 2-player motion planning (P vs. EXPTIME-complete), bounded 2-team motion planning (P vs. NEXPTIME-complete), and unbounded 2-team motion planning (P vs. undecidable). These results can be seen as an alternative to Constraint Logic (which has already proved useful as a basis for hardness reductions), providing a wide variety of agent-based gadgets, any one of which suffices to prove a problem hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • motion planning
  • computational complexity
  • NP
  • PSPACE
  • EXP
  • NEXP
  • undecidability
  • games

Metrics

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

Related Versions

References

  1. Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo Games are (NP-)Hard. In Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 2014. Google Scholar
  2. Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo Games are (Computationally) Hard. Theoretical Computer Science, 586:135-160, 2015. Originally at FUN 2014. Google Scholar
  3. Jeffrey Bosboom, Erik D Demaine, Adam Hesterberg, Jayson Lynch, and Erik Waingarten. Mario kart is hard. In Japanese Conference on Discrete and Computational Geometry and Graphs, pages 49-59. Springer, 2015. Google Scholar
  4. Erik D. Demaine. 6.890: Algorithmic Lower Bounds: Fun with Hardness Proofs. MIT lecture notes and videos, 2014. URL: http://courses.csail.mit.edu/6.890/fall14/.
  5. Erik D. Demaine, Isaac Grosof, and Jayson Lynch. Push-Pull Block Puzzles are Hard. In Proceedings of the 10th International Conference on Algorithms and Complexity, pages 177-195, Athens, Greece, May 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_16.
  6. 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 (FUN 2018), pages 18:1-18:21, La Maddalena, Italy, June 13-15 2018. Google Scholar
  7. Erik D. Demaine and Robert A. Hearn. Constraint Logic: A uniform framework for modeling computation as games. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pages 149-162, June 2008. Google Scholar
  8. Erik D. Demaine and Robert A. Hearn. Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. In Michael H. Albert and Richard J. Nowakowski, editors, Games of No Chance 3, volume 56 of Mathematical Sciences Research Institute Publications, pages 3-56. Cambridge University Press, 2009. Google Scholar
  9. Michal Forisek. Computational Complexity of Two-Dimensional Platform Games. In Proceedings International Conference on Fun with Algorithms (FUN 2010), pages 214-227, 2010. Google Scholar
  10. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. Google Scholar
  11. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, Ltd., Natick, MA, USA, 2009. Google Scholar
  12. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A Survey of NP-Complete Puzzles. ICGA Journal, 31(1):13-34, 2008. URL: http://www.bibsonomy.org/bibtex/25cc2e9e313951aad1b2127959e6b2269/dblp.
  13. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The Approximability of Constraint Satisfaction Problems. SIAM Journal on Computing, 30(6):1863-1920, 2000. URL: https://doi.org/10.1137/S0097539799349948.
  14. Dénes Kőnig. Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Sci. Math. (Szeged), 3(2-3):121-130, 1927. Google Scholar
  15. André G. Pereira, Marcus Ritt, and Luciana S. Buriol. Pull and PushPull are PSPACE-complete. Theoretical Computer Science, 628:50-61, 2016. URL: https://doi.org/10.1016/j.tcs.2016.03.012.
  16. Gary L. Peterson and John H. Reif. Multiple-person Alternation. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, SFCS '79, pages 348-363, Washington, DC, USA, 1979. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1979.25.
  17. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pages 216-226, San Diego, California, May 1978. Google Scholar
  18. Tom C Van Der Zanden and Hans L Bodlaender. PSPACE-completeness of Bloxorz and of games with 2-buttons. In International Conference on Algorithms and Complexity, pages 403-415. Springer, 2015. Google Scholar
  19. Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014. Google Scholar
  20. Giovanni Viglietta. Lemmings is PSPACE-complete. Theoretical Computer Science, 586:120-134, 2015. 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