# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 1 Introduction
First, in the CDVRP problem, the capacity of each vehicle (robot in our case) should be greater than the demand of each vertex [26]. In our case this cannot hold since the robot capacity is one (we assume that each robot can transport maximum one good) and the number of goods at the vertices is, in many cases, greater than one. Second, up to our knowledge, the heuristics considered in this work, which include relaxing the optimal solution of the MILP to a QP problem, have not been considered for the CDVRP. Finally, most of the works on CDVRP try to characterize worst-case scenarios through cost differences between heuristic and optimal methods. In this paper, we are also interested in the computational complexity and we evaluate the proposed solutions using numerical simulations. To the best of our knowledge, none of the mentioned works contains a directly applicable formulation that yields a solution for our specific problem. This work builds on solutions reported in [33; 34; 35]. In [33] we constructed a MILP problem that solves the minimum time sample gathering problem. Different than in [33], we also design a MILP solution that can be used when the initial problem is infeasible due to scarce energy limits. Besides the MILP formulations, one of the main goals of this research are to provide computationally efficient sub-optimal solutions for the targeted problems. The MILP solution was relaxed to a QP formulation in [34]. Here we also construct an iterative sub-optimal solution inspired by [35] as a QP alternative. Based on extensive simulations that involve the three proposed solutions, we conclude with a decision scheme that helps a user to choose the appropriate method for a specific problem instance. The purpose of this work is to plan a team of mobile agents such that they gather the samples scattered throughout the environment into a storage facility. The problem's hypothesis consists in a team of mobile robots which must bring to a deposit region a set of samples that exist in an environment at known locations. As main contributions we claim the new mathematical models for the considered problems and the numerical evaluation of the obtained solutions. The environment is modeled by a graph where an arc weight corresponds to consumed energy and time for moving between the linked nodes. Each robot has limited energy, and the goal is to collect all samples in minimum time. Because the robots are initially deployed in the storage (deposit) node and given the static nature of the environment, it is customary to build movement plans before the agents start to move. The problem reduces to a specific case of optimal assignment or task allocation [15; 17; 18]. The paper combines results from our previous research reported in [34; 36; 37]. We first build an optimal solution involving a MILP formulation. Then, we design two solutions with lower complexities, one as a Quadratic Programming (QP) relaxation of the initial MILP, and the other as an Iterative Heuristic (IH) algorithm. A numerical evaluation between the formulated solutions yields criteria as time complexities for computing robotic plans and the difference of costs between these plans. Based on these criteria, a decision diagram is provided such that a user can easily choose the appropriate method to embed. The remainder of the paper is structured as follows. Section 2 formulates the targeted problem, outlines the involved assumptions and introduces an example that will be solved throughout the subsequent sections. Section 3 details two optimal solutions, from which the first will be relaxed to a QP formulation, while the second can be used when robots have low energy supplies. The sub-optimal methods based on QP optimization or IH algorithm are presented in Section 4. The developed methods are numerically evaluated and compared in Section 5 and rules are given for choosing the proper method for a specific problem instance.