Automatic collision avoidance algorithm for unmanned surface vessel based on improved Bi-RRT algorithm Ouyang Zilu，Wang Hongdong ， Wang Jianyao，

Ouyang Zilu1，2，Wang Hongdong*1，2，Wang Jianyao1，2，Yi Hong1，2 1 State Key Laboratory of Ocean Engineering，Shanghai Jiao Tong University，Shanghai 200240，China 2 Key Laboratory of Marine Intelligent Equipment and System，Ministry of Education， Shanghai Jiao Tong University，Shanghai 200240，China Abstract：［Objectives］ This method is proposed for automatic collision avoidance during high-speed running of the Unmanned Surface Vessel（USV）.［Methods］The Bi-RRT algorithm was combined with the velocity obstacle algorithm for automatic collision avoidance algorithm for USV based on improved Bi-RRT algorithm. In view of the situation of the extension direction of the parent node inside the collision cone in the extended operation of Bi-RRT algorithm，the 'collision risk index' and 'obstacle repellent vector' were presented，making the extension direction of the parent node tend to move away from the obstacle. In addition，in view of the real time problem of the algorithm，the strategy of parallelly extending two search trees and the 'target attraction vector' when the extension direction of the parent node is outside the collision cone were introduced to accelerate the convergence of the algorithm.［Results］The results show that the algorithm using above-mentioned improvement method has reduced failed extension times of search tree，and the planned collision-free paths are shorter and smoother.［Conclusions］The research shows that the improved Bi-RRT algorithm has the advantages of high real-time performance and high path planning quality，which are of great significance for practical engineering application. Key words：Unmanned Surface Vessel（USV）；automatic collision avoidance；Bi-RRT algorithm; velocity obstacle algorithm