# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 4 Sub-Optimal Planning Methods
### Iterative Solution  
This subsection proposes an alternative sub-optimal allocation method, described in Algorithm 2. The method iteratively picks an uncollected sample whose transport to deposit requires minimum energy (line 7) and assigns it to a robot that has spent less energy (time) than other agents (lines 8-15). If a robot does not have enough energy to pick the current sample \(s\), it is removed from further assignments (lines 16-17), because the remaining samples would require more energy than \(\omega\big{(}\pi(s)\big{)}\). If the current sample \(s\) cannot be allocated to any robot, the procedure is stopped (lines 18-19), and in this case some samples remain uncollected. When Algorithm 2 reaches line 20, the robot assignments constitute a solution to Problem 1 for collecting all samples from \(S\). The robot-to-sample allocations returned by Algorithm 2 can be easily transformed to robot plans, as in lines 4-13 from Algorithm 1. The total time for completing the mission can be easily computed by maximizing over the times spent by each robot.  
```
Input:\(R,S,w,\mathcal{E}\) Output: Robot-to-sample assignments
1\(R_{assign}=R\)
2\(S_{uncollected}=S\) Set \(x(r,s)=0\), \(\forall(r,s)\in R\times S\) Let \(\mathcal{E}_{consumed}(r)=0\), \(\forall r\in R\)while\(S_{uncollected}\
eq\emptyset\)do
3\(S_{0}=S_{uncollected}\) Pick \(s\in S_{uncollected}\) s.t. \(\omega\big{(}\pi(s)\big{)}=\min_{s\in S_{uncollected}}\omega\big{(}\pi(s) \big{)}\) Sort \(R_{assign}\) based on ascending order of consumed robot energy (\(\mathcal{E}_{consumed}\)) for\(r\in R_{assign}\)do
4 if\(w(s)\leq\mathcal{E}(r)\)then
5\(x(r,s)=1\) (assign sample \(s\) to robot \(r\)) \(\mathcal{E}(r):=\mathcal{E}(r)-w(s)\) \(\mathcal{E}_{consumed}(r):=\mathcal{E}_{consumed}(r)+w(s)\) \(S_{uncollected}:=S_{uncollected}\setminus\{s\}\) Break \"for\" loop
6 else
7\(R_{assign}:=R_{assign}\setminus\{r\}\)
8 if\(S_{uncollected}=S_{0}\)then
9 Return current robot-to-sample allocations \(x\) Return robot-to-sample allocations \(x\)
```  
**Algorithm 2**Iterative heuristic solution  
Under these ideas, Algorithm 2 can be seen as a greedy approach (first collect samples that require less energy/time), while the allocations to robots with less spent energy tries to reduce the overall time until the samples are collected.  
Observe that this IH solution always returns a solution for collecting some (if not all) samples, whereas MILP from Section 3 may become computationally impracticable, while QP (8) may fail in providing a solution (Remark 3). Moreover, the software implementation of Algorithm 2 does not require additional tools, in contrast with specific optimization packages needed by MILP and QP solutions. A detailed analysis of the three methods is the goal of Section 5.  
**Example 4**: _For illustrating Algorithm 2 on the example considered in the previous sections, we give here the sample picking costs: \(\omega\big{(}\pi(s)\big{)}=16\), \(s=1,\ldots,4\), \(\omega\big{(}\pi(s)\big{)}=14\), \(s=5,\ldots,8\), \(\omega\big{(}\pi(s)\big{)}=10\), \(s=9,10\), \(\omega\big{(}\pi(11)\big{)}=8\), \(\omega\big{(}\pi(s)\big{)}=4\), \(s=12,\ldots,14\). First, IH solution allocates sample 12 to \(r_{1}\), then 13 and 14 to \(r_{2}\), \(r_{3}\), sample \(11\) to \(r_{1}\) and so on. Algorithm 1 was run in 0.015 s and it yielded the following robotic plans:_  
\[\begin{array}{l}\text{Robot $r_{1}$ collects samples from:}\\ \text{($v_{8}$), \text{($v_{5}$), \text{($v_{2}$), \text{($v_{2}$), \text{($v_{1}$)}}}}}\quad\quad\text{(time:56)}\\ \text{Robot $r_{2}$ collects samples from:}\\ \text{($v_{8}$), \text{($v_{3}$), \text{($v_{2}$), \text{($v_{1}$), \text{($v_{1}$)}}}}}\quad\quad\text{(time:60)}\\ \text{Robot $r_{3}$ collects samples from:}\\ \text{($v_{8}$), \text{($v_{3}$), \text{($v_{2}$), \text{($v_{1}$)}}}}\quad\quad\quad\quad\text{(time:44)} \\ \end{array} \tag{10}\]