Automated Parking Space Allocation during Transition with both Human-Operated and Autonomous Vehicles

Abstract

As fully automated valet parking systems are being developed, there is a transition period during which both human-operated vehicles (HVs) and autonomous vehicles (AVs) are present in the same parking infrastructure. This paper addresses the problem of allocation of a parking space to an AV without conflicting with the parking space chosen by the driver of a HV. A comprehensive assessment of the key factors that affect the preference and choice of a driver for a parking space is established by the fuzzy comprehensive method. The algorithm then generates a ranking order of the available parking spaces to first predict the driver’s choice of parking space and then allocate a space for the AV. The Floyd algorithm of shortest distance is used to determine the route for the AV to reach its parking space. The proposed allocation and search algorithm is applied to the examples of a parking lot with three designed scenarios. It is shown that parking space can be reasonably allocated for AVs.

1. Introduction

According to the International Parking Institute (IPI), the number of vehicles on the road will reach 2.5 billion in 2050 [1]. With this projected increase in the volume of vehicles, parking has become an emerging issue that affects not only drivers looking for parking spaces, but also city governments in their planning, particularly in urban areas where land resources are limited and constrained. It has been reported that about 30% of traffic backup in a typical downtown area is caused by drivers searching for parking spaces [2]. The expected increase in the number of vehicles likely implies more new drivers and drivers who are unskilled in parking, thus leading to more road congestion and increased waste of valuable manpower-hours and resources. In recent years, with the continuous advancement and development in computer and control technologies, automated parking has become feasible and various strategies have been proposed to help alleviate the unskilled parking problem [3,4]. Advances in V2X technology have also led related researchers to develop a more robust system of automated parking, namely the Automated Valet Parking System [5].

Compared with the automated parking system, the concept of automated valet parking system is based on V2X communication technology, which enables self-driving vehicles to interact and collaborate with an intelligent parking infrastructure during the entire parking space search process, from the entrance to the self-parking space [6]. Existing intelligent parking administration systems can detect the status of the parking spaces in real time through camera recognition, infrared sensing, and other technologies [7,8]. According to SAE (Society of Automotive Engineers) classification for autonomous driving levels, the automated valet parking system is classified as L4 autonomous driving, that is, under certain scenarios, an equipped vehicle can complete all the driving tasks autonomously without the participation of a driver. Although self-driving cars are gaining popularity, related research and testing are far from the level of completion required to bring automated valet parking to fruition. Even if L4 level self-driving cars were to enter the market in the short term, there is likely going to be a long transition period during which both human-operated vehicles (HVs), i.e., with drivers, and autonomous vehicles (AVs), i.e., self-driving or driverless, co-exist, and augmented search strategies need to be developed for the AVs. Self-driving vehicles execute well-defined algorithms based on sensor information, while drivers make cognitive decisions based on perception and surveying of the surrounding environment. The objective of this paper is to investigate parking space allocation and route selection (i.e., path planning to the allocated space) for self-driving vehicles during such a transition period in which significant interactions between the two types of vehicles are expected.

1.1. Motivation for Research

In this paper, as shown in Figure 1, we define an intelligent parking infrastructure (which refers to either a parking lot or a parking structure) as one that is equipped with a central command station that receives information from all sensors and interacts with autonomous vehicles in real time. In an automated valet parking system, the central command station is capable of determining the number of available parking spaces through geomagnetic sensors and obtaining the locations of these parking spaces through a pre-stored layout of the parking infrastructure. After an AV enters the parking infrastructure, the central command station utilizes information from multiple cameras to provide a road map to the allocated parking space, enabling the self-parking to be efficient. However, as development and implementation of automated parking systems move forward, there will be a transition period to fully automated valet parking unless the city government phases out HVs and mandates purchase of AVs, which is very unlikely, or designates parking spaces only for AVs. Thus, in an intelligent parking infrastructure, there will generally be both self-driving and human-driving vehicles. Self-driving vehicles can interact with the parking infrastructure in real time based on V2X communication. Human-driving vehicles are limited by non-intelligent devices that disengage any interaction with the central command station.

Consider the scenario when both a HV and an AV are looking for parking spaces. In order for the central command station not to allocate the same parking space for the AV as the driver would choose, the station must be able to predict with high probability the choice of parking space that the driver would make. Liang et al. proposed four preference factors that could affect the choice of parking spaces for an individual driver [9]. Logit models, based on fuzzy logic theory, were established to describe driver preference selection, which were then used to improve parking experience and alleviate difficulties in parking [9,10]. Although fuzzy evaluation methods have been widely employed with proven success to determine factors, which are otherwise difficult to quantify, and make optimal choices incorporating expert opinions, there are only few published studies related to parking choice preference. In this paper, by adopting the fuzzy evaluation method, a preference ranking method of parking spaces in an intelligent parking infrastructure is established based on four representative factors that would affect the parking space selection of drivers.

In an automated valet parking system, route selection is also a key enabling technology [11,12]. Since the AV might not know a priori the overall layout of the parking infrastructure, it is necessary for the central command station to guide the self-driving vehicle to the allocated parking space according to the current conditions of the intended route. In general, in searching for a parking space, the shorter the path distance, the better. There are several methods to find the shortest path, such as the Dijkstra and Floyd algorithms [13,14]. Shi et al. [15] studied the shortest path planning problem of mobile robots based on the Floyd algorithm, focusing on the node selection problem for mobile robot path planning and determination of the weighting factor of each passable road. Experiments have also illustrated that the Floyd algorithm has the advantage of providing the shortest path selection for mobile robots [15]. Based on a known layout of the environment, Dijkstra algorithm can also efficiently find the shortest path between two points. Although the Floyd algorithm is slightly more time-consuming than the Dijkstra algorithm, it is a dynamic programming algorithm aimed to solve the shortest path problem between multiple source points. In a complex environment such as parking, the Floyd algorithm appears to be more suitable for our current problem of interest.

1.2. Organization and Contributions of This Paper

In this paper, state-of-the-art research of automated parking space allocation and route selection is reviewed in Section 2. Section 3 describes the four factors that affect the choice of parking space for drivers. In Section 4, a fuzzy comprehensive evaluation method is proposed to evaluate and score (i.e., rank) the available parking spaces in an intelligent parking infrastructure [16]. The fuzzy algorithm is based on first predicting which space the driver would select and then allocating one of the remaining spaces to the autonomous vehicle. In Section 5, the Floyd algorithm is introduced to provide path navigation for autonomous vehicles [14] according to the nodes of available parking spaces and road information in the parking infrastructure. Section 6 provides three examples of a parking lot on the campus of Jiangsu University to illustrate the step-by-step implementation of the proposed algorithm via Python. Concluding remarks of this work are given in Section 7.

The contributions of this paper are listed as follows:

• In this paper, a fuzzy comprehensive evaluation method is used to first predict the parking preference of a driver based on four main factors that influence their choice of parking spaces. This procedure prevents conflict of allocation of parking space to the AV with that chosen by the HV.
• Based on the node information in a parking infrastructure, the Floyd algorithm is used to provide path navigation for the AVs.
• The proposed methodology, combining fuzzy theory and the Floyd algorithm, provides a novel scheme for a central command station to assign parking spaces for AVs in the presence of HVs. The merit of this work thus provides a foundation for future work to investigate the problem of automated parking for multiple vehicles.

2. Review of Related Work

In 2007, the DARPA (Defense Advanced Research Projects Agency) Urban Challenge (DUC) initiated numerous research projects to address challenges of autonomous driving. Since then, a great deal of research has been conducted in related topics. In addition to highway and urban driving, automated valet parking is also of major interest to relieve drivers from the stress of parking [17].

In 2012, a parking information acquisition and release system was designed by Dou et al. based on the dynamic allocation algorithm of parking spaces in the parking lot [18]. The main idea is to optimize among the distribution of parking spaces arranged in a tabulated format and driving paths/distances. However, the algorithm can obtain the availability of parking spaces only after the human-operated vehicles have completed their parking. Thus, if there are more than two vehicles, at least one HV and one AV, choosing the same parking space and converging near that space, this scenario could lead to traffic congestion and the wasting of time and fuel consumption.

In 2012, Audi Corporation developed a parking guidance system that could assist and orchestrate the entire parking process [19]. The approach of the system includes three steps: scanning, positioning, and arranging parking [20]. The distance to the obstacle is detected by eight ultrasonic sensors installed in the bumper and the parking space is detected by 10 ultrasonic sensors. This parking system can only be executed if the speed of the vehicle is below 30 km/h. While this is an excellent demonstration of an automated valet parking system, during the transition period to fully autonomous driving, HVs will also be represent; the guidance system cannot allocate parking spaces to the HVs with no communication devices equipped and hence cannot complete the space allocation task for the AVs.

In 2016, Kotb et al. [21] proposed a system to reduce the time wasted in looking for parking spaces by offering guaranteed parking reservations with the lowest possible cost and searching time for drivers and the highest revenue and resource utilization for parking managers. However, they did not include other important factors that influence how drivers choose parking spaces, such as the safe locations of the parking spaces and the distance to reach the parking space.

In 2018, Tcheumadjeu et al. [22] presented an architecture for Automated Valet Parking (AVP) connected to cloud-based IoT services and mobile user interfaces. Autonomous vehicles can share information and data via the phones of their occupants. Moreover, under this communication architecture, some functions of the AVs, such as drop-off and pick-up, can be activated by phones. However, the paper only considers the interactions between users and AVs. In an actual scenario, many vehicles will be present at the same time, making efficient planning of traffic flow in the parking lot not possible by just integrating the shared information provided by the users.

In 2019, a new path planning system based on the Dijkstra algorithm was designed by Yu et al. [23]. The road occupancy factor is calculated and added to the path weight of the Dijkstra algorithm, and a shortest path is selected by comparing the weight of each path. However, the traffic situation in the parking lot is complex, and each section of the path may be occupied at any time. Hence, the optimal path planning in the parking lot requires a dynamic planning.

In 2020, a parking guidance system based on the multi-objective point A* algorithm was designed by Xiao et al. [24], which combines the distance factor between the entrance and the parking spaces and path planning using a heuristic function of the A* algorithm to quickly generate multiple driving paths and select the most efficient path. However, the heuristic function of the A* algorithm cannot take into consideration traffic congestion. If congestion happens, the time loss on queuing will reduce the efficiency of the system and subsequently increase the fuel consumption.

Therefore, in an intelligent parking infrastructure with both HVs and AVs involved, it is important to have a central command station to schedule the overall traffic flow and interface with autonomous vehicles. Moreover, it is necessary to consider in detail the factors that would affect parking space selection by the drivers and efficiently guide/allocate potentially available parking spaces for the AVs. 3. Factors for Choosing Optimal Parking Spaces

In an automated valet parking system, AVs are assumed to be able to interface with the central command station in an intelligent parking infrastructure. However, under the scenario in which there are both HVs and AVs in a parking infrastructure, no matter how intelligent the parking infrastructure is, the central command station cannot allocate parking spaces for the HVs which are not equipped with any communication devices. Based on this scenario, we consider the problem of a HV looking for a parking space in an intelligent parking infrastructure when an AV enters at the same time. The central command station, before allocating a parking space for the AV, must predict which parking space that the driver of the HV would choose and then allocate one of the remaining parking spaces to the autonomous vehicle. When a driver enters a parking infrastructure, his choice of parking space is often affected by his perception of various factors in the parking environment. Chen et al. [25] proposed six major factors that influence drivers to choose parking spaces: the walking distance from the parking spaces to the exit of the parking facility, the distance to the parking space from the entrance, the status of the path to the parking spaces, the status of the available parking spaces, parking safety, and shade under sunlight when parked outdoors. Since parking safety is somewhat implied in the status of the path for the AVs and the test case considered in this paper (see Section 6) is an outdoor parking lot with no shaded area, the last two factors will not be discussed in this paper. Thus, this paper focuses on the following four factors.

• Walking distance

Walking distance is the distance between the parking space and the exit of the parking infrastructure. For drivers, they likely prefer to arrive at their destination as quickly as possible after parking. Therefore, the shorter the walking distance, the more likely the parking space will be chosen.

• Distance to parking

Distance to parking is the distance between the entrance of the parking infrastructure and the parking space. For drivers and occupants, they generally prefer to arrive at their vehicles as quickly as possible, particularly when they forget something (e.g., phones, wallets) or need to place something back in the vehicle. Therefore, the shorter this distance, the more likely the parking space will be chosen.

• Status of the path to the parking spaces

Vehicles that break down (e.g., dead batteries) may block the path to some available spaces. Generally, lanes in parking infrastructures are narrow and often only one vehicle can pass through the lane. Lane occupancy increases traffic congestion and reduces traffic efficiency in the parking infrastructure. Thus, drivers are concerned with the status of the path leading to the available parking spaces and will likely choose those parking spaces that have clear paths.

• Status of available parking spaces

Ma [26] hypothesized that, in general, particularly new drivers are more inclined to choose available parking spaces with spaces on both sides unoccupied. The order of the priority of choice is followed by those spaces with one adjacent space unoccupied, those adjacent to the road, and finally those with spaces on both sides occupied.

Characteristics of parking spaces can be grouped into two main types: the cost type and the benefit type. For the four factors mentioned above, walking distance and distance to parking are cost types. Status of the path lane to parking spaces and status of available parking spaces are benefit types. The lower the value of the cost type factor, the higher the priority of the parking space would have. Contrarily, the higher the value of the benefit type factor, the higher priority of the parking space. Walking distance and distance to parking can be described by measurable values based on the layout of the entire parking infrastructure. Fuzzy factors such as the status of lanes and available parking spaces can also be represented by quantitative values. Following [27], a value of three is assigned when the lane is occupied; nine when the lane to the parking space is clear; eight to available parking space whose both sides are unoccupied; seven to an available parking space with one adjacent space unoccupied; six to an available parking space adjacent to the road; five to an available parking space with spaces on both sides occupied. Note that these numbers are relative and their absolute values are irrelevant.

4. Optimal Parking Space Selection Model

For a driver, parking space selection is a decision based on his perception and assessment of the parking environment. As it is difficult to quantify these fuzzy concepts for humans, fuzzy theory is introduced to solve these types of problems. The concept of fuzzy theory was put forward by Professor Zadeh in 1965, aiming to quantify the uncertainty of issues [28]. Based on the fuzzy theory, the four factors affecting driver’s choice of parking space selection, discussed in Section 3, are quantified. In this section, we will introduce how to assign and sort the weights of available parking spaces based on the Fuzzy Comprehensive Evaluation (FCE) method [28]. As a result, the order of parking space preference will be displayed with different weights.

Procedure for Model Construction Based on FCE:

(1)

Establish a factor vectorU=(_u1, _u2, …, _um)where_uiis thei-thfactor that affects the parking selection. These factors usually have varying degrees of fuzziness.

In this paper, the factor vector for evaluating parking preference isU=(_u1, _u2, _u3, _u4), where_u1represents “walking distance”,_u2“distance to parking”,_u3“status of lane to the parking spaces” and_u4“status of available parking spaces”.

(2)

Establish an evaluation matrixAwhosei-th row,(_ai1, _ai2, …, _aim), is the evaluation vector for thei-th available parking space, and_aijis the evaluation value for thej-thfactor inU.

In this paper, the evaluation vector for evaluating each factor in the vectorUis(_ai1, _ai2,_ai3, _ai4)for the i-th parking space, where_ai1, _ai2are defined as the actual values of “walking distance” and “distance to parking” for evaluating_u1and_u2, respectively;_ai3and_ai4 are the scores under the evaluation standard discussed in Section 3 for evaluating the “status of lane to the parking spaces”_u3and “status of available parking spaces”_u4, respectively.

(3)

Establish the fuzzy comprehensive evaluation matrixR=_(rij)n×mby normalizingA, wherenis the total number of targeted parking spaces that need to be evaluated andmis the number of factors.

R= (_r11r12⋯_r1mr21r21…_r2m⋮⋮⋱⋮_rn1rn2⋯_rnm)

The purpose of this normalization is to eliminate the impact caused by the differences in the orders of numbers of the physical measurements in the decision making process. For example, distance of “walking distance” maybe several meters while there is no particular unit for “status of parking spaces”; the orders of these numeric values are very different. The normalizations are:

_rij= min(_aij)_aij, i∈(1,2, …, n), j∈_I1

_rij= _aijmax(_aij), i∈(1,2, …, n), j∈_I2

where,_I1and_I2 represent the cost type factors and benefit factors, respectively [25].

(1)

According to [29], to eliminate a potentially large number of combinatorial comparisons due to a large dimension of the factor vector, it is necessary to evaluate the independent relationship between every two factors by the pair-wise comparison matrixB= _(bij)n×mwhich is defined by drivers with different driving experiences, where_bii=0.5,_bij+_bji=1, and_bij≥0. _bijrepresent the value of factoricompared to the preference to factorj,_biirepresents the value of a factor compared to the preference to itself.

In this paper, we have collected opinions from twenty drivers to form the pair-wise comparison matrix. Our sample included five males and five females, with ages varying from 20 to 55 years old and with driving experiences ranging from less than one month to more than 35 years. This set of samples represents sufficiently broad variability.

(2)

Define the weight vector of the factors:w=(_w1, _w2, …, _wn), where_wi can be calculated by the least variance method (LVM) for further ranking priority of the factors based on the pair-wise comparison matrix. [30]:

_wi= 1n(∑j=1n_bij+1− n2), i=(1, 2, …, n)

(3)

According to Equations (1)–(3) we established a priority vector_zi(w), which can be described as follows:

_zi(w)=WA_Aw(_ri1, _ri2, …, _rin)= ∑j=1n_{Rn×m wi}

where,WA_Aw(_ri1, _ri2, …, _rin)is the weighted arithmetic average operator. The higher the weight value of a certain parking space in_zi(w) , the more likely it would be selected by the driver [31].

5. Optimal Route Selection

Shortest path planning is very important in path navigation. Traffic efficiency can be improved by planning the shortest path based on the distance information between locations. Floyd algorithm is a classic dynamic programming algorithm that uses dynamic programming to find the shortest path between multiple source points in a given weighted graph. The algorithm aims to find the shortest path from one point to another [32].

Assume that the shortest path from a nodeito another nodejhas no more than two possibilities, one is directly fromitoj,and the other is fromithrough nodektoj. Hence, the dynamic transfer function of this algorithm is:dis(i,j)=min(_Di,j, _Di,k+_Dk,j), wheredis(i,j)represents the shortest distance between nodeiand nodej. The specifics of our proposed algorithm is shown as follows:

(1) Number each parking location in the map as a node;

(2)

Initialize an adjacent matrix_Dp×q, where_Di,jrepresents the distance between nodeiandj; ifiandjare not adjacent,_Di,jwill be assigned with∞; ifi = j, the value of_Di,jwill be0.

_Dp×q= (0_D1,2D1,3⋯_{D1, q−1D1,qD2,1}0_D2,3⋯_{D2,q−1D2,qD3,1D3,2}0⋯_D3,q−1D3,q⋮⋮⋮⋱⋮⋮_{Dp−1,1Dp−1,2Dp−1,3}⋯0_{Dp−1,qDp,1Dp,2Dp,3}⋯_Dp,q−10)

(3)

Update the transfer function. For example, consider three nodesi, j, andkin the map, wherekis an intermediate node ofiandj, andiandjrepresents the start point and the end point, respectively. The transfer functiondis(i,j)is updated bydis(i,j)=min(_Di,j, _Di,k+_Dk,j)to select the smaller of the two distances fromitojand fromitoktoj. The Floyd algorithm finds an intermediate nodekto determine whether there is a shorter distance through this nodek.

6. Example: Results and Discussion

The example we consider is a single-entrance parking lot, see Figure 2. The layout of the parking lot has been redesigned according to the Engineering Construction Industry Standard JGJ100-98 and the layout of the example parking lot is shown in Figure 3. Since the entrance is located in the lower right of the entire layout, we define the coordinate system with the origin at the lower right corner, as shown in Figure 4.

As shown in Figure 4, in order to design the route selection, we denote each parking space and each turning intersection as a node (1–24) and a number (T1–T8). Additionally, considering the differences in sizes of vehicles entering the parking lot, we define the coordinates of each of the nodes and intersection numbers as the centered position of the parking space and the central line of the route at the turning. The coordinates of all nodes are listed in Table 1.

In this section, we have designed three specific parking scenarios to test our proposed algorithm via Python. In the following, we will take scenario 1 as an example to explain the application of our method in detail. As shown in Figure 5, red nodes represent the parking spaces that are occupied, brown ones are those that are currently available, and the light blue node (node 11) represents the parking space that is being parked by a vehicle. A blue vehicle, which is an AV, is just entering into the intelligent parking lot and sending a parking request to the central command station. Meanwhile, an orange vehicle, which is a HV and cannot communicate with the central command station, is seeking an available parking space. Under this situation, the problem is to allocate an available parking space for the blue autonomous vehicle by the central command station.

In order to solve this problem, we need to first determine which parking space that the driver of the orange vehicle would choose and offer the shortest path between the entrance and the allocated parking space. The overview scheme is described as a flowchart (Figure 6). The specific steps in the parking spaces selection and the shortest path planning are shown as follows:

Step 1: Set the properties table of all available parking spaces currently in the example parking lot. As shown in Table 2.

For the walking distance and distance to parking, distances in metric units are used in evaluating the values in matrixA , as defined in Section 4. For the status of lane and status of available parking spaces, fuzzy evaluation is assigned with values proposed in Section 3. Based on the values from Table 2, the evaluation matrixAis:

A=(51.036.79.06.044.330.09.05.027.836.53.05.041.827.59.05.011.163.69.05.0)

Step 2: Normalize the evaluation matrixAto form the fuzzy comprehensive evaluation matrixR=_(rij)n×maccording to Equations (2) and (3):

R= (0.2170.7491.0001.0000.2500.9171.0000.8330.3990.7530.3330.8330.2661.0001.0000.8331.0000.4321.0000.833)

Step 3: Establish the pair-wise comparison matrix by the comparison method, based on the opinions of our sample set of twenty drivers with a range of driving experiences, as described in Section 4. The following shows the response from one of the drivers:

_Bi= (0.50.80.90.40.20.50.10.40.10.90.50.90.60.60.10.5)

where,i =1,…,10for our data set. As shown in_Bi, all diagonal values are 0.5 as each factor complements itself. The values of_b12=0.8and_b21=0.2indicate that in the view of this driver, the factor “walking distance” is more important than “distance to parking”. “distance to parking” is still a factor that the driver would consider when choosing a parking space, but it is just less important.

Step 4: Obtain the weight vector for the pair-wise comparison matrix in Step 3 according to Equation (4):

_wi =(0.40, 0.05, 0.35, 0.20)

Applying Equation (4), the pair-wise comparison matrix from the twenty drivers is converted into the following weight matrix:

w=(0.4000.0500.3500.2000.2000.3250.4500.2750.5000.1250.1750.1750.175−0.0500.6250.7500.1500.3750.2500.2250.2250.1250.2500.4000.1250.5500.3500.3500.3750.1000.3500.1750.1250.2250.3750.2500.2250.2000.4000.2250.2500.0750.4750.2000.4250.0750.4750.2000.4250.0750.3250.1750.1250.1250.4250.3250.0500.2750.2250.4500.1750.2500.2750.3000.3000.1250.2500.3250.3250.1750.1000.4250.3000.0000.4500.2500.1500.1500.4250.3250.1000.3000.3250.275)

To make the above matrix representative of the preference of most drivers, we remove the largest and smallest values of each factor in the above matrix and average the remaining values to obtain an average weight vector:

w˜=(0.233, 0.170, 0.336, 0.286)

Step 5: With the average weight vector and Equation (5), the priority vector that contains the weights of every available parking space in the given situation can be obtained:

_zi(w)=(0.799, 0.788, 0.571, 0.806, 0.881)

Step 6: Ranking the priorities of the available parking spaces in this example parking lot according to_zi(w)gives:_z23(w)>_z18(w)>_z5(w)>_z9(w)>_z12(w).

Based on step 6, parking space23has the highest priority for the driver of the orange vehicle. Thus, parking space18will be allocated to the blue autonomous vehicle by the central command station. By analyzing the preferences of the human driver, the algorithm is able to provide the optimal parking space for the autonomous vehicle. Since an intelligent parking lot system cannot influence the choice of the driver, a suboptimal parking space, which is space 18, is allocated to autonomous vehicle in this situation.

Step 7: Establish the adjacent matrix with all the road intersection nodes and the node of parking space 18 for route selection based on the adjacent matrix assignment rule according to Equation (6) in Section 5:

D= (011.5∞∞∞∞∞17.6∞∞011.0∞∞∞17.6∞∞∞∞010.9∞17.6∞∞8.4∞∞∞013.6∞∞∞∞∞∞∞13.60∞∞∞∞∞∞∞∞11.60∞∞9.2∞∞∞∞∞11.00∞∞∞∞∞∞∞∞11.50∞∞∞∞∞∞∞∞00)

As shown in matrixD, there is only one passable path from T1 to parking space 18: starting from T1, go through T2, subsequently arrive at T3, then turn right to parking space 18, which is also the shortest path, with a total distance of30.9m. Through this method, under the scenario of the presence of one HV and one AV in this example, we simultaneously predict the parking space preference of the driver and allocate a parking space to the AV through V2X communication based on the driver preferences. Moreover, a parking lot may be constrained with traffic rules (e.g., one way road) and limited space, the adjacent matrixDcan, in addition to providing the shortest route navigation, also reflect the constraints of the traffic rules and other conditions.

Using the same approach as used in scenario one, we can also solve the similar issues, such as in the following two scenarios: Scenario 2:

Step 1: Set the properties table of all available parking spaces currently in the example parking scenario (Figure 7). As shown in Table 3.

Based on the values from Table 3 and assignment rule in Section 3, the evaluation matrixAis:

A=(43.529.29.05.044.330.09.05.027.836.59.05.021.842.59.06.03.255.79.06.011.163.69.05.0)

Step 2: Normalize the evaluation matrixAto form the fuzzy comprehensive evaluation matrixR=_(rij)n×maccording to Equations (2) and (3):

R= (0.0741.0001.0000.8330.0720.9731.0000.8330.1150.7991.0000.8330.1470.6871.0001.0001.0000.5241.0001.0000.2880.4591.0000.833)

Step 3: With the average weight vector calculated in scenario one and Equation (5), the priority vector that contains the weights of every available parking space in scenario two can be obtained:

_zi(w)=(0.761, 0.756, 0.737, 0.773, 0.944, 0.719)

Step 4: Ranking the priorities of the available parking spaces in this example parking lot according to_zi(w)gives:_z20(w)>_z19(w)>_z2(w)>_z9(w)>_z12(w)> _z23(w).

Based on Step 4, parking space20has the highest priority for the driver of the orange vehicle based on scenario two. Thus, parking space19will be allocated to the blue autonomous vehicle by the central command station.

Scenario 3:

Step 1: Set the properties table of all available parking spaces currently in the example parking scenario (Figure 8). As shown in Table 4.

Based on the values from Table 4 and assignment rule in Section 3, the evaluation matrixAis:

A=(51.036.79.06.041.827.59.05.025.334.09.06.027.836.59.07.021.842.59.06.03.255.79.06.011.163.69.05.0)

Step 2: Normalize the evaluation matrixAto form the fuzzy comprehensive evaluation matrixR=_(rij)n×maccording to Equations (2) and (3):

R= (0.0630.7491.0000.8570.0771.0001.0000.7140.1260.8091.0000.8570.1150.7531.0001.0000.1470.6471.0000.8571.0000.4941.0000.8570.2880.4321.0000.714)

Step 3: With the average weight vector calculated in scenario one and Equation (5), the priority vector that contains the weights of every available parking space in scenario three can be obtained:

_zi(w)=(0.723, 0.728, 0.748, 0.777, 0.725, 0.898, 0.681)

Step 4: Ranking the priorities of the available parking spaces in this example parking lot according to_zi(w)gives:_z20(w)>_z12(w)>_z11(w)>_z8(w)>_z19(w)>_z5(w)> _z23(w).

Based on step 4, parking space20has the highest priority for the driver of the orange vehicle based on scenario two. Thus, parking space12will be allocated to the blue autonomous vehicle by the central command station.

As can be seen from the above three test examples, people are more inclined to choose the available parking space near the exit of the parking lot.

In this paper, to validate of the proposed algorithm, we have collected opinions from fifty drivers on their most preferred parking spaces to check against the data from the twenty drivers mentioned in Step 3. Figure 9 shows that, in addition to the preferred choice of space 23, 20 and 20 in designed scenarios one, two and three, respectively, there are only four, six and four other choices among the fifty drivers who are surveyed. The accuracy of the prediction of the proposed algorithm is thus, 92%, 88% and 92%, respec-tively, in the three test cases.

7. Conclusions and Future Work In this paper, we studied the problem of automated parking space allocation during the transition period when both human-operated vehicles (HVs) and autonomous (driverless) vehicles (AVs) are present simultaneously in an intelligent parking infrastructure. Since not all vehicles will be autonomous in a near foreseeable future and fully automated parking systems are still being developed, the problem of interest, thus, has important and relevant applications. Based on four key factors that affect the choice of parking spaces for drivers, the fuzzy comprehensive evaluation (FCE) method is used to first predict the driver’s choice of parking space, since a HV cannot communicate with the central command station. This prediction then allows an intelligent parking system to allocate the remaining available parking spaces to the AVs without conflict arising with the HVs. Furthermore, by incorporating information of the parking spaces and road map of the parking facility, an adjacent matrix in the Floyd algorithm is then developed to determine the shortest feasible paths to arrive at the parking spaces safely. The proposed algorithms are applied to three parking lot scenarios in which both a HV and an AV are entering. It is shown that a parking space can be reasonably allocated to the AV after a prediction of the driver’s choice of parking space. This work lays the foundation for future investigation into the automated parking problem with multiple HVs and AVs. Moreover, since the test parking lot discussed in this paper is not very large, it is likely that drivers can observe the entire layout and the situation from the entry point. More complexities of the parking infrastructure, such as multiple entrances, exits, and levels, can be considered in the future. A faster and more robust dynamic planning method needs to be developed.

Figure 1. Flowchart of the entire process of parking space allocation and route selection for an autonomous vehicle.

Figure 2. Aerial view of the parking lot of our example problem.

Figure 3. Layout of the parking lot (distance unit in meter).

Figure 4. Layout of nodes in the parking lot and reference to a coordinate system.

Figure 5. Example of a parking scenario 1.

Figure 6. Flowchart for parking space selection and the shortest path planning.

Figure 7. Example of a parking scenario 2.

Figure 8. Example of a parking scenario three.

Figure 9. Comparison between the predicted parking space preference and the opinions of the most preferred parking space from fifty drivers in three example scenarios.

Figure 9. Comparison between the predicted parking space preference and the opinions of the most preferred parking space from fifty drivers in three example scenarios.

T1	(2.1, 17.0)	1	(9.7, 17.0)	9	(13.0, 17.0)	17	(8.0, 39.5)
T2	(2.1, 28.5)	2	(12.2, 17.0)	10	(15.5, 17.0)	18	(10.5, 39.5)
T3	(2.1, 39.5)	3	(14.7, 17.0)	11	(5.5, 28.5)	19	(13.0, 39.5)
T4	(2.1, 50.4)	4	(17.2, 17.0)	12	(8.0,28.5)	20	(5.2, 50.5)
T5	(15.7, 50.4)	5	(19.7, 17.0)	13	(10.5, 28.5)	21	(7.8, 50.5)
T6	(19.7, 39.5)	6	(5.5, 17.0)	14	(13.0, 28.5)	22	(10.4, 50.5)
T7	(19.7, 28.5)	7	(8.0, 17.0)	15	(15.5, 28.5)	23	(13.1, 50.5)
T8	(19.7, 17.0)	8	(10.5, 17.0)	16	(5.5, 39.5)	24	(15.7, 50.5)

Parking Space	Walking Distance (m)	Distance to Parking (m)	Status of Parking	Status of Available Parking Spaces
5	51.0	36.7	clear	adjacent to the road
9	44.3	30.0	clear	both sides are occupied
12	27.8	36.5	occupied	both sides are occupied
18	41.8	27.5	clear	both sides are occupied
23	11.1	63.6	clear	both sides are occupied

Parking Space	Walking Distance (m)	Distance to Parking (m)	Status of Parking	Status of Available Parking Spaces
2	43.5	29.2	clear	both sides are occupied
9	44.3	30.0	clear	both sides are occupied
12	27.8	36.5	clear	both sides are occupied
19	21.8	42.5	clear	adjacent to the road
20	3.2	55.7	clear	adjacent to the road
23	11.1	63.6	clear	both sides are occupied

Parking Space	Walking Distance (m)	Distance to Parking (m)	Status of Parking	Status of Available Parking Spaces
5	51.0	36.7	clear	adjacent to the road
8	41.8	27.5	clear	both sides are occupied
11	25.3	34.0	clear	adjacent to the road
12	27.8	36.5	clear	one adjacent space unoccupied
19	21.8	42.5	clear	adjacent to the road
20	3.2	55.7	clear	adjacent to the road
23	11.1	63.6	clear	both sides are occupied

Author Contributions

M.W. and H.J. designed the algorithm; C.-A.T. verified the rationality of the algorithm; M.W. performed the software simulation; H.J. and C.-A.T. analyzed the results of the simulation; M.W. wrote the paper with help of H.J. and C.-A.T.; C.-A.T. completed the final editing. All authors have read and agreed to the published version of the manuscript.

Funding

This work is financially supported by The Major University Nature Science Research Project of Jiangsu Province (No.16KJA580001).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

1. Kim, O.T.T.; Tran, N.H.; Pham, C.; Leanh, T.; Thai, M.T.; Hong, C.S. Parking Assignment: Minimizing Parking Expenses and Balancing Parking Demand among Multiple Parking Lots. IEEE Trans. Autom. Sci. Eng. 2020, 17, 1320-1331.

2. Nawaz, S.; Efstratiou, C.; Mascolo, C. ParkSense: A Smartphone Based Sensing System for On-Street Parking. In Proceedings of the 19th International Conference on Mobile Computing & Networking, Miami, FL, USA, 30 Sepetember-4 October 2013.

3. Jang, C.; Kim, C.; Lee, S.; Kim, S.; Lee, S.; Sunwoo, M. Re-Plannable Automated Parking System with a Standalone around View Monitor for Narrow Parking Lots. IEEE Trans. Intell. Transp. Syst. 2020, 21, 777-790.

4. Li, C.X. Research on Automatic Vertical Parking System Based on Intelligent Recognition Technology of Parking Space Scene. Ph.D. Thesis, Jiangsu University, Zhenjiang, China, 2016.

5. Schwarz, S.; Zochmann, E.; Muller, M.; Guan, K. Dependability of Directional Millimeter Wave Vehicle-to-Infrastructure Communications. IEEE Access 2020, 8, 53162-53171.

6. Sedighi, S.; Nguyen, D.V.; Kuhnert, K.D. Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications. In Proceedings of the 5th IEEE International Conference on Control, Automation and Robotics (ICCAR), Beijing, China, 19-22 April 2019.

7. Shih, S.; Tsai, W. A Convenient Vision-Based System for Automatic Detection of Parking Spaces in Indoor Parking Lots Using Wide-Angle Cameras. IEEE Trans. Veh. Technol. 2014, 63, 2521-2532.

8. Mohandes, M.; Deriche, M.; Abuelma'atti, M.T.; Tasadduq, N. Preference-based smart parking system in a university campus. IET Intell. Transp. Syst. 2019, 13, 417-423.

9. Liang, W.; Hu, J.M.; Zhang, Y.; Zhang, Z.; Wang, Z.W. Modeling and empirical analyses of parking space choices based on individual preferences. Tsinghua Univ. (Sci. Technol.) 2017, 57, 100-106.

10. Leephakpreeda, T. Car-parking guidance with fuzzy knowledge-based decision making. Build. Environ. 2007, 42, 803-809.

11. Marina, D.; Vladislav, L.; Inna, S.; Igor, K. Parking Guide Service for Large Urban Areas. In Proceedings of the 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), Metz, France, 18-21 September 2019.

12. Nesic, Z.; Ljubic, L.; Radojicic, M.; Vasovic, J.V. Some considerations on improvement of parking service information system. In Proceedings of the 24th Telecommunications Forum (TELFOR), Belgrade, Serbia, 22-23 November 2016.

13. Dijkstra, E.W. A Note on Two Problems in Connexion with Graphs. Numer. Math. 1959, 1, 269-271.

14. Floyd, R.W. Algorithm 97: Shortest path. Commun. ACM 1962, 5, 345.

15. Shi, W.; Wang, K. Floyd algorithm for the shortest path planning of mobile robot. Chin. J. Sci. Instrum. 2009, 10, 2088-2092.

16. Ji, Y.J.; Wang, W.; Deng, W. Micro-level parking behaviors within parking facilities and optimal parking space choice model. J. Southeast Univ. (Nat. Sci. Ed.) 2009, 2, 399-403.

17. Banzhaf, H.; Nienhuser, D.; Knoop, S.; Zollner, J.M. The future of parking: A survey on automated valet parking with an outlook on high density parking. Proceeding of the IEEE Intelligent Vehicles Symposium (IV), Los Angeles, CA, USA, 11-14 June 2017.

18. Dou, Y.X.; Zhang, M.M.; Zhang, J.; Fan, X.Y. Study on Dynamic Distribution Algorithm in Parking. J. Zhenzhou Univ. Light Ind. 2012, 6, 24-27.

19. Audi Industrial Group. Audi Technology Portal. Available online: https://www.audi-technology-portal.de/en/electrics-electronics/driver-assistant-systems/parking-assist (accessed on 10 September 2020).

20. Alfatihi, S.; Chihab, S.; Alj, Y.S. Intelligent Parking System for Car Parking Guidance and Damage Notification. In Proceedings of the International Conference on Intelligent Systems Modelling & Simulation, Bangkok, Thailand, 29-31 January 2013.

21. Kotb, A.O.; Shen, Y.C.; Zhu, X.; Huang, Y. iParker-A New Smart Car-Parking System Based on Dynamic Resource Allocation and Pricing. IEEE Trans. Intell. Transp. Syst. 2016, 17, 2637-2647.

22. Tcheumadjeu, L.C.T.; Andert, F.; Tang, Q.; Sohr, A.; Stürzl, W. Integration of an Automated Valet Parking Service into an Internet of Things Platform. In Proceedings of the 21st International Conference on Intelligent Transportation Systems (ITSC), Maui, HI, USA, 4-7 November 2018.

23. Yu, L.Y.; Jiang, H.B.; Hua, L. Anti-Congestion Route Planning Scheme Based on Dijkstra Algorithm for Automatic Valet Parking System. Appl. Sci. 2019, 9, 5016.

24. Xiao, W.; Zhang, L.; Qiu, Z.H.; Zhong, Y.; Zhang, T.N. Design of Parking Lot Path Guidance System Based on Multi-objective Point A* Algorithm. Comput. Mod. 2020, 6, 40-45.

25. Chen, M.; Hu, C.; Chang, T. The Research on Optimal Parking Space Choice Model in Parking Lots. In Proceedings of the 3th International Conference on Computer Research and Development (ICCRD), Shanghai, China, 11-13 March 2011.

26. Ma, J. Design and Implementation of Parking Space Recommendation System Considering User Preference. Master's Thesis, Henan University, Henan, China, 2018.

27. Chen, J. Study on Urban Parking Facilities' Planning Methods. Ph.D. Thesis, Southeast University, Nanjing, China, 2000.

28. Zadeh, L.A. Fuzzy sets. Inf. Control 1965, 8, 338-353.

29. Xu, Z.S. Uncertain Multiple Attribute Decision Making: Methods and Applications; Tsinghua University Press: Beijing, China, 2004.

30. Xu, Z.S. The Least Variance Priority Method (LVM) for Fuzzy Complementary Judgement Matrix. Syst. Eng. Theory Pract. 2001, 21, 93-96.

31. Waerden, P.; Borgers, A.; Timmermans, H. Travelers Micro-Behavior at Parking Lots: A Model of Parking Choice Behavior. In Proceedings of the 82nd Annual Meeting of the Transportation Research Board, Washington, DC, USA, 12-16 January 2003.

32. Sathyaraj, B.M.; Jain, L.C.; Finn, A.; Drake, S. Multiple UAVs path planning algorithms: A comparative study. Fuzzy Optim. Decis. Mak. 2008, 7, 257-267.