# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 3 Mathematical Model and Optimal Solution
\begin{array}{ll}\min\limits_{x,z}&z\\ \text{s.t.:}&\sum\limits_{r\in R}x(r,s)=1\,,\;\forall s\in S\\ &\sum\limits_{s\in S}\Big{(}\omega\big{(}\pi(s)\big{)}\cdot x(r,s)\Big{)}\leq \mathcal{E}(r)\,,\;\forall r\in R\\ &\gamma\cdot\sum\limits_{s\in S}\Big{(}\omega\big{(}\pi(s)\big{)}\cdot x(r,s) \Big{)}\leq z\,,\;\forall r\in R\\ &x(r,s)\in\{0,1\}\,,\;\forall(r,s)\in R\times S\\ &z\geq 0\end{array} \,. \tag{4}\]  
The MILP (4) can be solved by using existing software tools [46; 47; 48]. The solution is guaranteed to be globally optimal because both the feasible set defined by the linear constraints from (4) and the objective function (\(z\)) are convex [45; 49]. Thus, solution of (4) gives the optimal outcomes for \(x\) (unknown decision variables \(x(r,s)\)), as well as the time \(z\) in which the team solves Problem 1. Please note that the obtained map \(x\) indicates the samples that must be collected by each robot, as in (1). However, it does not impose any order for collecting these samples. For imposing a specific sequencing, each robot is planned to collect its allocated samples in the ascending order of the necessary costs. This means that robot \(r\) first picks the sample \(s\) for which \(x(r,s)=1\) and \(\omega\big{(}\pi(s)\big{)}\leq\omega\big{(}\pi(s^{\prime})\big{)}\), \(\forall s^{\prime}\in S\) with \(x(r,s^{\prime})=1\), and so on for the other samples. The optimum path for collecting sample \(s\) from node \(\pi(s)\) was already determined in step (i). Under the above explanations, Algorithm 1 includes the steps for obtaining an optimal solution for Problem 1. **Example 2**. : _We apply the optimal solution from this section on the example introduced in Section 2. The Dijkstra algorithm (line 1 from Algorithm 1) returns paths and corresponding energy for collecting each sample, e.g., \(path(\pi(1))=path(v_{1})=v_{10},v_{9},v_{1}\) and \(\omega\big{(}\pi(1)\big{)}=16\). The MILP (4) was solved in about 0.7 s and it returned an optimal solution with \(z=54\) (time for fulfilling Problem 1) and allocation map \(x\). Based on robot-to-sample allocations \(x\), lines 3-13 from Algorithm 1 yield the robotic plans for collecting samples from the following nodes (the sequences of nodes and the collect/deposit commands are omitted due to their length):_  
\[\begin{array}{ll}&\  
MILP (4) has a non-empty feasible when the required energy for collecting all samples is small enough, or when the available energy limits \(\mathcal{E}(r)\) are large enough. This is because the connectedness of \(G\) implies that the coefficients \(\omega\big{(}\pi(s)\big{)}\) are finite, \(\forall s\in S\). Therefore, the first two sets of constraints from (4) could be satisfied even by an initial solution of form \(x(r,s)=1\) for a given \(r\in R\), \(\forall s\in S\), and \(x(r^{\prime},s)=0\) for any \(r^{\prime}\in R\setminus\{r\}\).  
This aspect yields the idea that one can relax the first constraints from (4) whenever there is no solution, i.e., collect as many samples as possible with the available robot energy. Such a formulation is given by the MILP problem (6), which allows that some samples are not collected (inequalities in first constraints) and imposes a penalty in the cost function for each uncollected sample. Basically, for a big enough value of \(W>0\) from (6), any uncollected sample would increase the value of the objective function more than the decrease resulted from saved energy. The constant \(W\) can be lower-bounded by:  
\[W\,>\,\gamma\cdot\sum\limits_{s\in S}\omega\big{(}\pi(s)\big{)}.\]  
For this lower bound, the cost function increases whenever a sample \(s\) is not collected, because the term \(z\) decreases with \(\gamma\cdot\omega\big{(}\pi(s)\big{)}\) and the second term increases with more than this value. Since MILP optimization returns a global optimum, minimizing the cost function under constraints from (6) guarantees that the largest possible number of samples are collected while minimizing the necessary time.