Keywords

1 Introduction

In recent years, with the continuous development of science and technology and computer level, the wave of scientific and technological revolution with intelligence as the core has swept the world. As an intelligent product, mobile robots have been rapidly developed under technological innovation and market demand, and are widely used in manufacturing, medical services, military and other fields, effectively improving people’s production and lifestyle. Since path planning is the key technology to realize intelligent control of mobile robots, mobile robot path planning has become a hot research topic for scholars.

Path planning refers to finding an optimal or sub-optimal collision-free path from the starting node to the target node according to an evaluation index (such as time, distance, search efficiency, etc.) in the working environment with obstacles. Mobile robots can safely pass all obstacles in a complex work environment [1, 2]. Common path planning algorithms are Dijkstra algorithm [3], A* algorithm [4], Artificial potential field method [5], Fuzzy logic method [6], Genetic algorithm [7], Ant colony algorithm [8], etc. Among them, A* algorithm has the advantages of high search efficiency and short planning path in global path planning, and is widely used in mobile robot path planning.

At present, most scholars study mobile robot path planning mainly focusing on algorithm improvement, and make different improvements for different application requirements. In [9], Wang solved the problem of redundant points in the traditional A* algorithm path search and found the minimum corner at the path turning point. In [10], Chen improved the obstacle search method and heuristic function in the traditional A* algorithm, improved the path-finding speed of the path search, and narrowed the search range. In [11], Lu reduced the number of path search nodes by adding a threshold to the open list, and optimized the planned path to obtain a smooth path.

The rest of this article is organized as follows. In Sect. 2, introduce the basic principles and algorithm flow of the traditional A* algorithm. In Sect. 3, according to the shortcomings of traditional A* algorithm path planning, the optimization of heuristic function distance algorithm and path planning search neighborhood is improved. In Sect. 4, simulation experiment analysis for improved A* algorithm. In Sect. 5, introduce the conclusion of the paper.

2 Traditional A*Algorithm

The A* algorithm is a typical heuristic search algorithm, first proposed by Hart [12] in 1968. The algorithm combines the advantages of both Dijkstra algorithm and best-first search algorithm. By adding heuristic function in Dijkstra algorithm to determine the search direction, it solves the problems of large path search range and long response time, and has high search efficiency [13].

Cost function expression of A* algorithm:

$$ F ( {\text{n) = }}G({\text{n}}) + H({\text{n}}) $$
(1)

In the formula (1), F(n) is the value of the value from the starting node to the target node through the current node. G(n) is the actual value of the starting node to the current node. H(n) is the estimated cost of the current node to the target node.

When using the A* algorithm for path search. Firstly, the extended node that can be reached except the obstacle point around the starting node is added to the open list, and the value of all the nodes in the open list is calculated. The node with the smallest F value is added to the close list, which is recorded as the parent node, and as the starting node for the next search. Secondly, continue to calculate until the search target node stops, thus getting all path nodes. Finally, the parent node returns the starting node from the target node, and sequentially connects all the passed nodes to obtain the planned path. The open list is used to store extended nodes in the search process, and the close list is used to store the barrier points and the nodes with the lowest value F in the search process.

The flow chart of the A* algorithm is shown in Fig. 1.

Fig. 1.
figure 1

A* algorithm flow chart

Full size image

Using A* algorithm for path planning, the path search process is shown in Fig. 2. The side of the square is 10, The F, G, H values are calculated using the Manhattan distance formula. The red star indicates the starting point position, the green star indicates the target point position, the black square indicates the obstacle point position, and the red solid circle indicates the planned path node position. The values in the red square are the F, G, H values obtained in the first search, and the values in the blue square are the F, G, H values obtained in the second search, and the latter search will overwrite the value obtained in the previous search. The values in the yellow, brown, gray, and green squares represent the values obtained by the third, fourth, fifth, and sixth searches.

Fig. 2.
figure 2

A* algorithm path search

Full size image

3 Improved A* Algorithm

The traditional A* algorithm planning path has many problems such as many turning points, large search range, and long response time [14]. In order to optimize the planning path of the A* algorithm and optimize the planning path, the traditional A* algorithm is improved by optimizing the heuristic function distance algorithm and the path planning search neighborhood.

3.1 Heuristic Function Distance Algorithm

In the traditional A* algorithm cost function, the commonly used distance algorithm of the heuristic function H(n) is the Manhattan distance and Euclidean distance algorithm. Suppose the starting node coordinate is S(Sx, Sy), the current node coordinate is N(Nx, Ny), and the target node coordinate is T(Tx, Ty).

The Manhattan distance formula:

$$ H({\text{n)}} = \left| {N_{\text{x}} - T_{\text{x}} } \right| + \left| {N_{\text{y}} - T_{\text{y}} } \right| $$
(2)

The Euclidean distance formula:

$$ H({\text{n)}} = \sqrt {(N_{\text{x}} - T_{\text{x}} )^{2} \,{ + }\, (N_{\text{y}} - T_{\text{y}} )^{2} } $$
(3)

Because mobile robots use the Manhattan distance and Euclidean distance algorithm for path planning, there are often problems such as too many search nodes and too long calculation time [15]. In order to reduce the number of search nodes for path planning, narrow the search scope, and quickly find the optimal planning path. The heuristic function distance algorithm is improved, and a new distance algorithm is proposed, which is recorded as a complex diagonal distance algorithm. The algorithm considers the moving distance and moving steps of the current node to the target node, and performs weighting calculation.

The complex diagonal distance formula:

$$ H({\text{n}})\,{ = }\,\left( {\sqrt 2 - 2} \right)\, \times \,\hbox{min} \left\{ {\left| {N_{x} - T_{x} } \right|,} \right.\,\left. {\left| {N_{y} - T_{y} } \right|} \right\}\, + \,\left( {\left| {N_{x} - T_{x} } \right|\, + \,\left| {N_{y} - T_{y} } \right|} \right) $$

3.2 Path Planning Search Neighborhood

In the raster map, if the edges are calculated adjacent to each other, each grid is surrounded by 4 grids, as shown in Fig. 3(a). If the edge and the top corner are adjacent, each grid is surrounded by 8 grids, as shown in Fig. 3(b). Therefore, the path planning search neighborhood is divided into two types, four-neighbor search and eight-neighbor search. The light green fill in the raster map indicates the neighborhood search range, and the red arrow indicates the planned path direction.

Fig. 3.
figure 3

Path planning search type

Full size image

At present, four-neighbor search is widely applied to the path planning of the A* algorithm, but when the A* algorithm performs path planning search, the number of extended nodes affects the path search rate. The eight-neighbor search is doubled compared with the extended node of the four-neighbor search, which can improve the path planning search rate and ensure that the planned path is the optimal path.

4 Simulation Experiment and Result Analysis

In order to compare the optimization degree of the improved A* algorithm heuristic function distance algorithm, This paper constructs a 10 × 10 raster map environment model in which obstacle points are randomly distributed. Assuming the same starting point and target point, the heuristic function distance algorithm performs path planning simulation according to Manhattan distance, Euclidean distance and improved complex diagonal distance. The simulation results are shown in Fig. 4. The light green fill in the raster map represents the search node for the path plan.

Fig. 4.
figure 4

Mobile robot path planning simulation diagram

Full size image

From the simulation data of Table 1, it can be seen that the complex diagonal distance algorithm reduces the number of search nodes and path nodes by 30%, the path length by 20%, and the calculation time by 45%. Therefore, the mobile robot uses the complex diagonal distance algorithm for path planning, which can achieve the ideal effect of narrowing the search range, reducing the number of path nodes, shortening the path length and increasing the calculation rate.

Table 1. Mobile robot path planning simulation data
Full size table

In order to compare the superiority of A* algorithm in path planning under four-neighbor search and eight-neighbor search, select the same starting point and target point, use the improved complex diagonal distance algorithm to calculate, and set the accessibility environment as a comparison. To make the simulation comparison result of path planning more accurate, the simulation results are shown in Figs. 5 and 6. The light green fill portion of the raster map represents the search node for the path plan.

Fig. 5.
figure 5

Path search in an accessible environment

Full size image
Fig. 6.
figure 6

Path search in an obstacle environment

Full size image

From the simulation data of Table 2, it can be seen that in the barrier-free environment, the number of nodes and the path length of the eight-neighbor search are better than the four-neighbor search, in which the number of search nodes is reduced by nearly 1/2 and the path length is shortened by nearly 1/3. Therefore, the eight-neighbor search for path planning can obtain an optimal path with a small search range and a short path length.

Table 2. Four-neighbor and eight-neighbor search of A* algorithm
Full size table

5 Conclusion

In this paper, the optimization research of mobile robot path planning algorithm is carried out. By analyzing the shortcomings of the commonly used heuristic function distance algorithm in traditional A* algorithm, the A* algorithm is improved to get the complex diagonal distance algorithm. At the same time, the eight-neighbor search is proposed to optimize the path search mode, and the path planning simulation of the mobile robot is carried out in the raster map. The simulation results show that the improved A* algorithm can narrow the search range, reduce the number of path nodes, shorten the path length, solve the problem of too many search nodes and long calculation time in the path planning process, and the planned path is the optimal path.