# Automatic Parking Path Planning Based on Ant Colony Optimization and the Grid Method

Authors: Guo Liang Han
Journal: Journal of Sensors
 (2021)

---

## Abstract

This paper analyzes the path planning problem in the automatic parking process, and studies a path planning method for automatic parking. The grid method and the ant colony optimization are combined to find the shortest path from the parking start point to the end point. The grid method is used to model the parking environment to simulate the actual parking space of automatic parking; then this paper makes some improvements to the basic ant colony optimization, finds the destination by setting the ants’ movement rules in the grid, and finds the shortest path after N iterations; since the optimal path found is a polyline, it will increase the difficulty of controlling vehicle path tracking and affect the accuracy of vehicle path tracking. The bezier curve is used to generate a smooth path suitable for vehicle walking. Finally, through matlab simulation, the obstacles in the environment are simulated, and the parking trajectory is obtained. The results show that the path planning method proposed in this paper is feasible.


---

## Body

## 1. Introduction

The problem of automatic parking path planning is to find a better movement path from the parking start point to the end point in the known parking environment, so that the vehicle can reach the expected parking location safely and without collision during the movement.The current research status of automatic parking path planning at home and abroad is as follows:Piao CH, Zhang L, Lu S [1] and others combined the actual environment and used several arcs to form an automatic parking trajectory. It has strong adaptability to the environment and is similar to traditional parking trajectory generation methods. Compared with the method, the success rate and adaptability of this method are better; Jiang H, Guo KH, Zhang JW [2] analyzed and backed up the possibility of vehicle collision in the parking space, provided trajectory constraints for subsequent parking, realized parking path planning, and verified the correctness of the above strategy in actual simulations; Liang Z, Zheng G, Li J [3] studied the possible collisions of vehicles with obstacles in the parking space, using Ackerman geometric steering formula to generate parking arcs, and using Bezier curves to make the generated parking trajectory smoother, so as to get the final parking trajectory; Choi S, Boussard C, D’Andrea-Novel B, et al. and Vorobieva H, Glaser S, Minoiu Enache N, et al. [4, 5] calculated the parking trajectory of vehicle using a purely geometric method based on the geometry and maximum turning angle of the vehicle; Ge Y, Chen Y, Dai G [6] and others realized that when the vehicle is parked at the initial point, the vehicle can be in any position.Wu Bing, Qian Lijun and others of Hefei University of Technology analyzed the possible collision points of parallel parking process and calculated the minimum parking space required for parking through reverse path planning, replacing the initial points of traditional path planning with the initial parking area. The use of different data samples for the particle swarm optimization RBF neural network avoids the analysis of various constraint relations such as safety distance, so that the planned parking path can be better suitable for the parking process [7]. Li Hong and Guo Konghui of Hunan University analyzed the design requirements of the parking trajectory curve and integrated the characteristics of the B-spline curve, and proposed a method for automatic vertical parking trajectory planning based on the B-spline curve theory by optimizing the trajectory control points [8].Throughout the research on automatic parking trajectory planning at home and abroad, one-time global planning is mainly used to obtain a safe path from the parking start point to the end point, and some algorithms are used to optimize the path, such as genetic algorithm [9], B-spline curve algorithm and fuzzy algorithm, but these methods have problems such as large search space, complex algorithm, and low efficiency. The genetic algorithm’s ability to explore new spaces is limited, and it is easy to converge to a local optimal solution. The processing scale is small. When the problem is complex, the calculation time is very long. While using the B-spline curve for parking trajectory planning, although a B-spline curve can be drawn, it is necessary to repeatedly calculate the cubic polynomial of each coordinate component. The calculation amount is also quite large, and the drawing and fitting speed is extremely slow, which is difficult to satisfy actual needs. At the same time, the above method cannot effectively avoid obstacles when there are other obstacles in the parking environment (except for the already parked vehicles).Chen Xin and Lan Fengchong of South China University of Technology [10] used reinforcement learning to realize automatic parking, and proposed a staged training method based on curriculum learning for parking problems, which accelerated the algorithm convergence, and the planning success rate reached 90.6%; Wang Qiming and Zong Gaoqiang of the University of Shanghai for Science and Technology [11] proposed a multi-stage parking path planning for the narrow parallel parking path and the discontinuity of the parking trajectory. The final parking attitude angle is the smallest as the index for finding the optimal solution; Song Jie of Shanghai University of Engineering and Technology [12] combined panoramic vision and lidar to improve the accuracy of parking space detection when there is no nearby vehicle or parking space marking line, and proposed a parking path planning method based on B-spline theory.Ren-Fang Zhou, et al. [13], aiming at the error of the tracking algorithm in the automatic parking system, proposed a secondary path plan, updated the parking path, and divided the path into 24 Segment model, using traversal strategy to select path mode, using secondary planning algorithm to fine-tune the path model to achieve the best effect. Jiangbo Meng, et al. [14] have proposed a parking path tracking algorithm combining fuzzy control and Kalman filter for the low accuracy of automatic parking path tracking caused by sensor noise, and the actual driving is established based on the vehicle kinematics equations. The deviation model of the path and the reference path, the Kalman filter is used to reduce the measurement noise in the vehicle position and heading angle measurement data, and the simulation model is established through Matlab/Simulink to verify the effectiveness of the proposed algorithm. Hao Ye, et al. [15] proposed a linear model predictive control path tracking control strategy with softening constraints on how to improve the accuracy of automatic parking path tracking control. Establish a linear time-varying prediction model of the vehicle, predict the future state of the vehicle, add a relaxation factor in the optimization process, calculate the control increment of each cycle through quadratic programming, roll optimization and feedback correction, and correct various deviations in the control process in time. Ti-chun Wang, et al. [16] discussed the AGV Navigation Analysis method based on multi-sensor data fusion.In addition, the above-mentioned methods only start from a fixed parking starting point, and then complete the parking route planning and the entire parking process. However, in real life, the starting position is found by the driver. Since each driver’s driving skills and driving habits are different, it is difficult to ensure that each driver can drive to the ideal starting point during normal parking position. If the driver is strictly required to park the car at the specified starting position before parking, it will increase the difficulty of driving for the driver, and the driver will spend a lot of energy in determining the starting position, so that it will not be convenient for the driver to park in parallel into the parking space.In view of the shortcomings of the above-mentioned automatic parking path, this paper conducts a new research on the automatic parking algorithm, and proposes a more adaptable solution, which combines the ant colony optimization with the grid method to find the shortest path from a starting point to the end point, and the bezier curve function is added to obtain a trajectory that allows the vehicle to park, which can not only effectively increase the range for the driver to find the starting parking position, but also avoid obstacles when other obstacles are involved in the parking environment, which increases the adaptability of automatic parking to the environment.


## 2. Environmental Description and Modeling

A reasonable representation of the environment is conducive to the planning of the best path during the parking process. The grid method is a representation method of the spatial geographic environment. It divides the geographic space into regular grids, which have the characteristics of uniform size and binary value. The size of the grid is the same, and the selection of the grid size affects the effect of path planning. Smaller grids increase storage space and computing power. At the same time, interference signals will also increase. Larger grids make environmental planning unclear, and the results are not credible. Setting the grid size as the basic step length of the vehicle is a feasible solution; Binary means that each grid has only two values with different values, free grid and obstacle grid, depending on whether there are obstacles in the grid. The raster is stored in the form of a raster array, where there is an obstacle 1 to indicate, and there is no obstacle 0 to indicate. During the movement of the vehicle, the grid remains stationary, and the movement of the vehicle is converted into the movement of the vehicle from one grid to another.The establishment of the environmental model is a very important part of the automatic parking path planning of vehicles. The actual parking environment of the vehicle is an actual physical space, but the space processed by the path planning algorithm is an abstract representation of the environment.In this paper, the grid method [17] is used to establish an environment model to simulate the actual parking space of automatic parking. In the application of the grid method, the grid method uses the basic element as the minimum grid granularity to divide the map into grids. The basic element is located in the free area and the value is 0, and the obstacle area or the obstacle-containing area is 1; Then the model recursively divides the environment into 4 equal-sized sub-regions until the basic units contained in each region are all 0 s or all 1 s.For the automatic parking environment, a limited number of vehicles parked can be regarded as obstacles. These obstacles are easy to map due to their coordinate positions and can be regarded as known environmental information. After ergodic learning the two-dimensional space of automatic parking, a grid map can be established.Ignoring the information in the height direction of the vehicle, the two-dimensional space where the vehicle is parked is recorded as LOL, and a limited number of vehicles are parked in its internal parking space, which can be regarded as an obstacle. For automatic parking in a static environment, the position and size of obstacles can be detected, and they will not change during the movement of the vehicle. In LOL, the lower left corner is the coordinate origin, the direction parallel to the car body is the X axis, and the direction perpendicular to the car body is the Y axis to establish a system rectangular coordinate systemΣ. All the following diagrams are created in this way, and will not be repeated. The maximum value of LOL in the x-axis and y-axis directions is Xmax and Ymax, respectively.If there are no obstacles in a certain grid size range, the grid is called a free grid and expressed in white; otherwise, it is called an obstacle grid and expressed in gray. WhenXmax= Ymax=17, the grid model of the vehicle parking space is shown in Figure 1. In the figure, the side length of each grid is 0.5 m, and the ants can only move from one grid center point to another grid center point at a time during the ant’s marching process, which stipulates that they cannot walk diagonally.Figure 1
The grid figure of vehicle parking environment.In Figure1, the lower two black areas represent vehicles that have parked in the parking spaces, and the blank area between the two vehicles is the empty parking space to be parked. According to the relevant vehicle size information, the length of the vehicle is approximately 2.5 times the width of the vehicle. Therefore, for the convenience of description, in the grid environment, the size of the vehicle occupies 10 grids, and it is specified that the vehicle close to the lower left origin is car A, and the vehicle on the right is car B. Here we specify the grid number occupied by each vehicle is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 from the upper left corner to the right.In addition, we introduced the serial number method to identify all grids:As shown in Figure1, starting from the upper left corner of the grid array, each grid is numbered in the order from left to right and top to bottom, and the sequence number n is from 1 to 289 in turn. The grid identified by the serial number method is recorded asGn, for example, the grid with serial number 1 is recorded as G1.For grid environments of other scales, the relationship between grid number and grid coordinates is the same as this type.In order to verify the feasibility of the ant colony optimization in automatic parking path planning, in this study, the starting positionG209of the vehicle path planning is the ant nest and the target position G266is the food source. Set the 10th grid in the lower right corner of the 10 grids occupied by the vehicle as the research point of the vehicle so that it coincides with G209, and the trajectory of the vehicle during operation is the trajectory of the vehicle’s automatic parking. In the grid environment of 17×17, during the parking process, from the starting point G209 to G266, if no obstacles are detected in the forward direction of the parking, the two squares on the top right of the fifth square of car A, the grid G227 and G228 are set as a safe area, and the vehicle path cannot pass through this square. At this time, the first two steps in the ant’s pathfinding can only be two squares in the direction parallel to the vehicle body, and then go down in the direction closer to the destination. In such a grid environment, with the restriction of the safe area, not only can the vehicle to be parked avoid collision with car A, but at the same time, when the Bezier function is used to obtain the parking trajectory at the end, it can also ensure that the radius of the curve is larger than the minimum turning radius of the vehicle.In the same way, if an obstacle is detected in the forward direction of the parking at the beginning of parking, only set squareG227as the safe area, and the surrounding obstacle square is set as a safe area, so that the vehicle can avoid collision with car A and obstacles during parking, and also ensure that the final Bezier curved path meets the parking conditions.The proof is as follows:According to the theory of calculus, the curvature of the curve is:(1)k=dφds=y/1+y′2dx1+y′2dx=y′′1+y′23/2Then the radius of curvature is:(2)ρ=1kAccording to the quadratic Bezier curve:(3)Qt=∑t=02Bi,2t⋅Pi=P2−2P1+P0t2+2P1−P0⋅t+P0and so,(4)dydt=Y2−2Y1+Y0t+Y1−Y0dxdt=X2−2X1+X0t+X1−X0Therefore, the radius of curvature is:(5)ρ=dx/dt2+dy/dt23/2dy/dt′⋅dx/dt−dy/dt⋅dx/dt′(1)
In the case of obstacles, because the vehicle has to avoid obstacles, the first three points of its forward path are: starting point A, intermediate pointB1, and intermediate point B2. The coordinates are(6)AX0,Y0=4.5,4.5B1X1,Y1=6.5,4.5B2X2,Y2=6.5,2.5Putting the above coordinates into the curvature radius formula, we get(7)dydt=2.5−2×4.5+4.5t+4.5−4.5=−2tdxdt=6.5−2×6.5+4.5t+6.5−4.5=−2t+2Then, We can get(8)ρ=2−2t2+−2t23/2−2×2−2t+2t×−2=8t2+4−8t3/2−4,t∈0,1When t takes 0 or 1,ρ=2,that is, the curve composed of the first three points of the bezier curve is equivalent to a quarter circle, and the bezier curve in the presence of obstacles is a curve composed of more than three control points. Therefore, the curvature of the bezier curve is greater than ρ=2.In addition, according to the calculation formula of the vehicle’s minimum turning radius [14]:(9)R=Lsinθmax+b−M2Among them: L is the wheelbase,θmax is the maximum turning angle of the outer wheel of the steering wheel, b is the front track, and M is the center distance of the main pin.After consulting the relevant vehicle size, for the convenience of calculation, this article reduces the vehicle ratio to a ratio of vehicle length to vehicle width of 2.5, that is, the vehicle length is 2.5 m and the vehicle width is 1 m. In this way, we can get the corresponding wheelbase L =1.42 m, front wheelbase b =0.81 m, and kingpin center distance M =0.65 m,θmax=40°.It can be obtained from the above data that the minimum turning radius of the vehicle is R =1.96 m.It can be seen from the above calculation thatρis greater than the minimum turning radius R =1.96.Therefore, in the presence of obstacles, the vehicle can park along the path.(2)
In the absence of obstacles, since the safe area is two square spaces, the first three points of the path of the vehicle to be parked are the starting point A, the middle pointB1, and the middle point B2(10)AX0,Y0=4.5,4.5B1X1,Y1=7.5,4.5B2X2,Y2=7.5,1.5In the same way, it can be known from the formula of the radius of curvature of the Bezier function that the radius of curvature at this time must be greater than the radius when there are obstacles.In this way, while the grid environment is established and the safe area is set, it is ensured that the radius of curvature of the parking path is greater than the minimum turning radius of the vehicle.


## 3. Description and Definition of Parking Path Planning Problem

Problem Description: The path planning of automatic parking is to find a suitable parking trajectory from the parking start point to the parking end point, so that the vehicle can be parked into the empty parking space smoothly. Since this article uses the Bezier function to curve, it can fit any number of control points, and the curvature is relatively small. Therefore, the mathematical description of ant colony optimization applied to automatic parking can be find a path from the starting point A through the intermediate pointB=b1,b2,⋯⋯bn to the ending point C, so that the objective function:(11)D=∑1ndA,b1+db2,b3+⋯+dbn−2,bn−1+dbn,CGet the minimum value, whichdA,b1,dbn−2,bn−1,dbn,C are all equal to 1, when each ant is walking, it cannot walk along the diagonal. This can ensure that the middle point will not be far away from the target point during the path finding process, making the bezier curve fitting more suitable for parking.In order to simulate the foraging behavior of the actual ant colony, in this study, the starting position of the vehicle path planningG209 is the ant nest, and the target position G266 is the food source. If the starting point select G208, then the vehicle can also be parked, so there is no need to search for the starting point artificially.G209 is selected in the 10 grids above the A car and a row apart from the A car. The vehicle parking path planning based on the ant colony optimization is actually through the interaction and cooperation between the ants in the ant colony to avoid the front and rear cars of the parking space and finally find an optimal path from the ant nest to the food source. For the convenience of the following description, the variables used here are defined as follows:n is the total number of grids, in the environment studied in this paper, n =289. That is, when the vehicle perceives the entire parking environment, it is modeled as a 17 × 17 grid environment. For a more refined grid environment, further research is needed.K is the number of iterations, that is, how many waves of ants are dispatched in total; M is the number of ants (the number of ants in each wave), in this algorithm, m =50.S represents the starting point, E represents the end point, Alpha represents the parameter that characterizes the importance of the pheromone, Beta represents the parameter that characterizes the importance of the heuristic factor, Rho represents the pheromone evaporation coefficient, Q represents the pheromone increase intensity coefficient, and Tau represents the output dynamics Corrected pheromone.dij is a matrix that records the distance between all grids. dijrepresents the distance between Giand Gj, (the distance between the geometric center points of the two grids is defined as the distance between the grids), and there are:(12)dij=ai−aj2+bi−bj2Among them,aiand ajare the abscissas of grids Gi and Gj, respectively, and bi andbjare the ordinates of grids Gi and Gj, respectively.In the basic ant colony optimization, the ants decide the next transfer direction based on the amount of pheromone on each path and the heuristic information on the path. The state transition rule used is called the random proportional rule, which gives the probability that the ant k at the node i chooses the node j as the transition direction:(13)Pijkt=τijαtηijβt∑s∈allowedkτisαtηisβtj∈allowedk0otherwiseWhere:ηijrepresents the visibility in the direction i, j.τijt represents the amount of residual information on the line segment ij at time t.α represents the relative importance of pheromones (α≥0).β represents the relative importance of visibility (β≥0).


## 4. Automatic Parking Path Planning Based on Ant Colony Optimization and Grid Method

The ant colony optimization is a probabilistic algorithm used to find the optimal path. It was proposed by Marco Dorigo in 1992. It was inspired by ants finding the path when looking for food. It is a bionic algorithm, in the process of foraging, ants can always find the optimal path. The behavior of a single ant when looking for food is relatively simple, but a group of ants show intelligent characteristics when looking for food. The ants can communicate with each other and leave signals on the route they pass. The ants will choose the path with strong signal to walk through. For a period of time, the ants will walk along the optimal path, forming positive feedback. Suppose there are two paths from the starting point to the destination. At the beginning, there are as many ants on the two paths, and the ants on the short-distance path go back and forth faster. In the same time, there are more ants going back and forth, leaving more signals, attracting more ants to leave more signals, and form positive feedback. As time goes by, more and more ants will take the short path. This characteristic of ants benefits from their simple behavior. This behavior gives it positive feedback and diversity. Diversity is the ability to find paths. Positive feedback allows information to be preserved to optimize paths.


### 4.1. Improvements to Be Made when Applying the Basic Ant Colony Optimization to Vehicle Parking Path Planning

The mathematical model of the basic ant colony optimization successfully solved the TSP problem [18]. Before applying the basic ant colony optimization to the field of vehicle parking path planning, it is necessary to combine the characteristics of the vehicle parking path planning problem to make some improvements to the basic ant colony optimization.It is assumed here that the environment of the ants search path is a 17 × 17 grid environment.


#### 4.1.1. Limit the Grid Range Allowed to Be Selected in the Next Step when the Ants Travel to the Current Grid

In the basic ant colony optimization, the nodes that the ant allows to select in the next step include all the nodes that have not been visited. However, in the grid environment described in this article, in order to meet the needs of the problem of vehicle parking path planning, the next step allowed by the ants traveling to the current grid is limited to the unvisited free grids in the 8 adjacent directions. That is, the grid that the ant allows to select in the next step must meet the following three conditions at the same time: ① The adjacent grid of the current grid, ② the grid that has not been visited by this ant, ③ the free grid. Making such a restriction can ensure that the ants quickly bypass the barrier grid and find a continuous parking path that does not pass through repeated grids.


#### 4.1.2. Use the “Roulette” Method to Select the Next Grid according to the Transition Probability

When ants transfer from the current grid to the next grid, if the one with the highest transition probability is always selected from the grids allowed to be selected, the algorithm will lose randomness and fall into a local optimal solution. In order to solve this problem, this article uses the “roulette” method to select the next grid. The transition probability of the grid that the ant is allowed to select in the next step is used for cumulative probability statistics, and then a random number between 0 and 1 is generated. In which cumulative probability the random number falls into, the grid corresponding to the cumulative probability is selected.


### 4.2. Algorithm Flow Chart

According to the ant colony optimization, the algorithm flow chart is now drawn in Figure2:Figure 2
Ant colony optimization flow chart.


### 4.3. Algorithm Implementation Steps

In a grid environment where the total number of grids is n = 289, the steps of ant colony optimization to realize vehicle path planning are as follows:Step1: State initialization.Set the starting grid of path planning toG209and the target grid toG266. Set the maximum number of iterations K = 100. Set the initial pheromone matrix Tau, pheromone volatilization coefficient Rho, and heuristic information Eta. Place M ants at the starting point G209of path planning, and add G209to the taboo table tabuk (k = 1, 2, 3,..., m). The crawling route length PLkm is set to 0.Step2: An ant moves to the next grid [19].If the current grid is not the target grid, all grids that can be walked are calculated. First calculate the probability of the ant transferring to each grid that is allowed to be selected, and then use roulette to select the next grid. Assuming that the grid that the ant allows to choose in the next step isga,gb,gc, the transition probability calculated according to formula (13) is ζ1,ζ2,ζ3(0≤ζ1,ζ2,ζ3≤1), and ζ1+ζ2+ζ3=1, then generate a random number rand between 0 and 1. The implementation process of roulette is as follows: First, make cumulative probability statistics on the transition probability, and getζ1ζ1+ζ2ζ1+ζ2+ζ3=ζ1ζ1+ζ21, then generate a random number rand between 0 and 1.If rand is between 0 and ζ1, the ant chooses grid Gafor transfer; if rand is between ζ1and ζ1+ζ2, then the ant chooses gridGb for transfer: if rand is between ζ1+ζ2and 1, then the ant chooses gridGc to transfer.When the current grid where an ant is located is already the target grid, the ant is killed, that is, the ant has completed the path finding task in this cycle.Step3: Repeat Step2 until all ants that are not dead have completed the subsequent grid selection.Step4: Status update and record.When the path selection is completed, the status is updated and recorded. The path length increases, and the path length of each ant in each generation is recorded.Step5: Repeat Step2, Step3 and Step4 until all ants are transferred to the target grid.Step6: Pheromone update.When all the ants have completed the subsequent grid selection, follow the formula (14) to update the pheromone. The pheromone on the path gradually volatilizes over time, and 1-p represents the degree of volatilization of the pheromone.(14)τijn+1=1−ρτijn+ρΔτijkThere are many different ways to takeΔτijk in the formula. On the premise of ensuring the performance of the algorithm, in order to reduce the computational cost and improve the speed of the algorithm, this paper takes Δτijkas a constant and τmin<Δτijk<τmax.Whenτijn+1<τmin, set τijn+1=τmin; when τijn+1>τmax, set τijn+1=τmax. Among them, τminis the set pheromone minimum value, and τmaxis the set pheromone maximum value.Step7: Output the shortest path graphics.


## 4.1. Improvements to Be Made when Applying the Basic Ant Colony Optimization to Vehicle Parking Path Planning

The mathematical model of the basic ant colony optimization successfully solved the TSP problem [18]. Before applying the basic ant colony optimization to the field of vehicle parking path planning, it is necessary to combine the characteristics of the vehicle parking path planning problem to make some improvements to the basic ant colony optimization.It is assumed here that the environment of the ants search path is a 17 × 17 grid environment.


### 4.1.1. Limit the Grid Range Allowed to Be Selected in the Next Step when the Ants Travel to the Current Grid

In the basic ant colony optimization, the nodes that the ant allows to select in the next step include all the nodes that have not been visited. However, in the grid environment described in this article, in order to meet the needs of the problem of vehicle parking path planning, the next step allowed by the ants traveling to the current grid is limited to the unvisited free grids in the 8 adjacent directions. That is, the grid that the ant allows to select in the next step must meet the following three conditions at the same time: ① The adjacent grid of the current grid, ② the grid that has not been visited by this ant, ③ the free grid. Making such a restriction can ensure that the ants quickly bypass the barrier grid and find a continuous parking path that does not pass through repeated grids.


### 4.1.2. Use the “Roulette” Method to Select the Next Grid according to the Transition Probability

When ants transfer from the current grid to the next grid, if the one with the highest transition probability is always selected from the grids allowed to be selected, the algorithm will lose randomness and fall into a local optimal solution. In order to solve this problem, this article uses the “roulette” method to select the next grid. The transition probability of the grid that the ant is allowed to select in the next step is used for cumulative probability statistics, and then a random number between 0 and 1 is generated. In which cumulative probability the random number falls into, the grid corresponding to the cumulative probability is selected.


## 4.1.1. Limit the Grid Range Allowed to Be Selected in the Next Step when the Ants Travel to the Current Grid

In the basic ant colony optimization, the nodes that the ant allows to select in the next step include all the nodes that have not been visited. However, in the grid environment described in this article, in order to meet the needs of the problem of vehicle parking path planning, the next step allowed by the ants traveling to the current grid is limited to the unvisited free grids in the 8 adjacent directions. That is, the grid that the ant allows to select in the next step must meet the following three conditions at the same time: ① The adjacent grid of the current grid, ② the grid that has not been visited by this ant, ③ the free grid. Making such a restriction can ensure that the ants quickly bypass the barrier grid and find a continuous parking path that does not pass through repeated grids.


## 4.1.2. Use the “Roulette” Method to Select the Next Grid according to the Transition Probability

When ants transfer from the current grid to the next grid, if the one with the highest transition probability is always selected from the grids allowed to be selected, the algorithm will lose randomness and fall into a local optimal solution. In order to solve this problem, this article uses the “roulette” method to select the next grid. The transition probability of the grid that the ant is allowed to select in the next step is used for cumulative probability statistics, and then a random number between 0 and 1 is generated. In which cumulative probability the random number falls into, the grid corresponding to the cumulative probability is selected.


## 4.2. Algorithm Flow Chart

According to the ant colony optimization, the algorithm flow chart is now drawn in Figure2:Figure 2
Ant colony optimization flow chart.


## 4.3. Algorithm Implementation Steps

In a grid environment where the total number of grids is n = 289, the steps of ant colony optimization to realize vehicle path planning are as follows:Step1: State initialization.Set the starting grid of path planning toG209and the target grid toG266. Set the maximum number of iterations K = 100. Set the initial pheromone matrix Tau, pheromone volatilization coefficient Rho, and heuristic information Eta. Place M ants at the starting point G209of path planning, and add G209to the taboo table tabuk (k = 1, 2, 3,..., m). The crawling route length PLkm is set to 0.Step2: An ant moves to the next grid [19].If the current grid is not the target grid, all grids that can be walked are calculated. First calculate the probability of the ant transferring to each grid that is allowed to be selected, and then use roulette to select the next grid. Assuming that the grid that the ant allows to choose in the next step isga,gb,gc, the transition probability calculated according to formula (13) is ζ1,ζ2,ζ3(0≤ζ1,ζ2,ζ3≤1), and ζ1+ζ2+ζ3=1, then generate a random number rand between 0 and 1. The implementation process of roulette is as follows: First, make cumulative probability statistics on the transition probability, and getζ1ζ1+ζ2ζ1+ζ2+ζ3=ζ1ζ1+ζ21, then generate a random number rand between 0 and 1.If rand is between 0 and ζ1, the ant chooses grid Gafor transfer; if rand is between ζ1and ζ1+ζ2, then the ant chooses gridGb for transfer: if rand is between ζ1+ζ2and 1, then the ant chooses gridGc to transfer.When the current grid where an ant is located is already the target grid, the ant is killed, that is, the ant has completed the path finding task in this cycle.Step3: Repeat Step2 until all ants that are not dead have completed the subsequent grid selection.Step4: Status update and record.When the path selection is completed, the status is updated and recorded. The path length increases, and the path length of each ant in each generation is recorded.Step5: Repeat Step2, Step3 and Step4 until all ants are transferred to the target grid.Step6: Pheromone update.When all the ants have completed the subsequent grid selection, follow the formula (14) to update the pheromone. The pheromone on the path gradually volatilizes over time, and 1-p represents the degree of volatilization of the pheromone.(14)τijn+1=1−ρτijn+ρΔτijkThere are many different ways to takeΔτijk in the formula. On the premise of ensuring the performance of the algorithm, in order to reduce the computational cost and improve the speed of the algorithm, this paper takes Δτijkas a constant and τmin<Δτijk<τmax.Whenτijn+1<τmin, set τijn+1=τmin; when τijn+1>τmax, set τijn+1=τmax. Among them, τminis the set pheromone minimum value, and τmaxis the set pheromone maximum value.Step7: Output the shortest path graphics.


## 5. Smooth Parking Path Generation

The grid method is used to establish the environment model, and then the ant colony optimization and its improved algorithm are used to plan the vehicle parking path. The planned path is obviously a polyline path. The realization of the polyline path is very simple, and the path length is generally short, but the vehicle needs to stop frequently to change the direction of movement, which is simply impossible to achieve.As shown in Figure3, when the vehicle moves from point A to point B, it needs to stop to change the direction of movement. Due to the limitation of the driving mechanism of the mobile vehicle, it is difficult for the vehicle to accurately change the direction of movement from the AB direction to the BC direction at point B. When the vehicle moves to point C, it also needs to stop to change the direction of movement, and so repeatedly. If the polyline path is formed by connecting many straight lines, it will increase the difficulty of controlling the vehicle path tracking and seriously affect the accuracy of the vehicle path tracking.Figure 3
Wayfinding figure of ant colony optimization.This requires the vehicle to have a higher ability to generate a smooth path, and the generated path must meet the dynamic characteristics of the vehicle. If the ability of the vehicle to generate a smooth path is improved, the application flexibility of the vehicle will be effectively increased, and the accuracy of vehicle path tracking will be improved.


### 5.1. Bezier Curve and Smooth Path

Because of the smoothness and continuity of the Bezier curve, this paper applies it to the smoothing of the vehicle parking path. The popular meaning of smoothness means that there are not many inflection points of the curve. For a plane curve, the conditions for relative smoothness are: second-order geometric continuity, no redundant inflection points and singular points, and small changes in the curvature of the curve. Continuity refers to the smooth connection between the various curve segments forming a complex curve. These properties of the Bezier curve make it meet the dynamic characteristics of the vehicle, and it is very suitable as the vehicle’s walking path. Therefore, it is only necessary to fit the polyline path to a Bezier curve to generate a smooth path suitable for the vehicle to walk. The definition of Bezier curve [20] is: Given the position vector pii=0,1,⋯,n of n + 1 points in space, the interpolation formula of the coordinates of each point on the Bezier curve is as follows:(15)pt=∑i=0nPiBi,nt,t∈0,1Among them,Pi only constitutes the characteristic polygon of the Bezier curve, and Bi,nt is the Bernstein basis function of degree n. The convention is:(16)n=0,B0,0t=1n=1,B0,1t=1−t,B1,1t=tn=2,B0,2t=1−t2,B1,2t=2t1−t,B2,2t=t2n=3,B0,3t=1−t3,B1,3t=3t1−t2,B2,3t=3t21−t,B3,3t=t3In this paper, the final method of generating the smooth path of the vehicle curve is: first, on the basis of the polyline path of the vehicle, successively generate a three-dimensional Bezier curve, and then smoothly connect these Bezier curves to obtain a smooth Bezier curve suitable for vehicle walking.


## 5.1. Bezier Curve and Smooth Path

Because of the smoothness and continuity of the Bezier curve, this paper applies it to the smoothing of the vehicle parking path. The popular meaning of smoothness means that there are not many inflection points of the curve. For a plane curve, the conditions for relative smoothness are: second-order geometric continuity, no redundant inflection points and singular points, and small changes in the curvature of the curve. Continuity refers to the smooth connection between the various curve segments forming a complex curve. These properties of the Bezier curve make it meet the dynamic characteristics of the vehicle, and it is very suitable as the vehicle’s walking path. Therefore, it is only necessary to fit the polyline path to a Bezier curve to generate a smooth path suitable for the vehicle to walk. The definition of Bezier curve [20] is: Given the position vector pii=0,1,⋯,n of n + 1 points in space, the interpolation formula of the coordinates of each point on the Bezier curve is as follows:(15)pt=∑i=0nPiBi,nt,t∈0,1Among them,Pi only constitutes the characteristic polygon of the Bezier curve, and Bi,nt is the Bernstein basis function of degree n. The convention is:(16)n=0,B0,0t=1n=1,B0,1t=1−t,B1,1t=tn=2,B0,2t=1−t2,B1,2t=2t1−t,B2,2t=t2n=3,B0,3t=1−t3,B1,3t=3t1−t2,B2,3t=3t21−t,B3,3t=t3In this paper, the final method of generating the smooth path of the vehicle curve is: first, on the basis of the polyline path of the vehicle, successively generate a three-dimensional Bezier curve, and then smoothly connect these Bezier curves to obtain a smooth Bezier curve suitable for vehicle walking.


## 6. Simulation Results and Analysis

The author combined the ant colony optimization with grid method and Bezier function through matlab [21], and performed a lot of simulations. In all the following figures, the establishment of the x-axis and y-axis is as described above. Among them, the blue line (thick line) in Figures 4–6 represents the polyline path obtained by the combination of ant colony optimization and grid method; the red curve (thin line) represents the optimization of the polyline into the travel curve of the vehicle through the bezier function.Figure 4
Smooth figure of automatic parking path.Figure 5
The figure of automatic parking path with obstacle.Figure 6
The figure of automatic parking path with left starting point.Figure4 shows a situation where there are no obstacles in the parking environment. After verification (see Figure 7), the path is a trajectory that can be parked.Figure 7
The figure of automatic parking path. Without obstacle comparing with the minimum radius.Figure5 is a situation where there are obstacles in the parking environment. Its trajectory is somewhat different from that of obstacles. After verification (see Figures 8 and 9), it can also make vehicles park. It also proves the adaptability and superiority of the ant colony optimization when there are roadblocks or other obstacles in the parking environment.Figure 8
The figure of automatic parking path with obstacle comparing with the minimum radius.Figure 9
The figure of automatic parking path with obstacle comparing with the minimum radius.Figure6 shows the situation where the parking starting point is leftward. When the driver parks the car near the best parking point, the vehicle can also be automatically parked, which proves the superiority of the ant colony optimization in finding the starting point of parking.According to the calculation formula of the vehicle’s minimum turning radius [22] R=L/sinθmax+b−M/2. Among them: L is the wheelbase,θmaxis the maximum turning angle of the outer wheel of the steering wheel, b is the front wheelbase, and M is the center distance of the main pin.After consulting the relevant vehicle dimensions, for the convenience of calculation, this article reduces the vehicle ratio to 2.5 m in length and 1 m in width. In this way, the corresponding wheelbase L =1.42 m, front wheelbase b =0.81 m, kingpin center distance M =0.65 m,θmax=40°.It can be obtained from the above data that the minimum turning radius of the vehicle is R = 1.98 m.Figures8 and 9 show the verification of the parking trajectory in the presence of obstacles. Figure 8 is an enlarged view of the original image. The curve 1 shown in it is the circle that tangents the smallest turn when the vehicle starts to the starting point when there are obstacles, and 2 is the parking path; in the same way, Figure 9 is the circle where the minimum turning radius of the vehicle is tangent to the end point at the end point of parking in the case of obstacles. Obviously, the radius when the vehicle starts and when it ends parking is larger than the minimum turning radius of the vehicle, so the parking path can be exercised.Figure7 shows the verification of the parking trajectory in the absence of obstacles. Curve 1 is a circle obtained with the minimum turning radius of the vehicle. It is tangent to the parking trajectory 2. Obviously, the vehicle can be parked in the parking space along the curve 1. The parking trajectory is a symmetrical curve, so the curve at the end of parking also satisfies the condition that it is greater than the minimum turning radius of the vehicle, so it can be parked smoothly.A large number of simulation results show that the global path obtained by the ant colony optimization and the grid method has good adaptability, and the curve obtained by the bezier function can make the vehicle reach the target point smoothly. It can be seen that the path planning method proposed in this article is feasible.


## 7. Conclusion

This paper discusses the problem of automatic parking path planning in an environment with known environmental information. A new method is proposed from the system point of view, and effective simulation results have been obtained. Its main features are:(1)
The ant colony optimization is used to select the parking route, which effectively solves the problem of the driver finding the starting point of parking(2)
In the parking process, the ant colony optimization can also avoid obstacles other than the vehicle, showing the adaptability and superiority of the ant colony optimization(3)
Combining the ant colony optimization with the grid method and the Bezier function, the path found meets the requirement that the parking radius is greater than the minimum turning radius of the vehicle, and the vehicle can be parked



---

*Source: 8592558-2021-10-05.xml*