## 3 Task Assignment Algorithm Based on Extended CNP
### Distributed Multi-Constraint Dynamic Task Assignment Algorithm
### Bidding Function Design

As the core of extended CNP, the bidding function, which needs to be designed on the basis of the concrete task assignment problem in CNP, is a sort of objective function. According to the method process described above, the whole task assignment is divided into the target assignment and the subtask assignment. Both the target assignment and the subtask assignment are based on the extended CNP. Hence, the bidding function of each subset is designed for the target assignment, while the individual bidding function within the group is designed for the subtask assignment. #### 3.2.1 Individual Bidding Function

The individual bidding function \(B_{ij}\) consists of value function \(Re_{ij}\) and penalty function \(Pe_{ij}\). Based on the analysis for the UAV swarm task assignment model in Section 2, the individual bidding function mainly relates to: 1 the maximum task values, which is denoted in Section 2.5; 2 the flight path; 3 the time windows and start time of each subtask. Since the UAV task assignment couples with path planning, the bidding function needs to be designed in combination with the UAV flight path. By analyzing the scenario, it can be seen that the impact of the flight path on task assignment is mainly reflected in UAV survivability estimation \(h_{i,est}\) and air-range \(L_{ij}\) (fuel consumption), as shown in Figure 4:1

Supposing that UAV \(V_{i}\) participates in the bidding process of subtask \(Task_{j}\) with time window \(t_{task_{j}}\in[t_{s,j},t_{c,j}]\), where \(t_{task_{j}}\) is the start time of task execution, of which the

Figure 4:2 The coupling of the UAV mission assignment and path planning. mathematical expression is given in Section 2.5, \(t_{s,j}\) is the earliest start time, and \(t_{e,j}\) is the latest one. To evaluate the impact of threats \(\{O_{k}\mid k=1,2,\ldots,N_{obs}\}\) on UAV \(V_{i}\) performing tasks, it introduces the survivability estimation of \(V_{i}\), which can be expressed as

Figure 4:3

where \(h_{i}\) is the current survivability of \(V_{i}\), \(A_{k,app}\) is the impact of threats \(O_{k,app}\in\{O_{k}\}\) approached by \(V_{i}\), \(A_{k,app}\in(0,1)\), and \(N_{app}\) is the number of threats approached. (1) Value function \(Re_{ij}\)

In the actual scenario, the value of UAVs performing any task is generally related to the start time when the UAV performs the task. The nearer the start time \(t_{task_{j}}\) to the time window \(TimeBar_{k}\), the greater the value for UAV \(V_{i}\) to perform the task; otherwise, the smaller the value; hence, the item related to the start time \(t_{task_{j}}\) is introduced. The value function of \(V_{i}\) performing \(Task_{j}\) is designed as

Figure 4:4

where \(R_{x,j}\) is the maximum value of \(Task_{j}\); \(\lambda\) is the attenuation factor of the start time \(t_{task_{j}}\) on the task value. Apparently, \(Re_{ij}\) is a monotonic increasing function of battlefield survivability \(h_{i,est}\) and decreases monotonically with the start time \(t_{task_{j}}\). When \(h_{i,est}:1\to 0\), \(t_{task_{j}}:t_{s,j}\to t_{e,j}\), there is \(Re_{ij}\): \(R_{x,j}\to 0\). (2) Penalty function \(Pe_{ij}\)

The penalty function is composed of the consumption penalty and the threat penalty. Assuming that the per-unit fuel consumption of UAV \(V_{i}\) is \(F_{i}\), the air-range performing \(Task_{j}\) is \(L_{ij}\), the estimation of survivability is \(h_{i,est}\), and the penalty function is designed as

Figure 4:5

Obviously, \(Re_{ij}\) is a monotonic function of battlefield survivability \(h_{i,est}\). When \(h_{i,est}:1\to 0^{+}\), there is \(Pe_{ij}\): \(F_{i}L_{ij}\to+\infty\). The penalty indicates the coupling impact of flight path planning on task assignment. On one hand, the fuel consumption of performing subtask \(Task_{j}\) is directly related to the preplanned air-range \(L_{ij}\); on the other hand, the more threats approached by UAV \(V_{i}\) during the task execution, the lower the survivability estimation \(h_{i,est}\), which means more loss when the UAV performs the task.