Wu Bin, Zhang Wei, Chi Xiaonan, Jiang Di, Yi Yang, Lu Yi
College of Mechanical and Electronic Engineering, Nanjing Forestry University, Nanjing 210037, China.
Sensors (Basel). 2023 Aug 30;23(17):7547. doi: 10.3390/s23177547.
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.
当需要在狭窄通道环境中高效引导目标时，快速探索随机树（RRT）的效率会有所不足，存在收敛速度缓慢和路径成本增加等问题。为了克服这些算法限制，我们提出了一种基于双向RRT的窄通道路径查找算法（名为NCB - RRT），并引入了我们提出的研究失败率阈值（RFRT）概念。首先，采用三阶段搜索策略，根据实时采样失败率生成采样点。通过平衡策略，建立两棵随机生长的树来进行搜索，这提高了算法在窄通道环境中的成功率，加快了收敛速度并减少了所需的迭代次数。其次，集成了父节点重新选择和路径修剪策略。这缩短了路径长度，大大减少了冗余节点和拐点的数量。最后，利用分段二次贝塞尔曲线对路径进行优化，以实现平滑轨迹。本研究表明，NCB - RRT算法能够更好地适应复杂的窄通道环境，并且在路径长度和拐点数量方面性能也有大幅提升。与RRT、RRT*和双向RRT算法相比，成功率分别提高了2400%、1900%和11.11%。
