Abstract : To address the issue of high randomness in path planning for mobile robots using the Rapid Tree Spreading (RRT) algorithm, a target gravity-based RRT path planning algorithm is proposed. This algorithm introduces a target gravity function to drive the spreading random tree towards the target point. Simulation results show that this algorithm improves the efficiency of robot path planning in complex environments, obtains near-shortest paths, and exhibits repeatability for the same task, safely avoiding obstacles.
Keywords: Path planning; Rapid expanding random tree (RRT); Objective gravity function
Document Identification Code: A Chinese Library Classification Number : TP24
The Improved RRT Path Planning Algorithm Based on Unknown Environment
SUN Lina, SHEN Zhengjun
(College of Automation & Electronic Engineering , Qingdao University of Science and Technology, 266042, China)
Abstract: Aiming to solve the uncertainty using rapidly-exploring random tree (RRT) for path planning algorithm, an algorithm of mobile robot path planning based on target gravity is proposed. The algorithm introduces target gravitational function, which makes the random tree grow toward the target. Simulation results show that the algorithm improves path planning efficiency in the complex environment; the path is close to the shortest path, avoids obstacles safely and has a certain repeatability for the planning of the same task.
Key Words: Path Planning; Rapidly-Exploring Random Tree (RRT); target gravitational function
Path planning is an important aspect of mobile robot research, primarily addressing how to find an optimal path from the starting point to the destination within a workspace, and how to safely and collision-free bypass obstacles during movement. In unknown environments, robots lack prior knowledge and cannot perform offline global planning; they can only plan local paths based on real-time detected local environmental information. Researchers have proposed numerous solutions and strategies for planning a global path that is optimal [1,2] . However, as the environment becomes more complex or the number of obstacles increases, how to avoid oscillations and deadlocks, and how to ensure that the robot's path is globally optimal or near optimal, remain unresolved issues.
Rapidly Expanding Random Tree (RRT) is a widely used sampling-based single-query motion planning method. It guides the search through blank areas by randomly sampling points in the state space, thus finding a path from the starting point to the target point. It is suitable for path planning in complex environments and changing scenarios. However, the randomness of sampling in the RRT algorithm leads to problems such as low real-time performance, poor repeatability when performing the same task, and difficulty in planning the optimal path.
Currently, many improvements have been made to the RRT algorithm, such as heuristic RRT algorithms and rolling window-based RRT algorithms [3-5] . However, the generated paths may be circuitous or have obvious corners, making the paths unsmooth; or deadlock oscillations may occur. To address this, this paper introduces the target gravity from the artificial potential field method to make the planned path closer to the optimal or suboptimal, and improves the defect of unsmooth paths. By reasonably setting the gravity coefficient, the problem of local minima is overcome.
1. RRT Algorithm Analysis
The RRT algorithm uses an initial point in the state space as the root node, expands it through random sampling, and gradually adds leaf nodes to generate a random expansion tree. When the leaf nodes of the random tree contain the target point or points in the target region, a path from the initial point to the target point composed of the leaf nodes of the random tree is the path planning.
Figure 1. Construction of RRT
Fig. 1 The RRT construction
Because the RRT algorithm plans according to the growth path of tree branches, the planned path sometimes approaches the shortest path and sometimes deviates from it, lacking smoothness and repeatability for the same task. The algorithm's inherent randomness and other drawbacks limit its application in mobile robots.
2. Improved RRT Algorithm
By introducing the concept of target gravity from the artificial potential field method into the RRT algorithm, the random tree is guided to grow in the direction of the target, which greatly reduces the planning time, improves the real-time performance of the algorithm, ensures the optimality of the planned path, improves the disadvantage of non-smooth path, avoids the generation of local minima, and greatly enhances the algorithm's ability in path planning.
When adding new leaf nodes using the RRT algorithm, the target gravity function influences the selection of new nodes by calculating the gravitational force from each node to the target, guiding the random tree to grow in the direction of the target.
3. Simulation Analysis
Figure 2. Path planned by the RRT algorithm
Fig.3 The path planning for RRT algorithm
Figure 3. Path planned after algorithm improvement
Fig.3 The path planning for improved RRT algorithm
Simulation results show that by reasonably setting the gravity coefficient, the improved algorithm retains the characteristic of searching in open areas in the RRT algorithm, which can quickly bypass obstacles to find feasible paths, greatly reduce unnecessary expansion, improve the real-time performance of robot motion, and make the generated path relatively smooth, thus meeting the path planning needs of robots in complex environments.
4. Conclusion
This paper addresses the path planning problem for mobile robots in complex environments. Based on the randomized expanding tree algorithm, an improvement is made by incorporating the target gravity function of the potential field method. The improved algorithm guides new leaf nodes to expand towards the target direction, reducing the number of sampling points, significantly shortening the planning time, and resulting in a path closer to optimal or suboptimal. Simultaneously, it improves the repeatability of the robot performing the same task, and the path becomes smoother. Extensive simulation results demonstrate that the algorithm significantly improves robot planning efficiency, possesses high real-time computational performance, and is suitable for practical robot applications.
References
[1] Zhang Chungang, Xi Yugeng. Rolling path planning and safety analysis of mobile robots in dynamic unknown environment. Control Theory and Applications, 2003, 20(1): 37-44.
[2] Wang Li. Research on path planning methods for mobile robots [D]. Master's thesis, Northwestern Polytechnical University. 2007, 3.
[3] Kang Liang, Zhao Chunxia, Guo Jianhui. Improved path planning for mobile robots based on RRT algorithm under unknown conditions [J]. Pattern Recognition and Artificial Intelligence. 2009, 22(3): 337-343.
[4] MelchiorNA, SimmonsR. Particle RRT for Path Planning with Uncertainty[J]. Proc of the IEEE International Conference on Robotics and Automation. Roma, Italy, 2007:1617- 1624.
[5] Feng Lin, Jia Jinghui. An improved RRT path planning algorithm based on comparison optimization [J]. Computer Engineering and Applications, 2011, 47 (3): 210-213.
[6] Wang Bin, Jin Minghe, Xie Zongwu, et al. Heuristic-based fast extended random tree path planning algorithm [J]. Mechanical Manufacturing, 2007, 45 (12): 1-4.
[7] Song Jinze, Dai Bin, Shan Enzhong, et al. An improved RRT path planning algorithm [J]. Acta Electronica Sinica, 2010, 2A (38): 225-228.
[8] Gao Yunfeng, Huang Hai. Path planning method based on potential field principle in complex environment[J]. Robot, 2004, 26(2):114-118.
