# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 2 Related Work  
Centralized approaches to coupled MRTA and MAPF have been proposed that, given a fixed road-map, compute the shortest path first and then utilize integer linear programming (ILP) to compute the optimal task assignment [13]. Other approaches use search-based methods that can find optimal and bounded sub-optimal schedules with respect to the sum-of-cost [14] or optimal schedules with respect to make-span [15]. In obstacle-free spaces, the concurrent assignment and planning of trajectories (CAPT) finds optimal motions plans for multiple robots by minimizing the squared velocity. This method has been also proposed in a decentralized version, but with no optimality guarantees [16]. Other decentralized solutions for the combined problem include controller synthesis to solve the formation change problem in environments with obstacles and communication constraints [17]. However, this solution scales exponentially with the number of robots. In Reference [18], a decentralized control approach is presented featuring good performance for large robot teams, but--unlike our approach--it does not consider obstacles. Additionally, this approach considers pairwise task-swaps and, therefore, might not optimize the objective over the whole team. Other approaches are based on the estimation of the robot density [19]. The swarm distribution is estimated locally, followed by the distributed solution of an optimal transport problem. However, also this method does not consider obstacles posing constraints on motion and communication. Some traditional approaches to decentralized task assignment use auctions [20]. A great part of these methods rely on temporarily centralizing the decision-making on a auctioneer that collects offers and defines the winning robot, to which the task gets assigned. In swarm robotics contexts, similar techniques are often unpractical due to the high communication load for large groups, and the limited communication abilities of the individual robots. Instead, in swarm robotics, threshold-based approaches [21] or stochastic task switching [22] are often preferred. These methods are inspired by biological systems where a flexible and stochastic allocation of tasks is observed (e.g., in social insects, individuals engage in tasks on the basis of the urgency of accomplishing it [23; 24]). Robot swarms employ similar strategies, which allow to achieve coordination in an implicit way, relying on probabilistic rules that can be modulated by the individual ability to evaluate the utility in engaging in a given task. These methods can be improved by enabling interaction among individuals deciding collectively which tasks to execute or in which area to move, and various task assignment dynamics have been observed from winner take all to a balanced deployment [11; 25]. These latter studies are inspired by the decision-making abilities observed in ants [26; 27] and honeybees [28]. The latter, when searching for a site where to establish a new nest, engage in repeated interactions trying to recruit other scouts for high-quality sites, at the same time discouraging other individuals to recruit for alternative sites. Theoretical studies revealed that the mechanisms involved in this collective process can lead to optimal decisions in a relatively short time [28], also presenting striking similarities with the neural dynamics observed in human decision-making [29; 30]. Previous work deployed a decision-making algorithm based on the behavior of honeybees and tailored to collective decisions in decentralized systems [10], which proved useful for the design of artificial systems in a variety of contexts, from robot swarms [11; 25; 31; 32] to cognitive radio networks [33]. Here, we extend this framework to a hierarchy of sequential decisions, largely increasing the complexity of the resulting collective dynamics. In contrast to previous studies, we account for robot motion and collision costs, robot failures, and limited communication.