## 3 Methodology
### Dynamic Task Allocation  
The goal of our dynamic task allocation algorithm C-CBAA is to find a conflict-free matching of tasks to agents that minimizes the local cost to achieve the global reward. In our research, an assignment is said to be conflict-free if each agent is assigned to only one target but each target can be performed by multi-agent at the same time. In order to meet the needs of the actual goal, we proposed the idea of performing targets together by a team. This is the most different from the conventional task allocation concept. Consider the agents and dynamic task allocation problem where a group of \(N_{u}\) agents are planning to reach targets \(N_{t}\) while they also manage to minimize the overall trajectory cost of the group as Cost. This can be stated formally as:  
\[Cost=min\sum_{i=1}^{N_{u}}\sum_{j=1}^{N_{t}}Cost(i,j)T_{i}^{j} \tag{15}\]  
subject to  
\[\sum_{i=1}^{N_{u}}a_{it}\geq G_{t} \tag{16}\]  
where \(T_{i}^{j}\) means the trajectory \(j\) of agent \(i\) as defined in Equation (6). In Equation (16), \(a_{it}\) indicates agent \(i\) selects target \(t\) and \(G_{t}\) means the minimum number of agents that is required by each target \(t\). In other word, a target requires a minimum number of agents to reach the target to be sufficiently carried out the task. If the total number of agents of the group cannot execute all task requirements of targets, the farthest target away from the center of gravity of the group will be dropped automatically. This is to ensure some targets can be carried out by some agents successfully rather than fail all missions due to the limited number of agents. Figure 2 shows the case of three agents in an operation of five targets. The horizontal and vertical axes represent the x and y coordinates on the ground by assuming agents start near the origin. The colored circles are agents in operation and the dash lines represent the paths to the assigned triangular targets. Black dots are random obstacles in the scenario. Each target requires one agent to execute the task, the farthest yellow and green targets are abandoned. Our proposed automatic task allocation method is implemented in two phases: the auction phase and the consensus-conflict resolution phase. The former focuses on bidding a self-target and updating information, the latter is subjected to team communication and gain consensus to find the actual best agent to win in the auction process. Each iteration of the task allocation requires completing both phases in sequence to reach the consensus among agents in the task allocation. Algorithm 1 shows the auction process of agent \(i\) for target \(t\) at iteration \(\tau\). The re-auction process starts when there is a change in the number of targets. The conventional CBAA algorithm adds all agents to participate in the re-auction and award target \(t\) to the agent with the highest price even if an agent has already been assigned to some target. This can cause redundant and inefficiency of task assignments. In order to improve the efficiency of CBAA algorithm, our C-CBAA algorithm as shown in Algorithm 1 only allows partial agents to re-bid the un-allocated targets as shown in Equation (17). \[h_{it}=\Pi(c_{it}<Cost\,\&\,z_{it}>0) \tag{17}\]  
\(\Pi\) (\(\cdot\)) is a binary operation judgment on whether the condition is true or false, \(c_{it}\) is the agent \(i\)'s minimal trajectory cost for target \(t\) using a condition defined in Equations (15), \(z_{it}\) means agent \(i\) stores the least number of agents required for target \(t\). This condition reduces the number of participants in the bidding process and the number of auctions which are already awarded. Therefore, only when a target disappears or the number of agents assigned becomes less than the number of agents required by the changed target, an auction bidding process is invoked. The performance comparison is presented in Section 4.2.2. Algorithm 2 is the consensus and conflict resolve phase. Agent \(i\) will receive the information from all its neighbors \(k\) in each iteration.