# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 4 Sub-Optimal Planning Methods
### Quadratic Programming Relaxation  
We aim to relax the binary constraints from MILP (4), and for accomplishing this we embed them into a new objective function. The idea starts from various penalty formulations defined in [52], some being related to the so-called big M method [49].  
Let us replace the binary constraints \(x(r,s)\in\{0,1\}\) from (4) with lower and upper bounds of 0 and respectively 1 for outcomes of map \(x\). At the same time, add to the cost function of (4) a penalty term depending on \(M>0\), as shown in the objective  
\[\min_{x,z}\;z\;+\;M\cdot\sum_{r\in R}\sum_{s\in S}\Big{(}x(r,s)\cdot\big{(}1-x( r,s)\big{)}\Big{)}. \tag{7}\]  
For a large enough value of the penalty parameter \(M\), the minimization of the new cost function from (7) tends to yield a binary value for each variable \(x(r,s)\). This is because only binary outcomes of \(x\) imply that the second term from sum (7) vanishes, while otherwise this term has a big value due to the large \(M\). The quadratic objective from (7) can be re-written in a standard form of an objective function of a QP problem, and together with the remaining constraints from (4) we obtain the QP formulation:  
\[\begin{array}{ll}\min_{x,z}&z\;+\;M\cdot\sum\limits_{r\in R}\sum\limits_{s \in S}x(r,s)\;-\;M\cdot\sum\limits_{r\in R}\sum\limits_{s\in S}\big{(}x(r,s) \big{)}^{2}\\ \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\\ &0\leq x(r,s)\leq 1\,,\;\forall(r,s)\in R\times S\\ &z\geq 0\end{array}. \tag{8}\]  
Under the above informal explanations and based on formal proofs from [52], the MILP (4) and QP (8) have the same global minimum for a sufficiently large value of parameter \(M\) (The actual value of \(M\) is usually chosen based on numerical ranges of other data from the optimization problem, as values returned by maps \(\omega\) and \(\mathcal{E}\).).  
**Remark 3** (Sub-optimality or failure).: _Please note that the cost function from (8) is non-convex, because of the negative term in \(x(r,s)^{2}\). Therefore, optimization (8) could return local minima, while in some cases the obtained values of \(x\) may even be non-binary. If the obtained outcomes of \(x\) are binary, the value of completion time \(z\) for collecting all samples is directly returned as the cost of QP (8), while otherwise a large cost is obtained due to the non-zero term in \(M\) from (7)._  
The QP optimization (8) can be solved with existing software tools [46; 48]. As noted, it may return a sub-optimal solution. Nevertheless, such a sub-optimal solution is preferable when the optimal solution from Section 3 is computationally intractable. If the QP returns a (local minimum) solution with non-integer values for outcomes of map \(x\), then this result cannot be used for solving Problem 1.  
**Example 3**.: _Consider again the example from the end of Section 2. The paths in \(G\) and outcome values of map \(\omega\) were already computed as in Section 3, where the optimal cost from MILP (4) was 54. QP (8) was solved in less than 0.4 s and it led to a sub-optimal total time of 60 for bringing all samples in \(v_{10}\). The robots were allocated to collect samples as follows:_  
\[\begin{array}{ll}\text{Robot}\;r_{1}\;\text{collects samples from:}\\ (v_{8}),\;(v_{3}),\;(v_{2}),\;(v_{1}),\;(v_{1})&(\text{time}:60)\\ \text{Robot}\;r_{2}\;\text{collects samples from:}\\ (v_{8}),\;(v_{8}),\;(v_{3}),\;(v_{2}),\;(v_{1})&(\text{time}:48)\\ \text{Robot}\;r_{3}\;\text{collects samples from:}\\ (v_{5}),\;(v_{2}),\;(v_{2}),\;(v_{1})&(\text{time}:52)\end{array} \tag{9}\]A similar QP relaxation may be constructed for MILP (6) by considering \(M>>W\).