# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 1 Introduction  
Several service scenarios are characterized by new tasks appearing at any time and in any place, necessitating persistent operation [1]. As an example, consider a large warehouse where orders arrive erratically and diverse items need to be collected from different locations. In such context, besides retrieving goods, other services must be continuously executed on pallets, such as tidying, sorting objects, and controlling and refilling stocks [2, 3]. Similarly, in a greenhouse, continuous and localized operation is necessary for pruning plants, variable-rate spraying, and selective harvesting. Finally, in a facility or office environment, cleaning or delivery tasks may be continuously and unpredictably requested by users located in different areas [4]. Automation in such context cannot always rely on centralized, fixed infrastructures, which may be costly or impractical. Instead, wireless sensor networks, IoT, and mobile devices may be exploited to raise the need for tasks to be serviced by a swarm of specialized robots [5, 6]. Addressing a persistent and unpredictable service demand with a multi-robot system can provide higher efficiency, thanks to parallel operation, and larger flexibility by modulating the operational costs in terms of robots employed, as well as by deploying robots only where needed. At the same time, the robotic system must prove scalable, fault-tolerant and robust, to ensure continuous and efficient operation despite the number of units deployed, the occurrence of failures, and the variability in the task demands. Concrete solutions can be obtained by addressing two concurrent problems. On the one hand, it is necessary to find a suitable task assignment for each robot, so that costs are minimized in terms of relocation, robot idle time, and task waiting time [3; 7; 8]. On the other hand, a collision-free trajectory for the robot must be planned in order to safely reach the destination without interfering with other robots' plans [3; 9]. This class of problems is often split in Multi-Robot Task Allocation (MRTA) and Multi-Agent Path Finding (MAPF). A common naive approach consists in solving MRTA and MAPF separately. However, in cluttered environments, such as indoor spaces, those two problems are tightly coupled: the former provides a set of origin-destination pairs to the latter, which, in turns, returns back actual costs and timings associated to the movements planned by the different robots. For both MRTA and MAPF, many centralized and decentralized approaches exist in the literature (see Section 2). Centralized solutions often rely on perfect intra-robot communication and suffer the well-known issues of scaling with group size--especially when the task demand can rapidly change over time--and of fault-tolerance due to the existence of a single point of failure. Decentralized approaches, on the other hand, potentially feature high fault-tolerance and scalability, but few have been shown to operate in environments with limited communication. Here, we propose a decentralized algorithm for both task allocation and motion planning that is robust to limited communication and robot failures, and scalable to different environments and group size. Our method is referred to as Hierarchical Task Assignment and Path Finding (HTAPF) because the task allocation problem is solved exploiting a hierarchical representation of the locations where tasks must be executed. More precisely, by partitioning the work-area in a quad-tree, our MRTA problem is efficiently solved through the deployment of robots in areas of interest corresponding to the tree leafs where tasks to be executed are available. To this end, we propose a non-trivial extension of a collective decision-making process designed for robot swarms [10; 11] to deal with a hierarchy of sequential decisions, allowing a robot swarm to prioritize those areas with highest demand, while minimizing movement costs.