# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 5 Numerical Evaluation and Comparative Analysis
### Results  
The results from item (vii) allow us to draw some rules that guide a user to choose MILP, QP, or IH solution when solving a specific instance of Problem 1. The following figures present and comment these results, leading to the decision diagram from the end of this section. Figure 2 illustrates the success rates of the optimization problems from Sections 3 and 4.1, respectively. For a clearer understanding, Figure 3 presents pairs \((N_{R},N_{S})\) when MILP (4) fails  
in more than 50% from each set of 50 trials (see item (v) from Section 5.2). It is noted that MILP generally returns optimal solutions for small values of \(N_{R}\) and \(N_{S}\) and fails (because of optimization time limit) for larger values. QP returns usually returns feasible solutions, excepting some cases with small values of \(N_{R}\) and \(N_{S}\). Figure 4 presents the average computation time over the successful trials, for each solution we proposed. The representation is omitted for pairs \((N_{R},N_{S})\) when there are less than 5 (from 50) successful trials--as it is often the case for MILP solver, when \(N_{R}\geq 3\) and \(N_{S}\geq 13\). MILP time may sudden variations, whereas the times for QP and IH indicates predictable behaviors. The IH time is very small (note axis limits in Figure 4) and exhibits negligible variations versus \(N_{R}\) and almost linear increases versus \(N_{S}\), due to the main iteration loop from Algorithm 2. Figure 3: MILP (4): 2D projection for failures, defined as success rate of less than 50%. Figure 2: Success rates of MILP (**a**) and QP (**b**) vs. number of robots \(N_{R}\) and number of samples \(N_{S}\). To suggest the confidence intervals of values plotted in Figure 4, we mention that:  
* For \(N_{R}=3\) and \(N_{S}=15\), when the success rate of each optimization exceeds 98%, the standard deviations of optimization times are: 15 for MILP, 0.01 for QP, 0.002 for IH;
* For \(N_{R}=10\) and \(N_{S}=50\), when QP has 96% success rate, the standard deviations of optimization times are: 0.23 for QP and 0.003 for IH. Figure 5 presents the averaged relative differences of costs yielded by the three proposed solutions for solving Problem 1. As visible in Figure 5a, the QP (sub-optimal) cost is usually less than \(120\%\ldots 130\%\) of optimal MILP cost. More specifically, from all the 25,000 trials, in 8443 cases (about 33%) both optimizations succeeded. After averaging cost differences versus \((N_{R},N_{S})\), we obtained 348 points for representing Figure 5a, and in 330 cases the cost difference was less than 20%. Figure 5b compares the costs yielded by the sub-optimal solutions from Section 4 by representing variations of the IH cost related to the QP one. It follows that usually IH yields a higher cost than QP, but the difference decreases below \(5\%\ldots 10\%\) with the increase in problem complexity. Further studies can be conducted towards formulating a conjecture that gives a formal tendency for the variation of cost difference based on problem size. However, one issue for such a study is mainly given by the necessity of obtaining the optimal cost even for large problems, i.e., solving large MILP optimizations. For more complex problems (\(N_{R}>10\), \(N_{S}>50\)), the time tendencies from Figure 4b,c and the cost differences from Figure 5b suggest that the IH solution is preferable as a good trade-off between planning complexity and resulted cost. Figure 4: Average optimization times, for \((N_{R},N_{S})\) pairs for which at least 5 feasible solutions from the 50 tests were obtained: (**a**) MILP (4), (**b**) QP (8), (**c**) IH from Algorithm 2. Figure 5: Differences between costs induced by the three solutions: (**a**) difference between QP and MILP costs, related to the optimal MILP cost; (**b**) difference between IH and QP sub-optimal costs, related to QP cost. Extensive simulations yielded quantitative comparison criteria.