Simulation Evaluation of Vehicle Movement Model Using Spatio-Temporal Grid Reservation for Automated Valet Parking

Automated valet parking (AVP) systems aim to use automated driving technology to park a vehicle from the passenger’s boarding/exiting location to a parking space in a parking lot and recall the vehicle from the parking space to the boarding/exiting location. For multiple vehicles to move efficiently through a parking lot, travel must be mediated between each vehicle. We have proposed a driving control method that improves the efficiency of AVP by using the Spatio-Temporal Grid Reservation mechanism. We previously compared it with an autonomous driving, which showed that the proposed method improved the efficiency of vehicle movement when vehicles are entering small parking lots. In this paper, we modified our previous method to accommodate the increasing number of vehicles in a parking lot and created Spatio-Temporal Grid Model as a vehicle movement model. we evaluate this model by comparing it with Conflict Zone Model and MAPF Model created by the methods proposed in related studies, in addition to an autonomous driving model. We performed simulations varying the percentage of vehicles arriving at the parking lot and showed that Spatio-Temporal grid model improves the efficiency of vehicle movement when vehicles are entering and exiting the lot.

SECTION I. Introduction

Research and development on automated valet parking (AVP) systems has been underway [1]. Such systems can park a vehicle in a parking space in a parking lot from the passenger’s boarding/exiting location using automated driving technology and recall the vehicle from the parking space to the boarding/exiting location [2], [3]. For multiple vehicles to move efficiently through a parking lot, travel must be mediated between each vehicle [4], [5].

We have proposed a Spatio-Temporal Grid Reservation mechanism (Spatio-Temporal Grid Reservation for AVP) to improve the efficiency of vehicle movement in AVP [6], [7]. The proposed method mediates the movement between of each vehicle by the server to improve the efficiency of AVP. In the previous study, we evaluated the mechanism for a limited number of vehicles by using simulation [8]. Comparison was carried out for the proposed method and autonomous driving. The results showed that the proposed method improved the efficiency of vehicle movement when two to ten vehicles enter a parking space in a parking lot with ten parking spaces.

In this paper, we extensively examine the Spatio-Temporal Grid Reservation mechanism with respective to a large number of vehicles in AVP. Moreover, we evaluate the effectiveness of Spatio-Temporal Grid Model created by the proposed method in terms of efficiency of vehicle movement by comparing it with Conflict Zone Model and MAPF model created by the methods proposed in related studies for controlling vehicle movement in AVP, in addition to a vehicle movement model using autonomous driving. Conflict Zone Model and MAPF Model are created by using a method in which a server mediates the movement of each vehicle. By comparing Spatio-Temporal Grid Model with Conflict Zone Model and MAPF Model, we can verify its effectiveness as a method for mediating the movement of each vehicle by the server. Hundreds of vehicles enter the parking lot in this simulation, and each car exits and enters. The simulation is performed in an environment that is closer to the real environment than in our previous study. Since an increase in the number of vehicles in a parking lot affects parking time, it is important to conduct the evaluation in an environment where the number of vehicles is large [9].

The main contributions of this study are as follows.

• In order to solve the problem that the efficiency of vehicle movement decreases as the number of vehicles in a parking lot increases, we modified the conventional method based on Spatio-Temporal grid reservation to a method that accommodates an increase in the number of vehicles in a parking lot and created a vehicle movement model to obtain an evaluation in a large environment.

• We analyzed Spatio-Temporal Grid Model in comparison with Conflict Zone Model and MAPF model to investigate what kind of control of automated valet parking would improve the efficiency of vehicle movement.

• We compared and analyzed several vehicle movement models, and by varying the parameter of the number of vehicles, we showed that Spatio-Temporal Grid Model is the most efficient for vehicle movement in a parking lot environment with a large number of vehicles.

SECTION II. Related Work

A. Spatio-Temporal Grid Reservation for AVP

We have proposed an efficient AVP method based on a Spatio-Temporal Grid Reservation mechanism and are evaluating it by simulation [6], [8]. Spatio-Temporal Grid Reservation is a method of vehicle travel mediation. As shown in Fig. 1, in Spatio-Temporal Grid Reservation, the road space is divided into “cells” of predetermined size, and the aggregate of each cell and each time is defined as the Spatio-Temporal Grid and managed on the database.

FIGURE 1.

Concept of Spatio-Temporal grid reservation for AVP.

The flow of Spatio-Temporal Grid Reservation for AVP is shown in Fig. 2. Shortly before the vehicle begins driving through the parking lot, it sends the vehicle information necessary for the reservation to the server and requests a reservation. The server calculates the vehicle’s location at each time based on the requested information, queries the database for grid availability, and makes the reservation to avoid conflicts with other vehicles’ prior commitments. The vehicle travels in accordance with the path planning based on the reservations it was able to obtain.

FIGURE 2.

Spatio-Temporal Grid Reservation process.

B. Conflict Zone

Zhang et al. define the Conflict Zone as the area in front of a parking space or near an intersection in a parking lot and proposed a method to control the movement of vehicles in AVP by determining the order in which multiple vehicles pass through the Conflict Zone [4], [10]. Fig. 3 shows an example of three vehicles, A, B, and C, that are about to travel through an intersection. The order in which the vehicles pass through the intersection is determined to be vehicle A first, followed by vehicle B, and finally vehicle C, and the vehicle movement is controlled to pass in that order.

FIGURE 3.

Scenario of multiple vehicles driving with Conflict Zone.

This method takes three steps to solve for the sequence that minimizes time consumption. The first step is to detect the Conflict Zone and corresponding vehicles in each area of the parking lot. The second step enumerates all possible pass-through sequences and determines their validity. The third step solves the corresponding trajectory plan for each valid running sequence and outputs the least time-consuming result.

C. Multi-Agent Path Finding

Okoso et al. proposed a method to control AVP vehicle movement by solving the Multi-Agent Path Finding (MAPF) problem of planning the paths of multiple agents (vehicles) on a graph [5], [11], [12].

The solution to MAPF is the set of effective paths $\pi ^{\ast }$ that minimize the total travel cost, which can be obtained using the set of agents, A, the travel time for an agent to arrive at its destination, $T_{i}$ , and (1).\begin{equation*} \pi ^{\ast } =\underset {\pi } {\text {arg min}}\sum _{i\in A}T_{i}\tag{1}\end{equation*}

In this method, each agent’s route is searched sequentially in the order of the given priority. Each agent searches for collision-free paths on the graph using a Spatio-Temporal A* algorithm with a reservation table. In the reservation table, each agent writes a path (vertex $v$ at time step t and an edge at time step $t$ to $t+1$ ). When subsequent agents search for a path, they avoid vertices and edges that have already been written in the reservation table. The search and reservation process is repeated, and when valid paths have been computed for all agents, they are considered to be the solution.

SECTION III. Evaluation Methods

A. Vehicle Movement Model for AVP

The three vehicle movement models we compared and evaluated were developed on the basis of the following assumptions.

• Each vehicle accelerates with equal acceleration.

• Each vehicle travels at a constant speed when it reaches the speed limit.

• Each vehicle travels along the path that has the shortest distance.

1) Conflict Zone Model

We developed a vehicle movement model based on Zhang et al.’s Conflict Zone method (Conflict Zone Model) under the following conditions.

• Each vehicle cannot start running if another vehicle is present in the Conflict Zone where a collision could occur.

• After passing through the Conflict Zone, each vehicle cannot start driving if there is not enough space on the road to merge due to traffic congestion.

Collisions between vehicles are assumed to occur when the paths of multiple vehicles moving simultaneously in the Conflict Zone intersect or overlap.

2) MAPF Model

We developed a vehicle movement model based on Okoso et al.’s MAPF method (MAPF Model) under the following conditions.

• Each vehicle can move to an adjacent vertex at each time step or wait at the current vertex.

• Multiple vehicles cannot occupy the same vertex at the same time step.

• Multiple vehicles cannot use the same edge to change position at the same time.

3) Spatio-Temporal Grid Model

We proposed a method for controlling vehicle movement in AVP by using the mechanism of Spatio-Temporal Grid Reservation, which is a vehicle driving control method. We modified this method to accommodate the increasing number of vehicles in a parking lot to create a vehicle movement model (Spatio-Temporal Grid Model).

Let $c$ be the cell in which the vehicle runs, $t_{\mathrm {request}}$ the time when the vehicle wants to start occupying $c$ , $t_{\mathrm {start}}$ the time when the vehicle starts occupying $c$ , $t_{\mathrm {finish}}$ the time when the vehicle finishes occupying $c$ , $l_{\mathrm {vehicle}}$ the total length of the vehicle, $s_{\mathrm {cell}}$ the cell size, $v_{\mathrm {vehicle}}$ the maximum speed of the vehicle, $t_{\mathrm {departure}}$ the time when the vehicle wants to enter a parking lot, and i the order of the cells in which the vehicle runs $(i$ is a natural number and the initial value is 0). Our algorithm is shown in 1–5.

Let $c_{i}$ be the $i$ -th c, and $t_{\mathrm {request}}$ , $t_{\mathrm {start}}$ , and $t_{\mathrm {finish}}$ corresponding to $c_{i}$ be $t_{\mathrm {request}i}$ , $t_{\mathrm {start}i}$ , and $t_{\mathrm {finish}i}$ .

1. Set $t_{\mathrm {request}i}$ according to (2) and (3).\begin{align*} t_{\mathrm {request}i}=&t_{\mathrm {request}i-1} +\frac {s_{\mathrm {cell}}}{v_{\mathrm {vehicle}}}\tag{2}\\ t_{\mathrm {request}0}=&t_{\mathrm {departure}}\tag{3}\end{align*}

2. If $c_{i-\lceil {}\frac {l_{\mathrm {vehicle}}}{s_{\mathrm {cell}}}\rceil -1}$ exists, set time $t_{\mathrm {finish}i-\lceil {}\frac {l_{\mathrm {vehicle}}}{s_{\mathrm {cell}}} \rceil -1}$ to time $t_{\mathrm {request}i}$ .

3. If a vehicle can occupy $c_{i}$ from $t_{\mathrm {request}i}$ as a result of referring to the database that stores the grid reservation data (hereinafter referred to as the Spatio-Temporal Grid DB), then $t_{\mathrm {start}i}$ is set to $t_{\mathrm {request}i}$ . If the vehicle cannot occupy $c_{i}$ , set $t_{\mathrm {start}i}$ to the time at which the occupation of $c_{i}$ is terminated.

4. If, after consulting the Spatio-Temporal Grid Reservation DB, the vehicle is unable to occupy $c_{i-\lceil {}\frac {l_{\mathrm {vehicle}}}{s_{\mathrm {cell}}} \rceil -1}$ until $t_{\mathrm {finish}i-\lceil {}\frac {l_{\mathrm {vehicle}}}{s_{\mathrm {cell}}} \rceil -1}$ , $t_{\mathrm {departure}}$ is added as the amount of time taken by a conflict for the reservation in $c_{i-\lceil {}\frac {l_{\mathrm {vehicle}}}{s_{\mathrm {cell}}} \rceil -1}$ , and $i$ is set to 0 and the reservation is made again from the beginning. This process is repeated until the reservation is successfully made, thus preventing reservation failures due to an increase in reservation conflicts as the number of vehicles in the parking lot increases.

5. If $c_{i+1}$ exists, set $i$ to $i+1$ and return to step 1; if $c_{i+1}$ does not exist, set the unset time $t_{\mathrm {finish}}$ to the time when the entry or exit ends.

B. Evaluation Environment

For the evaluation, we constructed a parking environment with one lane on each side and 60 parking spaces as shown in Fig. 4. We also constructed an environment with a Conflict Zone for Conflict Zone Model as shown in Fig. 5, an environment with a graph for MAPF Model as shown in Fig. 6, and an environment with a grid for Spatio-Temporal Grid Model as shown in Fig. 7.

FIGURE 4.

Parking environment for evaluation.

FIGURE 5.

Parking environment with Conflict Zone.

FIGURE 6.

Parking environment with graph.

FIGURE 7.

Parking environment with grid.

The experimental scenario is that a vehicle requests an entry or exit reservation for this parking space. The speed limit in the parking lot is 10 km/h.

The evaluation experiments in this study were conducted under the following assumptions.

• Failed bookings are not considered.

• All vehicles always follow their individual vehicle movement model.

• reservations are not canceled.

• If no parking space is available at the time a vehicle wishes to enter, the vehicle does not park.

C. Parameters and Evaluation Items

We conducted an experiment to evaluate the arrival rate, which is the number of vehicles arriving at a parking lot per second, in six patterns ranging from 0.14 to 0.24 vehicles per second. We used the parking turnover rate and average time consumption as evaluation items in terms of the efficiency of vehicle movement. The parking turnover rate is the number of vehicles parked per hour divided by the number of parking spaces, indicating the number of times a parking space is occupied. Average time consumption is the sum of the time a vehicle travels from the entrance of the parking lot to the parking space and from the parking space to the exit of the parking lot.

For these evaluation items, we compared Conflict Zone Model with MAPF Model and Spatio-Temporal Grid Model. To see how these models perform, In addition to these models, the parking turnover rate was compared with a manual driving model in which a person drives the vehicle and an autonomous driving model in which the vehicle is driven based solely on its own sensors. Note that we implemented a manual driving model and an autonomous driving model based on the driving model of the vehicle micro-simulator Vissim [13].

SECTION IV. Results

A. Parking Turnover

A comparison of parking turnover rates for Conflict Zone Model, MAPF Model, Spatio-Temporal Grid Model, the manual driving model, and the autonomous driving model is shown in Fig. 8.

FIGURE 8.

Parking turnover results for Spatio-Temporal Grid Model and other models w.r.t. arrival rate.

For arrival rates above 0.18, Spatio-Temporal Grid Model produced a higher parking turnover rates than Conflict Zone Model and MAPF Model. Regardless of the arrival rate, Spatio-Temporal Grid Model had a higher parking turnover rate than that of the manual driving and autonomous driving models.

B. Average Time Consumption

A comparison of average time consumption for Conflict Zone Model, the MAPF Model, Spatio-Temporal Grid Model is shown in Fig. 9. Regardless of the arrival rate, Spatio-Temporal Grid Model took less time on average than Conflict Zone Model and MAPF Model. Spatio-Temporal Grid Model took up to 72.4% less time on average than Conflict Zone Model, and up to 60.6% less time than MAPF Model.

FIGURE 9.

Average time consumption results for Spatio-Temporal Grid Model and models developed based on related studies w.r.t. arrival rate.

SECTION V. Discussion

Simulation results show that Spatio-Temporal Grid Model moves vehicles more efficiently than Conflict Zone Model, MAPF Model, the manual driving model, and the autonomous driving model.

The manual driving model and the autonomous driving model did not share information with other vehicles and instead used human eyesight and sensors mounted on the vehicle to safely move the vehicle. In contrast, Spatio-Temporal Grid Model determined the space in which the vehicle would travel in advance and shared this information with other vehicles to keep the distance between vehicles small enough to prevent collisions. This improved the efficiency of vehicle movement.

In Conflict Zone Model, the parking lot was divided into Conflict Zones, and vehicles moved by sharing information about vehicles traveling in the Conflict Zones, whereas in Spatio-Temporal Grid Model, the parking lot was divided into smaller cells, and vehicles moved by sharing information about vehicles traveling in the cells. This reduced the waiting time of vehicles and improved the efficiency of vehicle movement.

While MAPF Model had vehicles moving on paths consisting of graph vertices and edges, Spatio-Temporal Grid Model had vehicles moving on paths represented by a set of cells, allowing for more flexible movement paths. This also improved the efficiency of vehicle movement.

However, when the arrival rate is low, the difference in efficiency of vehicle movement between the models is smaller because the density of vehicles in the parking lot is low and it is difficult for the travel mediation between each vehicle to occur between each vehicle.

SECTION VI. Conclusion

In AVP systems, the movements of multiple vehicles must be coordinated in order for them move efficiently through a parking lot. We previously proposed a method that improves the efficiency of AVP through the mechanism of Spatio-Temporal Grid Reservation and compared it with an autonomous driving model. Our previous studies have shown that our method improves the efficiency of vehicle movement when the vehicles are entering small parking lots. In this paper, we modified our previous method to accommodate the increasing number of vehicles in a parking lot and created Spatio-Temporal Grid Model as a vehicle movement model. We compared this model with Conflict Zone Model and MAPF Model created by methods proposed in related studies, in addition to an autonomous driving model. We evaluated the simulated parking turnover and average time consumption by varying the percentage of vehicles arriving at the parking lot. In the case of vehicles entering and exiting the parking lot, the efficiency of Spatio-Temporal Grid Model was the highest out of all models when the density of vehicles in the parking lot exceeded a certain level.