2.1. Parking scenarios

This study investigates two types of parking scenarios: ideal and actual ones. The actual scenario takes into account the impact of the FPS deviation of adjacent vehicles. As shown in Figure 1, adjacent vehicles 1–4 are within the normal FPS, while vehicles 5-10 deviate from it. Thus, parking spots 1 and 2 represent ideal scenarios without intrusion, and parking spots 3 and 4 are actual scenarios with one-sided and two-sided intrusions, respectively.

Figure 1.

Ideal parking scenarios and actual parking scenarios.

Figure 1 Long description

The diagram compares ideal and actual parking scenarios, showing different vehicle positions and intrusion levels. The top row depicts ideal parking scenarios with no intrusion, labeled from 1 to 5. The bottom row shows actual parking scenarios with one side intrusion and two side intrusion, labeled from 6 to 10. Each scenario is visually represented with vehicles positioned in parking spots, highlighting the challenges of narrow parking spaces and the potential for traffic disturbances and environmental impacts.

2.2. Safety index indicators for parking scenario with intrusion

The actual parking spot is determined by the edges of adjacent vehicles, as shown in Figure 2. For modeling purposes, a coordinate system $O_PXY$ is established with the geometric center of the original parking spot as the origin. The offset distance and angle of the left and right edges ( $\Delta x_L$ , $\Delta x_R$ , $\Delta \beta _L$ and $\Delta \beta _R$ ) are used to describe the parking scenario. Then, the coordinates of the four vertices of the actual parking spot are

(1) \begin{align} \left \{ \begin{array}{l} x_{\text{LU}} = - \dfrac {W_{\text{P}}}{2} + \frac {L_{\text{P}}}{2} \cdot \cot \beta _{\text{L}} + \Delta x_{\text{L}}, \quad y_{\text{LU}} = \dfrac {L_{\text{P}}}{2}\\[8pt] x_{\text{LB}} = - \dfrac {W_{\text{P}}}{2} - \dfrac {L_{\text{P}}}{2} \cdot \cot \beta _{\text{L}} + \Delta x_{\text{L}}, \quad y_{\text{LB}} = -\dfrac {L_{\text{P}}}{2}\\[8pt] x_{\text{RU}} = \dfrac {W_{\text{P}}}{2} + \dfrac {L_{\text{P}}}{2} \cdot \cot \beta _{\text{R}} - \Delta x_{\text{R}}, \quad y_{\text{RU}} = \dfrac {L_{\text{P}}}{2}\\[8pt] x_{\text{RB}} = \dfrac {W_{\text{P}}}{2} - \dfrac {L_{\text{P}}}{2} \cdot \cot \beta _{\text{R}} - \Delta x_{\text{R}}, \quad y_{\text{RB}} = -\dfrac {L_{\text{P}}}{2} \end{array} \right . \end{align}

where $\Delta x_L$ and $\Delta x_R$ are the offset distances of the mid-points of the left and right edges, respectively. $\beta _L$ and $\beta _R$ are the inclination angles of the left and right edges ( $\beta _L=\Delta \beta _L+\frac {\pi }{2}$ , $\beta _R=\Delta \beta _R+\frac {\pi }{2}$ ), respectively. $L_P$ and $W_P$ are the length and width of the original parking lot, respectively.

The shape of the actual parking spot is only determined by the total offset distance $\Delta x_O$ ( $\Delta x_O = \Delta x_L+\Delta x_R$ ) and the offset angles $\Delta \beta _L$ and $\Delta \beta _R$ . Thus, the vectors $[\Delta x_O, \Delta \beta _L, \Delta \beta _R]$ are used to characterize the actual parking scenarios.

Generally, SNPS, including the width of the corridor ( $W_C$ ) and the front space ( $S_F$ ), is limited, resulting in a higher risk of collision during parking. The intrusion of adjacent vehicles further increases this risk. As shown in 2, to ensure safety, a rectangular expansion is applied to the vehicle boundary, the expansion distance indicated as $d_E$ , which is set at 0.1 m in this study. During the parking process, the ego vehicle is subject to constraints from the left, right, and upper sides, as well as bottom constraints defined by the boundaries of the actual parking spot. The minimum DBVO is used for safety evaluation.

Figure 2.

Actual parking scenario model and safety characterization.

Figure 2 Long description

The diagram depicts the actual parking scenario model and safety characterization. It includes labeled points such as A, B, C, D, E, O_v, O_p, and R_u, along with lines and angles representing various constraints and measurements. The upper constraint, front constraint, and bottom constraint are shown, along with the parking path and the actual profile of a vehicle. The diagram also includes the expansion profile and the rear axle center, with annotations for distances and angles such as W_c, L_u, L_b, R_b, S_f, Δx_l, Δx_r, β_l, β_r, γ, and θ. The relationships between these elements illustrate the parking process and safety considerations.

The vehicle state is generally characterized by the coordinates of the rear axle center point and heading angle, represented as $\boldsymbol{S} = [x_E, y_E, \theta ]$ . To take advantage of the vehicle’s symmetry, the state $\boldsymbol{S}_{OV}$ ( $\boldsymbol{S}_{OV} = [x_{OV}, y_{OV}, \theta ]$ ), based on the geometric center of the vehicle, is adopted for safety analysis. The conversion formula between these two states is

(2) \begin{align} \left \{ \begin{array}{l} x_{\text{OV}} = x_{\text{E}} + \left ( \dfrac {L_{\text{V}}}{2} - l_{\text{R}} \right ) \cos \theta \\[8pt] y_{\text{OV}} = y_{\text{E}} + \left ( \dfrac {L_{\text{V}}}{2} - l_{\text{R}} \right ) \sin \theta \end{array} \right . \end{align}

where $(x_{OV}, y_{OV})$ are the coordinates of the geometric center of the vehicle. $L_V$ is vehicle length. $l_R$ is length of vehicle rear overhang.

The process for calculating the minimum distance between the vehicle and each obstacle is as follows. For the left, right, and upper constraints, the coordinates of the four expanded vertices of the vehicle are first computed for each heading angle, assuming the vehicle’s center is at the origin.

(3) \begin{equation} \left [ \begin{array}{c} \mathbf{x}_{\text{V}}(\theta ) \\ \mathbf{y}_{\text{V}}(\theta ) \end{array} \right ] = \left [ \begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right ] \left [ \begin{array}{c} \mathbf{x}_{\text{V}}(0) \\ \mathbf{y}_{\text{V}}(0) \end{array} \right ] \end{equation}

where $\boldsymbol{x}_V(\theta )$ and $\boldsymbol{y}_V(\theta )$ are the abscissa and ordinate vectors of the vehicle’s expanded vertexes (points A, B, C, D in Figure 2) for a heading angle of $\theta$ .

Then, the minimum distances between the vehicle and the upper, left, and right obstacles in state of $S_{OV}$ are calculated as follows.

(4) \begin{align} \left \{ \begin{array}{l} d_{\mathrm{U}} = W_{\mathrm{C}}+\dfrac {L_{\mathrm{P}}}{2}-\left [\max \left (\mathbf{y}_{\mathrm{V}}(\theta )\right )+y_{\mathrm{OV}}\right ]\\[3pt] d_{\mathrm{R}}=\dfrac {W_{\mathrm{P}}}{2}+S_{\mathrm{F}}-\left [\max \left (\mathbf{x}_{\mathrm{V}}(\theta )\right )+x_{\mathrm{OV}}\right ]\\[3pt] d_{\mathrm{L}}=\min \left (\mathbf{x}_{\mathrm{V}}(\theta )\right )+x_{\mathrm{OV}}-\dfrac {W_{\mathrm{P}}}{2}-S_{\mathrm{F}} \end{array} \right . \end{align}

where $d_U$ , $d_R$ , and $d_L$ are the minimum distances between the vehicle and the upper, left, and right obstacles, respectively, with negative values indicating a collision.

As illustrated in Figure 2, the bottom constraint consists of five line segments. Collision detection should be performed first, which involves checking for any interference between the four line segments of the vehicle’s expanded profile and the five line segments of the obstacles in the bottom constraint. The specific method is as follows.

(5) \begin{align} {f_{{\mathrm{IN}}ij}} = \left \{ \begin{array}{cc} 0&{{\mathrm{no\, intersection\, point}}}\\[3pt]1&{{\mathrm{else}}} \end{array} \right .,i = 1,2, \cdots ,4;\,\,j = 1,2, \cdots ,5 \end{align}

where $f_{IN_{ij}}$ is a logical variable indicating whether there is an intersection point between line segment $i$ of the vehicle’s expansion profile and the obstacle line segment $j$ . A sum of $\sum f_{IN}=0$ indicates no collision with the bottom constraint; otherwise, a collision occurs.

When there is no collision, the minimum distance between the vehicle and the bottom constraint is determined by the smallest distance from the four expanded vertices of the ego vehicle to the five obstacle line segments, as well as the distances from the two convex points, $L_U$ and $R_U$ , of the actual parking lot to the four expanded edges of the vehicle. The distance from point $L_U$ to line segment $AB$ is calculated as follows.

(6) \begin{align} d_{\mathrm{PL}i} = \left \{ \begin{array}{cc} \left | \mathrm{L}_{\mathrm{U}}\mathrm{L}_{\mathrm{U}_\bot } \right | & \angle \mathrm{L}_{\mathrm{U}}\mathrm{AB} \lt \dfrac {\pi }{2} \cap \angle \mathrm{L}_{\mathrm{U}}\mathrm{BA} \lt \frac {\pi }{2}\\[3pt] \min \left ( \left | \mathrm{L}_{\mathrm{U}}\mathrm{A} \right |, \left | \mathrm{L}_{\mathrm{U}}\mathrm{B} \right | \right ) & \text{else} \end{array} \right .,\quad i = 1, \cdots , 28 \end{align}

Thus, the minimum distance between the vehicle and the bottom constraint ( $d_B$ ) is

(7) \begin{align} {d_{\mathrm{B}}} = \left \{ \begin{array}{cc} {\min \left \{ {{{\bf{d}}_{{\mathrm{PL}}}}} \right \}}&{\sum {{f_{{\mathrm{IN}}}}} = 0}\\[3pt] { - 0.1}&{\sum {{f_{{\mathrm{IN}}}}} \ne 0} \end{array} \right . \end{align}

2.3. Partition-based calculation method for $d_{B}$ field

Calculating the minimum $\text{DBVO}$ for safety evaluation during the path planning phase can significantly reduce planning efficiency, as the calculation of $d_B$ involves numerous interference detection and distance computations from points to line segments for each node in every path during the search process. To achieve real-time parking path planning, a method based on partition for calculating the $d_B$ field is proposed.

As shown in Figure 3, under a constant heading angle, the trace of the vehicle’s geometric center – formed as the vehicle bottom slides along the bottom constraint line – divides the SNPS into three zones: the collision zone, the regular zone, and the key zone. The $d_B$ along the trace is zero. In the regular zone, the increment in $d_B$ equals the increment in the ordinate, as follows:

(8) \begin{equation} {d_{\mathrm{B}}}(x,y,\theta ) = {d_{\mathrm{B}}}(x,{y_{{\mathrm{OV1}}}},\theta ) + y - {y_{{\mathrm{OV1}}}} \end{equation}

where (x, y) are the coordinates of the geometric center of the vehicle. $y_{OV1}$ is the vertical coordinate of the vehicle geometric center when its lower-right vertex of the expansion boundary is at the top-left vertex position of the parking space.

Due to the symmetry of the vehicle,

(9) \begin{equation} {d_{\mathrm{B}}}(x,y,\theta ) = {d_{\mathrm{B}}}(x,y,\pi + \theta ) \end{equation}

Therefore, only the $d_B$ in the key zones within the heading angle range of $[0, \pi ]$ needs to be calculated to obtain the $d_B$ field of the entire $\text{SNPS}$ . As illustrated in Figure 3, the area of the key zones is substantially smaller than that of the entire $\text{SNPS}$ , which leads to a marked improvement in computational efficiency.

Figure 3.

Partition of SNPS.

Figure 3 Long description

The diagram illustrates the partition of the space near the parking spot (SNPS) into different zones. The zones are color-coded: green for regular zones, yellow for key zones, and pink for collision zones. The diagram includes labels such as 'Trace of vehicle center' and 'Lines of actual parking spot.' It also features various points labeled as O_v1, O_v2, O_v3, O_v4, O_v5, and O_v6, which represent different positions of the vehicle during the parking process. The angles θ, β_L, and β_R are marked to indicate the orientation of the vehicle relative to the parking spot. The diagram uses arrows to show the direction of movement and includes a coordinate system with axes labeled X and Y.

According to the relationship between the heading angle $\theta$ and the three angles of $\pi /2$ , $\beta _L$ , and $\beta _R$ , there are eight distinct partition situations. As illustrated in Figure 3, which represents the case where $\theta \lt \pi /2$ , $\theta \lt \beta _L$ , and $\theta \lt \beta _R$ , the coordinates of the six critical points ( $x_{OVi}$ , $y_{OVi}$ ) essential for the partitioning process are derived through geometric analysis.

(10) \begin{align} \left \{ \begin{array}{l} x_{\mathrm{OV}1} = x_{\mathrm{LU}} + L\cos (\gamma + \theta ),\quad y_{\mathrm{OV}1} = \dfrac {L_{\mathrm{P}}}{2} + L\sin (\gamma + \theta )\\[6pt] x_{\mathrm{OV}2} = x_{\mathrm{LU}} + L\cos (\gamma - \theta ),\quad y_{\mathrm{OV}2} = \dfrac {L_{\mathrm{P}}}{2} - L\sin (\gamma - \theta )\\[3pt] x_{\mathrm{OV}3} = (y_{\mathrm{OV}3} - y_{\mathrm{OV}2})\cot \beta _{\mathrm{L}} + x_{\mathrm{OV}2},\quad y_{\mathrm{OV}3} = -\dfrac {L_{\mathrm{P}}}{2} + L\sin (\gamma + \theta )\\[3pt] x_{\mathrm{OV}4} = x_{\mathrm{RB}} - L_{\mathrm{VE}}\cos \theta - L_{\mathrm{VE}}\sin \theta \cot \beta _{\mathrm{R}} + L\cos (\gamma + \theta ),\quad y_{\mathrm{OV}4} = y_{\mathrm{OV}3}\\[3pt] x_{\mathrm{OV}5} = (y_{\mathrm{OV}5} - y_{\mathrm{OV}4})\cot \beta _{\mathrm{R}} + x_{\mathrm{OV}4},\quad y_{\mathrm{OV}5} = \dfrac {L_{\mathrm{P}}}{2} + L\sin (\gamma - \theta )\\[3pt] x_{\mathrm{OV}6} = (y_{\mathrm{OV}5} - y_{\mathrm{OV}5})\cot \theta + x_{\mathrm{OV}5},\quad y_{\mathrm{OV}6} = \dfrac {L_{\mathrm{P}}}{2} + L\sin (\gamma + \theta ) \end{array} \right . \end{align}

where $\gamma$ is the angle between the diagonal of the expanding vehicle and the vehicle’s side. ${L}=|\mathrm{AC}|/2$ .

If the trace formed while sliding along the left side ( $OV_1 - OV_2 - OV_3$ ) is positioned to the right of the trace formed while sliding along the right side ( $OV_4 - OV_5 - OV_6$ ), the enclosed area constitutes the collision zone, as illustrated by the shaded region in Figure 3. The remaining enclosed area is designated as the key zone. Similarly, key zones for the other seven situations can be determined.

In conclusion, the total minimum $\text{DBVO}$ is given by:

(11) \begin{equation} {d_{\mathrm{A}}} = \min \left ( {{d_{\mathrm{U}}},{d_{\mathrm{B}}},{d_{\mathrm{L}}}\text{ or }{d_{\mathrm{R}}}} \right ) \end{equation}

The calculations for $d_U$ , $d_L$ , and $d_R$ are relatively straightforward. Thus, computing the $d_B$ field prior to path optimization and utilizing it during path search for safety detection can significantly enhance the computational efficiency of path planning.

3.1. Design of parking path curve

In traditional path planning, abrupt changes in curvature occur between straight lines and arcs (transitioning from $0$ to $\frac {1}{R}$ ), which complicates the parking process. To address this issue, some researchers have employed clothoids to ensure curvature continuity in the optimal paths derived from combinations of straight lines and arcs, thereby enhancing the quality of parking paths. However, this approach increases the spatial requirements for parking, which poses significant safety challenges in narrow spaces [Reference Wu, Li, Gao and Yang34]. To overcome these challenges, a Clothoid-Aca-Clothoid (CAC) curve, characterized by curvature values of $0$ at both the beginning and end, is proposed as an alternative to circular arcs. This CAC curve is directly applied in path optimization to ensure safer parking in tiny spaces.

Figure 4 presents a schematic illustration of the CAC curve, where $\delta _{Cm}$ is the maximum central angle of the clothoid, and $\delta _{T}$ is the central angle of the CAC curve. As depicted in Figure 4 (a), when the center angle of CAC $\delta _{T}\gt 2\delta _{Cm}$ , the CAC curve comprises two clothoids and an arc segment. Referring to Figure 4(c), it is evident that the curvature of this curve remains continuous, peaking at $\frac {1}{R_{min}}$ . However, when $\delta _{T}\leq 2\delta _{Cm}$ , as illustrated in Figure 4 (b), the CAC curve simplifies to just two clothoids. In this case, the maximum curvature of the curve stands at $\sqrt {\delta _{T}{\sigma }}$ . The detailed design of CAC curve can be found in the appendix.

As demonstrated in Figure 4 (d), the CAC curve, upon undergoing mirroring, translation, and rotation, transforms into the essential components of the parking path. Here, there exist four distinct CAC paths that originate from the initial state $S_{0}=[x_{0}, y_{0}, \theta _{0}]$ and share a center angle $\delta _{T}$ . These paths can be unambiguously determined based on the rotation angle ( $\delta _R=\theta _{0}$ or $\theta _{0}+\pi$ ) and the mirror logic variable ( $f_{M}=1$ or $- 1$ ), which are determined according to the path function. The parameters of CAC path ( $x_{c}, y_{c}$ and $\theta _{c}$ ) can be derived as follows.

(12) \begin{align} \begin{cases} x_{\mathrm{c}} = x_{\mathrm{c0}} \cdot \cos \delta _{\mathrm{R}} - f_{\mathrm{M}} \cdot y_{\mathrm{c0}} \cdot \sin \delta _{\mathrm{R}} + x_0 \\[3pt] y_{\mathrm{c}} = x_{\mathrm{c0}} \cdot \sin \delta _{\mathrm{R}} + f_{\mathrm{M}} \cdot y_{\mathrm{c0}} \cdot \cos \delta _{\mathrm{R}} + y_0 \\[3pt] \theta _{\mathrm{c}} = f_{\mathrm{M}} \cdot \theta _{\mathrm{c0}} + \theta _0 \end{cases} \end{align}

where $x_{c0}, y_{c0}$ and $\theta _{c0}$ are the coordinates and heading angle of the original CAC curve, respectively. $f_{M}$ is a logical variable signifying whether a path needs to be mirrored, with a value of $-1$ indicating mirroring.

For simplicity in our discussion, the CAC curve obtained through the processes of mirroring, rotation, and translation is denoted as:

(13) \begin{equation} \mathrm{path\_CAC} \, = \, f_{\text{CAC}}(\mathbf{S}_0, \delta _{\mathrm{T}}, f_{\mathrm{M}}, \delta _{\mathrm{R}}) \end{equation}

Figure 4.

CAC for parking path.

Figure 4 Long description

The diagram illustrates a parking path using arcs and clothoids. It consists of four subfigures labeled (a) through (d). Subfigure (a) shows a scenario where the turning angle delta sub T is greater than twice the critical angle delta sub Cm, with arcs and clothoids depicted in blue and red respectively. Subfigure (b) illustrates a case where the turning angle delta sub T is less than or equal to twice the critical angle delta sub Cm. Subfigure (c) presents a graph of curvature versus distance, comparing the CAC (in magenta) and CC (in dashed black). Subfigure (d) shows the mirror, rotation, and translation of the parking path.

3.2. Design of parking path in intrusion scenarios

Due to the intrusion into the parking spot, the current vertical straight parking path presents a significant risk of collision. To address this, a four-phase parking path pattern is created, as illustrated in Figure 5. The entire parking path, extending from the starting state $S_{s}$ near the target parking spot to FPS $S_{e}$ , is segmented into four distinct phases: the transition path, maneuver path, entry path, and adjustment path. This path is composed of CAC curves and straight lines. The path can be determined using a reverse design approach, with the specific process detailed as follows.

Figure 5.

Four-phase parking path pattern.

Figure 5 Long description

The diagram illustrates the four-phase parking path pattern for automatic parking path planning. It shows a vehicle profile transitioning through various paths: transition path, maneuver path, entry path, and adjustment path. The vehicle starts at point S_s, moves along the transition path (green dashed line), then follows the maneuver path (red dashed line) to align with the parking spot. The entry path (blue dashed line) guides the vehicle into the parking spot, and the adjustment path (magenta dashed line) fine-tunes the vehicle's position within the spot. The diagram includes labeled points such as S_s, S_Mn+1, S_Mi, S_M1, S_L, and S_e, indicating key positions along the paths. The lines of actual parking spot are marked in black, and the coordinate system with axes X and Y is shown in red. The origin point O_P is marked where the X and Y axes intersect.

3.2.1. Adjustment path and entry path

The entry path is a sloping straight line, while the adjustment path is a CAC curve, as depicted in Figure 6. If the FPS of the vehicle is $S_{e}=[x_{e}, y_{e}, \theta _{e}]$ and the inclination angle of the entry path is $\theta _{L}$ , then the total center angle of the CAC curve for adjustment path is $\delta _{T} = |\theta _{L}-\theta _{e}|$ . Furthermore, if $\theta _{L}-\theta _{e}\lt 0$ , the CAC curve must be mirrored for both forward and reverse parking scenarios.

For reverse parking, the original CAC curve needs to be rotated by $\theta _{e}$ . Consequently, the adjustment path is given by:

(14) \begin{equation} \mathrm{path\_A} = f_{\text{CAC}}\left (\mathbf{S}_{\mathrm{e}}, \left | \theta _{\mathrm{L}} - \theta _{\mathrm{e}} \right |, \text{sign}(\theta _{\mathrm{L}} - \theta _{\mathrm{e}}), \theta _{\mathrm{e}}\right ) \end{equation}

For forward parking, the original CAC curve needs to be rotated by $\theta _{e}+\pi$ , thus:

(15) \begin{equation} \mathrm{path\_A} = f_{\text{CAC}}\left (\mathbf{S}_{\mathrm{e}}, \left | \theta _{\mathrm{L}} - \theta _{\mathrm{e}} \right |, \text{sign}(\theta _{\mathrm{L}} - \theta _{\mathrm{e}}), \theta _{\mathrm{e}} + \pi \right ) \end{equation}

After determining the state adjustment path, the lower node state $S_{L}$ of the entry path (Path_E) can be calculated. Hence, with the FPS known, the entry path and state adjustment path can be defined by the ordinate $y_{M1}$ of the upper node of the entry path and $\theta _{L}$ .

Figure 6.

Four-phase parking path pattern.

Figure 6 Long description

The diagram illustrates the four-phase parking path pattern for both reverse and forward parking. It consists of two sub-diagrams labeled (a) and (b). Sub-diagram (a) shows the reverse parking process, which includes an entry path and an adjustment path. Key points such as S_M1, S_L, and S_e are marked, with angles θ_L and θ_e indicated. The paths are represented by different colored lines: blue for the initial path, magenta for the adjustment path, and dashed lines for the transition between phases. Sub-diagram (b) depicts the forward parking process, showing a similar structure with key points S_M1, S_L, and S_e, and angles θ_L and θ_e. The paths are again represented by blue and magenta lines, indicating the different phases of the parking process.

3.2.2. Maneuver path

The maneuver path consists of CAC curves, with the number of curves determined by the required maneuvers, as shown in Figure 7. The vector representing the center angles of these CAC curves is denoted as $\boldsymbol{\delta }=[\delta _{1},\delta _{2},\cdots ,\delta _{n}]$ . As illustrated in Figure 7 (a) and (c), when the vehicle approaches from the left, the heading angle changes from $0$ to $\theta _{L}$ . Conversely, when approaching from the right, the heading angle changes from $\pi$ to $\theta _{L}$ , as shown in Figure 7 (b) and (d). Thus, the sum of the total center angles of all CAC curves in the maneuver path is

(16) \begin{align} \delta _{\mathrm{A}} = \sum _{i = 1}^{n} \delta _{i} = \begin{cases} \left | \theta _{\mathrm{L}} \right | & f_{\mathrm{L}} = 1 \\[3pt] \pi - \left | \theta _{\mathrm{L}} \right | & f_{\mathrm{L}} = -1 \end{cases} \end{align}

where $f_L$ is a logical variable indicating whether the vehicle approaches from the left. In state $S_{M1}$ , the heading angle $\theta _{M1}=\theta _L$ . The heading angles of other node states $S_{M2}\sim S_{Mn}$ are given by:

(17) \begin{equation} \begin{cases} \theta _{\mathrm{M}i} = \theta _{\mathrm{L}} - \sum _{j = 1}^{i - 1} \delta _{j}, \quad i = 2, \cdots , n \end{cases} \end{equation}

where $n$ is number of maneuvers.

As shown in Figure 7(a) and (b), in the situations of reverse parking, the first maneuver path ( $S_{M1}\sim S_{M2}$ ) when vehicles approach from the left is obtained by rotating the mirrored original CAC by $\theta _{M1}$ and then translating it to $(x_{M1}, y_{M1})$ . The second maneuver path ( $S_{A2}\sim S_{A3}$ ) is obtained by rotating the mirrored original CAC by $\theta _{A2}+\pi$ and then translating it to $(x_{M2}, y_{M2})$ . The third section follows the pattern of the first, and the fourth section is similar to the second one. When the vehicle approaches from the right, the rotation angle of the original CAC curve remains the same as when approaching from the left, but the CVC curves do not require mirroring. In summary, the $i$ -th ( $i = 1,\ldots , n$ ) section of the maneuver path for reverse parking is

(18) \begin{equation} \mathrm{path\_}M_{i} = f_{\text{CAC}}\left (\mathbf{S}_{M_{i}}, \delta _{i}, -f_{\mathrm{L}}, \theta _{M_{i}} + \left [ 1 + (\!-1)^{i} \right ] \cdot \frac {\pi }{2} \right ) \end{equation}

Similarly, the $i$ -th ( $i = 1,\ldots ,n$ ) section of the maneuver path for forward parking can be derived.

(19) \begin{equation} \mathrm{path\_}M_{i} = f_{\text{CAC}}\left (\mathbf{S}_{M_{i}}, \delta _{i}, f_{\mathrm{L}}, \theta _{M_{i}} + \left [ 1 + (\!-1)^{i + 1} \right ] \cdot \frac {\pi }{2} \right ) \end{equation}

Figure 7.

Design of maneuver path.

Figure 7 Long description

The diagram illustrates the design of maneuver paths for reverse and forward parking. It features two sub-diagrams labeled (a) and (b). Sub-diagram (a) shows the reverse parking path, with key points labeled as S_Mi, S_M1, S_M2, and S_Mn+1, and angles θ_Mi, θ_M1, θ_M2, and θ_Mn+1. The path starts from the left and right directions, converging at the center. Sub-diagram (b) depicts the forward parking path, with similar key points and angles. The vehicle direction is indicated by blue arrows, and the forward direction of the path is shown by red dashed arrows. The diagram highlights the geometric relationships and angles involved in parking maneuvers.

Figure 8.

Design of state path.

Figure 8 Long description

The diagram presents four techniques for automatic parking path planning. Geometric approaches use analytical expressions to quickly identify key trajectory points, with Han proposing a geometric collision-free path planning method. Clothoid, Bezier, and spline curves are used for path smoothing. Search methods discretize continuous space into grids to find a feasible parking path, with Dolgov et al. introducing the Hybrid A* algorithm with Reeds-Shepp curve, considering vehicle kinematics and using heuristic functions. Sampling methods generate sample points in continuous space to find a kinematically feasible and obstacle-avoiding point sequence, with Kuwata et al. assessing sampling-point feasibility via Dubins path length and Han et al. proposing the Bidirectional Rapidly Random Tree (RRT) algorithm. Numerical optimization methods formulate trajectory planning as optimal control problems, with algorithms like Particle Swarm Optimization and Genetic Algorithm used to solve path optimization problems. Wang et al. proposed a hierarchical algorithm combining nonlinear optimization and an improved RRT with Reeds-Shepp curves, while Yang et al. proposed a Sobol-RRT algorithm with Reeds-Shepp curves and optimal control. Li et al. presented a Kinodynamic-Informed-Bidirectional Rapidly-exploring Random Tree Star algorithm to reduce unnecessary exploration near concave obstacles and generate kinematically admissible paths.

In the following, we present algorithms for offline planning with lead times in the order of tens of seconds to several minutes, depending on the complexity of the scenario and the desired quality of the solutions, and for online planning with computation times in the order of fractions of a second up to very few seconds. The algorithm for offline planning is based on a global optimization approach and ensures high-quality solutions. The algorithm for online planning uses a sequential optimization procedure that provides flight paths with slightly decreasing quality.

3.2.3. Transition path

As shown in Figure 8, the transition path consists of two CAC curves and a horizontal straight line segment. Its purpose is to move the vehicle from the starting state ( $S_S$ ) to the starting state of the maneuver path ( $S_{M_{n + 1}}$ ). Based on the orientation of the vehicle in $S_S$ and the vertical distance between $S_S$ and $S_{M_{n+1}}$ , the transition path can be categorized into four scenarios.

To demonstrate the design process of the transition path, consider the first scenario depicted in Figure 8(a). If the vertical displacement of the CAC curve, initiated with a heading angle of $\theta _s$ and terminated at a heading angle of 0, precisely matches the value of $y_{M_{n+1}}-y_s$ , the transition path can be efficiently constructed using a single CAC curve in conjunction with one linear segment. This optimal configuration is illustrated by the red curve in 8(a). In this case, the starting heading angle $\theta _s$ is referred to as $\theta _{cr}$ :

(20) \begin{equation} \theta _{\mathrm{cr}} = H_{\mathrm{C}0}^{-1}(y_{\mathrm{M}n + 1} - y_{\mathrm{s}}) \end{equation}

where $H_{C0}^{- 1}(y)$ is the inverse function of $H_C(\delta _T, \delta _R, f_M)$ with $\delta _R = 0$ and $f_M = 1$ . $H_C(\delta _T, \delta _R, f_M)$ represents the vertical distance between the two endpoints of the original or mirrored CAC curve, with a center angle of $\delta _T$ rotated by $\delta _R$ . $H_{C0}(\delta _T)=H(\delta _T, 0, 1)$ . In this case, the CAC curve of the transition path is

(21) \begin{equation} \mathrm{path\_}T_{\mathrm{C}} = f_{\text{CAC}}(\mathbf{S}_{\mathrm{s}}, \theta _{\mathrm{s}}, - 1, \theta _{\mathrm{s}}) \end{equation}

When $\theta _s\neq \theta _{cr}$ , the transition path requires two CAC curves ( $S_s\rightarrow S_{T1}$ and $S_{T1}\rightarrow S_{T2}$ ). The key to determining these curves is to find the heading angle $\theta _{T1}$ in $S_{T1}$ . If $\theta _s\gt \theta _{cr}$ , the transition path will produce an overshoot as indicated by the blue dashed line in Figure 8(a), and $\theta _{T1}$ must satisfy:

(22) \begin{equation} H_{\mathrm{C}}\left ( \left | \theta _{\mathrm{T}1} - \theta _{\mathrm{s}} \right |, \theta _{\mathrm{s}}, - 1 \right ) - H_{\mathrm{C}}\left ( - \theta _{\mathrm{T}1}, 0, 1 \right ) = y_{\mathrm{M}n + 1} - y_{\mathrm{s}} \end{equation}

If $\theta _s\gt \theta _{cr}$ , the transition path does not overshoot, and $\theta _{T1}$ must satisfy the condition specified in Eq. (23). The corresponding transition path is represented by the solid green curve in Figure 8(a).

(23) \begin{equation} H_{\mathrm{C}}\left ( \left | \theta _{\mathrm{T}1} - \theta _{\mathrm{s}} \right |, \theta _{\mathrm{s}}, 1 \right ) + H_{\mathrm{C}}\left ( \theta _{\mathrm{T}1}, 0, 1 \right ) = y_{\mathrm{M}n + 1} - y_{\mathrm{s}} \end{equation}

Using Eq. (22) or Eq. (23), $\theta _{T1}$ can be determined. Consequently, the two CAC curves for the transition path are

(24) \begin{align} \left \{ \begin{array}{l} \mathrm{path\_}T_{\mathrm{C}1} = f_{\text{CAC}}\left ( \mathbf{S}_{\mathrm{s}}, \left | \theta _{\mathrm{T}1} - \theta _{\mathrm{s}} \right |, - 1, \theta _{\mathrm{s}} \right )\\[3pt] \mathrm{path\_}T_{\mathrm{C}2} = f_{\text{CAC}}\left ( \mathbf{S}_{\mathrm{T}1}, \theta _{\mathrm{T}1}, 1, \theta _{\mathrm{T}1} \right ) \end{array} \right . \end{align}

For the remaining three scenarios shown in Figure 8(b), (c), and (d), the CAC curves of the transition path can be derived through symmetry. These CAC curves and the horizontal line segment connecting $S_{T1}$ to $S_{M_{n+1}}$ together form the complete transition path (path_T). In summary, given the starting and FPS of the vehicle, the parking path designed using the presented method can be determined by $\delta$ , $\theta _L$ and $y_{M1}$ .

4.1. Framework for two-step parking path optimization method

To enhance the computational efficiency of the two-step parking path optimization method, a framework that integrates both online and offline calculations has been developed, as illustrated in Figure 9. The offline calculations encompass the basic parameters of the CAC curve, the construction of the CAC curve set and its associated functions, the $d_B$ field in an ideal parking scenario, and the critical SNPS required for each parking manner.

Figure 9.

Framework of the two-step parking path optimization method.

Figure 9 Long description

The flowchart illustrates the two-step parking path optimization method. It begins with offline processes, including determining the basic parameters of the CAC, constructing CAC sets and their related functions, and calculating the space required for various parking manners. The online process starts with inputting the parking allocation and checking for any intrusion. If there is intrusion, the dB field is updated based on the zoning method. The first step involves optimizing the FPS and inclination angle. If there is a solution, it checks if the SNPS is sufficient. If sufficient, the parking manner is determined, followed by the second step of optimizing the transition and maneuver path. The output is the parking path. If no solution is found or the SNPS is insufficient, the process ends.

The online calculation process begins after parking allocation. If the parking spot is invaded, the dB field is updated accordingly. Subsequently, the first step of optimization is performed. If a solution is found, the process advances to the second step. In the second step, the parking manner is determined based on the actual SNPS, followed by the optimization of the transition and maneuver paths. Ant colony algorithms [Reference Han, Zhou, Zhang, Wang, Liu, Peng and Guizani35] are employed to solve the optimization models.

4.2. Optimization of FPS and inclination angle of entry path

For safety, the minimum DBVO under bottom constraints ( $d_B$ ) is taken as the index. The first-step optimization is to maximize $d_B$ during the entry and adjustment phases. Accordingly, the objective function is defined as follows:

(25) \begin{equation} d_{\min 1} = \min \left [ d_{\mathrm{B}}(\mathrm{path\_E}, \mathrm{path\_A}) \right ] \end{equation}

The optimization parameters include the vehicle FPS and the inclination angle of the entry path. To simplify calculations, the state based on the vehicle’s geometric center is adopted. The parameter $y_{M1}$ is preset to determine the entry path for calculating the objective function.

(26) \begin{equation} \mathbf{X}_1 = [x_{\mathrm{OVe}}, y_{\mathrm{OVe}}, \theta _{\mathrm{e}}, \theta _{\mathrm{L}}] \end{equation}

where $(x_{OVe}, y_{OVe})$ are coordinates of vehicle’s geometric center in FPS.

The constraints are outlined as follows. The range for the geometric center of the vehicle in FPS is given by

(27) \begin{align} g_1^1(\mathbf{X}_1)\,: \left \{ \begin{array}{c} - 0.5 \leq x_{\mathrm{OVe}} \leq 0.5 \\[3pt] - 0.5 \leq y_{\mathrm{OVe}} \leq 0.5 \end{array} \right . \end{align}

This equation expands the allowable range for the geometric center, which may lead to the vehicle not being entirely within the parking spot; therefore, additional constraints are necessary:

(28) \begin{align} g_2^1(\mathbf{X}_1)\,: \left \{ \begin{array}{l} \max \left ( \mathbf{y}_{\mathrm{V}}(\theta _{\mathrm{e}}) + y_{\mathrm{OVe}} \right ) \leq \frac {L_P}{2} \\[3pt] d_{\min 1} \geq 0 \end{array} \right . \end{align}

The directions of the final heading angle and the inclination angle should be between the directions of the two side lines of the actual parking lot. When parking forward, the constraints are defined as

(29) \begin{align} g_3^1(\mathbf{X}_1)\,: \left \{ \begin{array}{l} -\max (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \leq \theta _{\mathrm{e}} \leq -\min (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \\[3pt] -\max (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \leq \theta _{\mathrm{L}} \leq -\min (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \end{array} \right . \end{align}

When parking in reverse, the conditions are

(30) \begin{align} g_3^1(\mathbf{X}_1)\,: \left \{ \begin{array}{l} \min (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \leq \theta _{\mathrm{e}} \leq \max (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \\[3pt] \min (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \leq \theta _{\mathrm{L}} \leq \max (\beta _{\mathrm{L}}, \beta _{\mathrm{R}}) \end{array} \right . \end{align}

Thus, the optimization model for both FPS and entry path inclination angle is expressed as

(31) \begin{align} \begin{array}{cc} \max & d_{\min 1} \\[3pt] \text{s.t.} & \begin{array}{cc} g_i^1(\mathbf{X}_1) & i = 1,2,3 \end{array} \end{array} \end{align}

For the convenience of discussion, the optimal FPS based on the rear axle center is denoted as $S_{eO}$ , and the optimal inclination angle of the entry path is denoted as $\theta _{LO}$ .

4.3. Optimization of the maneuver and transition path

The maneuver and transition paths are defined by parameter $\delta$ and $y_{M1}$ . Therefore, the second step of optimization focuses on finding a set of maneuver path parameters that maximize parking efficiency. The parking efficiency is influenced by both the length of the parking path and the parking manner.

4.3.1. Optimization model of path length

The optimization function is based on the total length of the maneuver and transition path ( $l_{TM}$ ), the calculation formula is

(32) \begin{equation} l_{\mathrm{TM}} = L_{\mathrm{C}}\left ( \left | \theta _{\mathrm{T}1} - \theta _{\mathrm{s}} \right | \right ) + L_{\mathrm{C}}\left ( \left | \theta _{\mathrm{T}1} \right | \right ) + \sum _{i = 1}^{n} L_{\mathrm{C}}\left ( \delta _{i} \right ) + \left | x_{\mathrm{T}2} - x_{\mathrm{M}n + 1} \right | \end{equation}

where $L_C(\delta )$ is the length of the CAC curve with a central angle of $\delta$ .

The optimization parameters include the ordinate of the starting point of the entry path and the center angle vector of the CAC curves of the maneuver path.

(33) \begin{equation} \mathbf{X}_2 = [y_{\mathrm{M}1}, \mathbf{\delta }] \end{equation}

The range of values for the ordinate $y_{M1}$ is defined as

(34) \begin{align} g_1^2(\mathbf{X}_2)\,: \left \{ \begin{array}{cc} y_{\mathrm{LO}} \leq y_{\mathrm{M1}} \leq W_{\mathrm{C}} + \frac {L_{\mathrm{P}}}{2} - l_{\mathrm{A}} - l_{\mathrm{F}} - d_{\mathrm{E}} & \text{Reverse} \\[3pt] y_{\mathrm{LO}} \leq y_{\mathrm{M1}} \leq W_{\mathrm{C}} + \frac {L_{\mathrm{P}}}{2} - l_{\mathrm{R}} - d_{\mathrm{E}} & \text{Forward} \end{array} \right . \end{align}

where $y_{LO}$ is the starting point ordinate of the adjustment path obtained from the first-step optimization. $l_F$ is length of vehicle front overhang.

The constraint for the central angle vector $\delta$ is given by

(35) \begin{align} g_2^2(\mathbf{X}_2)\,: \left \{ \begin{array}{l} \sum _{i = 1}^{n} \delta _i = \delta _{\mathrm{A}} \\[3pt] \begin{array}{cc} 0 \lt \delta _i \leq \delta _{\mathrm{A}} & i = 1,2, \cdots , n \end{array} \end{array} \right . \end{align}

The vehicle’s FPS and the entry path inclination angle are set based on the results obtained from the first step of optimization.

(36) \begin{align} g_3^2(\mathbf{X}_2)\,: \left \{ \begin{array}{l} \mathbf{S}_{\mathrm{e}} = \mathbf{S}_{\mathrm{eO}} \\[3pt] \theta _{\mathrm{L}} = \theta _{\mathrm{LO}} \end{array} \right . \end{align}

To ensure non-collision, the minimum DBVO from the starting state to state $S_{M1}$ must be at least 0. Thus

(37) \begin{equation} g_4^2(\mathbf{X}_2)\,:\,d_{\min 2} = \min \left [ d_{\mathrm{A}}(\mathrm{path\_T},\mathrm{path\_M}) \right ] \geq 0 \end{equation}

Therefore, the optimization model for the path length is expressed as

(38) \begin{equation} \begin{array}{cc} \min & l_{\mathrm{TM}} \\ \text{s.t.} & \begin{array}{cc} g_i^2(\mathbf{X}_2) & i = 1,2,3,4 \end{array} \end{array} \end{equation}

4.3.2. Optimization of parking manners

Parking manners are influenced by the parking direction and the number of maneuvers required. As shown in Figure 10, forward parking with one maneuver (F1) does not involve any reversing, while forward parking with two or three maneuvers (F2 or F3) necessitates reversing the vehicle direction twice. In contrast, reverse parking with one or two maneuvers (R1 or R2) requires reversing only once, while reverse parking with three maneuvers (R3) requires reversing three times. Each reversal requires deceleration and acceleration, which not only decreases parking efficiency but also reduces passenger comfort. Additionally, compared to R1 and F2, R2 and F3 each involve one additional directional change operation, making vehicle control more challenging. Therefore, to minimize the number of reversals and directional changes, the priority order of parking manners, assuming no constraints on SNPS, is as follows: F1, R1, R2, F2, F3, and R3.

Figure 10.

Maneuver path under different maneuvering times.

Figure 10 Long description

The diagram illustrates different maneuver paths for automatic parking path planning. It includes six sub-diagrams labeled F1, F2, F3, R1, R2, and R3, each depicting a specific maneuver path. The paths are color-coded: red for maneuver path, green for transition path, blue for vehicle direction, and dashed red for the forward direction of the path. Each sub-diagram shows the initial position (S_M1) and the final position (S_Mn+1) of the vehicle, with arrows indicating the direction of movement. The diagram highlights the use of geometric approaches, search methods, sampling methods, and numerical optimization techniques for path planning. It demonstrates how different methods are applied to ensure collision-free, kinematically feasible, and efficient parking paths.

In actual parking scenarios, SNPS is limited, so parking manners must be optimized within SNPS constraints. Thus, it is necessary to analyze the SNPS requirements for various parking manners in intrusion scenarios. A multi-objective optimization model is established with the aim of minimizing both corridor width and front space, as represented by Eq. (39). By solving the Pareto optimal solution for this model, the critical SNPS required for each parking manner can be determined. Combining this with the priority order allows for the identification of the optimal parking manner.

(39) \begin{align} \begin{array}{cc} \min & f_{\mathrm{ob}}(\mathbf{X}_2) = \left [ W_{\mathrm{C}}, S_{\mathrm{F}} \right ] \\[3pt] \text{s.t.} & \left \{ \begin{array}{l} \begin{array}{cc} g_i^2(\mathbf{X}_2) & i = 1,2,3,4 \end{array} \\[3pt] \mathbf{S}_{\mathrm{e}} = \mathbf{S}_{\mathrm{eO}}, \theta _{\mathrm{L}} = \theta _{\mathrm{LO}} \\[3pt] \mathbf{S}_{\mathrm{s}} = [x_{\mathrm{s}}, y_{\mathrm{s}}, 0] \end{array} \right . \end{array} \end{align}

where

(40) \begin{align} \left \{ \begin{array}{l} W_{\mathrm{C}} = \max (\mathbf{y}_{\mathrm{V}}) - \dfrac {L_{\mathrm{P}}}{2}\\[8pt] S_{\mathrm{F}} = \left \{ \begin{array}{cc} \max (\mathbf{x}_{\mathrm{V}}) - \dfrac {W_{\mathrm{P}}}{2} & \text{From left}\\[3pt] - \dfrac {W_{\mathrm{P}}}{2} - \min (\mathbf{x}_{\mathrm{V}}) & \text{From right} \end{array} \right .\\[20pt] x_{\mathrm{s}} = \left \{ \begin{array}{cc} 10 & \text{From left}\\[5pt] -10 & \text{From right} \end{array} \right .\\[3pt] y_{\mathrm{s}} = 5 \end{array} \right . \end{align}

where $(x_s, y_s)$ is the starting position.