Abstract:A new target assignment problem for multi UAV ground attack is studied. In this issue, the attacker tries to destroy the high-value target of the defender through multiple UAVs, and the defender tries to intercept the UAVs by launching interceptor missiles, but the attacker and defender can not observe the target allocation scheme actually adopted by the other side in advance. By analysing the impact of the defender's interceptor missile allocation scheme on the profit of the attacker, this paper constructs the problem as a zero-sum matrix game model. The strategy space of the model increases explosively with the increase of the number of UAVs, high-value targets and interceptor missiles, and the existing algorithms are difficult to solve it in an effective time. Therefore, this paper proposes an improved Double Oracle algorithm based on two-stage neighbourhood search(DO-TSNS). The results of experiments show that, compared with the DO, UWMA and DO-NS algorithm, the DO-TSNS algorithm can solve the target assignment problem of multi UAV ground attack considering the interception behaviour of the defender more effectively.