cs.MASep 25, 2026
SaveCollision-free Movement on Grids and Beyond
Organizations: Chair for Algorithm Engineering, Hasso Plattner Institute, Potsdam, Germany · Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Abstract
We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.
Figures & tables
Figure 1: Illustration of the graph W[1]-hardness reduction. The black filled round vertices have obnoxious robots on them, and the blue filled square vertices have main robots on them. The red filled square vertices have main robots on them and paths of sufficient length attached to them that have main robots on each vertex (which are not depicted). The two red edges correspond to connections between the edge selecting gadget and the verification gadgets.
Figure 2: Illustration of a variable gadget. The black vertices have obnoxious robots on them.
Figure 3: Illustration of the informally described graph . The blue filled round vertices have obnoxious robots on them, and the black filled square vertices have main robots on them. The red edges correspond to long paths that have obnoxious robots on all inner vertices.
Figure 4: Illustration of an embedding of the graph obtained from graph . The drawing is not up to scale but rather should give the rough idea on how the embedding looks like. The grid points on the thick black lines have obnoxious robots on them, and the blue filled square vertices have main robots on them. The red edges correspond to long paths that have obnoxious robots on all inner vertices. The light blue area surrounded by the black dashed line indicates the part of the grid, where we make sure that all red paths have the same length, and the path connecting the last variable gadget with the first clause gadget is sufficiently long. This is also indicated by the snake-like shape of the paths in the area.
Figure 5: Illustration of the OR-cross-composition. Blue filled square vertices have main robots on them.
Figure 6: Illustration of the weak cross-composition. The drawing is not up to scale but rather should give the rough idea on how the embedding looks like. Black boxes correspond to the instances and red lines to the connecting paths. Blue filled square vertices have main robots on them. The thick lines correspond to the paths visited by the main robots when instance nr. is selected.
Figure 7: Illustration of the graph produced by Construction 1 . The black filled round vertices have obnoxious robots on them, and the blue filled square vertices have main robots on them. The red filled square vertices have main robots on them and paths of length attached to them that have main robots on each vertex (which are not depicted). The two red edges correspond to paths of length connecting the edge selecting gadget to the verification gadgets.
Figure 8: Illustration of a variable gadget for a variable ( Construction 2 ). The black filled vertices have obnoxious robots on them.
Figure 9: Illustration of an embedding described in the proof of Observation 17 of the graph produced by Construction 2 . The black filled round vertices have obnoxious robots on them, and the blue filled square vertices have main robots on them. There are two variable gadgets on the left and three clause gadgets on the right (indicated by light gray boxes). The red lines correspond to paths of length that have obnoxious robots on all inner vertices.
Figure 10: Illustration of a “unfolded” embedding of the graph produced by Construction 2 . The blue filled round vertices have obnoxious robots on them, and the black filled square vertices have main robots on them. The red edges correspond to paths of length that have obnoxious robots on all inner vertices.
Figure 11: Illustration of a variable gadget for a variable ( Construction 3 ). The black filled vertices have obnoxious robots on them. Red dashed lines indicate where the paths between variable gadgets and clause gadgets are connected.
Figure 12: Illustration of a clause gadget for a clause ( Construction 3 ). The black filled vertices have obnoxious robots on them. Red dashed lines indicate where the paths between variable gadgets and clause gadgets are connected.
Figure 13: Illustration of an embedding described in the proof of Lemma 20 of the graph produced by Construction 3 . The drawing is not up to scale but rather should give the rough idea on how the embedding looks like. The grid points on the thick black lines have obnoxious robots on them, and the blue filled square vertices have main robots on them. The red edges correspond to long paths that have obnoxious robots on all inner vertices. The light blue area surrounded by the black dashed line indicates the part of the grid, where we make sure that all red paths have the same length, and the path connecting the last variable gadget with the first clause gadget is sufficiently long. This is also indicated by the snake-like shape of the paths in the area.
Figure 14: Illustration of the OR-cross-composition from Theorem 5 . Blue filled square vertices have main robots on them.
Figure 15: Illustration the OR-cross-composition from Theorem 6 . The grid points on blue paths have main robots on them. The thick blue paths have the main robots on them that would move through the corresponding instance.
Figure 16: Illustration of the weak cross-composition from Theorem 7 . The drawing is not up to scale but rather should give the rough idea on how the embedding looks like. Black boxes correspond to the instances and red lines to the connecting paths. Blue filled square vertices have main robots on them. The thick lines correspond to the paths visited by the main robots when instance is selected.