2026-07-21T19:24:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20196 2024-07-02T07:52:51Z ddc:004 open_access

Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Ramanujan, M. S. coordinated motion planning multi-agent path finding parameterized complexity We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth - a class including, among others, all graphs of bounded genus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.53 urn:nbn:de:0030-drops-201968 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.53 eng https://creativecommons.org/licenses/by/4.0/legalcode