## 3 Task Assignment Algorithm Based on Extended CNP
### Distributed Multi-Constraint Dynamic Task Assignment Algorithm  
The algorithm includes four steps: target information release, bidding scheme generation, bid winning authorization, and task execution. The process is shown in Figure 3. The following describes the algorithm process in turn. Step 1: Release the information of targets  
Assume that the UAV detects a sudden target \(T_{k}\) and reports the target information to the subset leader UAV \(V_{i}\), which becomes the tendering UAV on behalf of the subset, and sends a bidding invitation to each subset in the local communication network. According to the hierarchical communication topology, the set of other subset leaders interacting with \(V_{i}\) is \(V_{p,i}=\{V_{j}|w_{ij}=w_{ji}=1,j\in[2,1+N_{m}]\cup j\
eq i\}\). \(V_{p,i}\) composes the potential bidders of assignment for target \(T_{k}\). Tendering UAV \(V_{i}\) releases tendering information \(I_{i}\) to each UAV in set \(V_{p,i}\), and \(I_{i}\) is expressed as  
\[I_{i}=(V_{i},T_{k},\{Task_{k}\},t_{now},H_{b}) \tag{10}\]  
where \(V_{i}\) is the index of tendering UAV; \(T_{k}\) is the index of the sudden target; \(\{Task_{k}\}\) is denoted as the subtask set of target \(T_{k}\); \(t_{now}\) is the releasing time; \(H_{b}\) is the information stateflag, of which value 0 means no relay, otherwise 1. The information structure of \(Task_{k}\) can be denoted as:  
\[Task_{k}=\left\{M_{t,k},\mathbf{q}_{t,k},TimeBar_{k},R_{x,k},N_{pe,j},Th_{k}\right\} \tag{11}\]  
where \(M_{t,k}\) means task type; \(\mathbf{q}_{t,k}\) is the position coordinates; \(TimeBar_{k}=[t_{b,k},t_{e,k}]\) is the time window; \(R_{x,k}\) is the maximum task value; \(N_{pe,j}\) is the expected number of participants; \(Th_{k}\) is the negotiation threshold. As attached information during the subtask \(Task_{k}\) assignment process, negotiation threshold \(Th_{k}\) is applied to preselect bidders from the potential bidder set \(\left\{V_{p,i}\right\}\), reducing the negotiation scale as well as the consumption of communication resources and improving assignment efficiency. To adjust the threshold adaptively, the reward of subtask \(Task_{k}\) in performing the subset to which UAV \(V_{i}\) belongs is selected as \(Th_{k}\). If the bidder's bidding value is greater than \(Th_{k}\), it indicates that the swarm efficiency will be optimized and improved after \(Task_{k}\) is assigned to the bidder. In the process of information release, different UAV groups with intersections of local communication topologies may discover the same target, causing multiple bidding UAVs to release information at the same time in their respective local communication topologies, resulting in system conflict and resource waste. In order to avoid this problem, it is necessary to ensure that different UAV subsets reach a consensus on tendering UAVs and tendering information, which is realized by Algorithm 1. In Algorithm 1, \"StopCmd\" means to abort the negotiation command, and the operation \".\" represents the reference to elements in the information structure. For any UAV \(V_{i}\) in the local communication topology, the tendering information related to subtask \(Task_{k}\) will be released to its directly connected UAV if it is not empty and has not been transmitted (Line 1-4). Meanwhile, the UAV can also receive the tendering information related to \(Task_{k}\) transmitted by others directly connected with it (Line 6-11). Figure 3: The process of task assignments based on extended CNP. If UAV \(V_{i}\) finds that the negotiation threshold of UAV \(V_{j}\) about \(\textit{Task}_{k}\) is greater, \(V_{i}\) saves the tendering information \(I_{j}\) and issues commands to other UAV groups interacted with \(V_{i}\) but not interacted with \(V_{j}\) to stop the negotiation so as to make them exit the assignment dominated by UAV \(V_{j}\). After Step 1, the tendering information released in the local communication network achieves consensus, that is \(I_{i}=I_{j}\).