Path planning for unmanned surface vehicle with improved CBS algorithm

An improved conflict-based search algorithm is introduced into USV（Unmanned Surface Vehicles, USV） path planning program to improve the feasibility of the path plan under practical navigational constraints. The path planning algorithm consists of 2 layers. The upper layer searches for conflict-free nodes and routes by using a constraint tree, and the lower layer includes an A^* algorithm to find the optimal path for each USV and solves the globally optimal USV path plan according to a value function. The value function is adjusted by integrating 2 constraints, the shortest safe distance and the collision risk. The latter is decided by means of fuzzy theory. The optimization problem is solved for the object of shortest travel distance under given constraints. Tests show that the proposed algorithm is effective in 2D navigational environments. The design concept here may be used in multi-ship collision avoidance.