Reconfiguration of Squares Using a Constant Number of Moves Each
Thijs van der Horst, Maarten Löffler, Tim Ophelders, Tom Peters · 2026
Read Reconfiguration of Squares Using a Constant Number of Moves Each by Thijs van der Horst, Maarten Löffler, Tim Ophelders, Tom Peters (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05203.txt.
Introduction
Thijs van der Horst and colleagues study restricted multi-robot motion planning where square robots slide along an arbitrary curve, each moving only a constant number of times. They show the problem stays NP-hard in most cases, with two exceptions. These are squares of unit size, and the unlabeled variant where each square's target location is left unspecified. The hardness results map the boundary of tractability for this sliding-squares model, showing that limiting each robot to a constant number of moves rarely makes planning easy.
Catalog record
| CREATOR | Thijs van der Horst, Maarten Löffler, Tim Ophelders, Tom Peters |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32456 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05203
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reconfiguration of Squares Using a Constant Number of Moves Each Thijs van der Horst, Maarten Löffler, Tim Ophelders, Tom Peters Abstract Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position only a constant number of times each. We show that the problem remains NP-hard in most cases, except when the squares have unit size and when the problem is unlabeled, i.e., the location of each square in the target configuration is left unspecified. TU Eindhoven and Utrecht University, the [email protected] Utrecht University, the [email protected] TU Eindhoven and Utrecht University, the [email protected] TU Eindhoven, the [email protected] keywords monotone reconfiguration, multi-robot motion planning † † runningauthor: T. van der Horst, M. Löffler, T. Ophelders and T. Peters 1 Introduction Multi-robot motion planning concerns problems where we are given a starting configuration of robots in the plane, as well as a desired target configuration. The goal is to move the robots from their starting location to the target configuration while avoiding collisions. Many different variants of these problems have been considered. Robots can have different sizes and shapes, they might have to avoid static obstacles in their workspace, and each robot can either have its own dedicated target, or robots can end up at arbitrary targets. Except for some trivial cases, solving these problems optimally, minimizing either the makespan or path length of a solution, is hard. In general, it is usually even hard to decide if a target configuration can be reached at all. For a full survey of these results, see [ 6 ] . Here, we give a brief overview of the known hardness results. One of the first hardness results is from 1984, when it was shown that it is PSPACE-complete to decide if a set of arbitrary shaped objects can be reconfigured into a designated target configuration [ 10 ] , this was then shown to already hold for rectangular objects moving in a rectangular region [ 11 ] . The proof was later generalized, and used to show that rectangles of size 1\times 2 and 2\times 1 suffice [ 9 ] . The well-known related Rush Hour Problem , where rectangles are only allowed to slide into one direction, was also proven to be PSPACE-complete [ 7 ] . For unit squares in a simple polygon, deciding if a target configuration is reached is also PSPACE-hard, both if the polygon can have holes [ 3 ] as well as when it cannot [ 1 ] . For many moving disks it has been shown to be NP-hard to decide if a target configuration is reachable [ 16 ] , even if the disks have the same size [ 5 ] . On the other hand, for two disks, a full characterization has been made of reconfiguration using minimum path length [ 13 ] , which has recently been extended to two arbitrary centrally symmetric objects [ 14 ] . Moreover, if the objects are pebbles moving on a graph, which corresponds to squares moving in a grid aligned polygon, a polynomial time algorithm is known to calculate the reconfiguration using the least amount of moves if one exists [ 15 ] . Most reconfiguration problems of this type are either hard, or a trivial algorithm exists. In an attempt to reduce the search space, monotone movement schedules have been proposed: movement schedules where each robot is allowed to move only once. This open problem was recently stated by Abrahamsen and Halperin [ 2 ] . If you furthermore only allow a single robot to move at each point in time, this reduces the problem to finding a valid permutation, hopefully reducing the complexity of the problem. In this paper, we investigate the multi-robot motion planning problem for square robots that are allowed to move at most a constant number of times. We show that in most cases, the decision problem remains NP-hard, except for some scenarios with unit size robots in which we can formulate the problem as a flow computation, and some trivial scenarios in which the robots are able to move arbitrarily far away and back again. 2 Preliminairies The multi-robot motion planning problem takes a set of robots (or objects) in the Euclidean plane and tries to move them around to create a new configuration, while avoiding collisions. Let a configuration be a set of non-overlapping squares in the Euclidean plane. Let a move be a square sliding on an arbitrary curve in one continuous motion without rotating. A move is valid if it does not collide (overlap) with any other square during the movement. Only a single square is allowed to move at any given time. A motion schedule is a sequence of moves. A valid motion schedule is a motion schedule where each move is valid. In the square reconfiguration problem, we are given a starting configuration S , and a target configuration T with |S|=|T| . The goal is to find any valid motion schedule that reconfigures S into T , or decide that such a schedule does not exist. We consider several variants of this problem, which we call scenarios . In the labeled scenarios, each square in S has a dedicated target in T . In the unlabeled scenarios, each square is allowed to end up at any target in T . In the bounded scenarios the squares lie in the interior of a rectilinear polygonal domain with integer coordinates (potentially with holes). A move is only valid if, besides not intersecting other squares, it does not intersect the boundary of this domain at any time during a move. In the unbounded scenarios, this polygonal domain does not exist and the squares move freely in plane (only colliding with other squares). We also distinguish between the sizes of the squares. The squares can have a side length of 1 unit, 2 units, or more. In the literature, some papers consider the squares to always have unit side length, and instead allow the squares and the polygonal domain to use non-integer coordinates. These definitions are equivalent. Lastly, we consider the number of moves that a square is allowed to perform. We only consider scenarios where each square is allowed to move at most x times, where x is a constant independent of the number of squares. If each square is allowed to perform only a single move, the problem and resulting movement schedule is also called monotonic . Note that in some scenarios the problem is trivial: in the unbounded scenarios in which the number of allowed moves is at least 2 , we can simply move all robots arbitrarily far away one by one until our workspace is empty, and then move them back in any different order. Contributions In Section 3 , we show that the labeled monotonic scenario is NP-hard. In Section 4 , we give a polynomial time algorithm for the scenario in which the squares are unlabeled and have unit length. In Section 5 , we show how for squares that are bigger than unit length, the unlabeled monotonic scenario is also NP-hard. Lastly, in