Focused Bidirectional Search Trees: A Bidirectional Optimal Fast Matching Method for Robot Path Planning

Chenming Li1; Jiankun Wang2; Max Q.-H. Meng2

10.1109/RCAR58764.2023.10249227

2023

2023 IEEE International Conference on Real-time Computing and Robotics (RCAR)

979-8-3503-2719-9

2023 IEEE International Conference on Real-time Computing and Robotics (RCAR)

638-643

17-20 July 2023

Datong, China

Robot path planning in high-dimensional continuous space is of great significance in robotics. The conventional bidirectional fast marching method utilizes brute-force search to explore the space, which is computationally expensive. Though improving the planning efficiency, heuristic-based bidirectional fast marching search results in a suboptimal path under a predetermined number of random samples. To address these issues, we propose Focused Bidirectional Fast Marching Trees (FBFMT*), developing a novel vertex exploring sequence to constrain the forward and backward searches within the brute-force searched regions. It enables the search trees to meet in the middle of the solution path, which guarantees the optimality under the current set of samples and searches faster than the bidirectional brute-force strategy. Extensive simulations in different scenarios validate the superiority of the proposed method, showing that FBFMT* can speed up the planning process and find a better solution. We also extend the proposed method to general conditions so that the forward and backward searches of FBFMT* can meet at any portion of the path. FBFMT* reveals that the heuristic-based bidirectional fast marching search strategy can be a general and efficient technique for robot path planning in high-dimensional continuous spaces.

Search Problems Path Planning Real-time Systems Space Exploration Planning Robots

通讯

EI

20234214881139

Motion Planning ; Optimization

Computer Programming:723.1 ; Robotics:731.5 ; Optimization Techniques:921.5

IEEE

1.Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China
2.Department of Electronic and Electrical Engineering, Shenzhen Key Laboratory of Robotics Perception and Intelligence, Southern University of Science and Technology, Shenzhen, China

Chenming Li,Jiankun Wang,Max Q.-H. Meng. Focused Bidirectional Search Trees: A Bidirectional Optimal Fast Matching Method for Robot Path Planning[C],2023:638-643.