On the parameterized complexity of a generalized Rush Hour puzzle ^{∗}

H. Fernau^{†}, T. Hagerup^{§}, N. Nishimura^{¶}, P. Ragde^{¶}, K. Reinhardt^{†}

July 11, 2003

Abstract

We consider the parameterized complexity of a generalized version of the game Rush Hour^{1}, which is a puzzle requiring the player to find a sequence of moves by vehicles to enable a special target vehicle to exit from a grid-shaped game board that might contain obstacles. Although the problem is PSPACE-complete, we demonstrate polynomial-time algorithms when either the total number of vehicles or the total number of moves is a fixed constant. Our contributions are two-fold, entailing the application of the ideas of parameterized complexity to games and to motion-planning problems (albeit in this case problems of a very constrained nature).

1 Introduction

The goal of the Rush Hour puzzle is to remove a target vehicle from a grid by moving it and other vehicles until eventually it reaches an exit on the perimeter of the grid. Each vehicle may move either horizontally or vertically, depending on its initial configuration, where a vehicle can be moved from one position to another only when all intervening grid positions are empty. The original puzzle consists of a 6 × 6 grid with a single target vehicle, a single fixed exit, and vehicles of width one and length two or three.

The Rush Hour puzzle is one of many games and puzzles determined to be computationally difficult to solve; the reader is referred to Demaine’s survey of such problems [Dem01]. For example, it has been shown by Ratner and Warmuth that the well-known (n^{2} − 1)-puzzle is NP-complete [RW90]. This is interesting, since it corresponds to a variant of Rush Hour where all cars have size 1 × 1 but can move in all four directions. The original Rush Hour problem was generalized by Flake and Baum to allow arbitrary grid sizes and placements of the exit, and shown to be PSPACE-complete [FB01].

∗This work was initiated while the authors were participants in the Dagstuhl Seminar on Parameterized Complexity, July 2001. The first author is currently with University of Newcastle, Australia. Contact author:

**fill in**.

†Universität Tübingen, Germany; {fernau,reinhard}@informatik.uni-tuebingen.de § Universität Frankfurt, Germany; torben@mpi-sb.mpg.de ¶ University of Waterloo, Canada; {nishi,plragde}@uwaterloo.ca

1The name “Rush Hour” is a trademark of Binary Arts, Inc.

To formalize the instance of the puzzle and the moves in its solution, we extend the generalization formulated by Flake and Baum [FB01]. In our generalization, the game board is an infinite plane; cars are either vehicles (which move) or obstacles (which do not move); cars are rectangles; each vehicle can move either north and south, or east and west; for each vehicle, the goal is a set of specified positions in the plane, one of which the vehicle must occupy. Clearly, by placing cars and obstacles appropriately, we can simulate the finite grid of the earlier formulations. Note that “exits” can be expressed as certain goal positions selected to ensure that no “interference” with the remaining cars occur. Finally, a similar argument shows that we could also have insisted on putting an explicit “boundary” around every game, e.g., by choosing an appropriately large delimiting rectangle; this can be easily modelled by four obstacles, as observed above.

The PSPACE-completeness result of Flake and Baum indicates that, from a “classical” point of view, there is not much hope of finding a solution to a given Rush Hour instance in polynomial time on a computer. We contrast their result therefore by showing that for small fixed numbers of cars or for small fixed numbers of moves allowed, there exist polynomial-time algorithms. More specifically, we employ the framework of fixed-parameter (in)tractability as developed (mainly) by Downey and Fellows [DF99]. A problem is called fixed-parameter tractable if, for a given instance of size n and of parameter value k, it is solvable in time O(f(k)p(n)), where f is an arbitrary function and p is a polynomial. In this line of research, one important aspect is to find parameters to which the seemingly unavoidable combinatorial explosion could be restricted. In the case of Rush Hour, we find two such parameters in a natural way: the number of cars and the number of moves.

We view our results as a first step towards applying the techniques of parameterized complexity to games and towards motion planning problems. Hence, our paper demonstrates that, in particular circumstances, parameterized algorithms can be successfully developed in the area of motion planning. In that area, the general aim is to develop algorithms that permit robots to optimally navigate in a specific terrain, such as an industrial plant. References can be found in the paper of Flake and Baum. We will return to this issue in the last section.

The paper is organized as follows. In Section 2, we introduce our formalization of Rush Hour. In the following two sections, we discuss two different parameterizations of Rush Hour: Section 3 deals with parameterizing by the number of cars, while Section 4 discusses the parameterization by the number of moves needed to reach a valid target configuration. Section 5 discusses two generalizations of the Rush Hour problem as examined up to this point, establishing a parameterized algorithm in the case in which the number of moves is the parameter. In Section 5, we summarize our results and open several avenues for future research.

2 Definitions

Need an introductory paragraph here.  PR

This section introduces the generalization of the Rush Hour problem in mathematical terms. Our notion is deliberately more general than Flake and Baum’s [FB01], but there is still room for further generalization, as indicated in the following sections.

To indicate some standard notation from mathematics, let us mention that often we use subscript notations like u_{a} in order to denote the function value u(a) for better readability. The symbol π_{i} denotes the projection of a vector to its ith coordinate.

   Maybe more general stuff here HF
   We need a better set of terminology than cars and vehicles, as both imply
motion.  Perhaps objects (obstacles, cars)?  NN I took the terminology cars
(obstacles, vehicles), because ``cars'' as the general term hints at the
``origin'' of our problem, while obstacles and vehicles express, from their
Latin origin, the disability and ability to move.  Moreover, I fear that with
changing notions (again) we must very carefully revise all ``abbreviations'':
now, os should consistently refer to obstacles, vs to vehicles and cs to cars.
Hopefully, we employed only the macros...  HF

Definition 1 An instance of the Rush Hour problem is given by a tuple (C, S, p^{0}, d, Z), where C is a set of cars and the remaining components are functions mapping C to P(ℝ^{2}), ℝ^{2}, ℝ^{2} and P(ℝ), respectively. For each c ∈ C, S_{c} is the shape of c, p_{c}^{0} is its initial position, d_{c} is its directional vector, and Z_{c} is the set of its goals.

We distinguish between two kinds of cars:

• a car c with d_{c} = (0, 0) cannot move; it is therefore an obstacle.

• a car c with d_{c} ≠ (0, 0) is able to move; it is therefore a vehicle.

C is therefore partitioned into the set O of obstacles and the set V of vehicles.

Let us clearly indicate once more in which ways our formalization deviates from the one of “Generalized Rush Hour” as offered by Flake and Baum:

• We allow arbitrary positions of objects, not just “grid positions” as Flake and Baum do.

As should become clear in the course of the following discussions, this generalization is not too extreme.

• We allow both vehicles and obstacles, while Flake and Baum only allow vehicles (called cars there).

• Cars can have arbitrary shapes and are not restricted to rectangles of size 1 × 2 or 1 × 3 as with Flake and Baum.

• Flake and Baum limit the game board to be a rectangle, while we allow arbitrary space for rearranging the cars.

• While Flake and Baum require a specific “target car” to leave the game board through a specific “exit”, we specify “goal positions” for each vehicle.^{2}

• Each vehicle may move in an arbitrary direction, while in the grid model of Flake and Baum, only vertical and horizontal movements were permitted.

2Formally, goal positions are also specifiable for obstacles, but this can make an instance easily and obviously unsolvable. In fact, by our definitions goal positions must be specified for obstacles.  NN

In fact, we will mostly discuss in this paper a restricted form of Rush Hour where we only allow rectangular cars (of arbitrary size) which can move only parallel to some coordinate axis.

A car c ∈ C initially covers the points p_{c}^{0} + S_{c} in the plane, and it can be moved to positions of the form p_{c}^{0} + ud_{c}, for u ∈ ℝ, where it will cover the points (p_{c}^{0} + ud_{c}) + S_{c}. In other words, the position of car c (at a certain moment in time) can be described by a number u_{c} ∈ ℝ.

The object of the game is, starting with u_{c} = 0 for all c ∈ C, to change the values u_{c} one at a time to make u_{c} ∈ Z_{c} for all c ∈ C without passing through situations in which some point in the plane is covered by more than one car. This motivates the following definitions.

Definition 2 A configuration of an instance (C, S, p^{0}, d, Z) of the Rush Hour problem is a function u : C → ℝ. A configuration u is legal if (p_{c}^{0} + u_{c}d_{c}) + S_{c} ∩ (p_{c′}^{0} + u_{c′}d_{c′}) + S_{c′} = Ø for all c, c′ ∈ C with c ≠ c′. The configuration 0 that maps every c ∈ C to 0 is the initial configuration, and a configuration u is a goal configuration if u_{c} ∈ Z_{c} for all c ∈ C.

Let us now fix an instance I = (C, S, p^{0}, d, Z) of the Rush Hour problem and define U to be the set of its configurations. A move is defined below to be an operation that adds to (or subtracts from) the position of a car a multiple of its directional vector. The move is legal if the initial and final configurations as well as all intermediate configurations are legal, that is, no other car blocks the passage.

Definition 3 For all c ∈ C and Δ ∈ ℝ, we define ϕ_{c,Δ} as the mapping from U to itself for which, for all u ∈ U,

(ϕ_{c,Δ}(u))_{b} = \{ \begin{matrix}u_{b} + Δd_{c}, & if b = c; \\ u_{b}, & if b ∈ C \ c. \end{matrix}

A move is a function of the form ϕ_{c,Δ} for some c ∈ C and Δ ∈ ℝ. A move ϕ_{c,Δ} is legal in a configuration u if the configuration ϕ_{c,δ}(u) is legal for each δ with 0 ≤ δ ≤ Δ if Δ ≥ 0 or 0 ≥ δ ≥ Δ if Δ ≤ 0.

Definition 4 Let u and v be configurations. If there is a move ϕ, legal in u, such that v = ϕ(u), we call v a successor of u and write u → v. Thus → is a relation on U.

Definition 5 A solution to I is a finite sequence u_{0}, u_{1}, …, u_{t} of legal configurations such that for i = 1, …, t, u_{i−1} → u_{i}, u_{0} is the initial configuration, and u_{t} is a goal configuration. The integer t is called the length of the solution.

Given a finite subset V of u and a subset E of (V × V) ∩ →, we can form a configuration graph G = (V, E). If there is a path in G from the initial configuration to a goal configuration, obviously I has a solution. The trick will be to define G in such a way that the converse also holds. In Section 4, the correspondence should also be length-preserving—the length of a shortest path in G from the initial configuration to a goal configuration should equal the length of a shortest solution, if either exists—whereas this is not necessary in Section 3.

We will actually consider only a very special case of the general problem, one in which all cars are axes-parallel rectangles and the only directional vectors allowed are (1, 0), (0, 1) and (0, 0).

Definition 6 An instance (C, S, p^{0}, d, Z) of the Rush Hour problem is an APR instance if, for all c ∈ C, d_{c} ∈ {(1, 0), (0, 1), (0, 0)} and S_{c} is an open rectangle contained in the first quadrant of the plane with the origin as a corner.

In this special case, a car c ∈ C is called horizontal if d_{c} ∈ {(1, 0), (0, 0)} and vertical if d_{c} ∈ {(0, 1), (0, 0)}. Horizontal and vertical vehicles are defined analogously. By using h or v as subscript, we can refer to the corresponding sets of cars or vehicles.

Observe that Flake and Baum actually introduced a special version of APR Rush Hour. We briefly discuss some modifications of the APR Rush Hour problem:

1. The arguments given for the two-dimensional case can be generalized in a natural way to multi-dimensional versions of the game. For example, in the three-dimensional case, cars would be “bricks” instead of rectangles.

2. Obstacles play a special role in the following arguments. In fact, the restriction to rectangular shapes is completely unessential for them. Each obstacle can be characterized by the blockage it causes in the “lane” in which each vehicle travels; it is thus equivalent to a collection of rectangular obstacles, as each interval of blockage can be associated with a rectangle.

3. In order to get the famous (n^{2} − 1)-puzzle as a special case, it would be interesting to consider a variant where cars may move both horizontally and vertically. In particular, it would be interesting to see whether the variant where each vehicle can move both vertically and horizontally (as it is the case for the (n^{2} − 1)-puzzle) would be in NP or also PSPACE-complete.

In this respect, it is interesting to observe that other “motion planning” puzzles like Sokoban and Atomix are in fact PSPACE-complete. In particular, the latter fact is interesting since the relations between Atomix and our case of Rush Hour appear to be rather close:

(a) The (n^{2} − 1)-puzzle is a special case of Atomix.

(b) Atomix with “generalized moves” [HEFN01] is, in a sense, a special case of this variant of Rush Hour, where all cars are squares of shape 1 × 1. To our knowledge, the “classical complexity” of this game has not yet been determined. The proof of PSPACE-completeness of Atomix [HS01] is not applicable in this case.

3 Parameterized by number of cars

In this section, we consider the following problem: Given an APR instance I = (C, S, p^{0}, d, Z) of the Rush Hour problem, decide whether I has a solution. Taking n as the size of (the encoding of) I and setting k = |C|, we are interested in algorithms whose running time grows slowly with n and possibly rapidly with k.

When the number of vehicles, k, is a fixed constant, we are able to derive a polynomialtime algorithm which entails a search for a path in a graph that represents transitions among configurations.

The idea behind our algorithm is that we can develop a succinct representation of a configuration so that the number of possible configurations is a function of k. By viewing configurations as nodes in a graph in which edges represent sequences of legal moves, finding a solution entails searching for a path from the initial configuration to a goal configuration. If the graph is guaranteed to be constant in size, then so is the cost of the search.

We formulate the following definitions and arguments considering the first coordinate, describing the horizontal direction. Analogous results hold for the vertical direction, namely the projection π_{2} to the second coordinate, obtained by replacing π_{1}, left, and right, respectively, with π_{2}, lower, and upper.

Definition 7 Given an APR instance (C, S, p^{0}, d, Z), for each c ∈ C_{h}, its (horizontal) lane is defined as the interval ℓ_{h}(c) = π_{2}(p_{c}^{0} + S_{c}). On C_{h}, we define the relation <_{h} as c <_{h} c′ iff

(ℓ_{h}(c) ∩ ℓ_{h}(c′) ≠ Ø) ∧ (π_{1}(p_{c}^{0}) < π_{1}(p_{c′}^{0})).

The horizontal conflict graph is a directed labeled graph with the vertices C_{h} and the edges <_{h}. The length of an edge (c, c′) is π_{1}(S(c)).

Intuitively, a lane of a vehicle c is the set of points that, in the absence of any other cars, c could possibly occupy in the course of the game. The intersection of horizonal lanes of two vehicles implies that there could exist situations in which one vehicle hinders the other.

Our aim is to define a discretized version of each configuration of an APR instance such that all legal moves can be simulated legally in the discretized version. To this end, we will define certain positions for each vehicle which are important for this vehicle in the sense that we can move it legally to its nearest “important position” to the left or downward, respectively, depending on whether we consider a horizontal or vertical vehicle. In this way, we can bound the number of possible positions of each vehicle, which puts the Rush Hour problem, restricted to APR instances and parameterized by the number of cars, into FPT.

We consider the case of a horizontal vehicle in more detail, as vertical vehicles can be treated analogously. Intuitively, the important positions correspond to locations resulting from a sequence of cars, corresponding to a path in the conflict graph, “piling up” against the right border of a vertical lane, against an initial or goal position of a car, or off the left end of the game board. Some of the important positions may not be reachable in the sense that one car in a path might be an obstacle, preventing further leftward motion; our goal is to bound the number of such points and, in Definition 11, to further distinguish among points to ensure that the resulting configuration is legal.

Definition 8 The length of a path q = {c_{1}, …, c_{j}} in the horizontal conflict graph is ∥ q ∥= ∑_{i=1}^{j−1} π_{1}(S(c_{i})). We use [c′, c] to denote the longest path from c′ to c.

Definition 9 An x-coordinate s is important for the horizontal vehicle c if one of the following conditions holds:

1. s = x+ ∥ [c′, c] ∥ for any car c′ and x one of the following: a goal position of c′, x_{r} for a vertical lane (x_{ℓ}, x_{r}), or π_{1}(p_{c′}^{0}), the initial position of the car c′; or 2. s = x− ∥ [c, c′] ∥ −π_{1}(S(c′)) for x the minimum over all x_{ℓ} for vertical lanes (x_{ℓ}, x_{r}) and

c′ such that ∥ [c, c′] ∥ is maximum.

We say that the important coordinate s is caused by c′ at x. For convenience, we refer to the last type of coordinate as the −∞ coordinate for c.

Example 1 Assume C_{h} = {o, c_{1}, c_{2}, c_{3}, c_{4}} with p_{o}^{0} = d_{o} = (0, 0), p_{c_{1}}^{0} = (1, 3), p_{c_{2}}^{0} = (8, 5), p_{c_{3}}^{0} = (9, 1), p_{c_{4}}^{0} = (15, 3) and d_{c_{i}} = (1, 0) for i ≤ 4. Furthermore, let (5, 8) be a vertical lane, and assume that all goal position sets are empty.

o c_{1}  c_{2} c_{3}  c_{4}  c_{5} c_{6}  c_{7} \overline{}x_{r} 0  5  10  15  20  25  30  35

The important coordinates can be determined as follows. Due to the trivial path [c_{1}, c_{1}], where ∥ [c_{1}, c_{1}] ∥= 0, 1 (initial position) and 8 (x_{r}) are important for c_{1}, as well as −12 (−∞, caused by c_{4}). For c_{2}, the important coordinates are 6 = 1 + 5 = π_{1}(p_{c_{1}}^{0}) + π_{1}(S(c_{1})) and 13 = 8 + 5 by the path [c_{1}, c_{2}] of length 5, 8 = 8 + 0 (initial position and x_{r}) by the path [c_{2}, c_{2}] of length 0, and −7 (−∞). The important coordinates for c_{3} caused by o are 2 (initial position) and 10 (x_{r}); we observe that it does no harm to include 10 even though it is not possible for o to move to the right of the vertical lane to form a “pileup” with c_{3}. Further important coordinates for c_{3} are 6 (caused by c_{1}, initial position), 13 (caused by c_{1}, x_{r}), 9 (caused by c_{3}, initial position), 8 (caused by c_{3}, x_{r}), and −5 (−∞). Finally since ∥ [o, c_{4}] ∥= π_{1}(S(o)) + π_{1}(S(c_{3})) = 7, ∥ [c_{1}, c_{4}] ∥= π_{1}(S(c_{1})) + π_{1}(S(c_{2})) = 12, ∥ [c_{2}, c_{4}] ∥= 7, ∥ [c_{3}, c_{4}] ∥= 5, and ∥ [c_{4}, c_{4}] ∥= 0, the coordinates 7 = π_{1}(p_{o}^{0})+ ∥ [o, c_{4}] ∥, 15 = x_{r}+ ∥ [o, c_{4}] ∥ = π_{1}(p_{c_{2}}^{0})+ ∥ [c_{2}, c_{4}] ∥ = x_{r}+ ∥ [c_{2}, c_{4}] ∥ = π_{1}(p_{c_{4}}^{0})+ ∥ [c_{4}, c_{4}] ∥, 13 = π_{1}(p_{c_{1}}^{0})+ ∥ [c_{1}, c_{4}] ∥= x_{r}+ ∥ [c_{3}, c_{4}] ∥, 20 = x_{r}+ ∥ [c_{1}, c_{4}] ∥, 14 = π_{1}(p_{c_{3}}^{0})+ ∥ [c_{3}, c_{4}] ∥, 8 = x_{r}+ ∥ [c_{4}, c_{4}] ∥, and 0 (−∞) are all important for c_{4}. Note that 18 = 8 + 5 + 5 = x_{r} + π_{1}(S(c_{1})) + π_{1}(S(c_{3})) is not important for c_{4}, since the path from c_{1} to c_{4} via c_{2} is longer than the path from c_{1} to c_{4} via c_{3}.

We briefly consider, in addition, the horizontal cars c_{5}, c_{6}, and c_{7}. Although there are four possible paths from c_{1} to c_{7}, and in general possibly an exponential number of paths, since the order of cars cannot be changed, it is the longest path between a pair of cars that determines the minimum distance between them in any configuration.

To determine the number of important coordinates, we first observe that there are at most k cars that can cause important coordinates for a particular car. The following statement

(and hence the lemma) is not true unless we restrict the number of goal
positions to a constant.  Other alternatives include making the number of goal
positions into a parameter or altering the lemma below.  NN I am currently

thinking that we may overcome this problem by taking the goal positions out of
our definition of important coordinates altogether.  Then, Theorem 1 would
have to be slightly changed, since at the very end of the simulation |C| more
moves might be necessary, since up to that point ``only'' the discretized
versions of the goal positions have been reached.  That this is indeed
possible should also follow with Lemma 4.  What do you think?  HF There are O(k)

values of x (O(1) goal positions, at most k right borders of vertices lanes, and one initial position), resulting in the lemma below:

Lemma 1 If we have k cars, then the total number of important coordinates is O(k^{3}).

In the following, we are going to show that Rush Hour, parameterized by the number of cars, is fixed-parameter tractable. To this end, we introduce “discretized” coordinates based on the notion of important coordinates introduced above.

Definition 10 The discretized configuration u′ of a configuration u of an APR instance I is derived from u by taking, for each position of a vehicle in u, a position whose coordinate is rounded down to the nearest important coordinate value for that vehicle. If the vehicle is to the left of all of its important coordinates, its position is rounded up (to the right) to the nearest important coordinate value for that vehicle.

Unfortunately this definition is not sufficient, as shown by the following sequence of moves, starting with the configuration given in Example 1: c_{3} moves left (to 6) touching c_{1}, c_{1} moves to −12, c_{2} moves to −7, and finally c_{4} moves left (to 11) touching c_{3}. If we were to now round c_{4}’s non-important x-coordinate down to its nearest important coordinate (8), c_{4} would then overlap with c_{3}.

One alternative would be to define 11 as an additional important coordinate for c_{4}, that is, for each pair of cars c′ and c, consider each path from c′ to c, not only the longest path from c′ to c. To see that we would then require an exponential number of important coordinates, we consider cars c_{5} through c_{7}, and in general cars c_{2+3i}, c_{3+3i} and c_{4+3i} in analogous positions to the right, where c_{2+3i} is longer than c_{3+3i}. The number of important coordinates for c_{4+3k} would be Ω(2^{k}), as for each of the k triples of cars, the position of c_{4+3i} could depend on c_{1+3_{i}} and c_{3+3i}, as in the set of moves given above, or on c_{1+3i} and c_{2+3i}, as obtained by moving c_{2+3i} and c_{3+3i} both until they touch c_{1+3i}, and then moving c_{4+3i} until it touches the longer of the two, namely c_{2+3_{i}}. We further observe that trying to fix the definition by rounding positions up in certain cases would run into similar problems with respect to paths from a car to cars to its right.

To alleviate the problem, we designate certain important coordinates as active; intuitively these consist of cars in their own initial or goal positions, touching right borders of lanes, or at −∞ coordinates, or in pileups based on current positions of cars. Although not every active important coordinate will be guaranteed to provide a clear spot for a vehicle, we will show that moving a vehicle left to the closest active important coordinate will always result in a legal move.

Definition 11 Let x_{u}(c) := π_{1}(p_{c}^{0}+u_{c}d_{c}) = x denote the x-coordinate of a car c in configuration u. An important coordinate for a vehicle c is called active in a configuration u if it is caused by a car c′ at x and either x_{u}(c′) = x or c = c′. Let <_{h}^{+} be the transitive closure of <_{h}. The discretized configuration δ(u) of a configuration u of an APR instance I is obtained iteratively from u by the following procedure: Take a (so far non-discretized) position of vehicle c′ where all cars c′′ with c′′ <_{h}^{+} c′ are already at discretized positions and move it left to the nearest currently active important coordinate value for that vehicle. If the vehicle is to the left of all of its important coordinates, its position is rounded up (to the right) to the nearest (hence leftmost) currently active important coordinate value for that vehicle.

As an example, we consider the previous figure with C_{h} = {o, c_{1}, c_{2}, c_{3}, c_{4}} and the initial positions of c_{2}, c_{3}, and c_{4} set to be (12, 5), (12, 1) and (20, 3), respectively. In the configuration u illustrated in the figure, we observe that c_{1} is at its initial position and hence at an active important coordinate. As c_{2}’s position is caused by c_{2} (for x_{r}), this is also an active important coordinate, and similarly does not need to be altered to form a discretized configuration. We next consider c_{3}, and as its current x-coordinate (9) is not important (as (9, 1) is not its initial position in this example), it is rounded down to 8 (caused by c_{3} for x_{r}). The current position of c_{4} (15) is caused by c_{2} at x_{u}(c_{2}) (x_{r} + ∥ [c_{2}, c_{4}] ∥) and hence active.

Suppose instead the configuration u had c_{1}, c_{2}, and c_{3} each two units farther to the left (at positions (−1, 3), (6, 5), and (7, 1), respectively). In this case, in δ(u) c_{1} would be moved to active important coordinate −12, as there is no other important coordinate left of −1. Although 6 is an important coordinate for c_{2} due to the initial position of c_{1}, since c_{1} is not in its initial position, 6 is not active, and hence c_{2} is moved to −7. Similarly, 6 is not active for c_{3}, which is moved instead to 2. Finally, c_{4} is moved to 8 (active for x_{r} and c = c′ = c_{4}).

Lemma 2 If I is an APR instance with k cars, then there are at most k^{2} important coordinates for a car and at most k^{2k} discretized configurations.

But only k^{k} configurations, which are really the discretization of another
configuration; we should be able to use that for a better estimation for the
graph KR

Since the cars on a path in the conflict graph from c to c′ must always lie between c and c′ in any legal configuration obtainable from the initial configuration, we can conclude the following:

Lemma 3 In a legal configuration u for every pair (c, c′) of horizontal cars and for each path q from c to c′ it is true that ∥ q ∥≤ x_{u}(c′) − x_{u}(c).

   The lemma above used to also say ``Furthermore, c′ can never be to the left
of an active important coordinate for c′.''  However, this is not true, for
example for c′ = c and x_{r} the right border of a lane to the right of its current
location.  NN

Lemma 4 The sequence of moves from u to δ(u) as described in the definition is legal. Thus the discretized configuration δ(u) of a legal configuration u is legal.

Proof: We consider the move of an arbitrary horizontal car c′ and show that in the discretized configuration δ(u) it will not overlap with any other car. If δ(u)(c′) is greater than x_{u}(c′), then x_{u}(c′) was to the left of any important coordinate, and hence δ(u)(c′) is the leftmost important coordinate, the −∞ coordinate for c′. In this position c′ cannot overlap with any vertical car. Suppose that there were a car c′′ such that c′′ in the configuration u would overlap with c′ in configuration δ(u). As c′ <_{h}^{+} c′′, c′′ must be to the left of its −∞ coordinate and hence to the left of all important coordinates. In δ(u), c′′ is placed at its −∞ coordinate, and thus will not overlap with c′. The argument can be made iteratively for c′′ and any potential overlap.

If instead δ(u)(c′) is less than x_{u}(c′), we show that c′ cannot overlap either a vertical car or a horizontal car. Clearly if c′ is to the left of a vertical lane in u, it will remain to the left of that lane in δ(u). Since the right border of any vertical lane is an active important coordinate, if x_{u}(c′) is to the right of a vertical lane, then δ(u)(c′) cannot be smaller than x_{r} for that lane. We can then conclude that the discretization does not introduce any overlaps with vertical cars.

Finally, since c′ is moved to the left and cannot overlap with cars whose horizontal lanes do not overlap with that of c′, it will suffice to show that for each car c′′ such that c′′ <_{h} c′, c′ does not overlap c′′ in δ(u). For any such c′′, since u is legal we have x_{u}(c′′) + π_{1}(S(c′′)) ≤ x_{u}(c′). Let c be the car which caused the important coordinate δ(u)(c′′) ≤ x_{u}(c′′) and ℓ be the length of the longest path from c to c′. Then by Lemma 3, x_{u}(c) + ℓ ≤ x_{u}(c′); since δ(u)(c) + ℓ is an active important coordinate and δ(u)(c′) the active important coordinate closest to x_{u}(c′), clearly δ(u)(c) + ℓ ≤ δ(u)(c′). Furthermore, let ℓ′ the length of the longest path from c to c′′. Then ℓ′+π_{1}(S(c′′)) ≤ ℓ and thus δ(u)(c′′)+π_{1}(S(c′′)) = δ(u)(c)+ℓ′+π_{1}(S(c′′)) ≤ δ(u)(c)+ℓ ≤ δ(u)(c′), hence after the move c′ does not overlap c′′, as needed to complete the proof.

[figure: c; c′; c′′; ℓ′; ℓ]

Theorem 1 If the APR instance I has a t-step solution u_{0}, …, u_{t}, then it also has a solution u_{0′}, …, u_{t′} consisting only of discretized configurations with t′ ≤ t|C|.

Proof: We prove this through a straightforward simulation of a legal sequence of moves in I by a sequence of moves which contains the sequence of discretized configurations δ(u_{0}), …, δ(u_{t}) and possibly some intermediate configurations as well (this is necessitated by the fact that δ(u_{i−1}) and δ(u_{i}) can differ in the placement of more than one car). The proof consists of showing that such a sequence of moves is legal. Note that the initial configuration is already discretized by definition.

It is easy to see that if the ith move from u_{i−1} to u_{i} is by a vertical vehicle then the same move from δ(u_{i−1}) to δ(u_{i}) is also legal. Since all right borders of vertical lanes are important coordinates, it is not possible for a lane to be blocked by a vertical car in δ(u_{i−1}) but not in u_{i−1} (nor in δ(u_{i}) but not in u_{i}).

Suppose that the ith move is by a horizontal vehicle h moving to the left. If u_{i}(h) < δ(u_{i−1})(h) ≤ u_{i−1}(h), then moving h from δ(u_{i−1})(h) to δ(u_{i})(h) is legal (and results in the legal configuration u′_{i−1}), as it consists of the move from δ(u_{i−1})(h) to u_{i}(h) (legal, since the move from u_{i−1}(h) to u_{i}(h) is legal) and the move from u_{i}(h) to δ(u_{i})(h) (legal, by Lemma 4). If instead u_{i}(h) ≥ δ(u_{i−1})(h), then δ(u_{i})(h) = δ(u_{i−1})(h), and the move is legal as a consequence of the legality of the the move from u_{i−1}(h) to δ(u_{i−1})(h) (from Lemma 4).

We observe that u′_{i−1} may not be equal to δ(u_{i}), as in the discretization of u_{i}, cars other than h may have moved as a consequence of the activation of coordinates caused by h’s new location. Since the location of each other car in δ(u′_{i−1}) = δ(u_{i}) will be at an active location, it then suffices to add intermediate discretized configurations, one for each of the at most |C| cars that are moved in the discretization.

We handle the case that h moves right in a symmetric way by regarding the left-move from δ(u_{i}) to δ(u_{i−1}) and then reversing the intermediate sequence, including the directions.

Analogous constructions can be made regarding vertical vehicles. Thus, the theorem above holds as well for the positions of vertical cars being discretized in the same way.

The previous theorem implies the correctness of an algorithm that consists of the formation of a configuration graph restricted to discretized configurations, followed by the search for a path from the initial to a goal configuration. To create the graph, we first form the nodes, one for each of the at most k^{2k} discretized configurations (Lemma 2). We observe that we can restrict the outdegree to 2k by allowing, from a particular node, each neighbour corresponding to one of the k cars moving to its next important coordinate to the left or to the right. Determining the existence of an edge is equivalent to determining if the move of a car is legal or not. To determine the running time of the algorithm, we observe that the cost of a search is no greater than that of creating the graph, and that the cost will be k^{2k} · 2k (the number of possible edges) multiplied by the cost of a legality test.

We analyze the cost of a legality test for the move of a horizontal car to the right, as the analyses of other moves are analogous. We define I_{h}(v) to be the open interval of positions at which some horizontal car h overlaps the lane of a vertical car v. Analogously, the interval I_{v}(h) can be defined.

It is legal for h to be able to move right to a position x if and only if the conditions are satisfied:

1. (no collisions with vertical cars) For each vertical car v at position y, either y ∉ I_{v}(h) or x ∉ I_{h}(v).

2. (no collisions with horizontal cars) For each horizontal car h′ to the right of h and at position x′, x + π_{1}(S_{h}) ≤ x′.

It is not difficult to see that Condition 1 can be checked in O(k^{2}) time Why not O(k)? NN

Naively, we check something for each vertical car v at y and for each position
z ∈ I_{v}(h), which looks quadratic HF

and that Condition 2 can be checked in O(k) time. This yields a running time of This is the

complexity from the previous version.  NN O(n + k^{3k} · k^{3}) = O(n + k^{3(k+1)}).

The algorithm above, applied to the case considered by Flake and Baum (an n by n grid), yields a fixed-parameter (FPT) algorithm. However, in full generality, there is no natural parameter n, and what we have is simply an algorithm whose running time is exponential in the number of cars.^{3} The main utility of this result can be seen in the next section, where we get a true FPT algorithm when the number of moves is a parameter.

3Following our arguments carefully, the reader will have noticed that the way we treat the case when a car moves “arbitrarily far” to the left in terms of discretized coordinates easily leads to the construction of an “enclosing rectangle formed by obstacles” which can be constructed for each APR instance, this way giving a suitable notion of an n × n grid also in our more general case.

4 Parameterized by number of moves

To handle the case where the number of moves m is a fixed constant, we compute a set of cars with the property that if all other cars are removed, we are certain that for every t ≤ m this will not change an instance without a t-step solution into one that has a t-step solution. In other words, the computed set should contain all cars that might be relevant. It may contain arbitrary spurious cars that, in actual fact, do not make any difference, but we bound the number of relevant cars by 3^{m}. Then we apply an algorithm similar to the one of the previous section, which leads to a running time of the form 2^{O(m^{2}·3^{m})}p(n).

We make use of the following definitions in proving a bound on the size of the set of cars relevant to a t-step solution. We first consider the set of possible moves of a car c in the absence of subset of the cars.

Definition 12 The instance (C′ ∪ {c}, S, p^{0}, d, Z) is obtained from the instance (C, S, p^{0}, d, Z) by removing the cars which are not in C′ ∪ {c} and thus regarding S, p^{0}, d and Z as restricted to C′ ∪ {c}. For a subset C′ ⊂ C of cars that are not removed and a special car c ∈ C \ C′, the restriction interval of c by C′ is

r(c, C′) := {Δ ∈ ℝ | ϕ_{c,Δ} is legal in the instance (C′ ∪ {c}, S, p^{0}, d, Z)}.

Definition 13 The set H(c, C′) is the smallest subset C′′ of C′ restricting c to the same interval r(c, C′′) = r(c, C′), where in order for the definition to be unambiguous, we assume some order of sets of equal size (i.e. lexicographically).

Since a car c is restricted by the closest car on each side, |H(c, C′)| ≤ 2.

Our goal is to give an upper bound on the size of the set of cars C(t) that need to be moved if there is a sequence of t moves resulting in a goal configuration. We define C(t) recursively with the base case C(ℓ) defined to be the set of ℓ cars whose goal positions do not include their initial positions (which must be moved anyway to reach a goal configuration, thus we have to consider t − l recursion steps), and

C(t + 1) := C(t) ∪ ⋃_{c∈C(t)} H(c, C \ C(t)),

where to C(t) we add for each car c in C(t) a set of cars sufficient for restricting its interval in C(t). Since |H(c, C′)| ≤ 2, |C(t + 1)| ≤ 3|C(t)| yielding the bound |C(t)| ≤ |C(l)|3^{t−l} = l3^{t−l} ≤ 3^{t−1}.

Lemma 5 For any solution w where there is an i > 0 such that no car in C(i + 1) \ C(i) is moved, there is a solution w′ that is a subsequence of w in which only cars in C(i) are moved.

Proof: Suppose w is a solution as described in the lemma; we consider the smallest i > 0 such that no car in C(i+1)\C(i) is moved during w. Since the cars in C(i+1)\C(i) stay in their initial positions during w, no car c ∈ C(i) can be moved to a position outside of r(c, C(i + 1) \ C(i)).

We now demonstrate that r(c, C(i + 1) \ C(i)) = r(c, C \ C(i)) by first observing that for each car c ∈ C(i), by the definition of H(c, C′) clearly r(c, C \ C(i)) = r(c, H(c, C \ C(i))). Using the recursive definition of C(i + 1), we observe that

C(i + 1) \ C(i) = ⋃_{c∈C(i)} H(c, C \ C(i)) \ C(i).

For any set X, H(c, X) is defined to be the smallest subset of X restricting c to the same interval as X. For X = C(i+1)\C(i), the only part of X restricting c is the subset H(c, C \C(i)). This proves that r(c, H(c, C \ C(i))) = r(c, H(c, C(i + 1) \ C(i))). Finally, by another application of the definition of H(c, C′), we can conclude that r(c, H(c, C(i + 1) \ C(i))) = r(c, C(i + 1) \ C(i)) and hence r(c, C \ C(i)) = r(c, C(i + 1) \ C(i))).

Since no car in C(i) can be in a position outside of r(c, C(i + 1) \ C(i))) = r(c, C \ C(i)), we can conclude that no car is further restricted if all cars in C \ C(i) stay in their initial positions. Thus, we can conclude that the subsequence w′ of w is legal, where w′ consists of moves in w of cars in C(i).

We can then conclude that an optimal solution of length m moves a car in C(i + 1) \ C(i) for every i ≤ m, and thus does not move any car outside of C(m).

We now restrict our attention to the instance (C(m), S, p^{0}, d, Z) and execute an algorithm similar to the one of the previous section. The difference to the previous section is that to maintain the number of moves, we need a 1-to-1 correspondence between moves in G and their counterparts in G′. Given a legal sequence of moves in G, we find the corresponding sequence in G′ by repeating the following procedure until no further changes are possible:

Take a move to the right (resp. down) and make it as short as possible such that the invariant in Section 3 holds and the rest of the moves is still legal. Take a move to the left (resp. up) and make it as long as possible such that the invariant holds and the move is still legal.

For the obtained sequence in G′ we can say the following: Every position, which is used at any time during the sequence by a vehicle v is

the initial position of v,

a goal position of v,

the right (resp. lower) border of a vertical (resp. horizontal) lane or

π_{1}(S(v′)) right of (resp. below) a position which was used by a vehicel v′ with v′ <_{h} v (resp. v′ <_{v} v) at any time during the sequence.

If none of these were the case then the above procedure would cause this position to be more to the left (resp. higher). Assume that 3^{m} is also an upper bound on the number of goal positions available to a single car, then the number of possible positions for a car in the first 3 cases is 2 · 3^{m}. The 4-th case means in other words that v touched one of 3^{m} possible vehicles v′ with v′ <_{h} v (resp. v′ <_{v} v) at some time. The position of this vehicle itself is either one of of 2 · 3^{m} possible positions for a vehicle in the first 3 cases leading to 2 · 3^{m}3^{m} possibilities in ”second cause” or it is caused by touching a third vehicle v′′ with v′′ <_{h} v′ (resp. v′′ <_{v} v′) at some time. Continuing this argument leads to a recursion on (the length of) a path in the horizontal (resp. vertical) conflict graph, where we can estimate each step in such a ”chain of causes” by an additional factor of 3^{m}. Since we consider only m moves, a ”chain of causes” can not be longer than m. Thus we obtain an upper bound of 2 · 3^{m}(3^{m})^{m} for the number of possible positions for one car in G′. This leads to at most (2 · 3^{m}(3^{m})^{m})^{3^{m}} possible configurations and thus a configuration graph of size 2^{O(m^{2}·3^{m})} and a running time of the form 2^{O(m^{2}·3^{m})}p(n), for a polynomial p. Again, the problem under consideration belongs to FTP.

5 Generalization to arbitrary polygons and directions

Here we consider instances (C, S, p^{0}, d, Z) of the Rush Hour problem where for all c ∈ C, S_{c} is a polygon (and we may assume, without loss of generality, that it, as well as d_{c}, is contained in the part of the plane with y > 0 or y = 0 ∧ x ≥ 0. Otherwise we choose another vertex or change the signs, as needed).

The following pictures show that in both cases of the generalization there are instances in which a very small space for maneuvering can lead to arbitrary long sequences of moves to solve a situation:

[figure]

   I know that I am ``holding'' this paper far too long now.  Anyways, I will
try to think about W[1] hardness of the problem.  Klaus' constructions surely
hint at this.  HF

This means we would have to deal with infinitely many important coordinates. Another problem arises if the polygons are not convex, then each spike can force the consideration of an additional position. For that reason we need another parameter l, which bounds the number of non-convex vertices. This allows us to view a vehicle as a conglomerate of at most l + 1 convex parts ([GO97, Cha84]), where each of them generates a lane and has to be considered if entering a lane of another vehicle.

[figure]

The idea is that for m moves we can restrict our focus to certain positions described in the following, which will allow us to simulate a given sequence of m legal moves in a copy G of the game through a sequence of m moves in another copy G′ of the game. The simulation will be characterized through the following generalized invariant:

If a convex part of a vehicle is entirely out of a^{4} lane of another vehicle in G′, the same is true in G′. Moreover, if a vehicle is in one of its goal intervals in G, it is in the same goal interval in G′.

Given a legal sequence of moves in G, we find the corresponding sequence in G′ by repeating the following procedure until no further changes are possible:

Take a move and make it as short as possible such that the generalized invariant holds and the rest of the moves is still legal.

For the sequence in G′ thus obtained we can say the following: every position, which is used at any time during the sequence by a vehicle v is

the initial position of v,

a goal position of v,

a position, where a convex part of the vehicle v just touches a lane of another vehicle (In the example below, −1 and 9 are such positons for a touching the lane of b and 2 and −3 are such positions^{5} for b touching the lane of a.) or

a position, where another vehicle v′ is touching v at any time later during the sequence.

If none of these were the case, then the above procedure would cause the move to this position to be shorter. Assume that 3^{m} is also an upper bound on the number of goal positions available to a single car, then the number of possible positions for a car in the first two cases is 3^{m}. In the third case we get at most 2(l + 1)^{2} · 3^{m} positions: Each of the p + 1 convex parts could touch l + 1 possible lanes of 3^{m} possible vehicles from one of 2 possible sides.

The fourth case means in other words that v touched one of 3^{m} possible vehicles v′ at some time at one of 2 possible sides in case both polygons are convex (i.e. if l = 0). In the example below, 1 and 7.666 are such positions^{6} for a and −1 and −2.5 are such positions^{7} for b.

[figure: a; b; 0; 1; 2; 3; 4; 5; 6; 7; 8; 0; 1; 2; 3]

In general however we have to consider up to 2(l + 1)^{2} possible ways how v can touch v′. The position of this vehicle itself is either one of of (2(l + 1)^{2} + 1) · 3^{m} possible positions for a vehicle in the first 3 cases leading to (2(l + 1)^{2} + 1)3^{m}2(l + 1)^{2}3^{m} possibilities or it is caused by touching a third vehicle v′′ at some time. Continuing this argument leads to a recursion on the length of a path in the horizontal (resp. vertical) conflict graph, where we can estimate each step in such a “chain of causes” by an additional factor of 2(l + 1)^{2}3^{m}. Since we consider only m moves, a “chain of causes” cannot be longer than m. Thus we obtain an upper bound of (2(l+1)^{2} +1)·3^{m}(2(l+1)^{2}3^{m})^{m} for the number of possible positions for one car in G′. This leads to at most ((2(l + 1)^{2} + 1) · 3^{m}(2(l + 1)^{2}3^{m})^{m})^{3^{m}} possible configurations and thus a configuration graph of size (l + 1)^{O(m^{2}·3^{m})} and a running time of the form (l + 1)^{O(m^{2}·3^{m})}p(n), for a polynomial p.

4In the case that the polygon is convex, there is only one lane but if the polygon has l non-convex vertices, we might have to consider l + 1 lanes.

5If b is on position 2, this means that its lower point has the coordinates p^{0}(b)+2d(b) = (7, 0)+2(1, 1) = (9, 2)

touching the lane of a from above. If b is on position −3, this means that its upper point has the coordinates p^{0}(b) + (1, 3) − 3d(b) = (8, 3) − 3(1, 1) = (5, 0) touching the lane of a from below.

6Assume the current postion of b to occur in the sequence of moves, then a on position 1 would touch b with its upper right corner having the coordinates (5, 2) and from the other side on position 7.666 it would touch b with its upper left corner having the coordinates (7.666, 2).

7Assume the current postion of a to occur in the sequence of moves, then b on position −1 would touch a with its left corner having the coordinates (4, 1) and from the other side on position −2.5 it would touch a with its upper edge at its lower right corner having the coordinates (4, 0).

Conclusions and future work

We investigated the parameterized complexity of (a certain formalization of) Rush Hour, asking whether a given instance of this game is solvable, meaning that each vehicle has reached a goal position. In particular, we showed fixed-parameter tractability of this problem (restricted to so-called APR instances) when the number of vehicles or an upper bound on the number of moves (to a goal configuration) is taken as parameter. We also considered the variant having each car move in a finite number of directions and being of arbitrary “polygonal shape”; here, parameterized tractability could only be established taking an upper bound on the number of moves (to a goal configuration) as parameter. It would be interesting to see whether the vehicleparameterization would yield a “hard” or an “easy” problem in the sense of parameterized complexity.

For future research, we propose the following generalizations and variations of Rush-Hour:

1. Investigate different parameterizations of this problem, e.g., parameterize by the size of goal configurations.

2. In contrast to the formalization given by Flake and Baum, we considered several target vehicles and required that each of them reach one of its goals. Alternatively, we could require that just one of them reaches its goal or even all cars in one of an arbitrary set of subsets of target vehicles to reach their goals.

3. Let every vehicle move along a fixed, but individual line, in particular allowing vehicles to make turns (with the idea that a locked seering weel could allow a car only to move on a circle).

4. Let each vehicle move at an individual speed and ask for a solution within a fixed time.

5. Let vehicles move “in parallel” if possible.

Note that especially the last three variants would probably bring these games closer to motion planning problems as occurring in industrial practice. This would, all in all, be the greatest challenge here: to provide fixed-parameter algorithms for realistic industrial-type motion planning problems. Then, it would be certainly worthwhile spending time on optimizing the obtained running times which, at this point in time, would only allow for solving instances where the parameter size is quite small.

Finally, we wish to comment on the “parameterized track” in this paper: we first gave a parameterized algorithm for solving APR instances with the number of cars as parameter; then, we showed a parameterized reduction from APR instances with the number of moves as parameter to the first-mentioned problem. In Section 5, we took a similar approach in a more general setting. Interestingly, we were not able to give a fixed-parameter algorithm when taking the number of vehicles as the parameter. Nonetheless, the mentioned reduction works out in this case, as well, hence providing a fixed-parameter algorithm when taking the number of moves as parameter. This might provide a more general guideline in the research of parameterized algorithms: even in cases where, for a specific parameterization, no fixed-parameter algorithm has been found, a non-fixed-parameter algorithm might be useful for developing fixed-parameter algorithms for a different (parameterization of that) problem.

Acknowledgments

We would like to thank Dagstuhl for hosting the Seminar in Parameterized Complexity, which made this collaboration possible.

References

[Cha84] B. Chazelle. Convex partitions of polyhedra. SIAM Journal on Computing, 13(3):488–507, 1984.

[Dem01] Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In J. Sgall, A. Pultr, and P. Kolman, editors, Mathematical Foundations of Computer Science (MFCS 2001), volume 2136 of LNCS, pages 18–32. Springer, 2001.

[DF99] R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999.

[FB01] Gary W. Flake and Eric B. Baum. Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Manuscript.

         http://www.neci.nj.nec.com/
           homepages/flake/rushhour.ps, 2001.

[GO97] J. E. Goodman and J. O’Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press LLC, 1997.

[HEFN01] F. Hüffner, S. Edelkamp, H. Fernau, and R. Niedermeier. Finding optimal solutions to Atomix. In F. Baader, G. Brewka, and T. Eiter, editors, KI 2001: Advances in Artificial Intelligence, volume 2174 of LNCS/LNAI, pages 229–243. Springer, 2001.

[HS01] M. Holzer and S. Schwoon. Assembling molecules in Atomix is hard. Technical Report TUM-I0101, Technische Universität München, 2001.

[RW90] D. Ratner and M. K. Warmuth. The (n^{2} −1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10(2):111–137, 1990.