New Algorithm Navigates Robots Through Complex Environments with Greater Efficiency
In the rapidly evolving landscape of robotics and autonomous systems, a critical challenge remains: how to enable machines to navigate complex, obstacle-filled environments efficiently and safely. This challenge is particularly acute for mobile robots operating in dynamic industrial settings, where precision, speed, and reliability are paramount. A team of researchers from Qilu University of Technology (Shandong Academy of Sciences) in China has taken a significant step forward in addressing this problem. They have developed a novel path-planning algorithm that dramatically improves the performance of mobile robots, specifically a disk-shaped model, in a variety of challenging scenarios.
The research, spearheaded by Han Fengjian, a master’s student in the School of Electrical Engineering and Automation, alongside collaborators Qiu Shubo and Liu Haiying from the School of Electronic and Information Engineering, introduces an enhanced version of the Bidirectional Rapidly-exploring Random Tree (BI-RRT) algorithm. The work, led by corresponding author Li Qinghua, an expert in machine learning and computer vision, was published in the peer-reviewed journal Shandong Science. The team’s innovation lies in a sophisticated blend of target-oriented guidance, a greedy optimization strategy, and a specialized collision-detection method, all designed to overcome the fundamental limitations of traditional path-planning approaches.
The quest for efficient robotic navigation has long been a focal point of artificial intelligence and automation research. As industries from manufacturing to logistics increasingly deploy autonomous mobile robots (AMRs), the demand for smarter, faster, and more reliable path-planning solutions has intensified. The environments these robots must traverse are often far from ideal—cluttered warehouses, narrow factory aisles, or complex urban settings—all of which are rife with obstacles. A robot’s ability to chart a course from point A to point B is not just a matter of reaching a destination; it is a direct determinant of operational efficiency, energy consumption, and overall system safety. An inefficient path with numerous sharp turns can lead to excessive wear and tear on the robot’s mechanics, increased travel time, and a higher risk of collisions.
Traditional algorithms have offered various solutions, each with its own trade-offs. The A* algorithm, a staple in grid-based pathfinding, is excellent for finding the shortest path in low-dimensional spaces but becomes computationally prohibitive as the complexity of the environment increases. Similarly, bio-inspired methods like ant colony optimization or genetic algorithms can find good solutions but often require significant computational time to converge, making them less suitable for real-time applications. The Artificial Potential Field method, while intuitive, is notorious for getting trapped in local minima, causing a robot to become stuck when faced with certain obstacle configurations.
This is where sampling-based algorithms like the Rapidly-exploring Random Tree (RRT) have gained prominence. Introduced by Steven M. LaValle and James J. Kuffner in the late 1990s, the RRT algorithm revolutionized high-dimensional motion planning by sidestepping the need to model the entire environment explicitly. Instead of trying to map every possible configuration, RRT builds a tree of feasible paths by randomly sampling points in the configuration space and incrementally growing a tree from the starting point toward these samples. This approach is particularly powerful for complex systems like robotic arms with many degrees of freedom, where the “configuration space” is vast and difficult to represent.
However, the original RRT has a critical flaw: its growth is purely random. While it is guaranteed to find a path if one exists (a property known as probabilistic completeness), it does so in a haphazard manner, often exploring large areas of free space that are irrelevant to the goal. This lack of “target orientation” results in a slow convergence rate and a path that is typically far from optimal, filled with unnecessary twists and turns.
To address this, the bidirectional variant, BI-RRT, was developed. The core idea is elegant: instead of growing a single tree from the start, grow two trees simultaneously—one from the start and one from the goal. The algorithm then alternates between extending these two trees, hoping that they will eventually meet in the middle. This bidirectional search dramatically improves the convergence speed compared to the single-tree RRT, as the two trees are effectively “reaching” for each other, reducing the volume of space that needs to be explored.
Even with this improvement, BI-RRT still inherits the core weakness of its predecessor: the direction of growth is determined by a randomly sampled point. The algorithm has no inherent knowledge of where the goal lies relative to the current tree, leading to inefficient exploration. It might spend valuable computation time growing a branch in the wrong direction, only to later discover a more direct route. Furthermore, the resulting path, while functional, is often a jagged, piecewise-linear route with a high number of inflection points—sharp changes in direction that are inefficient for a physical robot to execute.
The research team led by Han and Li recognized that to achieve a truly efficient and practical solution, they needed to imbue the algorithm with a sense of purpose. Their solution was to fundamentally re-engineer the node-expansion process. Instead of using a single random point to guide the growth of a tree, they introduced a dual-vector guidance system. When it’s time to expand a tree, the algorithm doesn’t just look at a random point in space. It considers the position of the other tree’s closest node to that random point. By combining the vector from the current tree’s nearest node to the random point with the vector from the current tree’s nearest node to the other tree’s nearest node, the algorithm calculates a new, more intelligent direction for growth.
This is where the concept of the “orientation coefficient” comes into play. This coefficient, denoted as k, acts as a weighting factor that determines how much influence the “toward-the-other-tree” vector has on the final growth direction. If k is too low, the algorithm behaves almost like the standard BI-RRT, with weak goal bias. If k is too high, the algorithm might become overly aggressive, potentially causing the tree to grow in a way that misses viable paths. Through extensive experimentation, the team found that a value of k=1.0 provided the optimal balance, leading to the fastest average planning time across a variety of environments.
This target-oriented approach is a game-changer. It transforms the algorithm from a blind explorer into a focused navigator. By constantly biasing the growth of each tree toward the position of the other, the two trees are far more likely to meet quickly. The researchers’ complexity analysis supports this, showing that the effective nodes in the “forward growth zone” are significantly increased, reducing the number of wasted collision checks by an estimated 50% compared to a purely random expansion. This translates directly into faster convergence, as the algorithm spends less time exploring dead ends.
While faster convergence is a major achievement, the quality of the resulting path is equally important. A path that is short but full of sharp turns is not practical for a real-world robot. This is the second major contribution of the team’s work: the integration of a greedy path-smoothing algorithm. After the two trees have connected and an initial path has been found, the algorithm doesn’t stop there. It initiates a post-processing phase to refine the route.
The smoothing process is both simple and effective. It starts at the goal point and works backward. The algorithm attempts to draw a straight line from the current point all the way back to the starting point. If this line is clear of obstacles, the entire segment of the original path between those two points is replaced by this single, direct line. If the line intersects an obstacle, the algorithm steps back to the last point where the connection was clear and uses that as the next anchor point. This process repeats iteratively, “pulling” the path taut like a string, removing all unnecessary intermediate waypoints.
The result is a path that is not only found quickly but is also remarkably smooth. The researchers’ experimental data is striking. In a broad, open environment, their improved algorithm reduced the number of inflection points—the sharp turns—by a staggering 95% compared to the standard BI-RRT and by 89% compared to a basic target-oriented BI-RRT without smoothing. This reduction was consistent across all tested environments, including narrow channels, grid-like obstacle fields, and complex mazes. In a maze environment, the number of turns was cut by 91% and 83% respectively. For a disk-shaped mobile robot, which must physically turn its entire body at each inflection point, this translates to a massive reduction in mechanical stress, energy consumption, and travel time.
To ensure the safety and feasibility of every new node added to the tree, the team also developed a specialized collision-detection method tailored to their disk-shaped robot model. Standard collision detection might check a single point, but a physical robot occupies space. Their “k-point collision detection” algorithm models the robot as a disk and checks not just the center point, but k points distributed around its circumference. In their implementation, they used k=50, creating a high-resolution approximation of the robot’s circular footprint. Only if all 50 points are in free space is a new node considered valid. This robust method prevents the robot from planning a path that would result in a collision, even if the center of the robot appears to be in the clear.
The team rigorously tested their algorithm in a series of simulations using the MATLAB platform. They created four distinct virtual environments to mimic real-world challenges: a broad, open area; a narrow channel; a grid of rectangular obstacles; and a complex maze. For each environment, they ran 50 simulations and compared their improved BI-RRT against the standard BI-RRT and a basic target-oriented BI-RRT. The results were unequivocal.
In terms of speed, their algorithm found a path in a fraction of the time. While the standard BI-RRT required hundreds of iterations to converge, the improved version typically succeeded in under 100. This represents a significant acceleration in planning speed. The average planning time was reduced by nearly 28% compared to the standard algorithm. The path lengths were also consistently shorter, indicating a more direct and efficient route.
The most visually compelling evidence of their success is in the quality of the planned paths. The visualizations from their experiments show a clear evolution. The standard BI-RRT produces a jagged, zig-zagging line that snakes through the environment. The target-oriented version is straighter but still has many turns. The final, smoothed path from their improved algorithm is a near-continuous curve, often consisting of just a few long, sweeping arcs that elegantly navigate around obstacles.
This research represents a significant leap forward in practical robotics. It is not just a theoretical exercise; it is a solution designed with real-world constraints in mind. The algorithm is computationally efficient, robust, and produces high-quality, executable paths. The work by Han Fengjian, Qiu Shubo, Li Qinghua, and Liu Haiying at Qilu University of Technology provides a powerful new tool for engineers and developers working on autonomous systems. It demonstrates that by thoughtfully combining existing concepts—target bias, bidirectional search, and greedy optimization—with a novel approach to collision detection, it is possible to create a path-planning algorithm that is greater than the sum of its parts. Their findings pave the way for more agile, efficient, and reliable mobile robots that can operate seamlessly in the complex, unstructured environments of the modern world.
By Han Fengjian, Qiu Shubo, Li Qinghua, and Liu Haiying of Qilu University of Technology (Shandong Academy of Sciences), published in Shandong Science, DOI: 10.3976/j.issn.1002-4026.2021.03.015