Global path planning on uneven terrain at construction sites for robots based on an improved A* Algorithm

Abstract

With the increasing application of construction robots on construction sites, autonomous path planning in unstructured and uneven construction sites has become an urgent challenge. Current path planning approaches face several issues, including prolonged computation times, low efficiency, and redundant nodes, often resulting in impractical paths for robots. Addressing these concerns, this study introduces a global path planning method based on an enhanced A* algorithm to ensure safe and robust navigation of construction robots in such challenging environments. The Improved A* algorithm initially incorporates a bidirectional alternating search strategy to expedite computational speed. Subsequently, it employs path node filtering to mitigate issues associated with bidirectional search and reduce the number of critical nodes, thereby enhancing search efficiency. Furthermore, the introduction of slope constraints decreases the robot's climbing and tilting angles, augmenting the safety of the planned paths. Finally, the paths are smoothed using Bézier curve fitting, facilitating better motion control for the robots. The efficacy of the improved algorithm was validated through experiments on elevation maps with varying terrain and obstacle densities. Simulation results indicate that, compared to the traditional A* algorithm, the Improved A* algorithm reduced computation time by 71.05% to 82.90% and the number of critical nodes by 51.94% to 70.53%, while only increasing the path length by 14.6% to 37.84%. Additionally, there was a significant reduction in climbing and tilting angles, and the paths have become smoother. Therefore, this method not only improves efficiency while generating safe and reliable paths in unstructured and uneven construction sites, but also enables robots to adapt to complex environments, and promotes automation and intelligent construction processes.

Keywords

construction site uneven terrain path planning improved A* algorithm construction robot

1. Introduction

In recent years, the rapid development of automation technology has led to the increasingly widespread deployment of robots in the construction industry, marking a global trend in their integration into construction processes (Jeong et al., 2021). In response to this evolution, researchers have proposed robotic systems equipped with perception sensors and intelligent algorithms designed to assist construction supervisors in remotely identifying building materials and detecting component installations and defects (Muhammad et al., 2021). The application of Virtual Reality (VR) technology in conjunction with construction robots has significantly enhanced workers’ trust in robots, self-efficacy, and situational awareness at construction sites (Adami et al., 2022). Furthermore, to address the challenge of initializing robots at unknown locations, a novel indoor robot initialization system based on Building Information Modeling (BIM) has been introduced, utilizing object detectors for automatic initialization (Zhao and Cheah, 2023). Despite significant progress in developing construction robot solutions, the unique characteristics of construction sites, such as temporary structures, equipment, and materials, pose considerable challenges for mobile robots. The complex and uneven terrain further complicates the path planning methods required for these robots.

Global path planning is one of the basic issues in robotics technology and the basis for robots to complete complex tasks (Li et al., 2022a). It is a kind of static planning, usually expressed as follows: given a mobile robot and an environment model, it must find the optimal path between the starting position and the final position without colliding with obstacles, while meeting certain criteria, such as distance, smoothness or safety (Châari et al., 2014; Saeed et al., 2020). The results of path planning can be evaluated in terms of path length, turning angle, calculation time, risk level, and other factors (Zhang et al., 2022). With the advancement of Simultaneous Localization and Mapping (SLAM) technology and improvements in computational performance, autonomous navigation techniques have found widespread application in ground robots. Currently, two-dimensional indoor planar mobile robot navigation technology is relatively mature. By enhancing the robustness and efficiency of existing two-dimensional autonomous navigation methods (Kalogeiton et al., 2019; Pütz et al., 2018), robots are now extensively deployed in various fields such as industry (Cardarelli et al., 2017), agriculture (Tevyashov et al., 2022), search and rescue (Berger and Lo, 2015), and transportation (Pereira et al., 2018). However, traditional path planning algorithms are primarily designed for flat, structured terrains and tend to idealize environmental conditions. Given that construction sites in the early stages are often scattered with rocks, soil piles, and slopes, mobile robots must determine whether the terrain ahead is safely traversable. In other words, devising the most practical and collision-free paths on uneven and unstructured terrains is a critical challenge. In such complex environments, traditional path planning algorithms face several difficulties and limitations, including:

The representation and computation of large-scale maps are time-consuming.

Unstructured terrains and obstacles severely affect the planning of paths.

The paths generated by planning do not meet the safety requirements of mobile robots.

Construction robots are a specialized application of mobile robots in specific scenarios. Given that mobile robot path planning is widely regarded as an NP-hard problem (Kyprianou et al., 2021), extending path planning to three-dimensional (3D) environments merely involves adding a height axis compared to two-dimensional (2D) plane-based path planning. Consequently, 3D path planning also falls within the NP-hard problem category (Zeng et al., 2016). In previous decades, several approaches have been developed to address this complex issue. Classic methods include artificial potential fields, sampling-based methods, and graph-based methods; heuristic algorithms mainly include A* and D* search algorithms; meta-heuristic algorithms have been applied in most research, such as the famous algorithms are Particle Swarm Optimization (PSO), Genetic Algorithm (GA), and Simulated Annealing (SA); methods based on artificial intelligence are among the most prevalent algorithms utilized in multi-robot systems, for example, Yakoubi MA and colleagues employed a Pulse-Coupled Neural Network model to achieve complete coverage navigation for a vacuum cleaner robot (Yakoubi et al., 2016). These algorithms have solved the path planning problem of mobile robots in a known environment to a certain extent. The classification of methods is shown in Figure 1.

Figure 1.

Classification of commonly used path planning methods.

In the realm of meta-heuristic algorithms, the Genetic Algorithm (GA) is widely applied in path planning due to its parallelism and global search capabilities. However, GA has the potential for premature convergence and is prone to falling into local optima (Elhoseny et al., 2018). The Simulated Annealing (SA) algorithm is used in global path planning to search for the optimal path. It is easier to implement than GA, as GA uses a population containing a set of chromosomes rather than a single solution (Miao and Tian, 2013). Despite this, SA has issues with slow convergence speed and large computational overhead (Liang and Xu, 2009). The Ant Colony Optimization (ACO) algorithm proposed by Dorigo is a heuristic search algorithm that simulates the foraging behavior of ant colonies (Dorigo and Gambardella, 1997). It has the advantages of strong robustness, excellent distributed computing performance, and ease of combination with other algorithms (Luo et al., 2019). Nonetheless, ACO has a slower convergence speed and is prone to falling into local optima (Miao et al., 2021). The Particle Swarm Optimization (PSO) algorithm is a swarm intelligence algorithm that simulates bird flocking behavior (Kennedy and Eberhart, 1995). It generates swarm intelligence to guide optimization search through cooperation and competition among particles in the swarm. Although PSO has the advantages of fewer individuals, simple computation, and good robustness, its convergence accuracy is lower, and it experiences search stagnation (Yuan et al., 2022).

Meta-heuristic algorithms are often used for path planning problems in static environments. However, when the environment changes, the time to replan is lengthy, and real-time performance is lacking. These algorithms also have a tendency to fall into local optima, hence their application in actual robots is limited. Among classical algorithms, the Rapidly-exploring Random Tree (RRT) is a sample-based search algorithm (LaValle and Kuffner, 2001). It is fast and powerful, holding a significant position in high-dimensional environments. Yet, this algorithm has low search accuracy, poor path smoothness, and struggles to plan the optimal path (Kuffner and LaValle, 2000). Dijkstra algorithm is a typical single-source shortest path search algorithm. Its search method is relatively simple, extending from the starting point to the outer layer until it reaches the target point. This is achieved by comparing all nodes through forward traversal to obtain the shortest path (Dijkstra, 1959). Dijkstra's algorithm has a high success rate in obtaining the shortest path and good robustness. But when the scale of environment mapping increases, the number of nodes calculated by the algorithm increases, and the memory space occupied by the algorithm also increases, severely reducing computational efficiency (Chen et al., 2013).In 1968, Hart proposed the A* algorithm, which added a heuristic function based on Dijkstra's algorithm. By evaluating the cost of nodes, it obtains the suboptimal nodes that need to be expanded until the algorithm expands to the target point (Hart et al., 1968). Compared with Dijkstra's algorithm, the path planning efficiency of this algorithm is significantly improved. The A* algorithm is favored by many scholars in the field of mobile robot path planning due to its simple principle, ease of implementation, and high search efficiency (Hong et al., 2021; Li et al., 2022b). Nevertheless, the A* algorithm has defects such as long computation time for large maps, large turning angles, redundant nodes, and unsmooth paths.

In order to enhance the efficiency of the A* algorithm, scholars have made improvements in multiple aspects such as data structure, retrieval strategy, path length, turning angle, and redundant nodes, thereby further enhancing the planning efficiency and path performance of the A* algorithm in various application scenarios. Cui et al. improved the search distance of the A* algorithm by expanding adjacent states, which shortened the planned path and improved search efficiency (Baoxia et al., 2018). Zhang, Ren, and others adopted a key point selection strategy for secondary planning to reduce the search for unnecessary nodes and improve path planning efficiency (YiYue et al., 2019; Zhang et al., 2018). Li et al. combined the Dynamic Window Approach (DWA) with the A* algorithm, giving the algorithm a certain dynamic obstacle avoidance capability and improving the robustness of the algorithm (Li et al., 2022b). Shang et al. improved the efficiency and obstacle avoidance capabilities of the A* algorithm by using criteria and key points (Shang et al., 2020). Wang et al. have effectively addressed the issues of shortest path planning and collision by incorporating a turning factor into the algorithm (Shang et al., 2020). Hong et al. improved the data structure of the algorithm, reducing its time complexity, and applied the A* algorithm to outdoor path planning (Hong et al., 2021), Gomathi N and others developed a hybrid algorithm, HSAStar (Hybrid SLAM & A Star), which offers a unique adaptive path planning framework to address the unknown environment persistent monitoring problem (Gomathi and Rajathi, 2023).

However, when conducting path planning in the uneven terrain environment of a construction site, it is necessary to consider factors such as obstacles and terrain slopes. Compared to a two-dimensional plane, the constraints imposed by the environment are greater, and the requirements for the algorithm are higher. The aforementioned improvements cannot solve the issues of the traditional A* algorithm, such as long computation time, numerous redundant nodes, unsmooth paths, and safety concerns. To summarize, there is currently little research on quickly planning a short, feasible, smooth, and safe path on a large, uneven surface. Therefore, this paper proposes an improved A* algorithm that significantly enhances algorithm efficiency and can plan a trajectory suitable for construction robots to move on uneven terrain with high smoothness.

The contributions of the method proposed in this paper are summarized as follows:

Construction of a Three-Dimensional Grid Map: By incorporating elevation data into the traditional two-dimensional grid map, a three-dimensional elevation grid map has been established to describe the uneven terrain of unstructured construction sites.

Algorithm Improvement: Comprehensive improvements have been made to the traditional A* algorithm from aspects such as bidirectional search strategy, node quantity, and path smoothness. This has greatly enhanced the computational speed of the algorithm and the quality of the path.

Establishment of Safety Constraints: Constraints on the climbing angle and tilt angle when the mobile robot moves on an uneven surface have been established, ensuring that the planned path is suitable for the robot's movement in uneven construction site.

The remainder of this paper is organized as follows: Chapter 2 presents the environmental model and the traditional A* algorithm. Chapter 3 details the multiple improvements made to the traditional A* algorithm. In Chapter 4, the effectiveness and significance of the proposed method are validated through experiments, and the research results are presented. Finally, Chapter 5 provides a summary of the entire paper and draws conclusions.

2. Terrain modeling

2.1 Elevation grid map

To achieve path planning for mobile robots, it is essential to acquire environmental map information. Environmental maps can be broadly categorized into static maps based on terrain and fixed obstacles, and dynamic maps that account for moving obstacles. The acquisition methods primarily involve importing known map information (static maps) or utilizing onboard sensors to detect the dynamic environmental map. Common environmental modeling methods currently include the Visibility Graph Method, Tangent Graph Method, Voronoi Diagram Method, Free Space Method, and Grid-based Method. In the current state of research and practical applications, the grid-based method stands out as the most extensively studied and widely utilized approach for modeling environments in the context of path planning. This method partitions the free space into non-overlapping grid cells, with each cell individually recording terrain information. Specifically, each grid cell represents a discrete portion of the environment. These cells are categorized as either “free” or “occupied.” A free grid cell indicates that a mobile robot can move to that location, while an occupied grid cell signifies the presence of an obstacle, rendering it inaccessible for robot traversal. The environment maps constructed using the grid-based method are commonly referred to as “grid maps.”

Conventional raster maps can only create two-dimensional environmental maps, as illustrated in Figure 2. In contrast, Digital Elevation Models (DEMs) represent the spatial distribution of terrain using a finite three-dimensional vector set $(x, y, z)$ .In this representation, the x and y coordinates describe position information, while the $z$ coordinate describes elevation. In this paper, we rasterize Digital elevation models (DEMs) by assigning elevation information to grid points, creating a static map model as shown in Figure 3(a). Each grid cell in the grid map is represented by its specific position using $p (x, y, z)$ coordinates. Additionally, we introduce obstacles onto the elevation grid map, depicted as blue cylindrical structures, with a red pentagon marking the robot's starting point and a green circle indicating the target location, as illustrated in Figure 3(b).

Figure 2.

Two-Dimensional grid map.

Figure 3.

The establishment process of an elevation raster grid map depicting uneven terrain. (a) Elevation grid map. (b) Elevation grid map with obstacles.

The fundamental element of grid-based methods is grid granularity. If the grid cells are too small, the path search process becomes challenging, consuming significant computational resources and time. Conversely, if the grid cells are too large, the environmental model will deviate significantly from the real environment, rendering expected path planning infeasible. Therefore, grid granularity is crucial for both environment modeling and path planning. In this study, we use a resolution of 100 × 100 for the grid map, with each grid cell having an actual side length of 0.5 meters. The actual grid distance can be adjusted based on the size of the mobile robot and the real-world map.

2.2 A* algorithm

The A* algorithm is a widely used heuristic search algorithm for static environments. It can be applied to path planning in known and fixed environments, and it can also adapt to dynamic environments by repeatedly invoking the algorithm for path planning. The primary characteristic of the A* algorithm is its use of a heuristic function to guide the search direction. The graph being searched has weights that remain constant over time, allowing direct search within the graph without the need for any preprocessing. The core of the A* algorithm lies in its evaluation function, which directs node expansion during each search iteration, as shown in Equation (1).

\begin{matrix} f (n) = g (n) + h (n) \end{matrix}

(1)

In the equation, n represents the current node. The evaluation function

f (n)

is the actual estimated cost used during planning. The cost function

g (n)

represents the actual traversal cost from the starting vertex to the intermediate vertex n. The heuristic function

h (n)

estimates the minimum cost from intermediate vertex n to the goal vertex. The A* algorithm's flowchart is depicted in Figure 4.

Figure 4.

The flow chart of the A* algorithm.

The main steps of the A* algorithm are as follows:

Initialize an OpenList, CloseList, and PathList. Insert the Start node into the OpenList.

When the OpenList is not empty, determine the node with the smallest $f (n)$ value in the OpenList, remove it from the OpenList, add it to the CloseList, and set it as the current node.

Traverse the feasible neighboring nodes of the current node. If a neighboring node is not in the OpenList, add it to the OpenList, add the current node to the PathList, and calculate the heuristic distance cost. If it is in the OpenList, calculate its G value; continue to traverse other feasible neighboring nodes; otherwise, add the current node to the PathList and update the heuristic distance cost of the node.

Iterate to move to subsequent nodes until the current node becomes the end node.

Commonly used heuristic functions

h (n)

include the Euclidean distance function, Manhattan distance function, and Chebyshev distance function. The current node is denoted as

(x_{n}, y_{n})

, and the target node is denoted as

(x_{G}, y_{G})

The Euclidean heuristic function between $(x_{n}, y_{n})$ and $(x_{G}, y_{G})$ can be expressed as:

\begin{matrix} h (n) = \sqrt{{(x_{G} - x_{n})}^{2} + {(y_{G} - y_{n})}^{2}} \end{matrix}

(2)

The Manhattan heuristic function between

(x_{n}, y_{n})

and

(x_{G}, y_{G})

can be expressed as:

\begin{matrix} h (n) = | x_{G} - x_{n} | + | y_{G} - y_{n} | \end{matrix}

(3)

The Chebyshev heuristic function between

(x_{n}, y_{n})

and

(x_{G}, y_{G})

can be expressed as:

\begin{matrix} h (n) = m a x (| x_{G} - x_{n} |, | y_{G} - y_{n} |) \end{matrix}

(4)

In this study, considering that the A* algorithm searches eight neighboring nodes in each expansion, the Euclidean distance function is chosen as the heuristic function. This function represents the direct distance between two coordinate nodes. In three-dimensional uneven terrain, the path estimated by the Euclidean distance function is closer to the actual path than other functions. In the three-dimensional elevation map, the Euclidean distance function is represented as:

\begin{matrix} h (n) = \sqrt{{(x_{G} - x_{n})}^{2} + {(y_{G} - y_{n})}^{2} + {(z_{G} - z_{n})}^{2}} \end{matrix}

(5)

Where

z_{G}

and

z_{n}

represent the elevation values of the goal node

(x_{G}, y_{G})

and the current node

(x_{n}, y_{n})

respectively.

It is straightforward to prove that the improved heuristic function remains monotonic and admissible, just as the original heuristic function was. Consequently, the improved heuristic function, like the original one, preserves both completeness and optimality. It should be noted that, due to the increased complexity of the improved heuristic function, the enhancement of the heuristic alone does not lead to an increase in the algorithm's computational speed. Instead, it improves the accuracy of the estimated path length by bringing it closer to the actual path length. Regarding the selection of the evaluation function $f (n)$ , the following conclusion has been reached: The closer the evaluation function value is to the actual path cost, the higher the accuracy of the selected points. An appropriate evaluation function can not only ensure that the algorithm searches for the optimal path, but also reduce the number of search nodes, thereby improving the efficiency of the algorithm. The original evaluation function is the sum of the cost function and the heuristic function in a 1:1 ratio. If we change the weights of the actual cost and the estimated cost, we can control the A* algorithm to lean more towards the actual cost or the estimated cost. When $g (n) >> h (n)$ , it is equivalent to $f (n)$ only considering the actual cost and not considering the estimated cost, which degenerates into the Dijkstra algorithm. Conversely, if the weight coefficient of $g (n)$ is less than the weight coefficient of $h (n)$ , the estimated cost will be considered first. By the same extension, when $h (n) >> g (n)$ , the A* algorithm does not rely on the actual cost to control the search direction, so the result obtained may not be the shortest path. Therefore, this paper uses an exponential function to weight the heuristic function $h (n)$ , and the weighted evaluation function is shown in Equation (6).

\begin{matrix} f (n) = g (n) + e^{h (n)} \cdot h (n) \end{matrix}

(6)

Where

h (n) = \sqrt{{(x_{G} - x_{n})}^{2} + {(y_{G} - y_{n})}^{2} + {(z_{G} - z_{n})}^{2}}

, When the current node and the target node are far apart,

h (n)

is larger, and the weight

e^{h (n)}

is also larger, which allows the nodes to meet quickly. When the current node and the target node are closer,

h (n)

is smaller, and the weight

e^{h (n)}

is also smaller, making the estimated cost closer to the actual cost.

Figure 5.

Schematic diagram of the four and eight moving directions of the robot in the grid map. (a) Four moving directions. (b) Eight moving directions.

2.3 Restrictive conditions

Ground robots cannot move arbitrarily in the actual moving process, and need to be constrained in multiple aspects. The constraints are as follows:

Path Continuity: The planned global path must be continuous. During the movement process, when moving to the next grid, it can move to a feasible grid among the 8 grids around it, as shown in Figure 5. For example, when the current node $(x_{1}, y_{1})$ moves to $(x_{2}, y_{2})$ , it should at least satisfy one of the conditions $(x_{1} ⟨ x_{2}, x_{1} ⟩ x_{2}, y_{1} ⟨ y_{2}, y_{1} ⟩ y_{2})$ .

Boundaries and Obstacles: The planned global path must be within the designated grid map and cannot exceed the map boundary. Grids with blue cylinders are the locations of obstacles, and thus, these grids are not feasible, while other grids are feasible.

Shortest Path: After satisfying conditions (1) and (2), the length of the planned global path must be the shortest, that is, the fitness function must take the minimum value. The traditional A* algorithm commonly uses distance calculation methods such as Manhattan distance and Euclidean distance. To make the algorithm adapt to uneven terrain, this paper proposes a new distance calculation method - slope distance (Sd). This distance is closer to the real value in the actual map than the Euclidean distance. The fitness function is expressed as:

\begin{matrix} L = \sum_{i = 0}^{n - 1} \sqrt{ρ^{2} s_{i}, s_{i + 1} + {(z (s_{i}) - z (s_{i + 1}))}^{2}} \end{matrix}

(7)

In the equation, n is the total number of nodes in the planned path, $S_{i}$ is the $i^{t h}$ node in Path, that is $x_{i}, y_{i}$ , $ρ$ is the Euclidean distance between two nodes, $ρ (s_{i}, s_{i + 1}) = \sqrt{{(x_{i + 1} - x_{i})}^{2} + {(y_{i} - y_{i + 1})}^{2}}$ , and $z (s_{i})$ is the elevation value of node $s_{i}$ .

To facilitate research and experiment, this paper makes the following assumptions:

The elevation map data has been obtained through other techniques, and this paper focuses solely on constructing the raster elevation map.

The grid is expanded using an eight-neighborhood approach, allowing the robot to move to the surrounding eight grid cells when conditions permit.

Dynamic map information is captured and updated in real-time by onboard sensors on the robot. These sensors can detect the terrain status of the surrounding eight grid cells at the current grid point.

3. Improvement of A* algorithm

In addition to the improvements to the heuristic function mentioned earlier, this study further enhances the A* algorithm by incorporating advancements in four key areas: bidirectional alternating search strategy, path node filtering, slope constraint, and arc optimization. These enhancements collectively improve the algorithm's performance in terms of the computational speed, number of critical nodes, climbing angle, and path quality. The flowchart of the improved A* algorithm is shown in Figure 6.

Figure 6.

The flow chart of the improved A* algorithm.

3.1 Bidirectional alternating search strategy

The traditional A* algorithm simply uses the geometric path length as the actual cost, which results in large memory consumption and long computation time. Especially in environments like construction sites with long-distance and uneven terrain, the increase in constraint conditions makes the computation time of the algorithm even longer. In order to further enhance the computational efficiency of the A algorithm, a Bidirectional Alternating Search (BAS) strategy has been introduced into the A* algorithm. This strategy, based on the A* algorithm, initiates an alternating search path from the starting point and the target point until the two search paths intersect which can effectively reduce the search time, thereby improving the efficiency of path planning. Theoretically, forward search and backward search will start from the target point and the starting point respectively, and finally meet at the center of the map. However, in practical applications, the search paths may not intersect at the center due to the uneven distribution of obstacles. Therefore, by alternately replacing the current optimal node in the forward and backward openlist, and by switching the target of the forward and backward heuristic functions, it is ensured that the forward path and the backward path meet. Both the forward and backward paths search for 8 adjacent nodes in each expansion. The forward evaluation function targets the current node in the backward direction, as shown in Equation (8). And the backward evaluation function targets the current node in the forward direction, as illustrated in Equation (9). The heuristic functions for forward and backward searches are respectively presented in Equations (10) and (11).

\begin{matrix} f_{F} (n_{F}) = g_{F} (n_{F}) + e^{h_{F} (n_{F})} \cdot h_{F} (n_{F}) \end{matrix}

(8)

\begin{matrix} f_{B} (n_{B}) = g_{B} (n_{B}) + e^{h_{B} (n_{B})} \cdot h_{B} (n_{B}) \end{matrix}

(9)

\begin{matrix} h_{F} (n_{F}) = \sqrt{{(x_{n_{B}} - x_{n_{F}})}^{2} + {(y_{n_{B}} - y_{n_{F}})}^{2} + {(z_{n_{B}} - z_{n F})}^{2}} \end{matrix}

(10)

\begin{matrix} h_{B} (n_{B}) = \sqrt{{(x_{n_{F}} - x_{n_{B}})}^{2} + {(y_{n_{F}} - y_{n_{B}})}^{2} + {(z_{n_{F}} - z_{n_{B}})}^{2}} \end{matrix}

(11)

Where

n_{F}

is the current node in the forward openlist,

n_{B}

is the current node in the backward openlist,

g_{F} (n_{F})

is the cost of the path from the starting point to

n_{F}

h_{F} (n_{F})

is the heuristic function that estimates the cost of the least expensive path from

n_{F}

n_{B}

g_{B} (n_{B})

is the cost of the path from the goal point to

n_{B}

,and

h_{B} (n_{B})

is the heuristic function that estimates the cost of the least expensive path from

n_{B}

to the next

n_{F}

Figure 7 is a schematic diagram illustrating the principle of path planning using the BAS-A* algorithm in a 100 × 100 grid map. When the algorithm starts running, the starting point S and the target point G of the path are used as the initial nodes for forward and backward search respectively. During the forward search, with S as the starting point and G as the target, the optimal forward node $S_{1}$ is obtained. Then with G and $S_{1}$ as the starting point and target node respectively, a backward search is conducted to obtain an optimal backward node $G_{1}$ , which is used as the target node for the next forward search. This process is repeated iteratively until the paths meet. That is the BAS-A* algorithm alternately expands each node forward and backward, and uses the optimal node obtained from the opposite search strategy as its own target node for expansion, thereby ensuring the meeting of the forward and backward paths.

Figure 7.

Schematic diagram of the search process using the BAS-A* algorithm.

The pseudo code of the BAS-A* algorithm is as follows:

Algorithm 1: The BAS-A* algorithm.
1	Initialize the environment model;
2	Initialize the OPEN list, the FORWARD CLOSE list, the FORWARD PARENT list, the BACKWARD CLOSE list, and the BACKWARD PARENT list;
3	FORWARD OPEN ←S, BACKWARD OPEN ←G;
4	While Both FORWARD OPEN and BACKWARD OPEN are not empty do
5	Find the forward current node N_F with the smallest f(N_F) value in the FORWARD OPEN;
6	Move NF to the FORWARD CLOSE;
7	Find the backward current node N_B with the smallest f(N_B)value in the BACKWARD OPEN;
8	Move N_B to the BACKWARD CLOSE;
9	If NF and N_B meet then
10	Output the FORWARD PATH and BACKWARD PATH according to the FORWARD PARENT and the BACKWARD PARENT;
11	Integrate the FORWARD PATH and BACKWARD PATH into an optimal path;
12	Exit the loop;
13	Else
14	According to the 8 adjacent nodes of N_F, update the FORWARD OPEN and the FORWARD PARENT;
15	According to the 8 adjacent nodes of N_B, update the BACKWARD OPEN and the BACKWARD PARENT;
16	End if
17	End while

Since the OpenList requires frequent insertions, deletions, updates, and retrievals, a min-heap is employed as its container. The space complexity of the min-heap is O(N), while its time complexity is O(NlogN). On the other hand, the CloseList, which involves frequent insertions and lookups, utilizes a hash table as its data structure. The space complexity of the hash table is O(N), and its overall time complexity is O(N).

It is worth noting that the calculation method of the BAS-A* algorithm is not to calculate the path from the current point to the end point, but to plan the path from the current point to the point with the smallest value in the openlist on the other side. This ensures that the paths in both forward and backward directions will definitely intersect. In addition, the BAS-A* algorithm does not need to ensure that the forward and backward directions are synchronized, and it allows one direction to be faster than the other. The openlist on both sides prioritizes processing the one with fewer nodes each time, which can ensure that the total number of nodes searched in the end will be reduced.

To verify the effectiveness of the BAS-A* algorithm, a simulation experiment was conducted in MATLAB 2022b. In 100 × 100 elevation grid maps, three different terrains were set up and 100 obstacles were randomly arranged on each terrain. Then, collision-free paths were generated in the maps, where the red represents the path of the BAS-A* algorithm, and the yellow represents the path of the A* algorithm. The generated paths are shown in Figure 8.

Figure 8.

The simulation results of A* algorithm and BAS-A* algorithm on map1-map3. (a) Path of A* and BAS-A*on map1. (b) Path of A* and BAS-A*on map2. (c) Path of A* and BAS-A*on map3.

To make the test results more representative, 50 tests were conducted on each map, and the 100 obstacles were randomly redeployed in each test. Table 1 presents the results of 50 simulation experiments of the A* algorithm and the BAS-A* algorithm on three different terrains. The results show that, in these three maps, compared to the traditional A* algorithm, the BAS-A* algorithm increases the number of search nodes by 12.48%, 18.67%, and 7.23%, while the path length remains almost unchanged. Despite this, the BAS-A* algorithm reduces the computation time by 89.14%, 86.12%, and 87.30% respectively, highlighting the effectiveness of the bidirectional alternating search strategy in enhancing the speed of the algorithm.

Table 1.

The calculation time, the number of search nodes, and the path length of the A* algorithm and the BAS-A* algorithm in maps 1 to 3. The values are reported as mean ± standard deviation for 30 executions.

	Average calculation time (ms)		Number of searched nodes		Path length (cells)
Map no.	A*	BAS-A*	A*	BAS-A*	A*	BAS-A*
Map 1	922.35 ± 13.56	100.20 ± 5.11	100.6 ± 1.8	112.7 ± 4.7	138.10 ± 17.43	140.17 ± 1.94
Map 2	897.73 ± 21.85	124.57 ± 19.66	98.7 ± 1.4	116.3 ± 7.0	179.43 ± 5.94	186.28 ± 3.26
Map 3	914.65 ± 16.01	116.17 ± 26.38	101.6 ± 1.3	108.3 ± 6.3	140.31 ± 6.50	142.30 ± 4.61

It is worth noting that the BAS-A* algorithm can effectively reduce the time of path planning. However, when the forward and backward paths meet, as can be clearly seen in the overhead view in Figure 9, the BAS strategy sometimes unnecessarily searches nodes back and forth, and may even search more nodes than the A* algorithm. This leads to path duplication, affecting the efficiency of path planning and the control of robot movement.

Figure 9.

Overhead view of the path generated by the BAS-A* algorithm.

3.2 Path node filtering

The challenges posed by the aforementioned BAS strategy can be addressed through the implementation of path critical node filtering within the planned trajectory. The filtering of path nodes can effectively reduce the quantity of critical nodes in the path planning facilitated by the BAS-A* algorithm, thereby avoiding path redundancy and diminishing the frequency of directional changes. Such optimization yields paths that are more conducive to the effective control of mobile robots during real-time navigation.

Figure 10 illustrates the selection process of key path nodes, where P₃, P₄, P₇, and P₉ are the critical path nodes selected by the filtering algorithm. Specifically, all path nodes planned by the improved BAS-A* algorithm are extracted (as shown in Figure 10(a)), namely S, P₁, P₂, P₃…P₁₆, G. Starting from the origin point S, S is connected to P₁. If there is no obstacle between S and P₁, then S is connected to P₂, and so on, until there is an obstacle between S and P_k (k = 3, 4, …, n). Then, P_k−1 is connected to S, and the redundant nodes in the middle (all path nodes between node S and node P_k−1) are removed to update the path. This operation is repeated starting from node Pk until the target point G is searched, resulting in the red path shown in Figure 10(b). Filtering path nodes can effectively eliminate path redundancy, reduce the number of search nodes, shorten the path length, and decrease the number of turns.

Figure 10.

The comparison of path before and after node filtering. (a) The path before filtering. (b) The path after filtering.

Figure 11 and Table 2 respectively present the simulation results and information of the BAS-A* algorithm on different environmental maps, before and after node filtering. Compared with the unfiltered BAS-A* algorithm, the node-filtered BAS-A* algorithm, in Maps 1 to 3, has slightly increased computation times by 2.97%, 4.99%, and 2.36% respectively. However, it has shortened path lengths by approximately 17.27%, 18.26%, and 19.17%, and reduced the number of nodes by 91.67%, 93.51%, and 90.33% respectively. This demonstrates that the introduction of node filtering significantly reduces redundant nodes in the BAS-A* algorithm and shortens path lengths. The improved paths better meet the requirements of optimal path planning for mobile robots.

Figure 11.

The comparison of paths before and after node filtering in map1-map3 for the BAS- A*. (a) The comparison of paths before and after node filtering in map 1 for the BAS- A*. (b) The comparison of paths before and after node filtering in map 2 for the BAS- A*. (c) The comparison of paths before and after node filtering in map 3 for the BAS- A*.

Table 2.

The calculation time, the number of search nodes, and the path length of the BAS-a* algorithm before and after node filtering in maps 1 to 3. The values are reported as mean ± standard deviation for 50 executions.

		Average calculation	Path length	Number of
Map no.	Algorithms	time (ms)	(cells)	searched nodes
Map1	BAS-A* before filtering	100.86 ± 6.41	142.18 ± 4.94	109.3 ± 7.6
Map1	BAS-A* after filtering	103.86 ± 11.37	117.63 ± 5.82	9.1 ± 4.20
Map2	BAS-A* before filtering	122.46 ± 15.99	167.68 ± 5.69	112.4 ± 7.3
Map2	BAS-A* after filtering	128.57 ± 19.68	137.06 ± 3.27	7.3 ± 1.7
Map3	BAS-A* before filtering	104.27 ± 11.23	146.36 ± 7.31	108.6 ± 4.3
Map3	BAS-A* after filtering	106.73 ± 9.91	118.30 ± 3.28	10.5 ± 3.5

3.3 Slope constraint

The traditional A* algorithm does not take into account the size of the mobile robot, instead treating it as a point mass. In practical path planning, the planning of paths in three-dimensional terrain needs to consider not only the length of the path but also impose restrictions on path safety.

Path safety is primarily reflected in the issue of slope, where the climbing slope of the planned path cannot exceed the maximum climbing slope $\emptyset_{c}$ that the robot is allowed to traverse (in this article, it is assumed that $\emptyset_{c}$ =30°), the calculation method is shown in the figure 12(a). Assume the current node of the robot is $s_{i}$ , with its adjacent nodes on the path being $s_{i - 1}$ and $s_{i + 1}$ respectively. The slope between points $s_{i - 1}$ and $s_{i + 1}$ is used to replace the slope of point $s_{i}$ . $s_{i}$ , $s_{i - 1}$ and $s_{i + 1}$ are all nodes on the path of the mobile robot, as shown in Figure 6, then

ϕ_{c} \geq max_{s_{i} \in P a t h \cap i \neq n} \arctan \frac{| z (s_{i - 1}) - z (s_{i + 1}) |}{ρ (s_{i - 1}, s_{i + 1})}

(12)

Figure 12.

Schematic diagram of the maximum climbing slope $\emptyset_{c}$ and maximum tilt angle $\emptyset_{t}$ . (a) The maximum climbing slope $\emptyset_{c}$ . (b) The maximum tilt angle $\emptyset_{t} .$

In the formula, n is the total number of nodes in the planned path, $s_{i}$ is the $i$ th node in Path, $ρ$ is the Euclidean distance between two nodes, $ρ (s_{i - 1}, s_{i + 1}) = \sqrt{{(x_{i + 1} - x_{i - 1})}^{2} + {(y_{i + 1} - y_{i - 1})}^{2}}$ , and z is the elevation value of the node.

In addition to the climbing angle, when the lateral tilt angle is large, it can also pose a threat to the safety of the mobile robot. The tilt angle of the planned path cannot exceed the maximum tilt angle $\emptyset_{t}$ that the robot is allowed to traverse (in this article, it is assumed that $\emptyset_{t}$ =10°). The improved algorithm adds a maximum tilt slope $\emptyset_{t}$ restriction in the determination of path safety as shown in Figure 12(b).

ϕ_{t} \geq max_{s_{i} \in P a t h} \arctan \frac{| z ({s_{i}}^{c 1}) - z ({s_{i}}^{c 2}) |}{ρ ({s_{i}}^{c 1}, {s_{i}}^{c 2})}

(13)

In the formula,

s_{i}^{c 1}

and

s_{i}^{c 2}

are the nodes on either side of the current node

s_{i}

, perpendicular to it.

The improved A* algorithm incorporates the robot's slope constraints by performing the following operations: when searching the neighboring nodes of the current node, the algorithm first evaluates whether these nodes satisfy the constraints of the maximum climb angle and the maximum tilt angle. If the conditions for the maximum climb angle $\emptyset_{c}$ or the maximum tilt angle $\emptyset_{t}$ (as specified in Equations 12 and 13) are not met, the node cannot be added to the OpenList. The nodes that satisfy the aforementioned two conditions are then evaluated using the improved heuristic function h(n), with the node having the smallest f(n) value being selected and added to the CloseList. This process ensures that each grid traversed by the robot during its movement adheres to the constraints of the maximum climb angle and maximum tilt angle.

To validate the effectiveness of slope constraints in avoiding areas with large slopes, the traditional A* algorithm and the A* algorithm with added slope constraints (abbreviated as SC- A*) were each tested 50 times for path planning on three different maps. The simulation results from Figure 13 show that, on the three different maps, compared to the traditional A* algorithm, the paths planned by the SC-A* algorithm noticeably avoid areas with larger slopes, and the climbing angle and tilt angle are significantly reduced. The data in Table 3 shows that the climbing angles have been reduced by 50.59%, 40.12%, and 32.85% respectively, and these angles are all kept below 30°. The tilt angles have been reduced by 91.24%, 75.84%, and 90.65% respectively, and are kept below 10°. This ensures the safety of the robot during movement. However, it is worth noting that although the SC-A* algorithm has significantly improved safety in path planning, the path length has increased by 14.92%, 30.54%, and 17.86% respectively, and the number of search nodes has increased by 29.57%, 48.78%, and 34.27% respectively. The increase in algorithm calculation time is relatively minor, at 2.09%, 0.96%, and 1.90% respectively.

Figure 13.

The simulation results of the A* algorithm and sc-A* algorithm. (a) Path of A* on map1. (b) Path of SC- A* on map1. (c) Path of A* on map2. (d) Path of SC- A* on map2. (e) Path of A* on map3. (f) Path of SC- A* on map3.

Table 3.

The calculation time, path length, number of search nodes, climbing angle, and tilt angle of the A* algorithm and SC- A* algorithm in maps 1 to 3. The values are reported as mean ± standard deviation for 50 executions.

		Average		Number of	Average
		calculation	Path length	searched	climbing	Average tilt
Map no.	Algorithms	time (ms)	(cells)	nodes	angle(°)	angle(°)
Map1	A*	903.49 ± 14.79	138.41 ± 0.85	100.1 ± 1.5	33.62 ± 0.63	18.73 + 0.82
Map1	SC- A*	922.35 ± 57.80	159.06 ± 4.67	129.7 ± 8.0	16.61 + 0.76	1.64 ± 0.45
Map2	A*	889.20 ± 21.05	136.58 ± 0.49	98.4 ± 1.8	45.89 ± 0.09	13.12 ± 0.77
Map2	SC- A*	897.73 ± 10.87	178.29 ± 0.65	146.4 ± 1.5	27.48 ± 0.72	3.17 ± 0.53
Map3	A*	920.85 ± 52.49	137.05 ± 0.77	99.2 ± 1.3	34.82 ± 0.94	15.50 ± 0.36
Map3	SC- A*	938.35 ± 17.79	161.53 ± 0.60	133.2 ± 4.2	23.38 ± 0.85	1.45 ± 0.40

3.4 Arc optimization

In practical path planning, the planned path and its curvature should be continuous, and the path should be easy for the motion control of mobile robots. Traditional A* algorithms have many path turning points, which pose a significant challenge to the load of the robot's motor and greatly affect the robot's work efficiency. The A* algorithm after node filtering has fewer turns and smaller turning angles than the traditional A* algorithm, but the planned path is still not smooth. In order to better meet the motion control of mobile robots, reduce the frequency and amplitude of motor start and stop, thereby improving the life and safety of robots, it is necessary to smooth the motion trajectory. Therefore, this article uses Bézier curves to optimize the trajectory.

The Bézier curve, developed from the Bernstein polynomial, is a type of parametric curve. Due to its simple control, it is widely used in practical engineering, mainly for smoothing line segments. Using Bézier curves to handle the corners generated by the A* algorithm can make the running path of mobile robots smoother. The Bézier curve is determined by a set of vectors called control points. Connect the given control points to form a control polygon, approximate this polygon with the Bézier curve formula, and get the Bézier curve. In the Bézier curve, n + 1 feature points can define an nth-order Bézier curve. The parametric equation of the point on the Bézier curve is:

\begin{matrix} P (t) = \sum_{i = 1}^{n} P_{i} B_{i, n (t)}, t \in [0, 1] \end{matrix}

(14)

In the formula,

P_{i}

is the position of the i point,

B_{i, n (t)}

is the Bernstein equation. It satisfies:

\begin{matrix} B_{i, n (t)} = C_{n}^{i} t^{i} {(1 - t)}^{n - 1}, i = 0, 1, \dots, n \end{matrix}

(15)

where,

C_{n}^{i}

is the coefficient of the quadratic term,

n

is the order of the Bézier curve.

Although the fourth-order Bézier curve can accurately describe complex curves by using more control points (a total of five: the starting point, the ending point, and three intermediate points), it may be more difficult to handle compared to the third-order curve. The calculation and drawing of the fourth-order Bézier curve may be more time-consuming, and sometimes the optimized path may collide with obstacles after optimization. Therefore, this paper uses the third-order Bézier curve to smooth the trajectory, as shown in Figure 14. When $n = 3$ , the third-order Bézier curve is a curve with 4 position points. As t fluctuates between 0 and 1, the parametric equation is:

\begin{matrix} P (t) = P_{0} {(1 - t)}^{3} + 3 P_{1} t {(1 - t)}^{2} + 3 P_{2} t^{2} (1 - t) + P_{3} t^{3} \end{matrix}

(16)

Figure 14.

Schematic diagram of third-order Bézier curve.

In order to smooth the path through Bézier curves and make it closer to the path after filtering, a midpoint and an eighth point near the key path node are added between every two key path nodes, and this series of path nodes are set as the control nodes of the Bézier curve. Figure 15 shows the comparison before and after the arc optimization of the path planned by the SC- A* algorithm. It can be clearly seen from the enlarged view of Figure 16 that the optimized path has been smoothed at the corners, ensuring that the robot operates smoothly during operation, reducing motor wear, avoiding imbalance in the robot itself, which is more conducive to practical control, and improving the actual motion efficiency of the mobile robot.

Figure 15.

Comparison of the path of SC-A* on Map1-3 before and after arc optimization. (a) The Path of SC- A* on Map1 before Arc Optimization. (b) The Path of SC- A* on Map1 After Arc Optimization. (c) The Path of SC- A* on Map1 before Arc Optimization. (d) The Path of SC- A* on Map1 After Arc Optimization. (e) The Path of SC- A* on Map1 before Arc Optimization. (f) The Path of SC- A* on Map1 After Arc Optimization.

Figure 16.

Enlarged view of the path before and after Arc optimization. (a) Enlarged View of the Path of SC- A* before Arc Optimization. (b) Enlarged View of the Path of SC- A* after Arc Optimization.

Figure 17.

The path of A* and improved A* on map1 to map3. (a) Path of A* and Improved A* on map1 with 50 barriers. (b) Path of A* and Improved A* on map1 with 100 barriers. (c) Path of A* and Improved A* on map2 with 50 barriers. (d) Path of A* and Improved A* on map2 with 100 barriers. (e) Path of A* and Improved A* on map3 with 50 barriers. (f) Path of A* and Improved A* on map3 with 100 barriers.

4. Algorithm simulation experiment

The effectiveness of each individual improvement has been demonstrated in Chapter 3. To validate the effectiveness of the Improved A* algorithm, which integrates all the aforementioned improvements, this study designed three different terrains (namely, concave terrain, convex terrain, and rugged terrain) on a 100 × 100 elevation grid map. Each terrain was set up with 50 and 100 obstacles respectively, resulting in six different maps for experimental validation. To compare the A* algorithm with the Improved A* algorithm, 50 simulation experiments were conducted on each map, yielding the average values for algorithm calculation time, average path length, number of key nodes, climbing angle, and tilt angle.

From the simulation results in Figure 17, it can be seen that compared to the A* algorithm, the Improved A* algorithm plans paths that avoid areas with larger slopes on all maps. Additionally, the positions of path turns are smoother. From the experimental results in Table 4, in Maps 1 to 3 with different terrains, compared to the A* algorithm, the Improved A* algorithm reduces the algorithm calculation time by 71.05% to 82.90%, the number of key nodes by 51.94% to 70.53%, and the climbing angle by 38.87% to 68.55% (all below 30°), and the tilt angle by 71.65% to 85.29% (all below 10°), under the premise that the path length increases by 14.6% to 37.84%. Under the same terrain, compared to the situation with 50 obstacles, when there are 100 obstacles, the search time of the A* algorithm will increase by about 4.32% to 7.65%, and the search time of the Improved A* algorithm will increase by about 12.76% to 32.22%. The changes in path length, search nodes, climbing angle, and tilt angle can almost be ignored.

In order to further compare the performance of the Improved A* algorithm with the A* algorithm, the following hypothesis test was conducted. The hypothesis test is a one-sided large sample population mean hypothesis test, with the null hypothesis H₀ defined as: the A* algorithm is statistically superior to the Improved A* algorithm. The significance level a = 0.01 was chosen, and the rejection region was $z \leq z_{α} = - 2.33$ . If $z \leq - 2.33$ , then the null hypothesis H₀ can be rejected, which means that the Improved A* algorithm performs statistically better than the A* algorithm.From the test results of Tables 5, 6, 7 and 8, it can be concluded that in terms of statistical performance, the Improved A* algorithm is superior to the unimproved A* algorithm in terms of calculation time, node count, climbing angle, and tilt angle.

To facilitate a more intuitive comparison between the original and improved algorithms, an uneven terrain, as depicted in Figure 18, was constructed in the Gazebo physics simulation software. This setup was used to further validate the effectiveness of the improved A* algorithm.

The robot primarily acquires external environmental information through a stereo depth camera and uses the Elevation_mapping algorithm for localization and the construction of an elevation grid map. Considering the actual dimensions of the mobile robot and the accuracy required for the grid map, the ground was divided into an elevation grid map with a resolution of 100 × 100 for the experiment. The elevation grid map generated by the Elevation_mapping algorithm is shown in Figure 19.

Table 4.
The calculation time, path length, number of search nodes, climbing angle, and tilt angle of the A* algorithm and improved A* algorithm in maps 1 to 3. The values are reported as mean ± standard deviation for 50 executions.

Average Number of Average

calculation Path length searched climbing Average tilt

Map no. Algorithms time (ms) (cells) nodes angle(°) angle(°)

Map1 with 50 A* 884.14 ± 14.60 139.52 ± 0.88 99.1 ± 1.4 31.18 ± 0.67 17.92 ± 0.69

barriers Improved A* 195.85 ± 7.28 159.89 ± 3.17 29.2 ± 5.6 14.39 ± 0.36 4.48 ± 0.81

with 100 A* 922.35 ± 9.35 137.76 ± 0.78 102.5 ± 1.7 30.09 ± 0.80 16.15 ± 0.74

barriers Improved A* 256.73 ± 15.18 189.89 ± 4.31 31.3 ± 5.3 13.87 ± 0.34 4.15 ± 0.21

Map2 with 50 A* 877.62 ± 9.69 135.74 ± 0.79 98.3 ± 0.8 41.25 ± 0.12 14.90 ± 1.19

barriers Improved A* 150.09 ± 5.52 171.58 ± 1.72 45.3 ± 4.2 13.16 ± 0.15 3.21 ± 0.36

with 100 A* 944.75 ± 10.15 136.93 ± 1.02 100.3 ± 1.1 40.96 ± 0.26 14.32 ± 0.23

barriers Improved A* 198.45 ± 25.67 172.32 ± 3.27 48.2 ± 3.7 12.88 ± 0.31 4.06 ± 0.35

Map3 with 50 A* 880.97 ± 11.61 136.93 ± 0.48 99.2 ± 1.7 33.44 ± 0.22 14.89 ± 0.84

barriers Improved A* 240.90 ± 7.38 158.10 ± 0.79 38.2 ± 2.2 20.26 ± 0.42 2.19 ± 0.22

with 100 A* 938.35 ± 26.38 138.10 ± 0.77 101.8 ± 1.3 32.34 ± 0.39 15.23 ± 0.21

barriers Improved A* 271.63 ± 17.79 156.18 ± 0.46 36.9 ± 2.7 19.77 ± 0.50 2.43 ± 0.34

			Average		Number of	Average
Map1	with 50	A*	884.14 ± 14.60	139.52 ± 0.88	99.1 ± 1.4	31.18 ± 0.67	17.92 ± 0.69
barriers	Improved A*	195.85 ± 7.28	159.89 ± 3.17	29.2 ± 5.6	14.39 ± 0.36	4.48 ± 0.81
with 100	A*	922.35 ± 9.35	137.76 ± 0.78	102.5 ± 1.7	30.09 ± 0.80	16.15 ± 0.74
barriers	Improved A*	256.73 ± 15.18	189.89 ± 4.31	31.3 ± 5.3	13.87 ± 0.34	4.15 ± 0.21
Map2	with 50	A*	877.62 ± 9.69	135.74 ± 0.79	98.3 ± 0.8	41.25 ± 0.12	14.90 ± 1.19
barriers	Improved A*	150.09 ± 5.52	171.58 ± 1.72	45.3 ± 4.2	13.16 ± 0.15	3.21 ± 0.36
with 100	A*	944.75 ± 10.15	136.93 ± 1.02	100.3 ± 1.1	40.96 ± 0.26	14.32 ± 0.23
barriers	Improved A*	198.45 ± 25.67	172.32 ± 3.27	48.2 ± 3.7	12.88 ± 0.31	4.06 ± 0.35
Map3	with 50	A*	880.97 ± 11.61	136.93 ± 0.48	99.2 ± 1.7	33.44 ± 0.22	14.89 ± 0.84
barriers	Improved A*	240.90 ± 7.38	158.10 ± 0.79	38.2 ± 2.2	20.26 ± 0.42	2.19 ± 0.22
with 100	A*	938.35 ± 26.38	138.10 ± 0.77	101.8 ± 1.3	32.34 ± 0.39	15.23 ± 0.21
barriers	Improved A*	271.63 ± 17.79	156.18 ± 0.46	36.9 ± 2.7	19.77 ± 0.50	2.43 ± 0.34

Table 5.

Results of the one-sided hypothesis test for average calculation time of the algorithms.

Map no.		H0	Test statistic	Conclusion
Map1	with 50 barriers	$μ_{I A } \geq μ_{A }$	−283.636	H0: rejected (Improved A* performs better than A*)
Map1	with 100 barriers	$μ_{I A } \geq μ_{A }$	−131.5455	H0: rejected (Improved A* performs better than A*)
Map2	with 50 barriers	$μ_{I A } \geq μ_{A }$	−395.3967	H0: rejected (Improved A* performs better than A*)
Map2	with 100 barriers	$μ_{I A } \geq μ_{A }$	−87.21854	H0: rejected (Improved A* performs better than A*)
Map3	with 50 barriers	$μ_{I A } \geq μ_{A }$	−260.1911	H0: rejected (Improved A* performs better than A*)
Map3	with 100 barriers	$μ_{I A } \geq μ_{A }$	−112.4317	H0: rejected (Improved A* performs better than A*)

Table 6.

Results of the one-sided hypothesis test for average node count of the algorithms.

Map no.		H0	Test statistic	Conclusion
Map1	with 50 barriers	$μ_{I A } \geq μ_{A }$	−37.44643	H0: rejected (Improved A* performs better than A*)
Map1	with 100 barriers	$μ_{I A } \geq μ_{A }$	−40.30189	H0: rejected (Improved A* performs better than A*)
Map2	with 50 barriers	$μ_{I A } \geq μ_{A }$	−37.85714	H0: rejected (Improved A* performs better than A*)
Map2	with 100 barriers	$μ_{I A } \geq μ_{A }$	−42.24324	H0: rejected (Improved A* performs better than A*)
Map3	with 50 barriers	$μ_{I A } \geq μ_{A }$	−83.18182	H0: rejected (Improved A* performs better than A*)
Map3	with 100 barriers	$μ_{I A } \geq μ_{A }$	−72.11111	H0: rejected (Improved A* performs better than A*)

Table 7.

Results of the one-sided hypothesis test for climbing angle of the algorithms.

Map no.		H0	Test statistic	Conclusion
Map1	with 50 barriers	$μ_{I A } \geq μ_{A }$	−139.9167	H0: rejected (Improved A* performs better than A*)
Map1	with 100 barriers	$μ_{I A } \geq μ_{A }$	−143.1176	H0: rejected (Improved A* performs better than A*)
Map2	with 50 barriers	$μ_{I A } \geq μ_{A }$	−561.8	H0: rejected (Improved A* performs better than A*)
Map2	with 100 barriers	$μ_{I A } \geq μ_{A }$	−271.7419	H0: rejected (Improved A* performs better than A*)
Map3	with 50 barriers	$μ_{I A } \geq μ_{A }$	−94.14286	H0: rejected (Improved A* performs better than A*)
Map3	with 100 barriers	$μ_{I A } \geq μ_{A }$	−75.42	H0: rejected (Improved A* performs better than A*)

Table 8.

Results of the one-sided hypothesis test for tilt angle of the algorithms.

Map no.		H0	Test statistic	Conclusion
Map1	with 50 barriers	$μ_{I A } \geq μ_{A }$	−49.77778	H0: rejected (Improved A* performs better than A*)
Map1	with 100 barriers	$μ_{I A } \geq μ_{A }$	−171.4286	H0: rejected (Improved A* performs better than A*)
Map2	with 50 barriers	$μ_{I A } \geq μ_{A }$	−97.41667	H0: rejected (Improved A* performs better than A*)
Map2	with 100 barriers	$μ_{I A } \geq μ_{A }$	−87.94286	H0: rejected (Improved A* performs better than A*)
Map3	with 50 barriers	$μ_{I A } \geq μ_{A }$	−173.1818	H0: rejected (Improved A* performs better than A*)
Map3	with 100 barriers	$μ_{I A } \geq μ_{A }$	−112.9412	H0: rejected (Improved A* performs better than A*)

Figure 18.

Uneven terrain physical simulation model.

Figure 19.

Elevation_mapping algorithm constructs elevation raster map.

Figure 20.

Comparison of A* and improved A* algorithm planning paths on simulated uneven terrain.

Using the same starting point and three different target points, the path planning results of the A* algorithm and the Improved A* algorithm are shown in Figure 20. As illustrated by the yellow paths in Figure 20(a-(c)), the paths generated by the A* algorithm exhibit issues such as sharp turns, numerous turning nodes, and lack of smoothness. Additionally, the algorithm fails to avoid areas with steep slopes that the robot cannot traverse, which could prevent the robot from reaching the target point in real-world environments. In contrast, the red paths shown in Figure 20(d-(f)) represent the paths planned by the Improved A* algorithm, which successfully avoids steep slope areas that the robot cannot navigate and produces smoother paths, facilitating better motion control of the robot.

Table 9 presents the average path planning time, path length, and number of nodes for both the A* algorithm and the Improved A* algorithm across different target points. The data indicate that, compared to the A* algorithm, the Improved A* algorithm reduces path planning time by 51.87% to 76.60% and decreases the number of nodes by 86.08% to 92.10%.The experimental results demonstrate that the Improved A* algorithm effectively completes the robot's path planning tasks. Moreover, the Improved A* algorithm outperforms the A* algorithm in terms of path optimization capability, planning efficiency, and path safety.

5. Conclusion

By using the A* algorithm for path planning of mobile robots, a collision-free path connecting the start and end points can be obtained. However, this algorithm has disadvantages such as long computation time, non-smooth paths, and unsuitability for rugged construction sites. To solve these problems, this paper proposes an Improved A* algorithm. This algorithm introduces a bidirectional alternating search strategy, which improves the efficiency of the search path. By filtering the path nodes, it not only overcomes the problem of path duplication caused by bidirectional search, but also reduces the number of key nodes, thereby reducing the difficulty of the search. By introducing slope angle constraints and tilt angle constraints, the search path is restricted to areas with smaller slopes. Finally, the path is fitted with a Bézier curve to obtain a smooth path.

Table 9.

Performance comparison of A* and Improved A* algorithms on simulated uneven terrain.

		Average calculation		Number of
Goal point	Algorithms	time (ms)	Path length (cells)	searched nodes
G₁	A*	100.86 ± 6.41	142.18 ± 4.94	109.3 ± 7.6
G₁	Improved A*	103.86 ± 11.37	117.63 ± 5.82	9.1 ± 4.20
G₂	A*	122.46 ± 15.99	167.68 ± 5.69	112.4 ± 7.3
G₂	Improved A*	128.57 ± 19.68	137.06 ± 3.27	7.3 ± 1.7
G₃	A*	104.27 ± 11.23	146.36 ± 7.31	108.6 ± 4.3
G₃	Improved A*	106.73 ± 9.91	118.30 ± 3.28	10.5 ± 3.5

Simulation results in elevation grid maps with different terrains and varying numbers of obstacles show that the Improved A* algorithm can significantly enhance the speed of path planning, reduce the number of key nodes in the search, and simultaneously decrease the climbing angle and tilt angle of the path. This makes the planned path practically feasible, ensuring the safety of the robot during movement. Furthermore, the path generated by the Improved A* algorithm is smoother, which is more conducive to the motion control of the robot.

However, the Improved A* algorithm only considers the algorithm's runtime and does not account for the time and energy costs associated with the robot adjusting its posture during actual movement. Additionally, the impact of dynamic obstacles has not been taken into consideration. Future work will involve integrating data from additional sensors, such as LiDAR and cameras, to explore how robots can perceive and dynamically model complex construction environments in real-time, thereby providing more accurate information for path planning. Efforts will also be made to combine the Improved A* algorithm with other algorithms to enable its application in multi-robot system path planning, allowing robots to share path planning information and environmental data, and achieve more advanced collaboration.

Footnotes

Authors contributions

Jvgang Guo: Methodology, Software, Writing – original draft, Writing – review & editing. Junqi Yu: Writing – original draft, Writing – review & editing. Chunyong Feng: Visualization, Writing – review & editing. Kai Wang: Data curation. Yisheng Chen: Software. Zhenping Dong: Supervision, Project administration, Funding acquisition. Jingdan Li: Writing – review & editing.

Funding

This work is supported by the Key Research and Development Program of Shaanxi under grant number (No. 2024GX-ZDCYL-02-04), the Shaanxi Provincial Technical Innovation Guidance Special (Fund) Project under grant number (No. 2023GXLH-064), and the Technology R & D project of XAUAT Engineering Technology Co., Ltd. under grant number (No. XAJD-YF24N008).

Conflict of interest

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

References

Adami

Rodrigues

Woods

, et al. (2022) Impact of VR-based training on human–robot interaction for remote operating construction robots. Journal of Computing in Civil Engineering 36(3): 04022006.

Baoxia

Miaochi

Yong

(2018) Path planning for A* algorithm based on searching 24 neighborhoods [J]. Journal of Shenyang University of TEchnology 40(02): 180–184.

Berger

(2015) An innovative multi-agent search-and-rescue path planning approach. Computers & Operations Research 53: 24–31.

Cardarelli

Digani

Sabattini

, et al. (2017) Cooperative cloud robotics architecture for the coordination of multi-AGV systems in industrial warehouses. Mechatronics 45: 1–13.

Châari

Koubâa

Bennaceur

, et al. (2014) On the adequacy of Tabu search for global robot path planning problem in grid environments. Procedia Computer Science 32: 604–613.

Chen

Sun

Dai

, et al. (2013) On the shortest and conflict-free path planning of multi-AGV system based on Dijkstra algorithm and the dynamic time-window method. Advanced Materials Research 645: 267–271.

Dijkstra

(1959) A note on two problems in connexion with graphs. Numerische Mathematik 1: 269–271.

Dorigo

Gambardella

(1997) Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1): 53–66.

Elhoseny

Tharwat

Hassanien

(2018) Bezier curve based path planning in a dynamic field using modified genetic algorithm. Journal of Computational Science 25: 339–350.

10.

Gomathi

Rajathi

(2023) Adaptive path planning for unknown environment monitoring. Journal of Ambient Intelligence and Smart Environments 15(4): 287–314.

11.

Hart

Nilsson

Raphael

(1968) A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4(2): 100–107.

12.

Hong

Sun

Tong

, et al. (2021) Improved A-Star algorithm for long-distance off-road path planning using terrain data map. ISPRS International Journal of Geo-Information 10(11): 785.

13.

Jeong

Jang

Park

, et al. (2021) Motion planning of mobile robots for autonomous navigation on uneven ground surfaces. Journal of Computing in Civil Engineering 35(3): 04021001.

14.

Kalogeiton

Ioannidis

Sirakoulis

, et al. (2019) Real-Time active SLAM and obstacle avoidance for an autonomous robot based on stereo vision. Cybernetics and Systems 50(3): 239–260.

15.

Kennedy

Eberhart

(1995) Particle swarm optimization. In: Proceedings of ICNN'95-international conference on neural networks, pp.1942–1948: ieee. https://doi.org/10.1007/springerreference_179342

16.

Kuffner

LaValle

(2000) RRT-connect: An efficient approach to single-query path planning. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), pp.995–1001: IEEE. https://doi.org/10.1109/robot.2000.844730

17.

Kyprianou

Doitsidis

Chatzichristofis

(2021) Towards the achievement of path planning with multi-robot systems in dynamic environments. Journal of Intelligent & Robotic Systems 104(1): 15.

18.

LaValle

Kuffner

(2001) Rapidly-exploring random trees: Progress and prospects: Steven m. Lavalle, Iowa state university, a james j. Kuffner, jr., university of Tokyo, Tokyo, Japan. Algorithmic and Computational Robotics: 303–307. https://doi.org/10.1201/9781439864135-43

19.

Huang

Ding

, et al. (2022a) Global path planning based on a bidirectional alternating search A* algorithm for mobile robots. Computers & Industrial Engineering 168: 108123.

20.

Jin

, et al. (2022b) A Mobile robot path planning algorithm based on improved A* algorithm and dynamic window approach. IEEE Access 10: 57736–57747.

21.

Liang

. (2009) Global path planning for mobile robot based genetic algorithm and modified simulated annealing algorithm. In: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, pp. 303–308. https://doi.org/10.1145/1543834.1543875

22.

Luo

Wang

Zheng

, et al. (2019) Research on path planning of mobile robot based on improved ant colony algorithm. Neural Computing and Applications 32(6): 1555–1566.

23.

Miao

Chen

Yan

, et al. (2021) Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering 156: 107230.

24.

Miao

Tian

Y-C

(2013) Dynamic robot path planning using an enhanced simulated annealing approach. Applied Mathematics and Computation 222: 420–437.

25.

Muhammad

Ying

Nithish

, et al. (2021) Robot-Assisted object detection for construction automation: Data and information-driven approach. IEEE/ASME Transactions on Mechatronics 26(6): 2845–2856.

26.

Pereira

Moreira

APGM

Veloso

(2018) Multi-Robot planning for perception of multiple regions of interest. In: ROBOT 2017: Third Iberian Robotics Conference, 275–286. https://doi.org/10.1007/978-3-319-70833-1_23

27.

Pütz

Simón

Hertzberg

(2018) Move base flex a highly flexible navigation framework for mobile robots. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 3416–3421. https://doi.org/10.1109/iros.2018.8593829

28.

Saeed

Recupero

Remagnino

(2020) A Boundary Node Method for path planning of mobile robots. Robotics and Autonomous Systems 123: 103320.

29.

Shang

Dai

Nie

, et al. (2020) A guide-line and key-point based a-star path planning algorithm for autonomous land vehicles. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). IEEE, 1–7. https://doi.org/10.1109/itsc45102.2020.9294336

30.

Tevyashov

Mamchenko

Migachev

, et al. (2022) Algorithm for multi-drone path planning and coverage of agricultural fields. In: Agriculture Digitalization and Organic Production: Proceedings of the First International Conference, ADOP 2021, St. Petersburg, Russia, June 7–9, 2021. Springer, 299–310.https://doi.org/10.1007/978-981-16-3349-2_25

31.

Yakoubi

Laskri

Zennir

(2016) The complete coverage for the vacuum cleaner robot using pulse-coupled neural network in dynamic environments. Journal of Ambient Intelligence and Smart Environments 8(6): 603–617.

32.

YiYue

XiaoRu

Song

(2019) Research on path planning of mobile robot based on improved A* in special environment. In: 2019 3rd International Symposium on Autonomous Systems (ISAS). IEEE, 12–16.https://doi.org/10.1109/isass.2019.8757721

33.

Yuan

Sun

(2022) Path planning of mobile robots based on an improved particle swarm optimization algorithm. Processes 11(1): 26.

34.

Zeng

Sammut

Lian

, et al. (2016) A comparison of optimization techniques for AUV path planning in environments with ocean currents. Robotics and Autonomous Systems 82: 61–72.

35.

Zhang

Zheng

, et al. (2022) Path planning for wheeled Mobile robot in partially known uneven terrain. Sensors (Basel) 22(14): 5217.

36.

Zhang

L-l

Lin

H-C

, et al. (2018) Development of path planning approach based on improved A-star algorithm in AGV system. In: IoT as a Service, pp.276–279. https://doi.org/10.1007/978-3-030-00410-1_32

37.

Zhao

Cheah

(2023) BIM-based indoor mobile robot initialization for construction automation using object detection. Automation in Construction 146: 104647.