# Numerical Evaluation of Sample Gathering Solutions for Mobile Robots
## Problem Formulation  
Consider a team of \(N_{R}\) identical robots that are labeled with elements of set \(R=\{r_{1},r_{2},\ldots,r_{N_{R}}\}\). The robots \"move\" on a weighted graph \(G=(V,E,c)\), where \(V=\{v_{1},v_{2},\ldots,v_{|V|}\}\) is the finite number of nodes (also called locations or vertices), \(E\subseteq V\times V\) is the adjacency relationship corresponding to graph edges, and \(c:E\rightarrow\mathbb{R}_{+}\) is a cost (weight) function. We mention that there are multiple approaches for creating such finite-state abstractions of robot control capabilities in a given environment [1; 2]. A widely used idea is to partition the free space into a set of regions via cell decomposition methods, each of these regions corresponding to a node from \(V\)[6; 11; 38]. The graph edges correspond to possible robot movements between adjacent partition regions, i.e., \(\forall v,v^{\prime}\in V\), if an agent can move from location \(v\) to \(v^{\prime}\) without visiting any other node from graph, then \((v,v^{\prime})\in E\). Each edge corresponds to a continuous feedback control law for the robot such that the desired movement is produced, and various methods exist for designing such control laws based on agent dynamics and partition types [39; 40]. Alternatives to cell decomposition methods, as visibility graphs or generalized Voronoi diagrams, can also produce discrete abstractions in form of graphs or transition systems [1]. We assume that the graph \(G\) is connected, and the adjacency relationship \(E\) is symmetric, i.e., if a robot from \(R\) can travel from location \(v\) to \(v^{\prime}\), then it can also move from \(v^{\prime}\) to \(v\). For any \((v,v^{\prime})\in E\), we consider that the cost \(c(v,v^{\prime})\) represents the amount of _energy_ spent by the robot for performing the movement from \(v\) to \(v^{\prime}\) and that \(c(v^{\prime},v)=c(v,v^{\prime})\). By assuming identical agents with constant velocity and a homogenous environment (i.e., the energy for following an arc is proportional with the distance between linked nodes), we denote the _time_ necessary for performing the movement from location \(v\) to \(v^{\prime}\) by \(\gamma\cdot c(v,v^{\prime})\), where \(\gamma\in\mathbb{R}_{+}\) is a fixed value. Initially, all agents are deployed in a storage (deposit) node \(v_{|V|}\) (labeled for simplicity as the last node in graph \(G\)), and each robot \(r\in R\) has a limited amount of energy, given by map \(\mathcal{E}:R\rightarrow\mathbb{R}_{+}\), for performing movements on abstraction \(G\). For homogenous environments and constant moving speeds, energy \(\mathcal{E}(r)\) can be easily linked with battery level of robot \(r\), with the distance it can travel, or the sum of costs of followed edges. There are \(N_{S}\)_samples_ or valuable items scattered throughout the environment graph \(G\). The samples are indexed (labeled) with elements of set \(S=\{1,2,\ldots,N_{S}\}\), while a map \(\pi:S\to V\) shows to which node each sample belongs. **Problem 1**. : _For every robot \(r\in R\) find a moving strategy on \(G\) such that:_  
* _the team of robots gathers (collects) all samples from graph_ \(G\) _in the storage node_ \(v_{|V|}\) _within minimum time;_
* _each robot can carry at most one sample at any moment;_
* _the total amount of energy spent by each robot is at most its initially available energy._  
**Remark 1** (NP-hardness). : _Our problem is related to the so-called Set Partitioning Problems (SPPs) [17], which are employed in various task allocation problems for mobile agents. A SPP formulation aims to find a partition of a given set such that a utility function defined over the set of acceptable partitions with real values is maximized. Various SPPs are solved by using Operations Research formulations that employ different standard optimization problems. In our case, the given set is \(S\) (samples to be collected), while the desired partition should have \(N_{R}\) disjoint subsets of \(S\), each subset corresponding to the samples a robot should collect.