关键词: 路径规划, 双向搜索, 双引力场, 试探性弹性扩展, 双向自由化生长树算法

Abstract: Most of the path planning algorithms used in the path planning of unmanned aerial vehicles such as UAVs and unmanned underwater robots working in three-dimensional space are RRT* algorithms. However， the RRT* algorithm has problems such as slow convergence speed， large number of iterations， and frequent collision detection. As a result， the path planning ability of UAVs is poor and cannot meet the application needs of many scenarios. Aiming at the insufficiency of existing algorithm sampling. Bidirectional-self-optimizing growing tree（B-SOGT*） was proposed， which used bidirectional search， double gravitational field， and tentative elastic expansion to realize path planning in three-dimensional space. The two-way search takes the starting point and the target point as the root nodes respectively， and constructs 2 random trees to perform spatial search at the same time， which improves the search efficiency； The double gravitational field is a gravitational field generated by the root nodes of 2 random trees respectively， and the sampling efficiency is improved under the action of the gravitational field; The tentative elastic expansion method introduces the parent node re-selection mechanism when generating the path， which does not require collision detection and improves the calculation speed of the algorithm. Simulation results show that the B-SOGT* algorithm has the advantages of faster convergence， better path quality and fewer iterations.

Key words: path planning, bidirectional search, double gravitational field, tentative elastic extension, bidirectional-self-optimizing growing tree