Driven by the swift evolution of technology, indoor mobile robot path planning has become a topic of keen interest in the research community. In essence, mobile robot path planning is in the case of excluding human manipulation, the mobile robot identifies and processes the data obtained by the sensor, and calculates an optimal path which is safe and collision-free at the same time [1]. At present, the widely used global path planning algorithms currently include A-Star algorithm [2], D-Star algorithm [3], etc. Frequently applied algorithms for local path planning are the artificial potential field method [4], dynamic sliding window method [5], fuzzy logic method [6], etc. A-Star algorithm is a well-known global path planning algorithm, which is a heuristic algorithm [7] that mainly uses heuristic information to find the optimal path [8]. The optimal path is selected by the artificial potential field algorithm in a manner that the potential function decreases within the obstacles force field.
The A-star algorithm excels in its direct search methodology, effectively delivering satisfactory planning solutions, but it is plagued by poor real-time performance and issues such as deviation caused by turning angles. The artificial potential field method stands out as a prominent local path planning technique. It boasts simplicity in calculation and analysis, easy control, and superior real-time performance. However, it is prone to issues such as local minima and unreachable targets. Moreover, both of them cannot get satisfactory results in the treatment of dynamic obstacles. To address these problems, relevant scholars have proposed various improvements and optimizations to the algorithm. For instance, literature [9] described a bidirectional time-efficient A-Star algorithm for path finding, employing a multi-neighbor grid distance calculation scheme to achieve improved efficiency and smoother paths. However, this approach tends to deviate during navigation when dealing with large, complex maps. Literature [10] avoided generating paths through obstacle grid vertices by adding a priority-based child node generation strategy into the A-Star algorithm, but the path smoothness during navigation is not enough, which has certain security risks. Literature [11] improved the key node selection strategy of A-star algorithm, thus optimizing path planning in static environments to some extent, but still unable to resolve errors in dynamic environments. Literature [12] put forward an iterative searching strategy capable of skipping intermediate nodes, leading to a decrease in the number of accessed nodes and an enhancement in the overall speed of the algorithm. Nevertheless, the path still contains numerous turning points, prone to issues such as path drift. Literature [13] proposed an improved ant colony algorithm in global path search. The smoothness and calculation effect of path planning is more obvious than A-star algorithm, but the amount of data in the search process is too large to be suitable for equipment with poor performance. In terms of artificial potential field algorithms, literature [14] used the improved Pseudo-Dubins curve to smooth the path, which can obtain better local path calculation effect, but the calculation is cumbersome and the operation efficiency is poor. The study in literature [15] introduced a hierarchical modification technique to tackle the dynamic obstacle avoidance challenge in artificial potential fields, resulting in improved obstacle avoidance performance during movement. Nevertheless, it still faces issues of unreachable targets and local optima. Literature [16] proposed a method to introduce the motion direction of the robot as the control variable in the operation of the potential field function, which can effectively reduce the repulsion of obstacles other than the motion direction to the robot, eliminate the inaccessibility of unreachable target points, but increase the risk of robot collision. Literature [17] used a method of adding virtual sub target points to address the local minimum issue in potential field algorithms, but it has the shortcomings of comprehensive path planning error and excessive fold angle.
Through the above research, it can be found that in indoor unstructured complex environments, the traditional A-Star algorithm tends to encounter path slippage and corner problems when dealing with global paths [18]; The traditional artificial potential field algorithm often fails to achieve optimal path planning results during local planning [19]. Therefore, an integrated path planning algorithm was presented in this paper, which combines an angle bisector tangent optimization for the A-Star algorithm with an enhanced artificial potential field method that constructs a dynamic force field. The improved fusion algorithm introduced ideas of angle bisector tangent points to perform global path planning based on the original A-Star algorithm. Moreover, for local planning, the utilization of an improved artificial potential field algorithm optimized the effect of obstacle avoidance when obstacles are detected during path traversal, achieving autonomous obstacle avoidance and overall path optimization. This results in a smoother path trajectory, a larger detection range, and a reduction in possible drift or errors in the path.
The construction of a grid map is the premise of mobile robot to perform path planning. Grid map is popular among scholars because of its simplicity and easy implementation. In the grid map, each grid contains information about obstacle occupancy, and each occupancy information can be represented by a specific letter, where 0 represents an occupied grid and 1 represents a free grid [20]. The grid size will affect the speed of path planning, so it is important to construct grid map reasonably.
A-Star algorithm, as a heuristic search algorithm, incorporates a heuristic factor function into the Dijkstra algorithm to steer its search direction, thus allowing it to compute globally optimal paths in static settings [21]. The evaluation function of the A-Star algorithm is:
The above formula is the evaluation function of A-Star algorithm. g(
In the above formula, (
The traditional A-star algorithm can plan an effective optimal path, but there are problems with too many redundant nodes and unsmooth paths. However, heuristic factor can effectively guide the search direction of the A-star algorithm. Therefore, this paper first optimized the heuristic factor function, and then smoothed the A-Star algorithm path.
Heuristic factor plays a key role in optimal path planning, which can guide the search direction of A-star algorithm. When
Since the traditional A-Star algorithm has an unsmooth path problem in the path planning process, the optimization method of tangent point of angle bisector was introduced to optimize the A-star algorithm, which helps generate smoother paths. The optimization model is shown in Fig. 2.
Assuming that the initial node position of the mobile robot is
Step 1: determine if the three points are collinear, that is, if the node is a turning point. Make a vertical line crossing the angle bisector at the previous node of the turning point. In the figure above, the slope of edge AB is
Where:
According to the slope relation formula
Then, the coordinates of the intersection point
Step 2: make a circle with the vertical length as the radius through the intersection
The radius
Step 3: determine whether there is a next turning point. If it exists, return to step 1; Otherwise, replace the distance between nodes with an arc.
Step 4: determine whether the optimized path contains every node from the path planned by A-star algorithm. If so, optimization process completes; Otherwise, return to step 1.
The following is a simulation experiment of the improved A-star algorithm on the grid model in Fig. 1 in MATLAB, where each grid in the abscissa and ordinate represents a distance of 1m. The verification results are as follows:
As evident in Fig. 3(b), compared to Fig. 3(a), the red trajectory was obviously smoothed and optimized in the trajectories of (12,12), (26,30) two meshes. By comparing various indicators in Table 1, it is evident that the improved A-Star algorithm effectively eliminated turning points, shortened the path length, improved path smoothness, reduced the time required to search for paths, and greatly reduced the number of nodes that need to be expanded during the path planning process. This shows that the A-Star algorithm modified with the heuristic factor surpasses the traditional A-Star in smoothness of path planning, reliability, and in judging actual trajectories.
Comparison of the effects of A-Star algorithm improvement
Algorithm | Path length/m | Time for path finding/s | Number of expansion nodes | Is there a turning point |
---|---|---|---|---|
A-Star | 22.42 | 5.9 | 166 | Yes |
Improved A-Star | 21.56 | 5.5 | 59 | No |
Artificial potential field algorithm is a popular choice among local path planning algorithms. Fig. 4 illustrates the force analysis conducted on the robot within this artificial potential field.
Artificial potential field algorithm's core concept is implemented through the simulation of an imaginary force field, and its theoretical idea can be summarized as follows: the robot is abstracted into a particle with point charge in a virtual force field. The target node generates an attractive potential field that pulls the mobile robot towards it, while obstacles create a repulsive potential field that pushes it away. As the mobile robot draws closer to the target node, the gravitational field intensifies. Similarly, the repulsive force field will also increase when approaching an obstacle. Under the influence of both gravitational and repulsive potential fields, the mobile robot is propelled towards the target node and finally generates an optimal path that can avoid obstacles autonomously [22].
As the mobile robot enters the obstacle's range of influence, it is simultaneously influenced by both the repulsive force
In the above formula,
In the above equation,
Due to the presence of complex obstacle environments in practical environments, the total force field function can be modified to the sum of the gravitational function and the combined repulsive function, namely:
The net force experienced by the mobile robot at point
Through the above analysis, it can be seen that the artificial potential field algorithm has the advantages of easy implementation and high performance, but it is also prone to the problem of unreachable target points, and it cannot play a good role in identifying and avoiding local dynamic obstacles [24]. To address these limitations of the traditional artificial potential field algorithm, this paper proposed solutions. Firstly, the repulsion field parameters were modified to resolve the problem of unreachable target points. Secondly, to enable the algorithm to handle dynamic obstacles, a dynamic potential field function was constructed. This approach solved the problem of dynamic obstacle avoidance.
Although the traditional artificial potential field algorithm is relatively easy to implement, when there are obstacles around target point and target point is within the range of obstacles influence, there may be a phenomenon where the target point is unreachable. To make the magnitude of the repulsive force change as the gravitational force changes with the distance, the repulsive force function was modified by referring to the gravitational potential field function. By introducing the relative position (
In the above formula,
With the negative gradient of the repulsive force field function signifying its intensity, the repulsive force can be expressed as:
The repulsive force
The force analysis after adjusting the repulsion field parameters is shown in Fig. 5, where the x-axis and y-axis represent the distance traveled, measured in meters.
The artificial potential field being a blend of gravitational and repulsive fields, therefore, it is logical to divide the dynamic potential field into two sections: a gravity field based on relative velocity and a repulsion field based on relative velocity.
Gravity field based on relative velocity: in an indoor unstructured environment, a mobile robot faces the challenge of path planning in the presence of dynamic obstacles. By adding a relative velocity term to the traditional gravitational potential field function, a dynamic gravitational potential field function is formed. The function for the relative velocity gravitational field can be formulated as:
In the above formula, (
Then the gravity function is expressed as:
The gravity
Repulsion field based on relative velocity: similar to the dynamic gravitational force field, the relative velocity term is also added in the construction of the dynamic repulsive field. Additionally, considering that there may be dynamic obstacles in the environment, the relative velocity based on obstacles is added. Thus, the repulsion field function based on relative velocity is as follows:
In which,
In which,
For the purpose of confirming the validity of the improved algorithm, a 30m×30m grid was constructed in the MATLAB environment, and two sets of experimental comparisons were carried out to analyze the improved artificial potential field algorithm, comparing it with the traditional version. The first set of experiments selected the grid map environment in Fig. 1 for simulation comparison. The unit of horizontal and vertical axes is m. As depicted in Fig. 6, these are the experimental results.
The second set of experiments was simulated, using red circles to represent obstacles set up, to test the path planning effectiveness of the two algorithms when encountering local obstacles.
Fig. 6 reveals that in a static setting, the improved artificial potential field algorithm achieves smoother path planning and more precise obstacle detection, outperforming the traditional approach. However, in the dynamic environment portrayed in Fig. 7, the traditional algorithm fails to navigate to the target due to challenges in obstacle recognition. The lengthy path and extended runtime depicted in Fig. 7(a) are symptomatic of the complex obstacle environment, which poses a challenge for the traditional algorithm. Fortunately, the enhanced algorithm overcomes this limitation.
As Table 2 indicates, by modifying the repulsion field parameters, the challenge of inaccessible target points was conquered, the oscillation phenomenon was effectively eliminated, compared with the traditional artificial potential field algorithm. Its running time was reduced by 13.92%, the path length was reduced by 4%. By way of comparative experiments, the efficacy of the improved artificial potential field algorithm was thoroughly validated.
Comparison results of improved algorithm
Experiment Name | Algorithm | Path length/m | Run time/s | Number of cycles |
---|---|---|---|---|
Path planning testing | APF | 49.970710 | 6.186677 | 447 |
IAPF | 48.003037 | 5.430491 | 440 | |
Complex obstacle testing | APF | ∞ | ∞ | ∞ |
IAPF | 51.519690 | 6.801836 | 451 |
In indoor unstructured complex environments, neither the artificial potential field algorithm nor A-star algorithm is capable of accomplishing optimal path planning on its own. Consequently, this paper integrated these two path planning algorithms into a hybrid solution that combines the advantages of both and can complete the optimal path planning task.
During the implementation process of the hybrid path planning algorithm, the following two problems should be considered: Firstly, when the mobile robot does not enter the obstacle's radius of influence, the optimized A-star algorithm is utilized to obtain global initial paths for global path planning; Secondly, utilizing this comprehensive global path as a foundation, it is necessary to determine whether there are any reserved nodes generated by A-star algorithm within the obstacle's range of influence. If there are, further reductions should be made. Fig. 7 depicts the model for the hybrid path planning algorithm:
In Fig. 8, (
Assuming that the robot at time
The hybrid path planning algorithm proceeds in the following execution stages:
Initialize map parameters; Carry out global path planning utilizing the A-Star algorithm, while documenting and storing the path nodes for future reference; Use node pruning strategy to retain key path nodes; Treat the key path nodes as local target points in turn. If the key target node is within the radius of the obstacle, the node is deleted and the next key node is selected as the target node; With the utilization of the improved artificial potential field algorithm, the robot systematically traverses from its current location to the next sub-target, ensuring accurate path planning; Check if the robot has completed its journey to the final target node. Stop if it has; otherwise, repeat step 5 for further route calculation.
The experiment used MATLAB to conduct simulation tests on the hybrid path algorithm. The experimental environment was also set as the grid map model depicted in Fig. 1. The experiment was carried out in both dynamic and static environments, grouped according to whether the obstacles are movable or not. The figure below demonstrates the experimental results.
The above three sets of experiments were conducted in a static environment to compare the path planning information generated by the improved A-star algorithm, the improved artificial potential field algorithm, DWA algorithm, and the hybrid algorithm. The comparison was based on their respective planning path lengths, search path durations and ability to handle dynamic obstacles.
As evident from Table 3 and Fig. 9, in the context of identical obstacles, the A-Star algorithm demonstrates an ability to plan a short path with rapid search speed during the path planning process, but it does not have the ability to dynamically avoid obstacles. Despite its longer planned path and increased search duration, the artificial potential field algorithm boasts the crucial capability of dynamically steering clear of obstacles, making it a practical choice for complex indoor navigation scenarios. By fusing the benefits of the two algorithms, the hybrid approach achieves not only a shorter search path and time but also the flexibility to handle dynamic obstacles effectively.
Algorithm comparison in static environment
Algorithm | Path length/m | Search time/s | Does the algorithm have the ability to handle dynamic obstacles |
---|---|---|---|
A-Star | 45.36 | 6.72 | No |
IAPF | 48.00 | 10.43 | Yes |
DWA | 48.86 | 28.21 | Yes |
Hybrid algorithm | 46.54 | 8.14 | Yes |
The path planning experiment of the hybrid algorithm was conducted in a 30m×30m environment. In the dynamic environment, the parameters for obstacle avoidance were set to include a step increment of 0.1, a gravitational and velocity gain of 3, an obstacle detection radius of 3 units, and a repulsive gain of 5. The predefined obstacle was programmed to traverse a path from the point (12, 17) to (16, 17). The figure below demonstrates the experimental results.
The purple circles in Fig. 10(a) represent static obstacles that already exist, while the blue circles represent dynamic obstacles that appear randomly. In Fig. 10(b), green circles represent persistent dynamic obstacles, which move left and right between positions with ordinates of 3 and 17. These images compared the path under the hybrid algorithm with the static simulated global path to show the impact of the introduction of dynamic and moving obstacles on the return of the global path. In Fig. 10(a), the hybrid algorithm can effectively avoid dynamically appearing obstacles in the simulated indoor environment and return to the global path, ensuring the real-time nature of the path planning task. Mobile obstacles were introduced in Fig. 10(b). Mobile robot effectively avoided dynamic obstacles and returned to the global path, which effectively verified the effectiveness of the improved hybrid algorithm. Additionally, this enhancement significantly improved the real-time performance of path planning.
The robot platform in this paper was built on the Hands-free mobile robot platform. RPLIDAR A1 lidar was selected as the main ranging sensor. To steer the mobile robot's motions precisely, the OpenRE Board controller was selected as the primary control mechanism. According to the composition structure of the Handsfree_Stone_V3 mobile robot, the various hardware parts were assembled. The finished assembly of Handsfree_Stone_V3 is shown in Fig. 11.
The physical environment verification was conducted in a room with dimensions of 4.5 meters in length and width. The laboratory was equipped with obstacles, and the test commenced from the doorway position. As shown in Fig. 12.
This paper used Gmapping to complete the mapping of the actual environment of the Hands-free robot. The mapping results and mapping parameters are shown in Fig. 13:
After completing the mapping of the actual environment as mentioned above, the next step is a comparative analysis of the path planning prowess of the traditional A-Star hybrid DWA algorithm and the improved A-Star hybrid improved artificial potential field algorithm presented herein. The comparison was executed in a real-life setting, mirroring actual environmental conditions. The figure below demonstrates the experimental results.
The navigation effects in Fig. 14 and Fig. 15 and the data in Table 4 show that, under the condition of setting the same starting and ending points, by comparing the path length, search time and passing nodes number of the two path planning algorithms, it can be found that the hybrid algorithm proposed in this paper reduced path planning length by 10.3%, reduced the running time by 12.5%, and passed through 34 less redundant nodes. This proved that in real environments, the hybrid algorithm introduced in this paper offers distinct advantages in path planning over the traditional hybrid algorithm.
Results of algorithm comparison in real environment
Path planning algorithm | Path length/m | Number of nodes passed through | Search time/s |
---|---|---|---|
A-Star Hybrid DWA | 3.66 | 126 | 54.42 |
Hybrid algorithm in this paper | 3.24 | 92 | 48.36 |
The objective of this paper is to primarily identify and enhance the weaknesses in the conventional A-Star algorithm and the artificial potential field algorithm, thereby optimizing their performance. Firstly, the heuristic factor of A-star algorithm was adjusted, and its redundant nodes were eliminated using the node deletion strategy. Simultaneously, the path turning points of A-star algorithm were smoothed. The search time was shortened effectively. Secondly, the deficiencies of the artificial potential field algorithm were addressed in static and dynamic environments separately. In the static environment, the target unreachable problem is solved by modifying the repulsion field parameters. In the dynamic environment, the relative speed term was introduced so that the speed of the mobile robot becomes smaller when approaching the obstacle and becomes larger when it is further away. The simulation results indicated that the hybrid algorithm efficiently addressed the path planning dilemma for mobile robots within a complex and unstructured indoor space. The improved algorithm’s running time was reduced by 13.92%, and the planned path length was reduced by 4%. In the part of actual environment verification, the path planning results between the traditional hybrid algorithm and the improved algorithm was compared. The results showed that the path planning length was reduced by 10.3%, the running time was decreased by 12.5%, and 34 redundant nodes were eliminated by the hybrid algorithm presented in this paper, demonstrating greater efficiency than the traditional hybrid algorithm.