# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 4 Experimental Evaluation
### Greedy and Auction-Based Strategies  
For MRTA, a greedy approach is suitable because \"anecdotal evidence suggests that the greedy algorithm works extremely well\" [36]. Indeed, with high robot density and low task generation rate, the greedy approach performs close to the optimal solution due to its intrinsic reactive property, provided that conflicts in task assignment can be easily resolved. Similarly, with few robots but many tasks, the robotic system is often fully occupied all the time, resulting in the maximum possible efficiency. For our baseline, each robot \(r\) chooses the closest available task \(T_{i}\). We propose a variation of the trivial greedy approach by including a task swapping procedure. If a robot \(r_{p}\) committed to task \(T_{i}\) receives information related to the commitment of a second robot \(r_{q}\) to the same task, a conflict resolution procedure begins. Robot \(r_{p}\) compares its utility against \(r_{q}\)'s utility and drops its current assignment only if \(U^{r_{p}}(T_{i})<U^{r_{q}}(T_{i})\implies H_{FW}(r_{p},T_{i})<H_{FW}(r_{q},T_{ i})\). Such greedy variant does not require the concept of areas (see Section 3.2.1); thus, the utility reduces to the heuristic \(h\).  
Our proposed auction-based baseline relies on the Contract Net Protocol scheme (CNP) [44], upon which several other systems have been built (e.g., Reference [45]). Our implementation models self-interested robots without the possibility of subcontracts and transfers [37]. During every selection step, if not assigned with any task, a robot starts the announcement phase and becomes the manager for the closest task distance-wise. During  
Figure 4: Example of communication range reduction in the facility (**left**) and the lab (**right**) environments. With respect to the position marked in red, the plot highlights areas within communication range (with probability 99%) for \(S=-80\) (blue), for \(S=-100\) (green), and for \(S=-120\) (yellow).  
Figure 3: The four environments used in the experimental setup. From **left** to **right**: the split16 environment of size \(16\times 16\), the empty32 environment of size \(32\times 32\), the facility environment of size \(32\times 32\), and last the lab environment of size \(64\times 64\). Black represent walls, white and grey areas are free cells where robots can move, but tasks can appear only in the gray shadowed areas.  
the submission phase, any other non-committed robot within the communication range answers with its current bid, equals to the heuristic \(H_{\text{FW}}\) as defined in above. The selection and contract phases proceed as normal giving priority to lower bids, i.e., robots with a shorter path to the task, and we break ties by following a FIFO selection. Note that, due to the announcement phase, task-related information might be propagated farther than the original task range, potentially increasing the number of robots involved in the transaction. In obstacle-free areas and, in particular, in absence of environmental bottlenecks one can imagine the CNP baseline to act as a improved variation of the greedy approach, but in complex scenarios it has several differences. The assignment process is synchronous and considers all the robots with related utilities at once, thus locally centralizing the system for a small time-frame and generating a bigger communication overhead than the other two proposed approaches.