# Resource Assignment Algorithms for Autonomous Mobile Robots with Task Offloading
## 4 Proposed Optimization Algorithms
### Greedy Approximation: SM Algorithm  
We approximate the problem (3.2) by using a greedy procedure, where each AV optimizes its own configuration without modifying that of the others. We use the natural ordering of the AVs. Since the minimizations are performed successively, we define this approximation as a sequential minimization (SM). We reformulate the original problem by considering an iterative minimization procedure to find partial solutions. By defining \(q=0,1,2,\dots\) as the iteration index, \((\mathbf{f}^{(q)},\mathbf{S}^{(q)})\) as the optimal configuration found at the \(q\)th iteration, and \(f_{i}^{(0)}=1\) with \(S_{i,k,m}^{(0)}=0\) as the initial configuration of the \(i\)th AV, we rewrite the problem (3.2) as  
\[\min_{f_{i}^{(q)}}\mathbf{S}_{i}^{(q)} \sum_{i=1}^{N_{\text{AV}}}L_{i}(\mathbf{f}^{(q)},\mathbf{S}^{(q)})\] (28) subject to \[\mathbf{f}^{(q)}\in\{0,1\}^{N_{\text{AV}}}\] \[\mathbf{S}^{(q)}\in\{0,1\}^{N_{\text{BS}}\times N_{\text{DC}}N_{ \text{AV}}}\] \[f_{i}^{(q)}+\sum_{k=1}^{N_{\text{BS}}}\sum_{m=1}^{N_{\text{DC}}} S_{i,k,m}^{(q)}=1,\;i=1,\dots,N_{\text{AV}},\] \[f_{i}^{(q)}=f_{i}^{(q-1)},\forall i\
eq i^{\prime},\;i=1,\dots,N _{\text{AV}},\] \[\mathbf{S}_{i}^{(q)}=\mathbf{S}_{i}^{(q-1)},\forall i\
eq i^{ \prime},\;i=1,\dots,N_{\text{AV}},\]  
where \(i^{\prime}\) is the index of the AV to be optimized in the \(q\)th iteration, defined as  
\[i^{\prime}= \begin{cases}1+(q-1)\text{ mod }N_{\text{AV}},&q\leq\vartheta N_{\text{AV}},\\ \arg\max_{i}L_{i}(\mathbf{f}^{(q-1)},\mathbf{S}^{(q-1)}),&q>\vartheta N_{ \text{AV}},\end{cases}  \tag{29}\]  
\(q>0\), and \(\vartheta\geq 1\) defines the number of times all the AVs are sequentially processed. The process stops after \(q_{\text{STOP}}\) iterations such that  
\[L_{i}(\mathbf{f}^{(q_{\text{STOP}})},\mathbf{S}^{(q_{\text{STOP}})})=L_{i}( \mathbf{f}^{(q_{\text{STOP}}-1)},\mathbf{S}^{(q_{\text{STOP}}-1)})\wedge q_{ \text{STOP}}>\vartheta N_{\text{AV}}\;. \tag{30}\]  
Note that this minimization procedure is greedy: at each step, each AV tries to minimize the average latency of all AVs, exploring only its own assignment subset, conditioned on the assignment at the previous iteration for the other AVs. The resulting procedure is listed in Algorithm 1. ```
\(\theta\geq 1\) \((\mathbf{k}^{*},\mathbf{m}^{*})\leftarrow(\mathbf{0}_{1\times N_{\text{AV}}}, \mathbf{0}_{1\times N_{\text{AV}}})\)\(\triangleright\) Solution holder \((\mathbf{k},\mathbf{m})\leftarrow(\mathbf{0}_{1\times N_{\text{AV}}},\mathbf{0}_{1 \times N_{\text{AV}}})\)\(\triangleright\) Initial and current configuration \(P^{*}\leftarrow\infty\)\(\triangleright\) Solution KPI \(q\gets 0\)\(\triangleright\) Flag variable while true do\(\triangleright\) Infinite loop \(q\gets q+1\)\(\triangleright\) Increment flag if\(q\leq\theta N_{\text{AV}}\)then\(\triangleright\) Optimize AVs one by one \(i\gets 1+(q-1)\bmod N_{\text{AV}}\)\(\triangleright\) Enumerate all AVs else\(\triangleright\) Optimize the slowest \(i=\arg\max_{\forall}L_{\forall}(\mathbf{M}(\mathbf{k},\mathbf{m}))\)\(\triangleright\) Find the highest latency endif \((\mathbf{k},\mathbf{m})\leftarrow\arg\min_{k_{\forall},m_{\forall}}\mathcal{P}( \mathbf{M}(\mathbf{k},\mathbf{m}))\)\(\triangleright\) Improve KPI on a single AV if\(\mathcal{P}(\mathbf{M}(\mathbf{k},\mathbf{m}))<P^{*}\)then\(\triangleright\) There is some improvement in the KPI \((\mathbf{k}^{*},\mathbf{m}^{*})\leftarrow(\mathbf{k},\mathbf{m})\)\(\triangleright\) Better configuration found \(P^{*}\leftarrow\mathcal{P}(\mathbf{M}(\mathbf{k}^{*},\mathbf{m}^{*}))\)\(\triangleright\) Better KPI found else\(\triangleright\) There is no KPI improvement if\(q>\theta N_{\text{AV}}\)then\(\triangleright\) Did the first phase break \(\triangleright\) Exit from infinite loop endif endwhile
```  
**Algorithm 1** Sequential minimization (SM) of average latency. During an initial phase, the algorithm explores the solution subspace where every AV is optimized sequentially, one by one, while keeping the other AVs' configurations unchanged.