# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 3 Mathematical Model and Optimal Solution  
To solve Problem 1, defined in the previous section, our approach consists from the following main steps:  
1. Determine optimal paths in graph \(G\) from storage node to all nodes containing samples. 2. Formulate linear constraints for correctly picking samples and for not exceeding robot's available energy based on a given allocation of each robot to pick specific samples. 3. Create a cost function based on robot-to-sample allocation and on necessary time for gathering all samples. 4. Cast the above steps in a form suitable for applying existing optimization algorithms and thus find the desired robot-to-sample allocations. Step (i) is accomplished by running a Dijkstra algorithm [42] on the weighted graph \(G\), with source node \(v_{|V|}\) and with multiple destination nodes: \(v\in V\) for which \(\exists s\in S\) such that \(\pi(s)=v\). Please note that a single run of Dijkstra algorithm returns minimum cost paths to multiple destinations. Let us denote with \(path(v)\) the obtained path (sequence of nodes) from deposit \(v_{|V|}\) to node \(v\in V\) and with \(\omega(v)/2\) its cost. Due to symmetrical adjacency relationship of \(G\), the return path from \(v\) to storage is immediately constructed by following \(path(v)\) in inverse order. The return path is denoted by \(path^{-1}(v)\) and it has the same cost \(\omega(v)/2\). (Because are interested in the round-trip cost between nodes \(v_{|V|}\) and \(v\), we denote the one-way cost by \(\omega(v)/2\) and thus the cost of the full path is simply denoted by \(\omega(v)\).). Therefore, for collecting and bringing to storage location the sample \(s\in S\), a robot spends \(\omega(\pi(s))\) for the round-trip given by \(path\big{(}\pi(s)\big{)}\), \(path^{-1}\big{(}\pi(s)\big{)}\). For solving steps (ii)-(iv), let us first define a decision function as \(x:N_{R}\times N_{S}\rightarrow\{0,1\}\) by:  
\[x(r,s)=\left\{ \begin{array}{ll}1,&\text{if robot $r$ picks sample $s$}\\ 0,&\text{otherwise}\end{array} \right.,\forall r\in R,s\in S. \tag{1}\]  
The actual values returned by map \(x\) for any pair \((r,s)\in R\times S\) give the most important part of solution to Problem 1, and these values are unknown, yet. The outcomes of \(x\) will constitute the decision variables in an optimization problem that is described next. Figure 1: Example: environment graph with 10 nodes, 3 robots, and 14 samples. The robot moving costs are marked on graph edges, and the samples are represented by the blue discs. Step (ii) is formulated as the following set of linear constraints:  
\[ \begin{array}{ll}\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\end{array} \,, \tag{2}\]  
where the first set of equalities impose that exactly one robot is sent to collect each sample, while the subsequent inequalities guarantee that the energy spent by robot \(r\) for collecting all its assigned samples does not exceed its available energy. The cost function from step (iii) corresponds to the first requirement of Problem 1. It means to minimize the maximum time among all robots required for collecting the assigned samples, and it formally translates to finding outcomes of \(x\) that minimize the objective function \(J(x)\) from  
\[J(x)=\min\limits_{x}\,\max\limits_{r\in R}\left(\gamma\cdot\sum\limits_{s\in S }\Big{(}\omega\big{(}\pi(s)\big{)}\cdot x(r,s)\Big{)}\right). \tag{3}\]  
The objective function from (3) and the constraints from (2) form a minimax optimization problem [43; 44]. However, decision function \(x\) should take binary values. To use available software tools when solving for values of \(x\), step (iv) transforms the minimax optimization into a MILP problem [44; 45], by adding an auxiliary variable \(z\in\mathbb{R}_{+}\) and additional constraints that replace the max term from (3). This results in the following MILP optimization:  
\[