4 papers
Coordinated Motion Planning is FPT on Discretized Simple Polygons
Argyrios Deligkas, Eduard Eiben, Robert Ganian +1
In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of robots. At each time step, any subset of robots may move…
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
Eduard Eiben, Robert Ganian, Iyad Kanj +1
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the \textsc{Coordinated Sliding-Motion Planning} (CSMP) problem. In this v…
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
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 …
On the Parameterized Complexity of Motion Planning for Rectangular Robots
Iyad Kanj, Salman Parsa
We study computationally-hard fundamental motion planning problems where the goal is to translate axis-aligned rectangular robots from their initial positions to their final po…