A Novel AGV Path Planning Approach for Narrow Channels Based on the Bi-RRT Algorithm with a Failure Rate Threshold

Bin Wu, Wei Zhang, Xiaonan Chi, Di Jiang, Yi Yang, Yi LuSensors 2023 · DOI

TL;DR

This paper introduces a new path planning algorithm, NCB-RRT, designed to improve the efficiency and success rate of Automated Guided Vehicles (AGVs) navigating complex, narrow environments. By combining a bidirectional search with a novel three-stage search strategy and path optimization techniques, NCB-RRT significantly outperforms existing methods in challenging scenarios.

What Problem Does This Paper Address?

Automated Guided Vehicles (AGVs) are increasingly vital in industrial automation, but their path planning in confined spaces like narrow warehouse aisles or factory corridors remains a significant challenge. Traditional algorithms, such as the Rapidly-exploring Random Tree (RRT), struggle with these environments, leading to slow convergence, inefficient paths, and a high failure rate. Existing improvements often increase computational cost or are not well-suited for the specific constraints of narrow channels. This paper aims to bridge this gap by developing an algorithm that is both effective and efficient in these demanding situations.

Methods

The proposed Narrow Channel Bi-directional Rapidly-exploring Random Tree (NCB-RRT) algorithm builds upon the Bi-RRT approach by introducing several key innovations:

  • Balanced Growth Strategy: Instead of growing two trees (from start and goal) equally, NCB-RRT prioritizes the growth of the tree with a lower "cost" (a combination of node count and distance to the target). This aims for more uniform sampling and prevents one tree from getting "stuck."
  • Three-Stage Search Strategy: This is a core novelty. The algorithm dynamically selects one of three search strategies (Adaptive Sector Search, Dynamic Right Angle Search, or Target Biased RRT) based on a real-time "search failure rate threshold" (SFRT). This allows the algorithm to adapt its exploration based on the complexity of the environment.
  • Parent Node Re-selection and Path Pruning: Inspired by RRT*, NCB-RRT incorporates a strategy to re-select parent nodes for newly added nodes, reducing redundancy. A triangle pruning strategy is also applied to shorten the path and remove unnecessary turns.
  • Bezier Curve Path Smoothing: To ensure smooth and practical AGV movement, the final path is smoothed using piecewise quadratic Bezier curves, making turns more gradual and suitable for AGV steering.

Datasets

The paper does not explicitly mention training datasets. Instead, it evaluates the proposed algorithm using five distinct simulation environments (A through E) designed to represent varying levels of complexity, from simple open spaces to dense, narrow channels. These environments are based on existing research benchmarks and are visualized in Figure 8.

Key Insights and Ideas

  • Adaptive Search is Crucial: The most significant insight is the effectiveness of dynamically switching search strategies based on real-time environmental complexity (measured by the SFRT). This allows the algorithm to leverage the strengths of different exploration methods in different scenarios.
  • Bi-directional Search Benefits from Balancing: Simply having two trees grow isn't enough. Actively balancing their growth based on cost indicators is key to improving efficiency in complex environments.
  • Post-processing Matters: Path pruning and smoothing are not just cosmetic; they significantly reduce path length, the number of turns, and improve the overall practicality for AGV operation.
  • Narrow Channels are a Unique Challenge: The paper highlights that while many algorithms perform reasonably well in open spaces, their performance degrades significantly in narrow environments, underscoring the need for specialized approaches.

Key Results

The NCB-RRT algorithm demonstrated superior performance across various metrics compared to RRT, RRT*, and Bi-RRT:

  • Success Rate: Achieved a significant increase in success rate, up to 2400% higher than RRT, 1900% higher than RRT*, and 11.11% higher than Bi-RRT in narrow channel environments.
  • Path Length: Reduced average path length by 13.89–16.83% compared to Bi-RRT.
  • Inflection Points/Corners: Drastically reduced the number of turns by 66.11–94.18% compared to other algorithms, leading to smoother paths.
  • Iterations and Time: Significantly decreased the number of iterations (up to 96.44%) and time consumption (up to 92.54%) compared to Bi-RRT in complex environments.
  • Adaptability: Showed strong performance across all tested environments, including complex narrow channels, where other algorithms struggled.

Limitations and Future Work

  • Single AGV Focus: The current algorithm is designed for planning the path of a single AGV. The authors acknowledge that real-world applications often involve multiple AGVs requiring collaborative path planning.
  • Slightly Higher Time in Simple Environments: In relatively simple environments, the NCB-RRT's running time was observed to be slightly higher than Bi-RRT due to the overhead of its additional strategies.
  • Future Work: The authors explicitly state that extending the algorithm to handle multiple collaborating AGVs is a key area for future research. They also suggest further exploration of optimizing the SFRT thresholds for different environments.

Summary updated

Abstract

The efficiency of the rapidly exploring random tree (RRT) falls short when efficiently guiding targets through constricted-passage environments, presenting issues such as sluggish convergence speed and elevated path costs. To overcome these algorithmic limitations, we propose a narrow-channel path-finding algorithm (named NCB-RRT) based on Bi-RRT with the addition of our proposed research failure rate threshold (RFRT) concept. Firstly, a three-stage search strategy is employed to generate sampling points guided by real-time sampling failure rates. By means of the balance strategy, two randomly growing trees are established to perform searching, which improves the success rate of the algorithm in narrow channel environments, accelerating the convergence speed and reducing the number of iterations required. Secondly, the parent node re-selection and path pruning strategy are integrated. This shortens the path length and greatly reduces the number of redundant nodes and inflection points. Finally, the path is optimized by utilizing segmented quadratic Bezier curves to achieve a smooth trajectory. This research shows that the NCB-RRT algorithm is better able to adapt to the complex narrow channel environment, and the performance is also greatly improved in terms of the path length and the number of inflection points. Compared with the RRT, RRT* and Bi-RRT algorithms, the success rate is increased by 2400%, 1900% and 11.11%, respectively.
BibTeX
@inproceedings{wu2023novel,
  author = {Bin Wu and Wei Zhang and Xiaonan Chi and Di Jiang and Yi Yang and Yi Lu},
  title = {{A Novel AGV Path Planning Approach for Narrow Channels Based on the Bi-RRT Algorithm with a Failure Rate Threshold}},
  booktitle = {Sensors},
  year = {2023},
  doi = {10.3390/s23177547},
}
Figure