# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 3 Hierarchical Task Assignment and Path Finding
### HTAPF: Principles and Methods  
We now illustrate the details of HTAPF, our novel distributed approach that couples MRTA and MAPF. The overall approach includes three main components: (i) the _local knowledge_ available to each robot, (ii) the _area_ _assignment_ leveraging interaction with other robots, and (iii) the _motion planning and task assignment_, which is performed by exploiting the knowledge of other robots' plans (see Figure 1, right). The local knowledge is available to each robot and consists of a world model, area utility estimations obtained via interaction with other robots, and motion plans of nearby robots. The world model has a map of the environment--the only information known a priori--and a hierarchical description of the work area, that is divided in sub-areas (see Section 3.2.1). As time goes by, the world model is updated including information about the available tasks and about the presence of other robots. Robots exchange two types of information. First, they share their locally-estimated perceived utility of working in the area they are currently located, which is exploited to support the area/task assignment process. Second, they exchange their motion plans, which are useful for path finding. The area assignment process generates goals for the motion planner in terms of a goal area where the robot wants to service tasks. To determine the robot destination, the area assignment exploits the world model, the information coming from other robots, and knowledge from the motion planner about the costs of reaching a target area. In other words, robots can choose to work in an area only if they are assigned to it, and their motion plan is, therefore, influenced by the area to which they belong. For instance, in Figure 1 (left), all robots can move and work within their current area but \(r_{4}\), the yellow robot, which has no task available in its area and needs to get assigned to a different one before selecting a task (in this case, \(T_{4}\)). Task assignment in the target area and motion planning are performed concurrently. The motion planner is fully distributed and does not require synchronization among robots. Given a goal area, it assign tasks and generates collision free paths according to the information previously received and stored in the local knowledge, including the plans of other robots. The current plan is also used internally to enhance the area assignment process and is also broadcast to other robots to support concurrent planning. For instance, in Figure 1, the green robot \(r_{2}\) first plans its path toward task \(T_{2}\), and \(r_{3}\), the blue robot, later decides to move to task \(T_{3}\) even if farther away to avoid interference with \(r_{2}\). From this high-level description, it is evident that there is a very tight coupling between the different components, which constantly share information to increase performance both at the level of the individual robot and of the group (also see Algorithm 1). In the following, we provide a detailed description, starting from the world model and then moving to the main contributions of this study, that is, the task assignment and path finding, giving particular attention to the coupling between the two.