Research On Multi-ship Collision Avoidance Algorithm Under The Framework Of Dynamic Game

In recent years,the world has witnessed a dramatic increase in maritime trade,traffics and ship tonnage,which causes much more complex maritime traffic environment in some waters.Especially during the multi-ship encounter,the complicated situation will result in ship collision accidents.In consequence,it is urgent to develop scientific research on the approaches of collision avoidance,which can provide decision making support for multi-ship collision avoidance to coordinate the behaviors among ships,and substantially reduce the occurrence of collision accidents.In multiple ship encounter,the process of collision avoidance is highly linked with the result of game and its interaction among ships.When the classical extensive game model is applied to multi-ship collision avoidance,the collision risk is measured by the risk model to determine the game order.The action set is screened based on experience,and the game tree is created based on all ships in the encounter situation.As the number of ships increases,the number of game tree layers and nodes increases exponentially,resulting in a significant decrease in the efficiency of collision avoidance decision making.In this context,the paper presents a multi-ship collision avoidance algorithm based on improved extensive game to provide theoretical and technical support for researches on multi-ship collision avoidance.On the basis of in-depth study of ship collision avoidance mechanism,an improved extensive game model of ship collision avoidance is presented.The method of screening players and action sets in multi-ship encounter situation is improved based on velocity obstacle.The algorithm to find the most dangerous target ship is designed.Based on the velocity feasible region of the ship avoiding the most dangerous target ship and its surrounding ships,the optional action range of the collision avoidance game model is determined,which can avoid the risk of collision with the third ship after the own ship turns to avoid collision.Consequently,multi-ship collision avoidance game is transformed into two-ship collision avoidance game on the premise of ensuring navigation safety.The offset of ship is taken as the payoff function,and the corresponding payoffs are calculated according to the action sets of the two ships in the game.A game tree of ship collision avoidance is created.The subgame perfect Nash equilibrium is solved out by backward induction,which makes two ships choose the most beneficial decisions for themselves,namely the decisions with the largest payoff to form the collision avoidance strategy profile.In this paper,the ship collision avoidance maneuvering has been simulated on the basis of MMG model and the ship’s course is controlled by an incremental PID controller.Encounter situations are derived by maneuvering simulation combined with multi-ship collision avoidance algorithm under the framework of dynamic game.The presented method is compared with the classical extensive game algorithm from two key aspects: action set screening and CPU time consuming.The performance of algorithm in the whole collision avoidance process is analyzed and its effectiveness is verified.Simulation results show that the range of feasible collision avoidance areas screened by the improved extensive game algorithm is reduced by 52.08% compared with the classical extensive game algorithm under the premise of ensuring navigation safety of all ships in the encounter situation.With the same accuracy of actions,the CPU time of the classical extensive game algorithm to solve the optimal action profile is about 5 times that of the improved extensive game algorithm.The presented method effectively reduces the optional range of collision avoidance action set and improves the efficiency of decision making for multi-ship collision avoidance.The innovation of this paper is as follow: the presented decision-making method is novel for multi-ship collision avoidance,which integrates the analysis of velocity obstacle into a dynamic game framework.The method demonstrates a new idea for the research of ship collision avoidance,which generates the course of collision avoidance.The output will benefit the solution to the complex problems of collision avoidance and the development of autonomous collision avoidance for intelligent ships in the future.