Reconfiguration of Squares Using a Constant Number of Moves Each

This paper investigates the computational complexity of multi-robot motion planning for sliding square robots with a constant move limit, demonstrating that the problem remains NP-hard in most scenarios except when the squares are unit-sized and the target configuration is unlabeled.

The Gist

Imagine you are playing a high-stakes game of Sliding Tile Puzzles, but instead of a flat board with numbers, you have a room full of giant, square furniture pieces (like coffee tables or rugs) that you need to rearrange.

The rules are simple but tricky:

1. You can only move one piece at a time.
2. You can slide a piece anywhere in a straight line or a curve, as long as it doesn't crash into another piece or the walls.
3. The Catch: Each piece is only allowed to move a fixed, small number of times (maybe just once, maybe twice, maybe five times) before the game ends.

The big question the researchers asked is: "Can we always figure out if there's a way to get from the messy starting room to the perfect target room without breaking the rules?"

The Main Discovery

The paper's answer is a bit of a "it depends," but mostly "No, it's incredibly hard."

In computer science terms, they proved that for almost every version of this game, figuring out the solution is NP-hard. Think of this as the "Super-Villain" level of difficulty. It means that as you add more furniture, the time it takes to solve the puzzle grows so fast that even the world's fastest supercomputers would take longer than the age of the universe to find the answer for a large room.

However, there is one special exception where the game is easy (solvable in seconds).

---

The "Easy" Mode: The Unlabeled Unit Squares

Imagine your room is filled with 1x1 inch sticky notes (tiny squares), and it doesn't matter which specific note ends up in which spot, as long as the final pattern looks right.

• The Analogy: Think of this like a game of musical chairs where the chairs are identical. If you have 100 people and 100 chairs, and everyone just needs to sit down, you don't care who sits where.
• The Solution: The authors found a clever "traffic flow" algorithm for this specific scenario. It's like a smart traffic light system that calculates the perfect path for every single note to slide into a spot without ever bumping into another note. Because the notes are tiny and interchangeable, the computer can solve this instantly.

The "Hard" Modes: Why is it so difficult?

For almost every other variation, the problem becomes a nightmare. Here is how the authors proved it, using some creative "gadgets" (miniature puzzle rooms):

1. The "Logic Gate" Puzzle (Labeled Squares)

Imagine you have a specific red chair that must end up in the red spot, and a blue chair that must end up in the blue spot.

• The Trick: The researchers built tiny puzzle rooms that act like logic switches (True/False).
• The Metaphor: Imagine a hallway blocked by a giant sofa. To get the sofa out, you have to move a specific table. But you can only move the table if you first move a specific lamp.
• They connected these "hallways" together to simulate a complex math problem called 3-SAT (a problem about satisfying logical conditions). If you can solve the furniture puzzle, you can solve the math problem. Since the math problem is famously hard, the furniture puzzle is too.
• The Result: If you have to move specific furniture to specific spots, and you can only move them once (or a few times), it's a nightmare to plan.

2. The "Big Furniture" Puzzle (Large Squares)

What if your furniture isn't tiny sticky notes, but huge 2x2 or 3x3 rugs?

• The Trick: Big rugs take up more space, making it harder to squeeze past things.
• The Metaphor: Imagine trying to navigate a crowded dance floor where everyone is wearing a giant, inflatable suit. You can't squeeze through gaps that a tiny person could.
• The researchers showed that even with just two moves allowed per rug, you can build a puzzle that simulates finding a Hamiltonian Path (a path that visits every single room in a building exactly once). This is another famous "hard" problem. If you can't find the path through the building, you can't rearrange the rugs.

3. The "Round Trip" Puzzle (Multiple Moves)

What if you are allowed to move a piece, move it somewhere else, and then move it back to where it started?

• The Trick: Even with this extra freedom, the researchers built "latches" (mechanical traps).
• The Metaphor: Imagine a door that requires you to turn a key three times to open, but if you turn it four times, it locks forever. They designed the puzzle so that if you try to solve it the "wrong" way, you run out of your allowed moves before you can finish.
• The Result: Even if you can move things back and forth a few times, as long as the pieces are big or the targets are specific, the problem remains unsolvable in a reasonable time.

Summary Table (The Cheat Sheet)

Scenario	Difficulty	Why?
Tiny, Interchangeable Squares	🟢 Easy	Like shuffling identical cards. A flow algorithm solves it instantly.
Tiny, Specific Squares	🔴 Hard	Like a specific logic lock. Solving it is as hard as cracking a complex code.
Big Squares (Specific or Not)	🔴 Hard	Like moving giant furniture. The lack of space creates "traffic jams" that simulate complex pathfinding.
Big Squares + Multiple Moves	🔴 Hard	Even with extra moves, clever "traps" prevent you from solving it unless the logic is perfect.

The Takeaway

The paper tells us that Multi-Robot Motion Planning (moving many robots or objects around) is generally a very hard problem if we restrict how many times each robot can move.

• Good News: If your robots are tiny, identical, and you don't care which one goes where, we have a fast, perfect solution.
• Bad News: If your robots are big, or if they have specific destinations, or if you are in a tight room, figuring out the moves is likely impossible to do quickly. You might have to rely on trial and error or lucky guesses rather than a perfect plan.

This research helps engineers understand the limits of automation. If you are designing a warehouse with hundreds of robots, you now know that unless your robots are small and interchangeable, you can't expect a computer to instantly calculate the perfect path for them if they are only allowed to move a few times.

Technical Summary

Here is a detailed technical summary of the paper "Reconfiguration of Squares Using a Constant Number of Moves Each" by van der Horst et al.

1. Problem Definition

The paper investigates the Multi-Robot Motion Planning problem, specifically focusing on the reconfiguration of square robots in a 2D Euclidean plane.

• Objective: Transform a starting configuration $S$ of non-overlapping squares into a target configuration $T$ ($|S|=|T|$) via a sequence of valid moves.
• Constraints:
  • Movement: A "move" consists of a single square sliding along an arbitrary continuous curve without rotation.
  • Collision: Squares cannot overlap with other squares or the boundary of the domain during a move.
  • Sequentiality: Only one square moves at a time.
  • Move Limit: Each square is allowed to move at most $k$ times, where $k$ is a small constant (independent of the number of squares).
• Variants: The authors analyze the problem across several dimensions:
  • Labeled vs. Unlabeled: In labeled scenarios, specific squares have dedicated targets. In unlabeled scenarios, any square can occupy any target location.
  • Bounded vs. Unbounded: Squares move within a rectilinear polygonal domain (potentially with holes) or in an infinite plane.
  • Size: Squares can be unit size ($1 \times 1$) or larger ($\ell \times \ell$, where$\ell \ge 2$).

2. Methodology

The authors employ a combination of computational complexity reductions and algorithmic flow-based approaches to classify the hardness of the problem.

• Hardness Proofs (NP-Hardness):

  • The authors reduce known NP-hard problems to specific square reconfiguration scenarios.
  • Planar Monotone 3-SAT: Used to prove hardness for labeled scenarios and scenarios with multiple moves ($k \ge 2$) for larger squares. This involves constructing "gadgets" (variable, clause, wire, splitter) that simulate logic gates using square movements.
  • Hamiltonian Path: Used to prove hardness for unlabeled scenarios with larger squares ($\ell \ge 2$) and labeled scenarios with unit squares ($1 \times 1$) allowing multiple moves. This involves creating vertex and edge gadgets where an "empty" space (or a specific moving square) must trace a path visiting every node exactly once.
  • Gadget Design: A key methodological contribution is the design of mechanical gadgets (e.g., latches, blockers, T-junctions) that enforce constraints such as "a square can only move if a specific variable is set" or "a square must move back to its start," effectively simulating logical constraints within the geometric domain.

• Polynomial Time Algorithm:

  • For the specific case of unlabeled, unit-sized ($1 \times 1$) squares, the authors develop a constructive algorithm based on network flow.
  • They model the grid of integer coordinates as a graph and construct a flow network where flow represents the movement of squares from start to target positions.
  • By computing a maximum flow and decomposing it into a Directed Acyclic Graph (DAG), they derive a valid movement schedule where each square moves exactly once (monotonic).

3. Key Contributions and Results

The paper provides a complete classification of the problem's complexity based on the parameters of size, labeling, and move limits. The results are summarized in Table 1 of the paper:

A. NP-Hard Scenarios

The problem remains NP-hard in almost all restricted variants:

1. Labeled, Monotonic ($k=1$): Hard for any square size (Theorem 1).
2. Unlabeled, Monotonic ($k=1$), Large Squares ($\ell \ge 2$): Hard (Theorem 3).
3. Bounded, Large Squares ($\ell \ge 2$), Multiple Moves ($k \ge 2$): Hard for any constant $k$ (Theorems 4 & 5).
4. **Bounded, Labeled, Unit Squares ($1 \times 1$), Multiple Moves ($k \ge 2$):** Hard for any constant$k$ (Theorems 6 & 7).

B. Polynomial Time Scenario

There is exactly one non-trivial scenario where the problem is solvable in polynomial time:

• Unlabeled, Unit Squares ($1 \times 1$), Monotonic ($k=1$):
  • The authors prove that if a solution exists, a monotonic solution (where every square moves exactly once) always exists.
  • They provide an algorithm using max-flow to find this schedule.
  • Note: In unbounded scenarios with $k \ge 2$, the problem is trivial (robots can move far away and return in any order), but the bounded unlabeled unit case with $k=1$ is the only non-trivial tractable case.

4. Significance

• Completeness of Classification: The paper closes the gap on the complexity of square reconfiguration under move constraints. It demonstrates that restricting robots to a constant number of moves does not generally make the problem easier, except for the specific case of unlabeled unit squares.
• Monotonicity: The work challenges the intuition that limiting moves (monotonicity) simplifies planning. While monotonicity is often a heuristic for simplification, this paper proves it remains NP-hard for labeled robots and large unlabeled robots.
• Algorithmic Insight: The flow-based algorithm for unlabeled unit squares provides a practical method for a specific class of multi-robot systems, showing that "unlabeled" flexibility combined with "unit" size enables efficient planning.
• Open Questions: The authors highlight that their reductions rely on polygonal domains with holes. It remains an open question whether these hardness results hold for simple polygons (without holes). Additionally, the optimality (minimum makespan or path length) of the solutions found is not addressed, only the decision problem.

Summary Table of Results

Scenario	Square Size	Moves ($k$)	Labeling	Complexity
Bounded	Any	1	Labeled	NP-hard
Bounded	$\ge 2$	1	Unlabeled	NP-hard
Bounded	$\ge 2$	$\ge 2$	Unlabeled	NP-hard
Bounded	1	$\ge 2$	Labeled	NP-hard
Bounded	1	1	Unlabeled	Polynomial
Unbounded	Any	$\ge 2$	Any	Trivial
Unbounded	Any	1	Labeled	NP-hard

In conclusion, the paper establishes that multi-robot motion planning for squares is computationally intractable (NP-hard) in nearly all realistic constrained settings, with the notable exception of unlabeled unit squares where a flow-based polynomial solution exists.