# Coordinated Multi-UAV Reconnaissance Scheme for Multiple Targets
## 4 Proposed Method
### Improved Dynamic Task Planning Algorithm Based on Market Auction Mechanism
#### 4.4.1 Insertion Mechanism for Task Areas  
Task area insertion is a common case in dynamic mission planning. When new task areas emerge on the map, they need to be inserted into the existing UAV reconnaissance sequence. When a UAV is damaged during the mission, the unfinished task area should be treated as a new task area and inserted into the reconnaissance sequence of the other UAVs. The task area insertion mechanism proposed in this paper considers the additional travel cost required by UAVs to add new task areas to the original reconnaissance sequence. It dynamically allocates the inserted task areas by means of bidding, and multiple UAVs compete for the newly inserted reconnaissance targets, as shown in Figure 6 where the extra distance (extra cost) needed for UAV\({}_{i}\) travel to the new task area is inserted between \(w_{1}^{i}\) and \(w_{2}^{i}\) is \(cost_{i,1}=d_{3}+d_{2}-d_{1}\). Let \(q_{new}\) denote the set of newly added task areas, and calculate the priority of the corresponding task targets based on the value coefficient of the task targets and the reconnaissance area. The priority coefficient of the new task area is defined as shown in Formula (14):  
\[R_{i}=\frac{J_{i}}{\sum_{i=1}^{d_{new}}J_{i}}\alpha+(1-\frac{s_{i}}{\sum_{i=1}^ {d_{new}}s_{i}})\gamma, \tag{14}\]  
where \(R_{i}\) is the priority coefficient corresponding to the newly added task in \(q_{new}\); targets with higher priority coefficient have higher priority and are added first. \(J_{i}\) denotes the value coefficient of the \(i\)-th task target in \(q_{new}\), and \(s_{i}\) denotes the area of the \(i\)-th task in \(q_{new}\). \(\alpha\) and \(\gamma\) are the weights of the value coefficient and area, respectively. This formula can make the task area with a high numerical coefficient and small area be prioritized by UAV competition. In order to ensure that the UAV reconnaissance sequence still satisfies the time constraint in Formula (8) after adding a new task area, this paper refers to the degree of constraint violation and proposes a feasibility index. This index is the endurance time (T) of the UAV minus the minimum reconnaissance time of the UAV unexecuted task area in the sequence and the time spent on the journey, then minus the minimum reconnaissance time of the new task. The feasibility \(FD(i)\) model of the \(i\)-th UAV is as follows:  
\[FD(i)=T_{i}-\frac{D_{i}+cost_{i}}{v_{i}}-\sum_{k=1}^{|q_{i}|-|w^{i}|}t_{q_{i},k }-\sum_{k=1}^{|w^{i}|}\min t_{q_{i},k}-t_{n}. \tag{15}\]  
where \(t_{q_{i},k}\) represents the reconnaissance time allocated by the UAV to the task area before the new task appears, and \(\min t_{q_{i},k}\) is the reconnaissance time needed to meet the minimum reconnaissance revenue of the task area, and \(t_{n}\) is the minimum reconnaissance time of the new task area. The UAV is eligible to compete for the task area only if \(FD\geq 0\). Otherwise, UAVs with \(FD<0\) abandon competition for the new mission areas. If the \(FD\) of each UAV is less than 0, the problem is considered unsolvable. Figure 6: UAVs compete for new task areas. When a new task area emerges or a UAV is damaged, the task execution status of all the UAVs at that time is recorded. The task sequence that needs to be scouted of UAV\({}_{i}\) is denoted as \(w^{i}\), \(w^{i}_{1}\) is the next task area for reconnaissance by the UAV, and the number of unexecuted task areas is denoted as \(num_{i}\). The emergence of new task areas can sometimes involve the appearance of multiple task areas simultaneously. In this paper, the priority coefficient \(R_{i}\) of each new task area in \(q_{new}\) is calculated using Formula (14), then each new task area is inserted into the \(w^{i}\) one by one, following the order of \(R_{i}\). After the insertion order has been determined, the new task areas will be inserted into the unexecuted reconnaissance sequence one by one, and the new task area currently inserted is denoted as \(a_{new}\).