HB-RRT:A path planning algorithm for mobile robots using Halton sequence-based rapidly-exploring random tree

Path planning remains crucial for efficient robot operation. A Halton Biased Rapidly-exploring Random Tree (HB-RRT) path planning algorithm is introduced in this study. The Halton sequence, known for its uniform distribution and low discrepancy, is employed for sampling. Issues arising from the pseudo-random sequence in the standard RRT algorithm, leading to uneven distribution of sampling points, are addressed. A mouse-inspired goal-oriented strategy and a candidate sampling pool strategy are incorporated to enhance the sampling point quality, thereby addressing the challenge of insufficient memory during node expansion. Path optimization is further achieved through a multi-level planning approach, which aims to minimize redundancy. A subsequent smoothing of the path is conducted using a cubic B-spline method. Comparisons with the RRT, Bionic Target Bias-RRT, and Informed-RRT* algorithms, through both numerical simulations and real-world testing, confirm the superiority of the HB-RRT algorithm in terms of planning time, path length, and overall path quality.

Authors

• Huageng Zhong
• Ming Cong
• Minghao Wang Guangdong Shuye Intelligent Technology Co., Ltd.
• Yu Du School of Automation, Northwestern Polytechnical University
• Dong Liu University of Science and Technology of China

Keywords

• Path planning
• Sampling-based algorithms
• Rapidly-exploring random tree (RRT)
• Optimal path planning
• Halton sequence
• Mobile robotics