# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 5 Numerical Evaluation and Comparative Analysis  
### Additional Examples  
Besides the remarks and examples from Sections 3 and 4, we present some slight modifications of the Example from Section 2 with the purpose of emphasizing the need for a comparative analysis of the three proposed solutions.  
**Example A:** Let us add one more sample in node \(v_{1}\) of the environment from Figure 1, leading to a total number of 15 samples. By running the MILP optimization (4), a solution was obtained in almost 40 s and it leads to an optimum time of 60. The QP relaxation (8) was run in almost 0.4 s (negligible increase from example from Section 4.1), and it implied a time cost of 62 for collecting all samples. The IH solution from Algorithm 2 yielded a cost of 60 in 0.016 s (practically no different to in Section 4.2). The actual robotic plans are omitted for this case.  
**Example B:** If we assume a team of 4 robots for Example A, the MILP running time exhibits a significant decrease, being solved in less than 0.1 s. The QP optimization was solved in 0.5 s, and the IH in less than 0.02 s. The resulted time costs were 44 for MILP (optimum) and 50 for QP and IH (sub-optimum).  
**Example C:** By adding one more robot to the team from Example B, the MILP optimization did not finish in 1 h, so it can be declared computationally unfeasible for this situation. The QP optimization finished in slightly more than 0.5 s, while the IH in around 0.02 s. Both QP and IH solutions returned a cost of 40.  
Similar modifications of the above examples suggested the following empirical ideas:  
* The running time of the MILP optimization may exhibit unpredictable behaviors with respect to the team size and to the number and position of samples, leading to impossibility of obtaining a solution in some cases;
* In contrast to MILP, the running times of the QP and IH solutions have insignificant variations when small changes are made in the environment;
* When MILP optimization finishes, the sub-optimal costs obtained by solutions from Section 4 are generally acceptable when compared to the optimal cost;
* In some cases the QP cost was better than the one obtained by IH, while in other cases the vice versa, but again the observed differences were fairly small.  
The above ideas were formulated only based on a few variations of the same example. However, they motivate the more extensive comparison performed in the next subsections between the computation feasibility and outcomes of MILP, QP, and IH solutions.  
**Remark 4**: _As mentioned, complexity orders of MILP and QP solutions cannot be formally given. However, as is customary in some studies, we here recall the number of unknowns and constraints of these optimizations. MILP (4) and QP (8) have each \(N_{R}\times N_{S}+1\) unknowns (from which \(N_{R}\times N_{S}\) are binary in case of MILP (4))and \(2N_{R}+N_{S}\) linear constraints. IH solution has complexity order \(\mathcal{O}(N_{R}\times N_{S})\), based on iterative loops from Algorithm 2 but, in all our studies the execution time of the algorithm is very small._  
**Real-time example:** Sample collecting experiments were implemented on a test-bed platform by using two Khepera robots equipped with plows for collecting items [53]. For exemplification, a movie is available at [[https://www.youtube.com/watch?v=2](https://www.youtube.com/watch?v=2) BQiWvquP7w]([https://www.youtube.com/watch?v=2](https://www.youtube.com/watch?v=2) BQiWvquP7w). In the mentioned scenario, the graph environment is obtained from a cell decomposition [1; 11] and a greedy method is employed for planning the robots. Although the collision avoidance problem is not treated in this paper, in the mentioned experiment the possible collisions are avoided by pausing the motion of one robot. In future work we intend to embed formal tools inspired by resource allocation techniques for collision and deadlock avoidance [54; 55].