Document Open Access Logo

The Parameterized Complexity of Coordinated Motion Planning

Authors Eduard Eiben , Robert Ganian , Iyad Kanj

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.28.pdf
  • Filesize: 2.05 MB
  • 16 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Computer Science, Royal Holloway, University of London, Egham, UK
Robert Ganian
  • Algorithms and Complexity Group, TU Wien, Austria
Iyad Kanj
  • School of Computing, DePaul University, Chicago, IL, USA

Funding

  • Ganian, Robert: Project No. Y1329 of the Austrian Science Fund (FWF), Project No. ICT22-029 of the Vienna Science Foundation (WWTF).
  • Kanj, Iyad: DePaul URC Grants 606601 and 350130.

Cite As Get BibTex

Eduard Eiben, Robert Ganian, and Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.28

Abstract

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n²-1)-puzzle as a special case.
In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • coordinated motion planning
  • multi-agent path finding
  • parameterized complexity
  • disjoint paths on grids

Metrics

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

References

  1. Computational Geometry Week: The Third Computational Geometry Challenge. URL: https://cse.buffalo.edu/socg21/challenge.html.
  2. Jacopo Banfi, Nicola Basilico, and Francesco Amigoni. Intractability of time-optimal multirobot path planning on 2D grid graphs with holes. IEEE Robotics and Automation Letters, 2(4):1941-1947, 2017. Google Scholar
  3. 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 SoCG, volume 224 of LIPIcs, pages 12:1-12:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  4. Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, and Solomon Eyal Shimony. ICBS: Improved conflict-based search algorithm for multi-agent pathfinding. In IJCAI, pages 740-746, 2015. Google Scholar
  5. Julia Chuzhoy and David H. K. Kim. On Approximating Node-Disjoint Paths in Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 187-211, 2015. Google Scholar
  6. Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat. Almost polynomial hardness of node-disjoint paths in grids. Theory of Computing, 17(6):1-57, 2021. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  8. 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
  9. Erik D. Demaine and Mikhail Rudoy. A simple proof that the (n²-1)-puzzle is hard. Theoretical Computer Science, 732:80-84, 2018. Google Scholar
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Adrian Dumitrescu. Motion planning and reconfiguration for systems of multiple objects. In Sascha Kolski, editor, Mobile Robots, chapter 24. IntechOpen, Rijeka, 2007. Google Scholar
  13. András Frank. Disjoint paths in a rectilinear grid. Combinatorica, 2:361-371, 1982. Google Scholar
  14. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. Google Scholar
  15. Tzvika Geft and Dan Halperin. Refined hardness of distance-optimal multi-agent path finding. In AAMAS, pages 481-488, 2022. Google Scholar
  16. Jr. H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  17. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. Google Scholar
  18. Md. Manzurul Hasan, Debajyoti Mondal, and Md. Saidur Rahman. Positive planar satisfiability problems under 3-connectivity constraints. Theoretical Computer Science, 917:81-93, 2022. URL: https://doi.org/10.1016/j.tcs.2022.03.013.
  19. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12(3):415-440, 1987. URL: https://doi.org/10.1287/moor.12.3.415.
  20. D. Kornhauser, G. Miller, and P. Spirakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In FOCS, pages 241-250, 1984. Google Scholar
  21. Mark Kramer. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Advances in Computing Research, 2:129-146, 1984. Google Scholar
  22. Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Applied Mathematics, 52(3):233-252, 1994. URL: https://doi.org/10.1016/0166-218X(94)90143-0.
  23. Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, and Meirav Zehavi. An exponential time parameterized algorithm for planar disjoint paths. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1307-1316. ACM, 2020. Google Scholar
  24. Dániel Marx. Eulerian disjoint paths problem in grid graphs is NP-complete. Discrete Applied Mathematics, 143(1):336-341, 2004. Google Scholar
  25. Geetha Ramanathan and V.S. Alagar. Algorithmic motion planning in robotics: Coordinated motion of several disks amidst polygonal obstacles. In ICRA, volume 2, pages 514-522, 1985. Google Scholar
  26. Daniel Ratner and Manfred Warmuth. The (n²-1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10(2):111-137, 1990. Google Scholar
  27. 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:46-75, 1983. Google Scholar
  28. Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40-66, 2015. Google Scholar
  29. Irving Solis, James Motes, Read Sandström, and Nancy M. Amato. Representation-optimal multi-robot motion planning using conflict-based search. IEEE Robotics Autom. Lett., 6(3):4608-4615, 2021. Google Scholar
  30. Hitoshi Suzuki, Akira Ishiguro, and Takao Nishizeki. Edge-disjoint paths in a grid bounded by two nested rectangles. Discrete Applied Mathematics, 27(1):157-178, 1990. Google Scholar
  31. Glenn Wagner and Howie Choset. Subdimensional expansion for multirobot path planning. Artificial Intelligence, 219:1-24, 2015. Google Scholar
  32. 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, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, June 26-30, 2018, 2018. Google Scholar
  33. Jingjin Yu and Steven M. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In Marie desJardins and Michael L. Littman, editors, AAAI. AAAI Press, 2013. Google Scholar
  34. 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