# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## 1 Introduction  
Much robotics research develops automatic planning procedures for autonomous agents such that a given mission is accomplished under an optimality criterion. The missions are usually related to standard problems such as navigation, coverage, localization, and mapping [1, 2]. Some works provide strategies directly implementable on particular robots with complicated dynamics and multiple sensors [3]. Other research aims to increase the task expressiveness [4], e.g., starting from Boolean-inspired specifications [5, 6] up to temporal logic ones [7, 8, 9, 10], even if the obtained plans may be applied only to simple robots. It is often common to construct discrete models for the environment and robot movement capabilities, by using results from multiple areas such as systems theory, computational geometry [11, 12], and discrete event systems [13, 14]. The current research is focused on solving a sample gathering problem. The considered task belongs to the general class of optimal assignment problems [15], since the sample can correspond to jobs and the robots to machines. The minimization of the overall time for gathering all samples (yielded by the \"slowest\" agent) thus translates to so-called min-max problems [16] or bottleneck assignment problems [15] (Chapter 6.2). However, these standard frameworks do not consider different numbers of jobs and machines, nor machines (agents) with limited energy amounts. A broad taxonomy of allocations in multi-robot teams is presented in [17; 18], according to which our problem belongs to the class of assignments of single-robot tasks (one task requiring one robot) in multi-task robot systems (a robot can move, pick up, and deposit samples). Again, the general solutions assume utility estimates for different job-machine pairs. For such problems, various Mixed-Integer Linear Programming Problem (MILP) formulations are given as in [17; 19; 20]. Some resemble our problem, but they are not an exact fit because of the specificities that all samples should be eventually gathered into the same node, a robot can carry one sample at a time, there are limited amounts of energy, and we do not know a priori a relationship between number of samples and number of robots. Furthermore, we provide a second MILP for the case of problems infeasible due to energy requirements. We further relax the complex MILP solutions into sub-optimal solutions as non-convex Quadratic Programming (QP) and iterative heuristics. Our goal is to draw rules of choosing the appropriate method for a given problem, based on extensive tests. Some preliminary mathematical formulations that generalize traveling salesman problems are included in [21], with targeted application to exploring robots that must collect and analyze multiple heterogeneous samples from a planetary surface. Other works focus on specific applications as task allocation accomplished by agents with different dynamics [22], or allocation in scenarios with heterogenous robots that can perform different tasks [23]. Various works propose auction-based mechanisms for various assignments problems or develop and apply distributed algorithms for specific cases with equal number of agents and tasks [24]. Research [25] assumes precedence constraints on available tasks and builds solutions based on integer programming forms and auction mechanisms. However, we do not include auction-based methods here. The closest solution we propose may be our iterative heuristic algorithm from Section 4.2, which can be viewed as a specific greedy allocation method [17]. Our problem can be seen as a particular case of Capacity and Distance constrained Vehicle Routing Problem (CDVRP) [26] with capacity equal to one and the distance constrains related to the limited energy. For this problem, many algorithms have been provided, for the exact methods [27; 28] and for heuristic methods [29; 30; 31; 32]. However, our problem is different in multiple aspects.