# Resource Assignment Algorithms for Autonomous Mobile Robots with Task Offloading
## 4 Proposed Optimization Algorithms
### Metaheuristic Optimization: GA Algorithm  
Many metaheuristic algorithms are nature-inspired and have proven useful in solving a vast set of optimization problems [36]. We use an evolutionary strategy like the genetic algorithm (GA) [37]. In this algorithm, a population of potential solutions (chromosomes) is let to evolve among successive generations. Each generation passes its genes to an offspring thanks to operators such as crossover and mutation. The chromosome of the \(e\)th individual in the GA population at the \(q\)th generation is specified as  
\[\mathbf{g}_{e}^{(q)}=\left[g_{i,e}^{(q)}\right]=\left[k_{1,e}\quad m_{1,e} \quad k_{2,e}\quad m_{2,e}\quad\ldots\quad k_{N_{\text{AV}},e}\quad m_{N_{\text {AV}},e}\right], \tag{20}\]  
and its fitness is directly calculated as \(\varphi_{e}^{(q)}=\mathcal{P}(\text{M}(\mathbf{g}_{e}^{(q)}))\). The initial population of \(N_{\text{GA}}\) individuals is generated with genes randomly distributed among the admissible values, i.e., \(g_{i,e}^{(0)}\sim\mathcal{U}[0,g_{i_{\text{MAX}}}]\), with \(g_{i_{\text{MAX}}}\) being \(N_{\text{BS}}\) for the elements in the odd positions in (20) and \(N_{\text{DC}}\) for the elements in the even positions. Another possibility is to assign to the initial population the internal service configuration, i.e., \(g_{i,e}^{(0)}=0\). To pass their genes among generations, parent chromosomes are chosen with fitness-proportionate selection (roulette wheel). The crossover operation generates offsprings by uniformly exchanging the parents' alleles, \((\mathbf{g}_{e^{\prime}}^{(q+1)},\mathbf{g}_{e^{\prime\prime}}^{(q+1)})= \text{XOV}(\mathbf{g}_{e^{\prime}}^{(q)},\mathbf{g}_{e^{\prime\prime}}^{(q)})\): a pair \((g_{2i},g_{2i+1})\) is exchanged in the offsprings with probability \(p_{\text{X}}=0.5\). In addition, 80% of the population is chosen for crossover, while the remaining 20% of the population does not withstand crossover. A graphical example of the crossover operation is shown in Figure 4.  
The mutation operation, similarly to crossover, randomly changes a pair \((g_{2i},g_{2i+1})\) with probability \(p_{\text{M}}=0.01\) to another admissible value, \(\mathbf{g}_{e^{\prime}}^{(q+1)}=\text{MUT}(\mathbf{g}_{e^{\prime}}^{(q)})\); a pair \((g_{2i},g_{2i+1})\) assumes random values chosen among the possible valid configurations for AV \(i\), as shown in Figure 5.  
Figure 4: Graphical overview of the crossover operation in the GA algorithm.  
An elite subpopulation (top 5% of individuals with the highest fitness) remains unchanged among the generations. The \(\hat{e}\)th chromosome with the highest fitness,  
\[\hat{\varphi}^{(q)}=\varphi_{\hat{e}}^{(q)},\;\;\hat{e}=\arg\max_{\hat{e}}\varphi _{\hat{e}}^{(q)}, \tag{21}\]  
represents a candidate solution. The GA search process stops either when the best fitness value stalls for \(q_{\text{STL}}\) generations,  
\[\hat{\varphi}^{(q)}=\hat{\varphi}^{(q-1)}=\ldots=\hat{\varphi}^{(q-q_{\text{ STL}})}, \tag{22}\]  
or when a maximum number \(q_{\text{MAX}}\) of generations has occurred. The complexity depends on the convergence speed of the GA population to the exact solution and on the number of calls \(N_{\text{call}}\) to the latency expression (17), so it is \(\mathcal{O}(N_{\text{AV}}N_{\text{BS}}N_{\text{DC}}N_{\text{call}})\). (We do not consider the complexity of selection, crossover, and mutation. Instead, in Section 5, the cost of these operations is counted in the total running time.)