\newcommand{\fig}[3]{
    \begin{figure}[!htb]
        \centering
        \includegraphics[width=#2\textwidth]{#1.png}
        \caption{#3}
        \label{#1-en}
    \end{figure}
}

\begin{center}
    \zihao{4}\textbf{Puzzle-based parking}\\    
    \zuozhe Parag J. Siddique, Kevin R. Gue, John S. Usher\\
    \xuexiao Department of Industrial Engineering, University of Louisville, Louisville, KY 40292, USA
\end{center}

\tnr
\fontsize{10.5pt}{10.5pt}\selectfont

\noindent\textbf{Abstract: }In a common parking lot, much of the space is devoted not to parking but to lanes in which cars travel to and from parking spaces. Lanes must not be blocked for one simple reason: a blocked car might need to leave before the car that blocks it. Self-parking and intelligent communication capabilities of autonomous vehicles introduces an opportunity to overcome this constraint, and therefore to achieve much higher storage capacity of cars. We show how to maximize the number of cars in a parking lot that assumes interfering cars could be moved out of the way by a centralized controller. We provide optimal results for small lots with a single entry point, and we offer heuristic methods for larger lots. Improvements in parking capacity of 80 percent is possible.

\section{A puzzle-based parking lot}
The prospect of autonomous passenger cars presents many interesting opportunities to improve urban transportation. With respect to parking, the potential for remote control of cars would allow, for example, cars to be parked closer together because there would be no need for doors to open to allow passengers to exit. The potential for improvement in parking density is estimated to be 20 percent. Another thought is that autonomous cars do not need to park in a busy urban area. Rather, a remote parking zone can be created in inexpensive suburban areas. Another widely accepted thought is, autonomous vehicles will eliminate private vehicle ownership. Autonomous taxis will bring shared mobility, which will reduce parking demand in a significant amount.

In this context, Bosch , collaborating with Mercedes and Ford, has designed an automated valet parking lot for autonomous vehicles. Upon arrival at the parking lot, human rider leaves the car at a drop-off point. The parking lot is equipped with smart sensor systems which guide vehicles to a parking spot. Whenever the rider needs the car, it can be retrieved using a smartphone app, and the car comes to the pick-up point. It is interesting to note that no human is needed to control the cars, and no additional civil infrastructure is needed to be built. 

In such an automated parking lot, it is possible to achieve higher parking density by eliminating driving lanes. In a common parking lot, driving lanes cannot be blocked for one simple reason: a blocked car might need to leave before the car that blocks it. However, an automated valet parking lot creates an opportunity to overcome this problem, and to achieve higher parking density. Therefore, we already have the required technology to achieve higher density, all we need is efficient facility design and planning. 

\fig{f1}{0.8}{High density parking designs from other authors. (a) Ferreira et al. (2014) propose a design to park cars by blocking each other in parallel lanes. They allocate a buffer area on both the entrance and the exit of the facility so that cars can make necessary moves for relocations. (b) Timpner et al. place perpendicular aisles between the lanes of the blocked cars to reduce the number of interfering cars. Blocking vehicles relocate to the aisle to clear the path for the leaving vehicle. (c) Banzhaf et al. modify existing parking lots by adding an aisle of blocking cars. (d) In the design of Nourinejad et al., the width of the aisle varies with the depth of the lane to help accommodate relocating cars.}

Some authors have envisioned parking schemes to improve the density of parked cars, or equivalently, the capacity of the parking lot. Ferreira et al. were first to propose high density parking for autonomous vehicles. In their design, cars are parked by blocking each other in parallel lanes, similar to the deep lane storage systems used in material handling systems(Fig. \ref{f1-en}a). They assume that there is an autonomous parking controller that controls vehicle mobility inside the parking lot. The same group of researchers has extended this work to consider various operational parameters such as parking space per car, number of maneuvers, travel distance, and retrieval time. Their design increases parking capacity by 50 percent.

To reduce the number of interfering cars, Timpner et al. modified the design of Ferreira et al., by reducing the lane depth and allowing cars to depart from either end of a lane. The authors estimate density improvement of 33 percent. Banzhaf et al. propose modifying existing layouts by allowing perpendicular lanes of blocking cars within existing aisles. They report an increase in density of 25 percent. Nourinejad et al. describe a similar system in which the width of the aisle varies with the depth of the lane to help accommodate relocating cars. The authors develop a mixed-integer non-linear program to minimize the expected number of vehicle relocations. However, all these researchers are planning for large parking lots which are more appropriate for suburban areas.

From the literature we have learned that an autonomous car will not sit idle in the parking lot. After dropping a passenger, it will be used to transport another passenger. However, due to the gap between supply and demand, there will be some idle time when there is no trip, hence the car must park somewhere. If these cars go to suburban areas for parking, they will not be able to response to customer calls. Therefore, autonomous vehicles will not prefer to go outside of the city for parking, but instead, it will cruise around the city center to kill time which will lead to city congestion. Therefore, we cannot completely eliminate urban parking. Rather, we can look for ways to make parking easily accessible and cheaper. To do this, we can offer small and dense parking lots for urban areas. Such parking lots can be compared to micro-fulfillment centers in the retail industry. Micro-fulfillment centers are small warehouses located near customers which are designed for on-demand e-commerce fulfillment. Whenever an autonomous vehicle is idle, it can be parked in these small lots. As these lots will be located in urban areas, whenever a car receives a trip request it can serve the request quickly. As a valued-added service: vehicle charging, cleaning or similar services can also be introduced in such parking lots.

In this paper, we study high-density layout design of a parking lot for autonomous vehicles. Our work differs from existing literature in two important ways:

\begin{enumerate}
    \item We develop optimal designs for small parking lots, which one might expect to find in urban settings.
    \item All existing research presupposes a layout and then investigates optimal parameters and performance with respect to that layout. We ask and answer the more basic question of how many cars can be parked in a lot, without assuming any particular layout or structure. As we will show, this relaxation leads to designs with maximum density without the traditional “row-and-aisle” parking structure.
\end{enumerate}

\fig{f2}{0.5}{The Rush Hour puzzle. The goal of the game is to move the red car to the exit directly on the opposite side by moving other cars out of the way.}

\fig{f3}{0.9}{(a) An example of a $4 \times 4$ Parking lot with two cars, one car is parked horizontally on cells (43, 44), and another is parked vertically on cells (23, 34), and cells (11, 21) are the I/O point. (b) Three valid moves inside a parking lot. Each of these moves is assigned a weight according to number of cells travelled.}

The problem we address is similar to the Rush Hour puzzle (Fig. \ref{f2-en}), which is the subject of a considerable literature in the theoretical computer science community. Flake and Baum showed that the generalized version of Rush Hour with an $n \times n$ grid is PSPACEcomplete. Tromp and Cilibrasi and Hearn and Demaine showed that Rush Hour with cars only (no $3 \times 1$ trucks) is also PSPACE-complete. Our problem is different from Rush Hour in a number of ways: the game allows only forward and backward movement of vehicles, whereas real cars can turn; and, the objective of Rush Hour is to remove one specific car, whereas a real parking lot must allow arrival or departure of any vehicle requesting it. High-density storage without defined aisles has also been addressed in the material handling literature, where unit-loads or containers are stored and retrieved using conveyor modules which can move in the four cardinal directions. Whereas in our parking lot problem, cars move on its own without help of any conveyor module, and cars can travel in different directions.

\section{Modeling a puzzle-based parking lot}

We consider a parking lot as a rectangular grid. Cars can be parked horizontally or vertically. We assume cars take two cells in the grid, which means the car size is $1 \times 2$. There is one entrance/exit point in the parking lot on the lower-left corner. We call this point as input–output (I/O) point. In Fig. \ref{f3-en}a, two cars are parked in a $4 \times 4$ parking lot, one in cells (43, 44) and the other in cells (24, 34). Cells (11, 21) represent the I/O point.

\fig{f4}{1}{Process to generate the state space graph of a $4 \times 4$ parking lot. (a) The 1-car graph. The large red node is the root node—the very first node in this graph. The green nodes are open nodes. Open nodes always allow a new car to enter the parking lot. The root node and one of the open nodes are annotated. (b) 2-car graph in a $4 \times 4$ grid. Red colored nodes are the initial nodes which include the I/O cells. One of the initial nodes is annotated. (c) Bridging 1-car graph and 2 car graph. Open nodes from the 1 car graph connect the initial nodes from the 2-car graph, highlighted in blue. These connectors are called bridging edges. Position of earlier annotated nodes are also shown.}

Cars can make three types of moves inside the lot: straight, right angle, and parallel, and they accomplish these maneuvers in forward or reverse (Fig. \ref{f3-en}b). Assuming cars take one unit of time to travel one cell, each movement can be assigned a weight to quantify travel time. For instance, vehicles travel one cell when making a straight move, so this move is assigned a weight of one. Similarly, vehicles travel four cells when making right angle and parallel moves, so these moves are assigned a weight of four. We assume there is a central controller agent in the parking lot, that can communicate with the vehicles to execute all the movements.

Readers may note here that we have not specified dimension of a cell. The size of a cell is decided based on vehicle dimension and kinematics. Rather, we want to leave this cell design for the subject matter experts.

\subsection{How many cars can be parked in a parking lot?}

We model cars in a parking lot with a state space graph $G = (V, E)$, where $V$ is the set of vertices representing configurations of parking lot, and $E$ is the set of edges representing feasible transitions between configurations. A vertex is also synonymously referred as node in this paper. A configuration is defined as the size of a parking lot, number of cars parked and their locations. The term state is also used as an alternative to configuration. We want to know: how many cars can be parked in a parking lot? We solve a small example, a $4 \times 4$ parking lot, to get started with this problem.

In a $4 \times 4$ parking lot, there are sixteen cells, and each car takes two cells. Therefore, we can place eight cars at most. We begin by generating the state space graph for a $4 \times 4$ grid. Without considering maneuverability, a single car can be placed in 24 distinct locations, each representing a potential node in the graph. We then execute a pair-wise search of all potential nodes to determine whether they can be connected by a feasible maneuver. We refer to the result as the 1-car graph (Fig. \ref{f4-en}a). Next, we place two cars in every possible way to create the 2-car graph. We then eliminate configurations with overlapping cars. For example, configuration [(11, 21), (21, 22)] is infeasible because cell 21 is used by both of the cars, which is not physically possible. We also eliminate configurations that occupy an entire row or column because they are infeasible (except [(11, 21), (31, 41)]). Finally, we connect the nodes using their respective moves to construct the complete 2-car graph (Fig. \ref{f4-en}c). Similarly, we can continue to construct graphs up to eight cars.

We find an interesting feature to connect these eight graphs. In an empty parking lot, when the first car arrives, it is initially parked on the I/O cells. This is the starting node of the 1-car graph. This car can move to different locations inside the parking lot. Once the car leaves the I/O cells, the parking lot is open to receive a second car. When the second car arrives, it parks itself on the I/O cells. This is the starting point of the 2 car graph. After that, cars can be relocated to other locations in the parking lot. Similarly, when both of these cars are parked anywhere except the I/O cells, the parking lot is open to receive a third car, and we can continue the process up to 8 cars. Therefore, we observe that each of the $k$ car graphs, ($k = 1, 2, \dots, 8$) starts from the I/O cells. Hence, we define a parking lot configuration that includes occupied I/O cells as initial node. Initial nodes of the 2-car graph are highlighted in red in Fig. \ref{f4-en}b. Note that each $k$ car graph has multiple initial nodes, except the 1-car graph. To distinguish this node from other initial nodes, we define it as the root node (see large red node in the Fig. \ref{f4-en}a). We also observe that to accommodate a new car into a parking lot, we have to make sure that no car is parked on the I/O cells. Such a configuration—I/O cells are unoccupied—always allows a new car to come into the lot. We define these configurations as open nodes (See the green colored nodes in Fig. \ref{f4-en}a). If any of the I/O cells are occupied, a new car cannot enter the parking lot which are called non-open nodes. There are five non-open nodes (grey nodes) in Fig. \ref{f4-en}a: (11, 21), (11, 12), (21, 22), (21, 31), and (31, 41). Though (31, 41) does not immediately block the parking lot, it allows only a second car on (11, 21) and after that no more cars can enter the parking lot.

\fig{f5}{0.7}{State space graph of a $4 \times 4$ parking lot. This graph has 5,913 vertices and 14,635 edges. Some of the vertices are annotated for the purpose of visualization.}

When a second car arrives at the I/O point, it becomes the initial node of a 2-car graph. Therefore, open nodes of the 1-car graph and initial nodes of the 2-car graph are connected by an entering car maneuver. Similarly, open nodes of the 2-car graph and initial nodes of the 3-car graph are connected. We call these connectors bridging edges. The bridging edges of 1 car and 2 car graphs are highlighted blue in Fig. \ref{f4-en}c. We generalize, open nodes of the $k$ car graph and initial nodes of the $(k + 1)$-car graph are connected using bridging edges. With bridging edges entered, we have one graph representing the entire state space (see Fig. \ref{f5-en} for the $4 \times 4$ lot state space).

\fig{f6}{1}{Puzzle-based retrieval test. (a) A $4 \times 4$ parking lot with 3 cars. (b) We perform Puzzle-based retrieval test on the layout on the left, and find the all the three cars can be retrieved by relocating other cars inside the parking lot.}

This state space graph has 5,913 vertices and 14,635 edges. There are 72 connected components, set of vertices reachable from one another, in this graph. Vertices from one connected component do not communicate with vertices from other connected components.

However, all vertices inside a connected component can reach one another. To better visualize the graph, we have annotated a few nodes. For example, Fig. \ref{f5-en}a is a parking lot with only one car, Fig. \ref{f5-en}d is a parking lot with four cars, and so on. To determine how many cars can drive into a parking lot, we begin by looking for vertices from the 1-car graph. The 1-car graph starts when the first car comes into the parking lot which is the root node. If we explore the root node’s connected component, we can reach vertices up to 7-car graph. Remaining connected components do not start from the root node. Hence, it is not possible to reach these configurations by driving the car. For example, vertices in Fig. \ref{f5-en}i, \ref{f5-en}j, \ref{f5-en}k, \ref{f5-en}l are not reachable from the root node. Therefore, we can park 7 cars in a $4 \times 4$ parking lot at most. A parking lot with 7 cars is shown in Fig. \ref{f5-en}g. In summary, though a $4 \times 4$ parking lot has the capacity to hold 8 cars, we can only drive 7 cars into it. Steps to find the maximum number of cars which we can drive into an $m \times n$ parking lot are as follows:

\begin{itemize}
    \item Count the maximum number of cars that can be placed in a parking lot, $k_{max} = \lfloor\frac{m\times n}{2}\rfloor$.
    \item Generate the state space graphs for a parking lot with $k$ cars, where $k = 1, 2, \dots, k_{max}$.
    \item For each of the graphs, identify initial nodes and open nodes.
    \item Bridge the open nodes of the $k$ car graph with the initial nodes of the $(k +1)$ car graph. This yields a graph with a set of connected components.
    \item Find the connected component with the root node. This component is comprised of vertices from the 1 car graph to kle car graphs, where $k_{le}\le k_{max}$.
    \item Return the value of $k_{le}$, the maximum number of cars that can be driven into a parking lot.
\end{itemize}

We have learned that we can park a maximum of 7 cars in a $4 \times 4$ parking lot. We can retrieve these 7 cars only in last-in, first-out sequence. However, always we do not want to leave a parking lot for the sole purpose of allowing another car to exit. Therefore, we want to know: how many cars can be parked in a parking lot, so that any car can depart while other cars remain? To answer this question, we select a parking lot with $k$ cars, where $k = 1,2,\dots,7$, and test whether is it possible for any car to depart. As this test resembles the Rush Hour puzzle, we call this as puzzle-based retrieval test. For example, in Fig. \ref{f6-en} we perform a puzzle-based retrieval test on a parking lot with 3 cars. We observe that in all the three cases the target car reaches the I/O point and remaining cars do not need to leave the parking lot, but relocate to allow the target car to leave. Then, we perform the puzzle-based retrieval test on the entire state space to find the number of cars that can be parked in a $4 \times 4$ parking lot. However, to minimize our search effort, we begin this test from parking lot configurations with 7 cars. We find that it is not possible to park 7 cars in this way. Then we explore configurations with 6 cars and the test fails again. Finally, for configurations with 5 cars, we find all the cars can leave. We do not need to continue this test for configurations with less than 5 cars, as surely there will be some configurations that will pass this test. Therefore, we find that a maximum of 5 cars can be parked in a $4 \times 4$ parking lot, so that any car can depart while other cars remain.

In a traditional setting, we want to park such a way that any car can leave, without relocating other cars. Therefore, we want to know: how many cars can be parked in a parking lot, so that no car is blocked? To answer this question, we select a parking lot with $k$ cars, where $k = 1,2,\dots,5$, and test whether it is possible for any car to depart the parking lot, without relocating other cars. We call this test as unblocked retrieval test. Then performing a brute-force operation, we find that a maximum 4 cars can be parked in a $4 \times 4$ parking lot, so that no car blocks each other.

\fig{f7}{1}{Three parking lot designs.}
\fig{f8}{1}{Single-car heuristic for $A^*$ search. To retrieve the dark colored car from the parking lot on the left, the parking lot on the right is used as heuristic by placing only one car on the same location as the dark colored car. (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.)}

Observing the state space graph, we discover there exists three types of parking lot designs. The first type is a parking lot with maximum number of cars, cars completely block each other, and cars can only leave in last-in, first-out sequence. We call this design as limited egress (Fig. \ref{f7-en}a). Such parking is commonly found in different events like, a concert or a ball game. Then the second type, where cars also block each other, but any car can leave by moving other cars, like the Rush Hour puzzle. We call this design as complete egress (Fig. \ref{f7-en}b). And finally, the third one is the traditional parking lot (Fig. \ref{f7-en}c), where no car blocks each other. We discovered these designs as we have initiated our research question without presupposing any particular layout or structure.

\subsection{How long does it take to retrieve a car?}

The retrieval time of each vehicle is one of the performance measures of these designs. We use the same state space graph to compute retrieval. We apply an $A^*$ search algorithm on the state space graph to compute optimal retrieval of each of the cars in the parking lot.

$A^*$ is an informed search algorithm which explores a graph by expanding the most promising node chosen according to the smallest path cost. The path cost is evaluated as $f(s) = g(s) + h(s)$, where $g(s)$ is the cost from the initial state to current state s, and h(s) is the estimated cost of the cheapest path from current state s to the goal state. Hart et al. also showed that $A^*$ algorithm guarantees to produce optimal results if the heuristic function $h(s)$ is admissible and consistent. An admissible heuristic, $h(s)$, is one that constructed in such a way that it generates lower bound to the real cost, $h(s^*)$, of reaching the goal states: $h(s)\le h(s^*)$. A consistent heuristic is one in which for every state s and each successor state $s'$ of s, the estimated cost, $h(s)$, of reaching the goal from s is no greater than the step cost, $c(s,s')$, of getting to $s'$ plus the estimated cost, $h(s')$, of reaching the goal from $s'$, which can be expressed as $h(s)\le c(s, s') + h(s')$. A consistent heuristic is necessarily admissible while the reverse case need not be true. We have covered brief literature about $A^*$ search, for more information readers are referred to Hart et al., Pearl, Russell and Norvig.

In our implementation of $A^*$ algorithm, inputs are: a start node, a target car, and a heuristic function. The start node is the initial state which is represented by the size of a parking lot, number of cars parked and their locations. The target car is the car which we want to retrieve. As a heuristic function, we use the retrieval time of a single car. For example, in Fig. \ref{f8-en}, to estimate the cost to retrieve the dark car from the parking lot on the left, we place only one car in the parking lot on the same location as the target car and compute retrieval time. The retrieval cost for the dark car is 27 (Fig. \ref{f8-en})a and heuristic cost is 5 (Fig. \ref{f8-en}b). As it is a relaxed version of our problem, it will always be consistent and we can get the optimal result. We call this heuristic function a single-car heuristic.

Our retrieval algorithm explores the state space by using two lists: i) frontier and ii) explored. The frontier list is a priority queue that ranks all the nodes to be visited according to $f(s)$ value and the explored list stores all the visited nodes. In the beginning, the frontier list contains only the initial node and the search stops when a goal node is chosen to visit. A goal node is a configuration where the target car is on the I/O point. We also create a third list called the parent–child which tracks relationships between the nodes—- whenever our search reaches the goal node, this list is used in constructing the path from the initial node to the goal node. Applying $A^*$ search, we have computed optimal number of moves required to retrieve vehicles from the limited egress, complete egress, and traditional parking lot in Fig. \ref{f9-en}. Please note vehicle retrieval in a limited egress parking lot follows last-in, first-out sequence, we retrieved the $7^{th}$ car first then the $6^{th}$ and so on (see Fig. \ref{f7-en}a), then computed cumulative retrieval time as shown in Fig. \ref{f9-en}a.

\fig{f9}{1}{Vehicle retrieval time.}

Here, we have computed retrieval time assuming that a car takes one unit of time to travel one cell. However, reader may be interested to learn about retrieval time in a real parking lot. In this regard, we show an example here. In general, a parking spot dimension is $9' \times 18'$. As we have considered a parking spot $1 \times 2$, we can consider dimension of one cell as $9' \times 9'$ . According to Schwesinger et al., speed limit for the autonomous vehicles in a parking lot is $10 km/h (≈ 9ft/s)$. Hence, travel time for one cell is 1 s. In the complete egress parking lot (Fig. \ref{f9-en}b), to retrieve car 02, all the cars travel 27 cells. Therefore, retrieval time of the car 02 is 27 s.