BDRP: A Binary Divisive Recursive Planner for Path Planning

Abstract

Narrow passage scenarios pose significant challenges for path planning, especially for tasks requiring real-time performance. Traditional asymptotically converging sampling-based planners (SBPs) often exhibit poor initial path quality and slow convergence, limiting their ability to efficiently construct high-quality paths in such environments. To address these limitations, we propose the Binary Division Recursive Planner (BDRP), a novel approach for global path planning. BDRP explores the free configuration space by randomly sampling points on the perpendicular bisector hyperplane between the start and goal configurations. Using a divide-and-conquer strategy, BDRP recursively decomposes the problem into two subproblems: connecting the start point to the sampled points and connecting the sampled points to the goal point, thereby constructing collision-free paths. Heuristic-based cost estimation predicts potential minimum path costs, enabling redundant search pruning and optimizing the sampling space to improve computational efficiency. Experimental results show that, compared with benchmark SBP methods, BDRP exhibits superior performance in narrow passages and other complex environments. This is particularly evident in scenarios with high real-time requirements, highlighting its potential in robotic navigation and path planning applications.