Bidirectional Search Strategy for Incremental Search-based Path Planning

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

10.1109/IROS55552.2023.10342039

2023

2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

2153-0858

978-1-6654-9191-4

2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

7311-7317

1-5 Oct. 2023

Detroit, MI, USA

345 E 47TH ST, NEW YORK, NY 10017 USA

IEEE

Planning a collision-free path efficiently among obstacles is crucial in robotics. Conventional one-shot unidirectional path planning algorithms work well in the static environment, but cannot respond to the environment changes timely in the dynamic environment. To tackle this issue and improve the search efficiency, we propose a bidirectional incremental search method, Bidirectional Lifelong Planning A* (BLPA*), which searches in the forward and backward directions and performs incremental search bidirectionally when the environment changes. Furthermore, inspired by the robot perception range limitation and BLPA*, we propose the fractional bidirectional D* Lite (fBD* Lite(dp)), which constraints the forward search to the robot perception range and uses the backward search to expand the rest area. Our simulation results demonstrate BLPA* and fBD* Lite(dp) can achieve superior performance in the dynamic environment. It reveals that the bidirectional incremental search strategy can be a general and efficient technique for graph-search-based robot path planning methods.

Heuristic Algorithms Simulation Search Problems Path Planning Planning Collision Avoidance Intelligent Robots

通讯

英语

EI ; CPCI-S

National Key Research and Development Program of China[2019YFB1312400] ; Shenzhen Outstanding Scientific and Technological Innovation Talents Training Project[RCBS20221008093305007] ; National Natural Science Foundation of China[62103181]

Computer Science ; Robotics

Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Computer Science, Theory & Methods ; Robotics

WOS:001136907801105

20240315412786

Robot Programming

Computer Programming:723.1 ; Robotics:731.5

IEEE

1.Department of Electronic Engineering, The Chinese University of Hong Kong, Shatin, N.T., 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,Han Ma,Jiankun Wang,et al. Bidirectional Search Strategy for Incremental Search-based Path Planning[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:IEEE,2023:7311-7317.