## 5 Task Allocation Scheme
### Task Selection Algorithm  
The task selection process employs the multi-objective utility function \(\Phi\) defined in (7) with \(\alpha_{\text{HO}}\) values dynamically adapted by (15) to solve the _MRTA_ problem stated in Secion 2.5. The corresponding algorithm is sketched in Algorithm 2. ```
1:functiongetASSignment(\(i\), \(R^{*}\), \(T\), \(M\), HO-Threshold)
2:\(\triangleright\) i stands for the robot position in vector \(R^{*}\). 3:\(\triangleright\)\(R^{*}\) stands for the robots location vector. 4:\(\triangleright\) T stands for the current tasks location vector. 5:\(\triangleright\) M stands for the fleet size. 6:\([T^{u},T^{a}]\gets T\)
7:\(R^{u}\gets R^{*}\)
8:\(T^{\text{HO}}\leftarrow\{T_{j}\mid T_{j}\in T^{u},\Delta_{k}(T_{j})\leq \text{HO-Threshold},\forall R_{k}\in R^{u}\}\)\(\triangleright\) Relative distance \(\Delta_{k}(T_{j})\) is defined in Section 3.2. 9:for each \(k\) in \(R^{u}\)do
10:for each \(j\) in \(T^{\text{HO}}\)do
11:\(PU[k,j]=\Psi_{k}(T_{j})\)\(\triangleright\) Path utility matrix. 12:endfor
13:\(\alpha_{\text{HO}}\leftarrow\dfrac{\Omega_{1}}{1-\Psi_{i}(\text{HO-Threshold})+\Omega_{1}}\)\(\triangleright\) (15)
14:\(\beta=1-\dfrac{1}{\Lambda_{\text{HO}}^{\text{HO}}}|\)
15:\(N^{\text{HO}}=|T^{\text{HO}}|\)
16:\(M^{u}=|R^{u}|\)
17:\(T2 RDist\gets M^{u}\)\(ArN^{\text{HO}}_{M^{u}}\)\(\triangleright\) Tasks-to-robots distributions \(T2 RDist\in\mathbb{N}^{|Ar^{\text{HO}}_{M^{u}}|\times M^{u}}\)
18:for each row \(r\) in \(T2 RDist\)do
19:\(\Phi[r]=\sum_{k=1}^{M^{u}}\alpha_{\text{HO}}\cdot PU[k,j]+\beta\cdot\Omega_{k} \left(T^{\text{HO}}_{j},[R^{u},T^{a}]\right),j=T2 RDist(r,k)\)
20:endfor
21:\(T^{*}\gets T2 RDist[r,i]\mid\arg\max_{r}\Phi[r]\)
22:return\(T^{*}\)
23:endfunction
```  
**Algorithm 2** Task selection algorithm. Firstly, the input parameter \(R^{*}\) specifically corresponds to the locations of the teammates currently connected with the robot \(R_{i}\). Next, in lines 2 and 3, both the _task_ and _robot_ location sets are split up into two subsets each one (assigned and unassigned items, respectively). Line 4 is in charge of taking only the unassigned tasks that are within the _HO-Threshold_ scope from every robot. Afterwards, from lines 5 until 9, the path utility matrix is computed regarding all possible task-robot combinations. Next, lines 10 and 11 aim to compute the \(\alpha_{\text{HO}}\) and \(\beta\) values according to (15). The set of tasks-to-robots distributions is calculated from line 12 to 14. Finally, from line 15 to 17 all possible assignments are evaluated using the \(\Phi\) function while the task corresponding to robot \(i\) of the best assignment is selected in line 18. Some considerations on Algorithm 2 are hereafter discussed. Concerning the computation of the set of tasks-to-robots distributions (lines 12 to 14), it provides a way to potentially avoid falling in local minima or even taking wrong decisions. Note that the _connectivity utility_ function is subject to locality conditions and thus, it is not possible to compute optimal distributions from the application of iterative polynomial-time assignation algorithms such as the _Hungarian method_[14]. On the contrary, Algorithm 2 can choose the optimum tasks-to-robots distribution by evaluating all possible \(T^{\text{HO}}\)-to-\(R^{u}\) distributions. Nevertheless, this process may be potentially very hard since \(|Ar^{\text{HO}}_{M^{u}}|=\frac{N^{\text{HO}}_{1}}{(N^{\text{HO}}-M^{u})! }= \Gamma^{n}_{m=1}(N^{\text{HO}}-m+1)=\Gamma^{n-1}_{m=0}(N^{\text{HO}}-m)\to O (N^{*M^{u}})\). Therefore, the smaller \(|T^{\text{HO}}|\) and \(|R^{u}|\) the faster the algorithm will run. In the first case \(|T^{\text{HO}}|\) is bounded by pruning \(|T^{u}|\) with the help of _HO-Threshold_. On the contrary, even being naturally bounded (\(|R|\geq|R^{*}|\geq|R^{u}|\)), the set \(R\) could imply a large \(R^{u}\). Besides, all efforts are to keep the fleet connected as much as possible, leading to \(|R^{*}|\rightarrow|R|\).