# Multi-Population Parallel Wolf Pack Algorithm for Task Assignment of UAV Swarm
## 2 Basic Knowledge and Literature Review  
### Task Assignment Model  
The background of the mission is to attack static present targets on the ground using a UAV swarm consisting of isomorphic attack UAVs with limited weapons. The objective of the mission is to attack all targets in the shortest time or with the least total fuel consumption. When a UAV's weapons are insufficient to cope with one target, multiple UAVs need to be scheduled to attack the target at the same time. UAVs can control their speeds to achieve the salvo attack. Any UAV needs to avoid obstacles and no-fly zones as it flies to the target. In a specific mission, various constraints should be considered to assign the UAVs, such as the mobility constraints, the weapon quantity constraints, the fuel quantity (or flying range) constraints and the flyable zone constraints. In this paper, a simplified task assignment model is described, which involves as little uncertain information as possible, so as to facilitate the performance comparison of optimization algorithms. The objective function is to minimize the costs of all tasks, including the cost of the total range and the cost of the time to complete all tasks [2]. To formalize the problem, the following assumptions are set up. 1. There is no consideration of obstacles and no-fly zones, so the range between the UAV and target can be expressed by their straight-line distance. 2. UAVs fly at fixed altitudes with the same constant velocity. Thus, the flight time can be equivalent to the fight range. 3. The UAV drops the weapon directly above the target, so the task position is the projection of the target position on the flight level. In other words, the UAV's fight range flying to the task position is the straight-line distance between the UAV's position and the target position in the horizontal plane, regardless of the altitude. 4. The time consumption involved in preparing and firing the weapon is not taken into account. In other words, the time cost to complete a task includes only the flight time. 5. Each target can be attacked only once, while any UAV can attack multiple targets. 6. Targets' initial positions are revealed. The UAV swarm consists of \(N_{V}\) attack UAVs, which can be expressed as \(\mathbf{V}=\{V_{i}|i=1,2,\cdots,N_{V}\}\), and \(N_{T}\) targets, which can be expressed as \(\mathbf{T}=\{T_{j}|j=1,.,2,\cdots,N_{T}\}\). The task sequence of UAV \(V_{i}\in\mathbf{V}\) is  
\[ \begin{split} plan_{i}=\left\{stage_{i}^{(k)}\middle|k=1,2, \cdots,N_{si}\right\}\\ stage_{i}^{(k)}=\left(T_{n},Range_{m,n}^{i}\right),T_{n}\in\mathbf{T} \end{split}  \tag{1}\]  
where \(stage_{i}^{(k)}\) is the stage \(k\) of UAV \(V_{i}\), \(N_{si}\) is the task number assigned to UAV \(V_{i}\), \(T_{n}\) is the target of UAV \(V_{i}\) in the \(k^{th}\) stage, and \(Range_{m,n}^{i}\) is the distance between \(T_{m}\) and \(T_{j}\) for UAV \(V_{i}\), where \(\mathrm{m}=0,1,2,\cdots N_{T}\) and \(\mathrm{n}=1,2,\cdots N_{T}\), \(T_{0}\) is a virtual target representing the initial position of a UAV. This task assignment problem is similar to the Vehicle Routing Problem (VRP) in which UAVs equate to vehicles, targets equate to customers and the initial position of each UAV equates to a depot. VRP [3] is a reasonably well-studied problem with extensive related derivative problems, such as the Capacitated Vehicle Routing Problem (CVRP) [4], the Vehicle Routing Problem with Time Window (VRPTW) [5], the Split Delivery Vehicle Routing Problem (SDVRP) [6], the Dynamic Vehicle Routing Problem (DVRP) [7], the Vehicle Routing Problem with Simultaneous Delivery Pickup (VRPSDP) [8] and so on. At present, the existing VPR models can basically meet the requirements for the modeling of task assignment problems. In this paper, we introduce the basic VRP to build the task assignment model. The decision variable of task assignment is \(x_{m,n}^{i}\in\{0,1\}\), representing whether UAV \(V_{i}\) attacks target \(T_{n}\) after \(T_{m}\); \(x_{m,n}^{i}=1\) represents an attack, other values signify no attack.