## 3 Dynamic Multi-Objective (DYMO) Auction-Based Task Allocation
### Cost Function  
Because we have three bidding rules, each of which considers an objective to satisfy, there is a need to combine these bids into a single bid to be sent to the auctioneer. For this purpose, we normalize the values and use the weighted sum model to compute the final bid. We normalize each value to its maximum expected value as follows. Assuming (a) the maximum distance between any two points in the area is \(D\) (diagonal of the area), (b) the maximum deviation between a robot quality level and task quality level is \(\Delta Q\), and (c) the maximum expected tasks for each robot is L. We use these values to normalized the objective as follows:  
\[\bar{d_{ij}}=\frac{d_{ij}}{D}\]  
\[\bar{q_{ij}}=\frac{q_{ij}}{\Delta Q}\]  
\[\bar{l_{i}}=\frac{l_{i}}{L}.\]  
Figure 3: A robot state diagram in during auction process. Therefore, the cost value for a robot \(R_{i}\) to execute a task \(T_{j}\) is given by the following equation:  
\[C_{ij}=W_{d}*\bar{d_{ij}}+W_{q}*\bar{q_{ij}}+W_{l}*\bar{l_{i}}, \tag{5}\]  
where \(W_{d}\),\(W_{q}\), and \(W_{l}\) are the weights that sum up to one. The cost is proportional to the distance, the absolute difference between the task quality requirement and the robot quality, and the current load. Hence, all three terms have a positive sign. We have tested the dependency of all factors (distance, quality, load). Firstly, we will analyze the relationship between the distance and quality factors, hence, we assume \(W_{l}=0\). Later, we will include \(W_{l}\) when we discuss the impact of synergy on the overall performance. Costs computed based on the distance factor alone lead to insufficient quality satisfaction because there is no relation between the task quality and being close or far from robots. Therefore, the distance and quality factors are independent factors. A test has been conducted to determine the appropriate weights of the distance and quality factors, i.e., \(W_{d}\) and \(W_{q}\), respectively \((W_{d}+W_{q}=1)\) given that the robots' quality levels are three (low, medium, high). Figure 4 shows the relationship between the traveled distance and quality satisfaction with respect to changes in \(W_{d}\). The best quality satisfaction occurs when \(W_{q}=1\) (i.e., \(W_{d}=0\)); however, this is the worst-case for travel distance. As expected, the travel distance decreases as \(W_{d}\) increases, whereas the departure from quality satisfaction increases. The point at which the two objectives intersect (i.e., \(W_{d}=0.7\) and \(W_{q}=0.3\)) will be the optimal setting for both. These weights are used in the cost function in our simulation experiments. Figure 5 shows that the optimal weights change with respect to the available number of robots' quality level. As the number of robots' quality level increases, the weights of distance gets close to 0.5. This is expected as the normalized value of the difference in the distance between a robot and a task is almost the same as the difference in quality level, as we have a large number of quality level for robots' and tasks'. Figure 4: Effect of increasing the value of \(W_{d}\) on the traveled distance and the drift of quality with respect to different tasks’ quality levels. Although considering task synergy reduces the total traveled distance, it has a side effect on the workload balance objective. In Figure 6, robot \(R_{1}\) won all of the tasks, whereas robot \(R_{2}\) won nothing (i.e., using Equation (4), \((d_{1x}<d_{2x}\)\(\forall\)\(x=1,2,3,4)\). We call this problem the 'jump to the middle' problem (JMP). The JMP occurs because once the robot \(R_{1}\) wins a task located close to the middle of the area of interest, it becomes closer to more new incoming tasks. Because of the synergy definition in Equation (4), it consequently wins an increasing number of tasks, leading to a compromised load-balancing objective. Therefore, we had to re-design the cost function in Equation (5) to include the workload balance objective, and we recomputed the weights associated with each objective.