A new geometry-based secondary path planning for automatic parking

Abstract

In auto-parking systems, a certain degree of error in the path tracking algorithm is inevitable. This is caused by actuator error, tire slipping, or other factors relevant to and included in the parking process. In such situations, the parking path needs to be updated to finish parking successfully which is referred to as secondary path planning. Herein, a new geometry-based method is proposed to deal with this issue, which can be called the pattern-based method. In this method, a predefined path pattern set consisting of 24 multi-segment patterns is developed first. These patterns are composed of straight lines and arcs and account for constraints due to motion and the immediate environment. Then, a traversal policy is adopted to select the path pattern from the set, and the sequential quadratic programming algorithm is used to determine the optimal parameters that fine-tune the pattern to meet the current constraints. In the simulation section, the effectiveness of the proposed method is demonstrated. Moreover, compared to the search-based method represented by a variation of rapidly exploring random tree*, the proposed method has a higher planning performance.

Keywords

Auto-parking system parallel parking secondary path planning path patterns nonlinear optimal algorithm mobile robot

Introduction

Auto-parking system (APS) refers to the technology embedded in the vehicle for autonomous parking. Such a system utilizes sensor technology, computer technology, and automatic control technology to perceive and interpret the environment, plan the parking path, and then track the path. Since APS can not only free the driver from the tedious parking task but also immensely increase safety. It has caught the attention of many manufacturers, including BMW, Audi, Ford, Land Rover, Toyota, Nissan, and Mercedes-Benz.¹ Though APS has made progress in practical applications, the system still faces some challenges before it is completely independent of the driver. For instance, conducting secondary path planning (SPP) still is a big challenge when the vehicle deviates from the preplanned path in the parking process, especially for parallel parking. To this extent, parking path planning in APS requires further study.

Up to now, many methodologies and strategies on the parallel parking planning issue are proposed in the literature, which can be mainly divided into three branches: geometry-based methods, optimization-based methods, and search-based methods. In the geometry-based methods, several kinds of predefined paths consisting of multi-segment fundamental curves, such as straight line, arc, β-spline, and others, are chosen as the parking path patterns, and the curve parameters are employed as the planning variables. These parameters are determined by algebraic or optimization method according to the kinematics and environment constraints. For example, Ankit and Rohan² employ the straight line and the circular arc to plan the parking path. Hélène et al.³ propose a new strategy to find the parallel parking path, in which the parking process is viewed as its inverse process first, retrieving process, and circle arcs are adopted to generate the parking path. Besides the straight line and arc, other curves can also be used to achieve a feasible parking path. For instance, Gomez-Bravo et al.⁴ plan the parallel parking path based on β-spline. Liang et al.⁵ adopt Bezier curve to smooth the turning point which meets the continuity of the parallel parking requirements. Aneesh et al.⁶ take the sigmoidal Gompertz curve as the path component and use an optimization scheme to obtain a parallel parking path. Comparing to the other kinds of methods, the advantage of geometry-based methods mainly lies in the low cost of calculation, while the disadvantage is the poor planning success rate.⁷

In the optimization-based method, the motion parameters of the vehicle, like linear velocity and steering angle, are taken as the planning variables. And the variables are obtained under an established optimization framework. For example, a fast optimization-based parking path planner that focuses on narrow environments is developed by Zips et al.⁸ Kondak and Hommel⁹ formulate parking path planning as a nonlinear optimal control problem and solve it by numerical method. The nonlinear programs are utilized to obtain the time-optimal parking path.^10
–12 Here, a time-optimal parking path is obtained under a unified dynamic optimization framework that includes initial and goal configuration constraints, collision-free constraint, vehicle kinematics constraint, and an optimizing module. The minimum length path is found based on the numerical solution for the Hamilton–Jacobi–Bellman equations, where the fewest possible motion direction changes are required.¹³ Comparing to the other kinds of methods, the advantage of the optimization-based methods is the high path quality. But it has a difficulty to express an obstacle as an equation, and the computation cost highly depends on the solver of the optimization problem.⁷

In the search-based methods, a collision-free path from the initial configuration to the goal one is conducted by sampling randomly or searching directly. For example, the A* algorithm^14,15 and the rapidly exploring random tree (RRT)^16
–18 are employed to generate parking path. Generally speaking, search-based algorithms are computationally expensive. To reduce the computation cost, the authors of a study at Korea University presented a three-step path planning method for parallel parking and vertical parking.¹⁹ In this method, reachable regions are calculated first based on the collision-free constraint and kinematic constraint. Then the generation of candidate paths follows this by searching through reachable region sets. Finally, an optimal path is achieved by determining the lowest cost according to a cost function. Orientation Aware Space Exploration Guided Heuristic Search is proposed to solve the parallel parking planning problem.²⁰ It shows constant performance in different maneuvering scenarios and converges faster than basic Exploration Guided Heuristic Search.²¹ A two-stage RRT algorithm is presented.²² In this method, the first step is to create waypoints. Then a feasible path is obtained by constructing a kinematic tree that connects the start and goal waypoints. Besides, RRT*²³ and its variations^24,25 are also effective for parallel parking planning problems. In these methods, the cost of the returned solution converges to the optimum and the computational complexity of this algorithm is within a constant factor of that of their probabilistically complete counterparts. Comparing with the other kinds of methods, the search-based methods can be applied to different planning scenarios, but its computation cost is still too high and the path is not continuous.²⁶

As mentioned above, most research studies focus on the parallel parking planning problem when the initial configuration is outside the slot. However, few research studies are centered on the SSP problem. In fact, due to the control error and other factors, the vehicle cannot continue to follow the preplanned parking path. In this situation, a new parking path needs to be planned. Nevertheless, since the operation room is highly restricted due to the vehicle being wholly or partially inside the slot, this brings a challenge to plan a new path. For the geometry-based methods, since the design process of predefined paths only considers the scenario when the vehicle is outside of the slot and the amount of them is limited, they cannot solve the SSP problem. For the optimization-based methods and the search-based methods, since the planning process is not limited by the predefined paths, these two kinds of methods have higher success rate and are suitable for solving the SSP problem. However, considering that the general commercial automotive electric control unit (ECU) employed in the assisted parking system^26
–28 has limited performance due to the nature of the price-sensitive automotive industry, it requires that the parking planning algorithm must have low computational complexity.²⁶ Meanwhile, Lee et al.²⁶ also pointed out that the search-based methods with high computation cost cannot meet the low planning time requirement. Similarly, the computation cost of the optimization-based method is also too high for automotive ECUs. For example, the computation time of Li’s^11,12 and Micelli’s¹³ is beyond 1 s on a PC whose CPU has better computation performance than that of ECU. Thus, we can say that the optimization-based method is also not suitable for the ECU. According to the above analysis, from the viewpoint of computation complexity, the geometry-based method is the most suitable one for automotive ECUs. However, its planning success rate for SPP is too low. Therefore, for the automotive ECU, it is necessary to develop a new parking planning method to solve the SPP issue.

In this article, a new geometry-based method is proposed, which can be called as the pattern-based method. In this method, a pattern set composed of 24 predefined parking path patterns is designed according to the kinematics and environment constraints first. All of the predefined path patterns are multi-segment curves connected by straight lines and arcs. To accelerate the planning process, these predefined patterns are divided into four subsets based on the geometric relationship between the vehicle body and the environment, and the patterns are sorted by the number of path segments in each subset. Then, a traversal searching policy is adopted to select the path pattern from the corresponding pattern subset, and the sequential quadratic programming (SQP) algorithm is used to determine the optimal parameters of that pattern. During optimization, collision-free constraints, kinematics constraints, and goal configuration constraints are all considered. Comparing with the exiting geometry-based methods, since the predefined parking paths of the proposal are designed considering the characteristics of the SPP scenario, the success rate of the proposed method is improved. Meanwhile, by classifying the predefined parking paths and applying an optimization method to determine the parameters of parking paths, the computation cost is much lower than that of the optimization-based and search-based methods. The presented simulation results clearly show that the proposed method has high planning performance.

The rest of this article is organized as follows. In the second section, the kinematics of the vehicle and the parameters of the parallel parking slot are described in detail. The third section presents a unified SPP framework for parallel parking. Simulation studies that cover multiple scenarios to demonstrate the effectiveness of the proposed method are described in the fourth section. Moreover, the performance comparison between the proposed method and the RRT* method is also conducted in this section. Finally, the conclusion is presented in the fifth section.

Problem formulation

The kinematics model of a vehicle

The kinematics model and size parameters, as shown in Figure 1, serve as a basis for the mathematical description of the vehicle. P (x, y, θ) represents the rear axle center, x and y refer to the position of the vehicle, θ refers to the orientation angle, v denotes the linear velocity of P , and φ denotes the steering angle of the front wheel. Other parameter settings related to the geometric size of the vehicle include vehicle length L, vehicle width 2W, front overhang L_f , and rear overhang L_b , respectively, as shown in Figure 1. The kinematic concern on the front steering wheels can be expressed as

{\begin{matrix} \dot{x} = v cos θ \\ \dot{y} = v sin θ \\ \dot{θ} = v tan φ / (L - L_{f} - L_{b}) \end{matrix}

By ignoring the side slip motion of the vehicle, the kinematics are limited by a nonholonomic constraint that can be written as

\dot{x} sin θ - \dot{y} cos θ = 0

Figure 1.

Parametric notations of vehicle size and kinematics.

The motion trajectory of the four vertices (A, B, C, and D in Figure 1) in the vehicle body can be obtained according to P

[\begin{array}{l} A_{x} \\ A_{y} \end{array}] = [\begin{array}{l} P_{x} \\ P_{y} \end{array}] + M [\begin{matrix} L - L_{b} \\ W \end{matrix}]

[\begin{array}{l} B_{x} \\ B_{y} \end{array}] = [\begin{array}{l} P_{x} \\ P_{y} \end{array}] + M [\begin{matrix} L - L_{b} \\ - W \end{matrix}]

[\begin{array}{l} C_{x} \\ C_{y} \end{array}] = [\begin{array}{l} P_{x} \\ P_{y} \end{array}] + M [\begin{matrix} - L_{b} \\ - W \end{matrix}]

[\begin{array}{l} D_{x} \\ D_{y} \end{array}] = [\begin{array}{l} P_{x} \\ P_{y} \end{array}] + M [\begin{matrix} - L_{b} \\ W \end{matrix}]

where [P_x , P_y ]^T is the positional coordinates of the rear axle center. M denotes the direction cosine matrix of the local coordinate system related to the inertial coordinate system, which can be expressed by

M = [\begin{matrix} cos θ & - sin θ \\ sin θ & cos θ \end{matrix}]

Description of a parallel parking slot

As shown in Figure 2, the notations of a parallel parking slot are as follows: sl and sh denote the slot length and width, respectively. S ₁, S ₂, S ₃, and S ₄ are the four corner points of the slot. The inertial coordinate system is established on S ₄.

Figure 2.

Notations of a parallel parking slot.

Collision-free constraints

Collision-free constraints between the vehicle and obstacles in the environment play an important role in path planning issue. Generally, there are two kinds of collision scenarios: a vertex of the vehicle collides with the edge of the slot (see Figure 3(a)) and an edge of the vehicle collides with one of the two corner points of a slot (see Figure 3(b)). For the first scenario, as shown in Figure 3(a), the environment is at rest. Therefore, to determine a collision, we only need to judge whether the position of any vertex is outside of the allowed area. This is a simple process that requires only a small number of numerical comparisons. For the other type of collision, as shown in Figure 3(b), however, the vehicle is in motion and collision detection is complex.

Figure 3.

Possible collisions: (a) scenario 1 and (b) scenario 2.

To solve this problem in a straightforward manner, the vehicle body is regarded as a box, and geometry-based methods are used for collision detection. Examples of this include the Minkowski sum method²⁹ and the area-based method.¹⁰ Here, we employ the area-based method to judge whether a collision occurs, the process of which is as follows.

Setting Q as the vertex of the slot, and the relationship between the vehicle body and Q is depicted in Figure 4. If $S_{Q A B} + S_{Q B C} + S_{Q C D} + S_{Q D A} > S_{A B C D}$ (S represents the area, e.g. S_QAB is the area of ΔQAB), Q is outside the rectangle ABCD, as shown in Figure 4(a), otherwise, Q is inside the rectangle ABCD, as shown in Figure 4(b).

Figure 4.

Schematic showing a collision decision method: (a) non-collision case and (b) collision case.

Secondary path planning

As presented in the introduction, the APS is required to conduct the SPP when the vehicle deviates the preplanned path. Since the available space is very small due to the vehicle being partly or wholly inside the slot while executing SPP, a continuous path does not exist in most cases. Consequently, it is necessary to design a multi-segment path for the parking operation. By summarizing the human driving experience, we found that drivers can always use a finite number of unique path patterns to park the vehicle to the goal configuration. This inspires us that there may exist a feasible solution set consisting of a finite number of path patterns for the parking path planning issue, and a specific parking path satisfying the constraints can be found out from this set by searching. Based on this idea, a pattern-based parking path planning method is proposed. This method is described in detail below.

Current configuration analysis

The geometric relationship between the vehicle body and the parallel parking slot can be classified into four scenarios which are illustrated in Figure 5, where P _s (x _s, y _s, θ _s) and P _g (x _g, y _g, θ _g) denote the start and goal configurations, respectively. For the goal configuration, it satisfies L_b < x _g < sl − (L − L_b ), y _g = (S _1y + S _4y)/2 and θ _g = 0. Thus the goal configuration is not determined, once the vehicle arrived P _g, it only needs to go forward or backward to approach the final configuration. In scenarios 1 and 2, the angular attitude of the depicted configuration is greater than 0. P _s is higher than P _g in the first scenario and lower in the second. In scenarios 3 and 4, a similar situation is depicted with an opposing angle. The angular attitude of the start configuration is less than 0, but the configurations are still off the mark in terms of the goal.

Figure 5.

Deviation from the preplanned path: (a) y _s > y _g, θ > 0; (b) y _s < y _g, θ > 0; (c) y _s > y _g, θ < 0; and (d) y _s < y _g, θ < 0.

Path pattern description

Since straight line (S) and circle arc (C) are the basic motions of the vehicle, any path of the vehicle can be decomposed into straight lines and arcs.^30,31 In view of this, we selected the straight line and the arc as the basic units for parking path patterns.

According to the differences in types of the vehicle motion, the basic unit of the parking path can be divided into six types: $S^{+}, S^{-}, C_{φ l}^{+}, C_{φ r}^{+}, C_{φ l}^{-}, and C_{φ r}^{-}$ , where + and − denote the forward and backward motions, respectively, r and l mean the steering orientation of the front wheel is right and left, and φ is the value of the steering angle, as shown in Figure 6.

Figure 6.

Basic path unit: $(1) S^{+}, (2) S^{-}, (3) C_{ϕ l}^{+}, (4) C_{ϕ r}^{+}, (5) C_{ϕ l}^{-}, and (6) C_{ϕ r}^{-}$ .

The following example illustrates the use of patterns in expressing a parking path. As shown in Figure 7, the path is composed of three segments: the first segment denotes the vehicle moving forward, on an arc, with right steer angle φ; the second segment denotes the vehicle moving backward in a straight line; the last segment denotes the vehicle moving forward, again on an arc, but with the left steer angle φ. The entire path can be expressed as $C_{φ r}^{+} S^{-} C_{φ l}^{+}$ .

Figure 7.

Pattern $C_{ϕ r}^{+} S^{-} C_{ϕ l}^{+}$ .

Path pattern designing

In terms of the proposed method, the important part is to design a pattern path set. This set is composed of 24 predefined pattern paths. It has been deduced by testing that the planning success rate of the proposed method can be as high as 99% once the maximum number of segments of the predefined path is set to 4. However, the contribution of the added predefined paths to the planning success rate is very little as the maximum number of paths is set to 5. This approach tends to influence the computation time negatively thereby the maximum number is selected as 4 in the current study. The predefined pattern paths whose solution space is small and covered by the other predefined ones are also eliminated to reduce the computation cost. Finally, only 24 predefined pattern paths are left to construct the pattern set. Since some of the valid pattern paths are eliminated, the planning result of the proposed method is not optimal rather local optimal. The removal of valid pattern paths is beneficial since it reduces the computational cost.

According to the description in the “Current configuration analysis” section, the pattern set can be divided into four subsets corresponding to the four scenarios and sorted by the number of segments.

Scenario 1: $(a) C_{φ l}^{-},$ $(b) C_{φ r}^{+} C_{φ l}^{+},$ $(c) C_{φ l}^{-} C_{φ r}^{+} C_{φ l}^{-},$ $(d) S^{+} C_{φ r}^{-} C_{φ l}^{-},$ $(e) C_{φ l}^{+} C_{φ r}^{-} C_{φ l}^{-},$ $(f) C_{φ r}^{+} C_{φ r}^{-} C_{φ l}^{-},$ $(g) C_{φ r}^{+} S^{+} C_{φ r}^{-} C_{φ l}^{-},$ $(h) S^{-} C_{φ l}^{+} C_{φ r}^{-} C_{φ l}^{-},$ $(i) S^{-} C_{φ r}^{+} C_{φ r}^{-} C_{φ l}^{-},$ and $(j) S^{+} C_{φ r}^{+} C_{φ r}^{-} C_{φ l}^{-}$ (see Figure 8).

Scenario 2: $(a) C_{φ r}^{+},$ $(b) C_{φ l}^{-} C_{φ r}^{-},$ $(c) S^{+} C_{φ l}^{-},$ $(d) C_{φ r}^{+} C_{φ l}^{-},$ $(e) C_{φ r}^{-} S^{+} C_{φ l}^{-},$ and $(f) C_{φ l}^{+} S^{-} C_{φ r}^{+} C_{φ l}^{-}$ (see Figure 9).

Scenario 3: $(a) C_{φ l}^{+},$ $(b) C_{φ r}^{-} C_{φ l}^{-},$ $(c) S^{+} C_{φ r}^{-},$ $(d) C_{φ l}^{+} C_{φ r}^{-} C_{φ l}^{-},$ and $(e) S^{-} C_{φ l}^{+} C_{φ r}^{-} C_{φ l}^{-}$ (see Figure 10).

Scenario 4: $(a) C_{φ r}^{-},$ $(b) C_{φ l}^{+} C_{φ r}^{+},$ and $(c) S^{-} C_{φ l}^{+}$ (see Figure 11).

Figure 8.

Patterns for scenario 1. $(a) C_{ϕ l}^{-},$ $(b) C_{ϕ r}^{+} C_{ϕ l}^{+},$ $(c) C_{ϕ l}^{-} C_{ϕ r}^{+} C_{ϕ l}^{-},$ $(d) S^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(e) C_{ϕ l}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(f) C_{ϕ r}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(g) C_{ϕ r}^{+} S^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(h) S^{-} C_{ϕ l}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(i) S^{-} C_{ϕ r}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ and $(j) S^{+} C_{ϕ r}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-}$ .

Figure 9.

Patterns for scenario 2. $(a) C_{ϕ r}^{+},$ $(b) C_{ϕ l}^{-} C_{ϕ r}^{-},$ $(c) S^{+} C_{ϕ l}^{-},$ $(d) C_{ϕ r}^{+} C_{ϕ l}^{-},$ $(e) C_{ϕ r}^{-} S^{+} C_{ϕ l}^{-},$ and $(f) C_{ϕ l}^{+} S^{-} C_{ϕ r}^{+} C_{ϕ l}^{-}$ .

Figure 10.

Patterns for scenario 3. $(a) C_{ϕ l}^{+},$ $(b) C_{ϕ r}^{-} C_{ϕ l}^{-},$ $(c) S^{+} C_{ϕ r}^{-},$ $(d) C_{ϕ l}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-},$ and $(e) S^{-} C_{ϕ l}^{+} C_{ϕ r}^{-} C_{ϕ l}^{-}$ .

Figure 11.

Patterns for scenario 4. $(a) C_{ϕ r}^{-},$ $(b) C_{ϕ l}^{+} C_{ϕ r}^{+},$ and $(c) S^{-} C_{ϕ l}^{+}$ .

Pattern parameters solving

In the patterns depicted above, all of the values for the segment parameters are unknown, including the length of the straight line, the radius and length of arcs. Herein, the optimization algorithm is employed to determine these parameters. The cost function is the minimum sum distance of the parking path, and the goal configuration constraints, vehicle kinematics constraints, and collision-free constraints are considered. For each pattern, since collision-free constraints are different, the optimization problem is given by a simple unified form in this section first. The specific implementation details are given in Appendix 1. The unified form of the optimization problem is

\begin{array}{l} min_{x} (l_{1} (x) + ... + l_{n} (x)) n represent the segment number \\ s.t. c_{1} (x) < 0 \\ c_{2} (x) < 0 \\ c_{3} (x) < 0 \\ c_{4} (x) = 0 \end{array}

where l_i ( x ) is the length of the ith segment, and x represents the optimization variables including the length of straight lines, the radius and center angle of arcs; c ₁( x ) < 0 represents the collision constraint, c ₂( x ) < 0 denotes the kinematic constraint of the vehicle, and c ₃( x ) < 0 and c ₄( x ) = 0 denote the inequality constraint and equality constraint of the goal configuration, respectively. In order to solve this optimization problem, the SLSQP function of NLOPT, an open-source nonlinear optimization library, is called to finish this optimization task. As described in the official website, the SLSQP function employs an SQP algorithm to solve the nonlinearly constrained gradient-based optimization problem (supporting both inequality and equality constraints).³²

The procedure to plan a feasible parking path is as follows:

Obtaining current configuration of the vehicle.

Determining the corresponding scenario, shown in Figure 5, of the current configuration. Here, assuming that the ith scenario is selected.

Taking the first predefined path of pattern subset i as the candidate path pattern.

Solving parameters of the candidate path pattern by the optimization algorithm.

If the solution is found, the planning is succeeded and the generated path is returned; otherwise, go to step 6.

Judging whether there are pattern paths behind the candidate one. If true, taking the next pattern path as the candidate one and go back to step 4; otherwise, the planning is failed and the driver will take over the vehicle.

Numerical simulation

To illustrate the effectiveness of the proposed method, several numerical simulations with different scenarios are investigated. In these simulations, the geometric size of the adopted vehicle is similar to a mid-sized commercial vehicle, as shown in Table 1. To guarantee safety during parking, there is a margin of d = 0.1 m that is added to the vehicle body size.

Table 1.

Basic parameters of the vehicle.

L (m)	L_f (m)	L_b (m)	2W (m)	ϕ _max (°)	R_C _min (m)
4.8	1.2	0.8	1.8	35°	4

For the slot dimension, as listed in Table 2, Blackburn³³ presented a specific function to determine the minimum length of the slot corresponding to the car’s size. The function is

s l_{min} = L + \sqrt{(R_{k} ​^{2} - L_{w b} ​^{2}) + {(L_{w b} + L_{f})}^{2} - {(\sqrt{R_{k} ​^{2} - L_{w b} ​^{2}} - 2 W)}^{2}} - L_{w b} - L_{f}

where $R_{k} = \sqrt{{(L_{w b} + L_{f})}^{2} + {(R_{min} + W)}^{2}}$ denotes the kerb-to-kerb turning radius. Considering that the collision-free constraints requirement, the turn radius of the front vertex is chosen as the kerb-to-kerb turning radius. Considering the safe distance d = 0.1 m, the minimum length of slot should be sl _min = 6.8 m.

Table 2.

Basic parameters of the parallel parking slot.

sl (m)	sh (m)	H (m)
7	2.5	4.5

Pattern path effectiveness evaluation

To prove the validity of the predefined path patterns and there is no redundant predefined path, 24 initial configurations, listed in Table 3, are chosen to plan the parking path. These configurations are selected from the corresponding solution space of each pattern, respectively. The slot dimensions are listed in Table 3. The simulations are performed on the Raspberry Pi 3 whose CPU clock speed is 1.2 GHz, RAM is 1 G. The CPU performance of it is similar to the processing unit NXP S32V234 SoC, which is developed for automotive.³⁴ The parking paths planned by our method are drawn in Figures 12 to 15, and the computing time is listed in Table 4. It can be observed from these figures that every pattern path designed is useful. As could be seen in Table 4, the computing time of the proposed method is less than 220 ms. These illustrate that all of predefined paths are available and the proposed method can be applied in the low-cost platform.

Table 3.

Initial configurations.

Scenario 1		Scenario 2		Scenario 3		Scenario 4
Case no.	Configuration	Case no.	Configuration	Case no.	Configuration	Case no.	Configuration
1	(2.5, 1.5, 0.35)	1	(1, 1.2, 0.1)	1	(1.4, 1.3, −0.08)	1	(2.6, 1.22, −0.05)
2	(1.2, 1.28, 0.05)	2	(2.8, 1.2, 0.05)	2	(2.8, 1.35, −0.1)	2	(1.2, 1.15, −0.05)
3	(2.5, 1.55, 0.6)	3	(1.2, 1.15, 0.1)	3	(1.2, 1.3, −0.05)	3	(2.2, 1.22, −0.04)
4	(1.6, 2.8, 0.2)	4	(2, 1.2, 0.3)	4	(1.3, 3, −0.1)
5	(1.3, 2.4, 0.05)	5	(1.6, 1.1, 0.05)	5	(2, 2.5, −0.1)
6	(1.8, 2.6, 0.55)	6	(1.8, 1.15, 0.03)
7	(1.3, 2.6, 0.7)
8	(2.5, 2, 0.1)
9	(2.8, 3.4, 0.7)
10	(4.5, 2.1, 0.7)

Figure 12.

Planned path of the pattern-based method in scenario 1: (a) case 1, (b) case 2, (c) case 3, (d) case 4, (e) case5, (f) case 6, (g) case7, (h) case 8, (i) case 9, and (j) case 10.

Figure 13.

Planned path of the pattern-based method in scenario 2: (a) case 1, (b) case 2, (c) case 3, (d) case 4, (e) case 5, and (f) case 6.

Figure 14.

Planned path of the pattern-based method in scenario 3: (a) case 1, (b) case 2, (c) case 3, (d) case 4, and (e) case 5.

Figure 15.

Planned path of the pattern-based method in scenario 4: (a) case 1, (b) case 2, and (c) case 3.

Table 4.

Computation time.

Scenario 1		Scenario 2		Scenario 2		Scenario 4
Case no.	Computation time (ms)	Case no.	Computation time (ms)	Case no.	Computation time (ms)	Case no.	Computation time (ms)
1	1	1	1	1	1	1	1
2	1	2	1	2	1	2	1
3	1	3	1	3	1	3	1
4	9	4	1	4	9
5	13	5	1	5	19
6	85	6	1
7	125
8	179
9	201
10	219

Performance analysis

In order to illustrate the validity of the proposed method and analyze its planning performance, the geometry-based method in the work of Hélène et al.,³ the optimization-based method represented by Li et al.,¹² and RRT* variation²⁵ are taken as the comparison object. Different from our method, the method in Hélène’s,³ and RRT* variation, the goal configuration of Li’s method only requires the whole vehicle body inside the parking slot, which means the goal configuration constraints of Li’s is looser than that of the others. In all simulations, the parameters of Li’s are listed in Table 5, all of which are the same as the settings in Li’s. The parameters of RRT* adopted are proved to be optimal by testing, which are listed in Table 6. The simulation in this section is executed on a computer with Intel Core i7-4790 CPU (3.6 GHz) and 16 GB memory. In these simulations, limited time planning success rate and path quality are discussed. The specific simulation scenarios and results are given as follows.

Limited time planning success rate: To evaluate the success rate of the proposed method and illustrate its computation cost is lower than other methods, a group of simulation tests is carried out. In these tests, a uniform sampling manner is employed to select initial configurations from a testing configuration space, as shown in Figure 16. The range of x is (0, sl) (sl = 6.8 m, 7 m, 7.2 m), the range of y is (1 m, 3.4 m), and the range of orientation is (−0.1 rad, π/4 rad). The corresponding sample intervals are 0.1m, 0.1 m, and 0.05 rad, respectively. As a result, three testing configuration sets are obtained. Getting rid of the configurations colliding with the environment, the number of valid samples of them are 11,120, 11,916, and 12,702, respectively. When the maximum computation time is limited to 200 ms, 1000 ms, 5000 ms, 10,000 ms, and 15,000 ms, respectively, the simulation results of the proposed method and the other methods are illustrated in Figure 17. It can be observed that when the maximum computation time is 200 ms, the planning success rates of the proposed method are 99.08%, 99.09%, and 99.13% in three testing scenarios, respectively. Meanwhile, we find that the failed configurations under these time limits, shown in Figure 18, have quite small moving room. Although a feasible parking path can be obtained in these configurations by adding some new patterns consisting of more path segments, it is meaningless. That is because these failed configurations exist only in theory, but the vehicle is scarcely possible to reach. Removing them from the test set, the planning success rate of our method can reach 100%. As could be seen from Figure 17, the success rate of the geometry-based method in Hélène’s³ is less than 26% no matter what’s the length of the slot and how long the maximum time is. It illustrates that the proposed geometry-based method has a great improvement in the planning success rate compared with the ordinary geometry-based method. Besides, according to Figure 17, the success rate of RRT* variation²⁵ and Li’s¹² can reach 99% only when the computation time beyond 5000 ms and 15,000 ms, respectively, which demonstrates that these two methods have higher computational complexity than our proposal. Therefore, it can be said that although our method is not complete, it has high success rate and has better limited time planning performance in practice.

Path quality: To compare the proposed method with other methods in terms of path quality including the number of segment and path length, numerical simulations are performed without limiting computation time, respectively. For each scenario listed in Figure 5, three initial configurations are selected randomly to generate paths with the proposed method, Li’s method,¹² and the variation of RRT*,²⁵ respectively. Considering that the method in Hélèn’s³ cannot find the parking path in most of initial configurations, it is not selected as the comparison objective in this subsection. For each initial configuration, we performed 10 Monte Carlo simulation runs, respectively. The average path length and average number of segment are listed in Table 7. To show the comparison more clearly, selecting one initial configuration from each scenario and draw its path, as shown in Figure 19.

Table 5.

Parameters of Li’s.¹²

NE	Φ _max (rad)	a _max (m/s²)	v _max (m/s)	Ω _max (rad/s)
20	0.61	0.75	1.8	1.2

Table 6.

Parameter of RRT* variation (MATLAB Automotive Tools).

Goal tolerance	Goal bias	Connection distance	Max iteration	Connect method
[0.01 m, 0.01 m, 1°]	0.4	4 m	1000	Reeds–Shepp

RRT: rapidly exploring random tree.

Figure 16.

Testing area.

Figure 17.

Comparison of the pattern-based method and other methods in terms of limited time planning success rate: (a) sl = 6.8 m, (b) sl = 7.0 m, and (c) sl = 7.2 m.

Figure 18.

Failed configurations (the red line is the safe margin): (a) sl = 6.8 m, (b) sl = 7 m, and (c) sl = 7.2 m.

Table 7.

Comparison of pattern-based and other methods in terms of path length and number of segment.

Scenario no.	Initial configuration	Number of segment			Path length (m)
Scenario no.	Initial configuration	Ours	Li’s¹²	RRT*²⁵	Ours	Li’s¹²	RRT*²⁵
1	(3.5, 3, 0.5)	3	4	6.4	7.97	4.61	10.98
	(2.7, 2.2, 0.1)	4	3	9.5	10.90	4.67	12.82
	(1.5, 2.7, 0.3)	3	4	6.3	10.73	8.01	14.84
2	(2, 1.2, 0.1)	2	1	6.1	2.71	0.12	6.58
	(1.5, 1.15, 0.05)	2	1	4.5	3.10	0.08	8.39
	(1.3, 1.2, 0.08)	2	1	4.8	2.90	0.10	3.42
3	(2, 1.8, −0.1)	4	4	5.8	9.51	2.82	10.15
	(1.2, 2.6, −0.1)	3	8	6.5	8.97	9.12	12.11
	(1.7, 3.2, −0.05)	3	4	6.3	9.49	8.28	10.06
4	(2.3, 1.2, −0.08)	1	0	2.2	1.41	0	1.41
	(1.2, 1.22, −0.05)	2	0	4.1	3.5	0	7.33
	(1.8, 1.2, −0.02)	3	0	5.4	3.09	0	14.15

RRT: rapidly exploring random tree.

Figure 19.

The path generated with pattern-based method (a-1, b-1, c-1, d-1), Li’s¹² (a-2, b-2, c-2, d-2), and the variation of RRT*²⁵ (a-3, b-3, c-3, d-3). The selected initial configurations are (a) (1.5, 2.7, 0.3), (b) (2, 1.2, 0.1), (c) (1.2, 2.6, −0.1), and (d) (2.3, 1.2, −0.08).

According to Table 7 and Figure 19, the paths generated by RRT*²⁵ have the longest path length and the biggest number of segments, which is a foreseeable outcome since the RRT* method employs a random sampling way to plan paths. Comparing with the planning results of Li’s method,¹² that of the proposed method has longer path length and similar number of segments. These demonstrate that the quality of the parking path planned by the current approach is higher than RRT* variation, but slightly inefficient than Li’s. The reasons for achieving a shorter path by Li’s are: (i) the goal configuration of Li’s method only requires the vehicle body inside the slot, that is, if the corresponding vehicle body of the initial configuration is almost or completely inside the slot, it only requires to plan either a short parking path or no plan at all. This can explain the reason for the length of the parking paths approaching 0 in scenarios 2 and 4. (ii) Li’s path is generated by optimization in the global solution space, but the path obtained by the proposed method is found by optimization in the local solution space. Thus, it can be said that the result of Li’s is globally optimal, but the result of the current method is locally optimal.

Conclusion

In this article, a new geometry-based parking path planning method, named the pattern-based method, is proposed aimed at solving the SPP when the vehicle deviates from the preplanned path in a parallel parking process. In this method, a predefined path pattern set consisting of 24 path patterns is designed first. Then during planning, a practicable parking path can be found out from the pattern set by searching. In numerical simulations, the effectiveness and the performance of the proposed method are both verified and discussed. Meanwhile, the simulation results demonstrate that the proposed method has high limited time planning success rate compare to geometry-based, optimal-based, and RRT* method and high quality than RRT* method. Although the planning quality of Li’s¹² is better, the computation time is much higher than the method proposed in the current study. Therefore, it can be said that the proposed method has the highest comprehensive performance, and can be considered as a simpler and higher efficient parking path planning method, which is more suitable for automotive ECUs.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Natural Science Foundation of China (grant nos 11772187 and 11802174), the China Postdoctoral Science Foundation (grant no. 2018M632104), and the Shanghai Institute of Technical Physics of the Chinese Academy of Sciences (grant no. CASIR201702).

ORCID iD

Xiao-Feng Liu

Appendix 1

According to the “Pattern parameters solving” section, the unified form of optimization equation (8) is

Here, the pattern scenarios 1(d) and 1(h), as shown in Figures 1A and 3A, respectively, are taken as examples to give the implementation details of the optimization problem.

(1) In pattern scenario 1(d), as shown in Figure 1A, the length of $P_{s} P_{1}$ , the radius and the center angle of $P_{1} P_{2}$ are the optimization variables x_i , i = 1, 2, 3, respectively. In vector form, they are expressed as $x = {[x_{1}, x_{2}, x_{3}]}^{T}$ . As shown in Figure 2A, there are five collision cases. According to the geometric relationship, the collision-free constraints c ₁( x ) < 0 are expressed as

The kinematic constraint c ₂( x ) < 0 is

The inequality constraint of the goal configuration c ₃( x ) < 0 is

The equality constraint of the goal configuration c ₄( x ) = 0 is

According to equations (1A) to (5A), the whole optimization can be expressed as

where x ₁, x ₂ x ₃, l( x ) is the length of segment $P_{s} P_{1}$ , $P_{1} P_{2}$ , $P_{2} P_{g}$ , respectively.

(2) In pattern scenario 1(h), as shown in Figure 3A, the length of $P_{s} P_{1}$ , the radius and the center angle of $P_{1} P_{2}$ , and the radius and the center angle of $P_{2} P_{3}$ are the optimization variables x_i , i =1, 2, 3, 4, 5, respectively. In vector form, they are expressed as $x = {[x_{1}, x_{2}, x_{3}, x_{4}, x_{5}]}^{T}$ . As shown in Figure 4A, there are eight collision cases if pattern scenario 1(h) is taken as parking path. According to the geometric relationship, the collision-free constraints c ₁( x ) < 0 are expressed as

The kinematic constraint c ₂( x ) < 0 is

The inequality constraint of the goal configuration c ₃( x ) < 0 is

The equality constraint of the goal configuration c ₄( x ) = 0 is

According to equations (1A) and (7A) to (10A), the whole optimization can be expressed as

where x ₁, x ₂ x ₃, x ₄ x ₅, l( x ) is the length of segment $P_{s} P_{1}$ , $P_{1} P_{2}$ , $P_{2} P_{3}$ , $P_{3} P_{g}$ , respectively.

References

Blosseville

Flonneau

. From traffic signal control systems to automated driving, a review of its systems based on a cross historical and technical perspective. In: Transport research arena (TRA) 5th conference: transport solutions from research to deployment, Paris, France, 14–17 April 2014, pp. 1–7. Washington DC: TRID.

Ankit

Rohan

. Autonomous parallel parking methodology for Ackerman configured vehicles. ACEEE Int J Commun 2010; 1(2): 22–27.

Hélène

Sébastien

Nicoleta

, et al. Automatic parallel parking in tiny spots: path planning and control. IEEE Trans Intell Transp 2014; 16(1): 396–410.

Gomez-Bravo

Cuesta

Ollero

, et al. Continuous curvature path generation based on β-spline curves for parking maneuvers. Robot Auton Syst 2008; 56(4): 360–372.

Liang

Zheng

. Automatic parking path optimization based on Bezier curve fitting. In: Proceeding of the IEEE international conference on automation and logistics (ICAL), Zhengzhou, China, 15–17 August 2012, pp. 583–587. New York: IEEE.

Aneesh

Michihiro

Tatsuo

. Application of sigmoidal Gompertz curves in reverse parallel parking for autonomous vehicles. Int J Adv Robot Syst 2015; 12(9): 1–11.

Jang

Kim

Lee

, et al. Re-plannable automated parking system with a standalone around view monitor for narrow parking lots. IEEE Trans Intell Transp 2019; 21(2): 1–14.

Zips

Böck

Kugi

. Optimisation based path planning for car parking in narrow environments. Robot Auton Syst 2016; 79: 1–11.

Kondak

Hommel

. Computation of time optimal movements for autonomous parking of non-holonomic mobile platforms. In: Proceedings of IEEE international conference on robotics and automation (ICRA), Seoul, South Korea, 21–26 May 2001, pp. 2698–2703. New York: IEEE.

10.

Shao

. A unified motion planning method for parking an autonomous vehicle in the presence of irregularly placed obstacles. Knowl Based Syst 2015; 86: 11–20.

11.

Wang

Shao

. Time-optimal maneuver planning in automatic parallel parking using a simultaneous dynamic optimization approach. IEEE Trans Intell Transp 2016; 17(11): 3263–3274.

12.

Zhang

Shao

. Spatio-temporal decomposition: a knowledge-based initialization strategy for parallel parking motion optimization. Knowl Based Syst 2016; 107: 179–196.

13.

Micelli

Consolini

Locatelli

. Path planning with limited numbers of maneuvers for automatic guided vehicles: an optimization-based approach. In: Proceedings of IEEE 2017 25th Mediterranean conference on control and automation (MED), Valletta, Malta, 3–6 July 2017, pp. 204–209. New York: IEEE.

14.

Dolgov

Thrun

Montemerlo

, et al. Practical search techniques in path planning for autonomous driving. Ann Arbor 2008; 1001(48105): 18–80.

15.

Kummerle

Hahnel

Dolgov

, et al. Autonomous driving in a multi-level parking structure. In: Proceedings of IEEE international conference on robotics and automation (ICRA), Kobe, Japan, 12–17 May 2009, pp. 3395–3400. New York: IEEE.

16.

LaValle

Kuffner

. Randomized kinodynamic planning. Int J Robot Res 2011; 20(5): 378–400.

17.

Kuwata

Teo

Fiore

, et al. Real-time motion planning with applications to autonomous urban driving. IEEE Trans Control Syst 2009; 17(5): 1105–1118.

18.

Han

Mita

. Unified path planner for parking an autonomous vehicle based on RRT. In: Proceedings of IEEE international conference on robotics and automation (ICRA), Shanghai, China, 9–13 May 2011, pp. 5622–5627. New York: IEEE.

19.

Kwon

Chung

. Performance analysis of path planners for car-like vehicles toward automatic parking control. Intel Serv Robot 2014; 7(1): 15–23.

20.

Chen

Rickert

Knoll

. Path planning with Orientation-Aware Space Exploration Guided Heuristic Search for autonomous parking and maneuvering. In: 2015 IEEE intelligent vehicles symposium, Soul, Korea, 28 June–1 July 2015, pp. 1148–1153. New York: IEEE.

21.

Chen

Rickert

Knoll

. Combining space exploration and heuristic search in online motion planning for nonholonomic vehicles. In: 2013 IEEE intelligent vehicles symposium, Gold Coast, Australia, 23–26 June 2013, pp. 1307–1312. New York: IEEE.

22.

Wang

Jha

Akemi

. A two-stage RRT path planner for automated parking. In: Proceedings of IEEE conference on automation science and engineering(CASE), Xi’an, China, 20–23 August 2017, pp. 496–502. New York: IEEE.

23.

Sertac

Walter

Perez

, et al. Anytime motion planning using the RRT*. In: Proceedings of IEEE international conference on robotics and automation (ICRA), Shanghai, China, 9–13 May 2011, pp. 1478–1483. New York: IEEE.

24.

Csorvasi

Nagy

Kiss

. RTR+C*CS: an effective geometric planner for car-like robots. In: IEEE 16th international carpathian control conference (ICCC), Szilvasvarad, Hungary, 27–30 May 2015, pp. 85–90. New York: IEEE.

25.

Help document MATLAB Automated Driving Toolbox, https://ww2.mathworks.cn/help/driving/ref/pathplannerrrt.html (2018, accessed 16 February 2019).

26.

Lee

Kang

, et al. Trajectory folding-based path planning for automated parking system. In: 2018 21st international conference on intelligent transportation systems (ITSC), Maui, HI, USA, 4–7 November 2018, pp. 1083–1088. New York: IEEE.

27.

Jeong

Choi

. Low cost design of parallel parking assist system based on an ultrasonic sensor. Int J Autom Technol 2010; 11(3): 409–416.

28.

Von Reyher

Naya

Chiba

. Parking assist system. Patent application 12/741 940, USA, 2010.

29.

Lozano-Pérez

. Spatial planning: a configuration space approach. IEEE Trans Comput 1983; C-32(2): 259–271.

30.

Dubins

. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math 1957; 79(3): 497–516.

31.

Reeds

Shepp

. Optimal paths for a car that goes both forwards and backwards. Pac J Math 1990; 145(2): 367–393.

32.

Dieter

Algorithm 733: TOMP–Fortran modules for optimal control calculations. ACM Trans Math Softw 1994; 20(3): 262–281.

33.

Blackburn

. The geometry of perfect parking. Egham: Department of Mathematics, Royal Holloway, University of London, 2009.

34.

ARM®-based processors, https://www.nxp.com/products/processors-and-microcontrollers/arm-processors:ARM-PROCESSORS (accessed 16 February 2019).