PaperlayerView exact revision on arXiv

Source-linked AI summary

Collision-free Movement on Grids and Beyond

Hendrik Molter, Meirav Zehavi

arXiv:2609.31099v1cs.MAcs.DS

TL;DR

The paper asks how to coordinate collision-free robot movement toward a connected formation while minimizing total travel. It analyzes the problem’s parameterized complexity across graph classes, establishing grid kernelization and planar tractability alongside lower bounds on kernel sizes.

  • Problem

    Prior work studied collision-free motion to assigned targets and motion to specified formations with collisions allowed, leaving collision-free motion to a formation as an open question.

    Source: §1 · p. 2

  • Method

    The paper analyzes parameterized complexity for collision-free movement to connected formations, using grid kernelization, an MSO formulation for planar graphs, and reductions for hardness results.

    Source: §1 · p. 2, §2 · pp. 6–9, §4 · p. 15

  • Results

    Grid instances admit a kernel of size O(k · c^2) for general formations, while general formations on planar graphs are FPT parameterized by k + c.

    Source: §2 · pp. 8–9

  • Takeaways & Limitations

    The results delineate tractable and intractable cases for collision-free movement to connected formations across grids and their generalizations.

    Source: §1 · p. 2, §8 · p. 41

    The correctness proofs for one reduction assume s^2/4 > c, which holds when |X| and |Y| are sufficiently large.

    Source: §4 · p. 19

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses collision-free motion to a specified robot formation, focusing on connected formations and total travel distance. It establishes parameterized complexity results across grids, planar graphs, and unit disk graphs, delineating tractable and hard cases.

1.2 Further Related Work

  • Prior work studied either collision-free motion to individual targets or motion to a formation with collisions allowed; related work also covers MAPF, coordinated motion planning, and movement without collision constraints.The paper identifies its problem as combining formation goals with collision avoidance, a question left open by the two established formulations.Source: §1 · p. 2, §1.2 · p. 5

1.1 Our Contributions

  • With no obnoxious robots, connectivity is FPT parameterized by k; for hereditary properties excluding all complete and all empty graphs, the problem is W[1]-hard parameterized by k + c.When deciding whether a graph has property Π is polynomial-time solvable, the problem is in XP parameterized by c.Source: §1.1 · p. 3
  • Collision-Free Movement to Connectivity is W[1]-hard parameterized by k + c and NP-hard on grids even with k = 2.The hardness constructions have an unbounded number of obnoxious robots; without them, the connectivity problem is FPT parameterized by k.Source: §1.1 · pp. 3–4
  • For grid input graphs, Collision-Free Movement to Π parameterized by k + c has a polynomial kernel of size O(k · c^2); for Connectivity, the bound is O(min{k · c^2, k^2 + c^2}).Source: §1.1 · p. 4
  • For connectivity, polynomial kernels parameterized by c are ruled out under standard complexity assumptions on both planar graphs and grids.The authors also show that the grid kernel’s dependence on k is presumably unavoidable.Source: §1.1 · p. 4
  • On grids, no kernel of size O((k + c)^(2 − ε)) is possible for any ε > 0 unless coNP ⊆ NP/poly.This lower bound addresses the size of the polynomial kernel parameterized by k + c.Source: §1.1 · p. 4
  • For general formations on planar graphs, the problem is FPT parameterized by k + c, via an MSO formulation and Courcelle’s theorem [2, 5, 6].The result applies to general formation properties, not only connectivity.Source: §1.1 · p. 4
  • On unit disk graphs, connectivity admits a fixed-parameter approximation parameterized by k + c, with energy at most 2 · OPT + 3k.Here OPT is the energy of an optimal solution.Source: §1.1 · p. 4

2 Overview of Results and Techniques

The overview establishes hardness results alongside kernelization and fixed-parameter algorithms across grids, planar graphs, and unit disk graphs. Its techniques include gadget reductions, distance-based kernel rules, MSO, and clique-grid structure.

Hardness Resuls (Section 4)

  • Collision-Free Movement to Connectivity is W[1]-hard parameterized by k + c, via a Multicolored Clique reduction using edge-selection and color-verification gadgets.Selecting an edge moves an obnoxious robot and enables main robots to reach verification gadgets; selected edges for each color combination must share endpoints.Source: §2 · pp. 5, 10
  • Linked Planar 3-SAT yields NP-hardness on grids even with only two main robots.The reduction first builds a planar instance, then embeds it into a grid; variable-gadget moves encode truth assignments, and clause paths can clear only when a literal satisfies the clause. Grid clause gadgets and equal-length connecting paths preserve the construction, with a sufficiently long boundary path.Source: §2 · pp. 5–7

Collision Free Movement on Grids (Section 5)

  • Distance-based reduction rules give a general-formation kernel of size O(k · c^2), improved for connectivity to O(min{k · c^2, k^2 + c^2}).Vertices far from every main robot can be discarded; for connectivity, vertices too far from a main robot are also irrelevant because the robots must eventually be close together.Source: §2 · p. 8
  • On planar graphs, the authors show that polynomial kernels parameterized by c are unlikely even when k = 2.The OR-cross-composition uses planar instances from the hardness reduction and connects their former main-robot starting locations to a new start with long paths, preventing travel between instances.Source: §2 · pp. 8–9
  • On grids, polynomial kernels are unlikely for either parameter c or parameter k alone.For the c lower bound, a tree-like grid and a snake of main robots replace a high-degree connection that cannot be embedded in a grid.Source: §2 · p. 9
  • A weak cross-composition indicates that the connectivity kernel cannot be significantly improved in size.Input instances are arranged grid-like with two main robots; the produced parameter is bounded by t · xmax, where t is the number of inputs and xmax is their maximum size.Source: §2 · p. 9

Collision Free Movement on Planar Graphs (Section 6)

  • For planar inputs, Collision-Free Movement to any formation property Π is fixed-parameter tractable parameterized by k + c.An MSO formulation models vertex-time visits and collision-free movements; pruning distant vertices bounds the input diameter, and planarity then bounds treewidth.Source: §2 · pp. 9–10

Collision Free Movement on Unit Disk Graphs (Section 7)

  • For unit disk graphs, connectivity admits an FPT approximation parameterized by k + c with energy at most 2 · OPT + 3k.The method uses clique grids, guesses a spanning tree and vertex types, and allows at most one extra move to reach a free vertex of a type plus at most three extra moves per main robot to reach the guessed tree vertices.Source: §2 · p. 11

3 Preliminaries and Known Results

This section defines collision-free movement to a graph property, focusing on connected final formations, and reviews its movement model and known complexity results.

Parameterized complexity

  • Parameterized-complexity terminology distinguishes FPT algorithms, kernels, polynomial kernels, and XP algorithms by their dependence on the parameter.A kernel reduces an instance in polynomial time to an equivalent instance bounded in size by a function of the parameter; a polynomial kernel uses a polynomial bound.Source: §3 · pp. 11–12

Movement model

  • Collisions include robots sharing a vertex at the same step or traversing the same edge in opposite directions simultaneously.A plan’s total length is the sum of the lengths of its robots’ movements.Source: §3 · p. 12

Problem definition

  • A solution is a collision-free movement plan of total length at most c whose main robots’ final positions induce a graph with property Π; the paper focuses on connectivity.A robot may stay put or move to an adjacent vertex at each step, and its movement length counts only steps in which it moves.Source: §3 · pp. 12–13

Known results

  • With no obnoxious robots, collision-free movement to connectivity coincides in yes/no status with movement without collision constraints and is FPT parameterized by k.The equivalence is stated for O = ∅; it lets known algorithmic results for movement without collision constraints carry over in that case.Source: §3 · pp. 13–14
  • Even with no obnoxious robots, the problem is W[1]-hard parameterized by k + c for hereditary properties excluding all complete and all empty graphs, and connectivity is NP-hard on planar inputs.These are distinct hardness statements: the first applies to the stated class of properties, while the second concerns connectivity.Source: §3 · p. 14
  • If deciding Π is in NP, movement to Π is in NP; if deciding Π is polynomial-time solvable, movement to Π is in XP parameterized by c.The XP result follows by guessing and checking a set of at most c moves.Source: §3 · pp. 14–15

4 Hardness Results

The section establishes hardness for Collision-Free Movement to Connectivity, including W[1]-hardness parameterized by k + c and NP-hardness on grid graphs even with k = 2. It also treats planar instances with two main robots and adapts the reduction to grid graphs.

General graphs

  • Collision-Free Movement to Connectivity is W[1]-hard parameterized by k + c, via a parameterized reduction from Multicolored Clique [19].The construction uses O(ℓ^4) main robots and sets c ∈ O(ℓ^4).Source: §4 · pp. 15–16
  • The clique reduction forces edge selections to agree on one vertex per color, so any feasible movement plan yields a clique of size ℓ.Long attached paths prevent verification-gadget robots from moving, while the movement budget forces selected edges to place main robots at consistent endpoints.Source: §4 · p. 17

Hardness on Grids

  • Collision-Free Movement to Connectivity is NP-hard on grid graphs even when k = 2, using a polynomial-time reduction from Linked Planar 3-SAT [37].The proof first constructs a planar graph and then modifies the construction to obtain a grid.Source: §4 · p. 18
  • The Linked Planar 3-SAT reduction first produces a planar graph by replacing variables with gadgets and routing clause connections in their embedding order.The construction's graph is planar; variable-gadget ports follow the cyclic order of incidence edges, and the paths to clauses can be embedded without crossings.Source: §4 · pp. 19–20

Planar reduction

  • The forward reduction ends with the two main robots on connected vertices, using a movement plan of length 16 · |X| + (s + 2) · (|Y| + 1) + 1.Source: §4 · pp. 20–21
  • In the reverse reduction, main robots avoid variable-to-clause paths, and tight movement lower bounds force gadget moves that encode a satisfying assignment.The argument uses a lower bound of 7 · |X| + |Y| + s + 3 main-robot moves; the total lower bounds add up to c.Source: §4 · p. 21

Planar hardness

  • Collision-Free Movement to Connectivity is NP-hard on planar graphs even when k = 2.Source: §4 · p. 21

Grid construction

  • The grid embedding lines up variable and clause gadgets with a wide gap between them, where snake-like paths realize the required lengths without interfering.The construction uses paths of lengths s, s + 2, or s + 4.Source: §4 · pp. 24–25

Grid hardness

  • Construction 3 produces a grid instance with two main robots, and Theorem 2’s correctness follows by adapting the earlier gadget arguments.The proof says the movement details are omitted.Source: §4 · pp. 24–25

5 Collision Free Movement on Grids

On grids, the paper gives polynomial kernels for movement to connected formations and proves limits on shrinking them or dropping parameters. Its bounds depend on the number of main robots and the travel budget.

Kernelization

  • The grid kernels can be combined with Theorem 16 to obtain a running time of (k · c)O(c) + nO(1).The general-formation kernel follows by retaining radius-c balls around main-robot starting vertices; each such ball has O(c2) grid vertices.Source: §5 · pp. 25–26
  • O(k · c2) is a polynomial kernel for Collision-Free Movement to Π parameterized by k + c on grids.The reduction removes vertices farther than c from every main robot's starting location.Source: §5 · p. 26
  • O(min{k · c2, k2 + c2}) is a polynomial kernel for Collision-Free Movement to Connectivity parameterized by k + c on grids.The refined bound improves on O(k · c2) when k < c2.Source: §5 · pp. 25–26

Kernelization Lower Bounds

  • Unless coNP ⊆ NP/poly, parameter c alone admits no polynomial kernel for planar graphs or grids.The planar lower bound also rules out obtaining the grid kernelization results on planar graphs; the grid lower bound is stated separately.Source: §5 · p. 28
  • For the grid lower bound with parameter c, the reduction uses main robots in variable gadgets in place of obnoxious robots.Theorem 6 rules out a polynomial kernel unless coNP ⊆ NP/poly; the construction makes main robots play the former obnoxious robots' role.Source: §5 · pp. 28–29
  • Unless coNP ⊆ NP/poly, no kernel of size O((k + c)2−ε) exists on grids for any ε > 0.Theorem 7 uses a weak cross-composition from Linked Planar 3-SAT.Source: §5 · p. 30

6 Collision Free Movement on Planar Graphs

For planar input graphs, Collision-Free Movement to Π is fixed-parameter tractable in k + c. The proof encodes movements in monadic second-order logic and uses bounded treewidth to apply Courcelle’s theorem.

Planar-graph algorithm

  • Collision-Free Movement to Π is fixed-parameter tractable parameterized by k + c when the input graph is planar.The proof applies a reduction rule before bounding treewidth and invoking Courcelle’s theorem.Source: §6 · pp. 31, 37

Treewidth bound

  • The relational structure encoding the instance has treewidth O(c · tw(G)2).Its universe includes graph vertices and edges, time steps, and vertex-step and edge-step pairs.Source: §6 · p. 33

MSO encoding

  • The MSO encoding represents robot movements and checks collision avoidance, the c-move limit, and whether the final main-robot vertices satisfy Π.The formula is satisfiable exactly when the instance is a yes-instance.Source: §6 · pp. 31, 34, 35

Beyond planar graphs

  • The algorithm also yields fixed-parameter tractability parameterized by k + c together with the input graph's treewidth, without requiring planarity.Planarity is used only to bound treewidth by the reduced graph's diameter.Source: §6 · p. 37

7 Collision Free Movement on Unit Disk Graphs

The section gives a fixed-parameter 2-approximation with additive error 3k for energy-minimizing Collision-Free Movement to Connectivity on unit disk graphs. Its algorithm works on clique grids, using movement templates based on vertex types and a final adjustment to reach the connected target formation.

7 Collision Free Movement on Unit Disk Graphs

  • Clique grids generalize grids, and unit disk graphs admit computable clique-grid representations, allowing the algorithm to apply to unit disk graphs.The section assumes a point set or clique-grid representation is supplied as part of the input.Source: §7 · p. 37
  • The algorithm is fixed-parameter in k + c and returns a collision-free connected solution with energy at most 2 · OPT + 3k.Here, OPT is the optimal energy; c is the number of moves in an optimal solution.Source: §7 · p. 37
  • It guesses an optimal energy bound, a tree witnessing target connectivity, and movement vectors, then checks feasibility and embeds the tree into the graph.The checks enforce movement adjacency and collision avoidance; the embedding is constrained by the guessed vertex types.Source: §7 · pp. 37–38
  • Step-indexed continuation types record occupancy and reachable neighboring-clique types, while omitting exact vertices can require an extra move within a clique.At the final step, occupancy is the relevant information; earlier types also encode which neighboring-clique vertex types are reachable.Source: §7 · p. 38
  • The constructed movement plan is collision-free and uses at most 2c moves before the final adjustment to the tree embedding’s target vertices.The final adjustment uses at most three additional moves per main robot.Source: §7 · p. 40

8 Conclusion

The conclusion reports first computational results for Collision-Free Movement to Π and Collision-Free Movement to Connectivity, and identifies unresolved complexity questions and extensions.

8 Conclusion

  • The authors report first computational results for Collision-Free Movement to Π and Collision-Free Movement to Connectivity.They leave open whether connectivity movement is FPT in c on planar graphs and in k + c on unit disk graphs.Source: §8 · p. 41
  • Open directions include polynomial-time solvability on trees or other graph classes and parameterizations using obnoxious robots or graph structure.Treewidth is given as an example of a structural parameter.Source: §8 · p. 41
  • The conclusion proposes makespan minimization and alternative target properties, including perfect matching; for two robots, perfect matching coincides with connectivity, so some hardness results transfer.Source: §8 · p. 41
Loading 2609.31099v1…