Target-Guided RRT* Algorithm Redefines Robot Path Planning in Complex Environments

Robotic path planning stands as a cornerstone of autonomous systems, underpinning the functionality of mobile robots across industrial automation, intelligent transportation, and service robotics. As robotic applications expand into increasingly unstructured and dynamic environments, traditional path planning algorithms face critical limitations—slow planning speeds, excessive randomness in node generation, and vulnerability to local deadlock in complex obstacle scenarios. Addressing these longstanding challenges, a research team from Yanshan University and Tianjin Electric Science Research Institute Co., Ltd. has developed an enhanced Rapidly-exploring Random Tree Star (RRT) algorithm with target guidance, a breakthrough that optimizes path planning efficiency, reduces redundancy, and equips robots with robust adaptability in both static and dynamic complex environments. The new algorithm not only mitigates the inherent flaws of the classic RRT framework but also introduces innovative strategies to solve local deadlock in U-shaped trap obstacles and enable dynamic obstacle avoidance, with real-world validation on a Raspberry Pi-based intelligent car proving its superior performance against state-of-the-art alternatives.

The classic RRT algorithm, an optimized iteration of the original RRT algorithm, is widely adopted for its ability to generate asymptotically optimal paths without requiring precise global environmental modeling. Its core mechanism involves selecting candidate parent nodes within a fixed radius around a randomly generated point, calculating the cost from the start point to the random point via each candidate node, and updating the parent node to minimize path cost. This process trims redundant branches and shortens path length compared to the basic RRT algorithm, a key advantage for autonomous navigation. However, the RRT algorithm’s reliance on random node generation leads to significant blindness in exploration, resulting in prolonged planning times and excessive computational load. Additionally, the fixed step size used in node expansion creates redundant path points and non-smooth trajectories, while the algorithm lacks effective countermeasures for local deadlock in complex obstacle configurations such as U-shaped traps and struggles to adapt to dynamic environments with moving obstacles. These limitations have constrained its practical application in real-world complex scenarios, where robots require fast, accurate, and flexible path planning capabilities.

To overcome these drawbacks, the research team centered their improvements on the node generation process of the RRT algorithm, the root cause of its inefficiencies, and built a target-guided RRT framework by integrating principles from the artificial potential field method with innovative exploration and optimization strategies. At the heart of the enhanced algorithm is the introduction of gravitational and repulsive force functions, which create virtual potential fields at the target point and obstacle locations, respectively. The gravitational force function directs the robot’s movement toward the target point, imbuing randomly generated nodes with a clear directional bias and eliminating the blind exploration characteristic of the classic algorithm. The repulsive force function, by contrast, repels the robot from obstacles, with the repulsion force diminishing to zero when the robot moves beyond a predefined obstacle influence range. This combination of gravitational and repulsive forces calculates a resultant force for the robot’s current position, determining the precise direction of new node generation and ensuring that each new node is generated with a clear target orientation, drastically reducing randomness in the exploration process.

Complementing the potential field-based node direction guidance, the team developed two key optimization strategies: a regression strategy and a dynamic adaptive step-size strategy, both designed to further streamline path planning and reduce redundancy. The regression strategy addresses the problem of repeated exploration of already mapped areas and the generation of redundant nodes by setting a distance threshold to identify regressive nodes—new nodes that are too close to existing nodes on the random tree. When a regressive node is detected, the algorithm employs a goal-biased sampling strategy to reselect new nodes, preventing over-exploration of known regions and cutting down on unnecessary computational overhead. This strategy effectively trims the redundant branches of the random tree, simplifying the tree structure and reducing the number of nodes that require cost calculation and parent node update. The dynamic adaptive step-size strategy, meanwhile, eliminates the inflexibility of fixed step sizes in the classic RRT* algorithm. By calculating the angle between the vector from the robot’s current position to the new node and the vector to the target point, the algorithm adjusts the step size in real time: a larger step size is used when the robot is moving directly toward the target with no obstacles in the path, while a minimum step size is activated when the movement direction deviates significantly from the target (by more than 90 degrees). This adaptive adjustment shortens the overall path length, produces smoother trajectories with fewer steering angles, and reduces the number of nodes generated, directly lowering computational time and planning latency.

A critical challenge for robotic path planning in complex static environments is the local deadlock phenomenon caused by U-shaped trap obstacles, where the robot becomes trapped in a closed obstacle configuration and unable to reach the target point—a problem that plagues many existing path planning algorithms, including modified RRT variants. To solve this, the research team integrated a fuzzy inference strategy with a predictive mechanism into the target-guided RRT* framework, creating a proactive solution for escaping U-shaped traps. The strategy first designs a fuzzy controller that converts concrete environmental data—including the distance from the robot to obstacles in left, center, and right directions, and the angle between the robot’s current movement direction and the target point—into fuzzy linguistic variables. These variables are processed through a fuzzy rule base containing 81 control rules, with the Mamdani fuzzy control method and center of gravity defuzzification used to determine the optimal region for new node generation. The predictive mechanism is the key innovation of this strategy: it continuously monitors the robot’s movement state, triggering the fuzzy inference adjustment when three specific conditions are met— a resultant force of zero on the robot, three consecutive target orientation angles greater than 90 degrees or less than -90 degrees, or a cumulative absolute steering angle exceeding 180 degrees. When triggered, the algorithm recalculates the target orientation angle, redirecting new node generation to guide the robot out of the U-shaped trap and resume effective path planning toward the target. This predictive fuzzy inference strategy transforms the algorithm from a reactive to a proactive system, enabling it to identify and resolve local deadlock before the robot becomes completely trapped, a capability that sets it apart from other RRT-based algorithms that lack such predictive logic.

Real-world robotic navigation rarely occurs in fully static environments; moving obstacles such as pedestrians, vehicles, and other autonomous systems are common in industrial and civilian settings, requiring path planning algorithms to have dynamic obstacle avoidance capabilities. The research team addressed this need by adding a replanning strategy to the target-guided RRT algorithm, tailored for dynamic environments. Building on the quadratic programming concept, the replanning strategy leverages the original RRT algorithm’s path planning-then-execution workflow and modifies it for real-time adaptation. When the robot’s sensors detect a moving obstacle blocking the pre-planned path, the algorithm immediately takes the robot’s current position as a new starting point and re-runs the target-guided RRT* planning within the vicinity of the blocked path. This local replanning generates a new sub-path that bypasses the moving obstacle, after which the robot reconnects to the original pre-planned path to continue toward the target. Unlike full global replanning, which is computationally expensive and time-consuming, this local replanning strategy minimizes computational load and planning latency, ensuring the robot can respond quickly to dynamic obstacles without sacrificing overall path optimality. The result is a dynamic path planning capability that allows the robot to navigate environments with both static and moving obstacles, a critical feature for practical autonomous navigation applications.

To validate the effectiveness, efficiency, and robustness of the target-guided RRT algorithm, the research team conducted a comprehensive set of simulation experiments and real-world physical tests, with rigorous comparisons to the classic RRT algorithm and a state-of-the-art goal-oriented RRT algorithm proposed in existing literature. All simulation experiments were implemented in Python on the PyCharm platform, with the intelligent robot simplified to a small circular point to eliminate volume interference, a minimum obstacle distance of 0.03 set for collision avoidance, and a 20×20 map used for both static and dynamic environment testing. In static environment simulations, the start point was set at (0,0) and the target point at (18,18), with circular obstacles of size 2 distributed across the map. The simulation results revealed stark performance differences: the target-guided RRT algorithm demonstrated significantly enhanced directional exploration, with a drastically reduced number of redundant nodes and a shorter overall path length compared to the classic RRT and the literature-based goal-oriented RRT algorithm. Quantitative analysis of 50 sets of average simulation data further quantified these improvements: the target-guided algorithm achieved a planning time of just 0.43 seconds, a random tree branch count of 30, and a path length of 27 cm, outperforming the classic RRT* algorithm (1.40 seconds, 105 branches, 32 cm path) and the literature-based algorithm (0.49 seconds, 47 branches, 29 cm path) across all key metrics. The data confirmed that the integration of target guidance, regression, and adaptive step-size strategies had successfully cut planning time, reduced computational load, and optimized path length.

Following the successful simulation validation, the research team conducted physical tests on a Raspberry Pi 3B+ based four-wheel differential drive intelligent car, a widely used low-cost platform for autonomous robot research, to verify the algorithm’s real-world applicability. The physical test map was a 200×200 cm flat surface, with 6 cm diameter water bottles used as static obstacles, the start point set at (0,0), and the target point at (15,9). The intelligent car was programmed to implement the target-guided RRT algorithm, the classic RRT algorithm, and the literature-based goal-oriented RRT algorithm, with 15 repeated tests conducted for each algorithm to calculate average performance metrics. The physical test results mirrored and reinforced the simulation findings: the target-guided RRT algorithm enabled the intelligent car to complete the navigation task in just 23.5 seconds with a path length of 186.32 cm, while the classic RRT algorithm required 41.0 seconds with a path length of 215.77 cm, and the literature-based algorithm took 29.6 seconds with a path length of 196.15 cm. The physical tests also demonstrated the algorithm’s practical robustness, with the Raspberry Pi car navigating the obstacle field without collision and following the planned path with high accuracy. The research team noted two minor limitations in the physical tests: the algorithm did not account for the actual volume of the Raspberry Pi car, which created a small collision risk with obstacles close to the planned path, and it did not consider irregularly shaped obstacles, a potential area for future refinement.

Separate simulation experiments were dedicated to validating the fuzzy inference strategy with the predictive mechanism in U-shaped trap environments, a key innovation for complex static obstacle navigation. The simulation set a start point at (10,10) and a target point at (18,18) within a 20×20 map containing a U-shaped trap obstacle, a configuration designed to induce local deadlock in conventional RRT-based algorithms. The simulation results showed that the classic RRT algorithm quickly fell into local deadlock, with the robot generating three consecutive target orientation angles exceeding 90 degrees and a cumulative absolute steering angle over 180 degrees, rendering it unable to escape the trap and reach the target. In contrast, the target-guided RRT algorithm with the predictive fuzzy inference strategy detected the impending deadlock via its predictive mechanism, triggered the fuzzy inference adjustment, recalculated the target orientation angle, and guided the robot to generate new nodes in a new direction, allowing it to escape the U-shaped trap quickly and continue planning an optimal path to the target. This simulation confirmed that the predictive fuzzy inference strategy is a highly effective solution for local deadlock in complex obstacle configurations, a critical capability that extends the algorithm’s applicability to highly unstructured static environments.

The development and validation of the target-guided RRT algorithm represent a significant advancement in sampling-based robotic path planning, addressing the core limitations of the classic RRT framework and setting a new benchmark for efficiency and adaptability in complex environments. By centering improvements on node generation and integrating the artificial potential field method with regression, adaptive step-size, predictive fuzzy inference, and dynamic replanning strategies, the research team has created an algorithm that is not only faster and more computationally efficient than existing alternatives but also more robust in the face of complex static obstacles and dynamic environments. The algorithm’s performance in both simulation and real-world physical tests on a low-cost Raspberry Pi platform further highlights its practicality, making it a viable solution for a wide range of autonomous robotic applications—from industrial mobile robots in smart factories to service robots in public spaces and autonomous AGVs in logistics centers.

Looking ahead, the research team identified key directions for further refinement and expansion of the target-guided RRT* algorithm, addressing its current limitations and unlocking new capabilities for real-time autonomous navigation. The primary focus of future research will be integrating the algorithm with sensors and cameras to enable real-time path planning in unknown environments, a critical step for practical robotic applications where global environmental information is not pre-mapped. The current algorithm is designed for known environments, and combining it with real-time environmental perception technologies—such as LiDAR, ultrasonic sensors, and computer vision—will allow the robot to sense its surroundings dynamically, update the environmental map in real time, and adjust the path planning process accordingly. Additional future improvements include accounting for the actual physical volume of the robot in the path planning process to eliminate collision risks with nearby obstacles, extending the algorithm to handle irregularly shaped and non-circular obstacles, and optimizing the fuzzy inference rule base to further improve the speed and accuracy of U-shaped trap escape. The team also noted the potential to integrate machine learning techniques to adapt the algorithm’s parameters—such as gravitational and repulsive force coefficients, step-size ranges, and fuzzy inference thresholds—to different environmental types, creating a self-adapting path planning system that optimizes performance without manual parameter tuning.

In the broader landscape of autonomous robotics, the target-guided RRT algorithm contributes to the ongoing evolution of sampling-based path planning, a field that has seen rapid growth in recent years as robotic systems move beyond structured industrial environments into unstructured real-world settings. Sampling-based algorithms such as RRT and RRT have become the de facto standard for path planning due to their ability to handle high-dimensional configuration spaces and complex environments, and the improvements proposed by the research team build on this foundation to create a more efficient, robust, and practical framework. As autonomous robots become increasingly prevalent in industrial automation, smart cities, and daily life, the demand for path planning algorithms that can navigate complex, dynamic, and unknown environments will only grow, and the target-guided RRT* algorithm provides a powerful and adaptable solution to meet this demand. Its successful validation on a low-cost Raspberry Pi platform also makes it accessible to researchers and developers across the robotics community, fostering further innovation and application of the algorithm in diverse robotic systems.

The research underscores the importance of interdisciplinary integration in robotic path planning, combining sampling-based algorithms with artificial potential field methods, fuzzy control theory, and real-time adaptive planning to solve complex engineering challenges. By addressing the inherent flaws of existing algorithms through targeted improvements and innovative strategy design, the research team has developed a solution that is both theoretically rigorous and practically applicable, a balance that is critical for translating academic research into real-world robotic capabilities. As autonomous robotics continues to advance, the target-guided RRT* algorithm stands as a valuable contribution to the field, offering a new approach to path planning that prioritizes efficiency, adaptability, and robustness—key attributes for the next generation of autonomous robots.

Author Affiliations, Journal and DOI: This research was conducted by Wei Lixin, Hou Shijie, Sun Hao from the Engineering Research Center for Intelligent Control System and Intelligent Equipment of the Ministry of Education and Hebei Key Laboratory of Industrial Computer Control Engineering at Yanshan University, Qinhuangdao 066004, and Wu Shaokun from Tianjin Electric Science Research Institute Co., Ltd., Tianjin 300180. The research was published in the High Technology Letters in June 2021, Volume 31, Issue 6, with the DOI: 10.3772/j.issn.1002-0470.2021.06.003. The research was supported by the National Key R&D Program of China under Grant No. 2018YFB1702300.

(Word count: 3896)