# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 3 Hierarchical Task Assignment and Path Finding
### Problem Description  
We consider the class of problems characterized by tasks that can be executed by a single robot at a time (SR), and robots that can execute only a single task at the time (ST). We also consider instantaneous assignment (IA), as the arrival of further tasks is not available and unpredictable [36; 37]. Without loss of generality, the work area is defined as a square partitioned in a 4-connected grid of size \(N\times N\), \(N\in\mathbb{N}\) (see Figure 1, left), which can be configured to represent spaces of different complexity, from an office to a warehouse. A grid cell \(c_{i}\in\mathcal{C}\) is identified by its coordinates \(x_{i},y_{i}\in\{1,\ldots,N\}\), and might represent free space where robots can move and tasks might appear, or an obstacle (e.g., a wall). Each free cell can be occupied by at most one robot and can contain at most one task at any time. A task \(T_{i}\in\mathcal{T}\) is a tuple \(T_{i}=(x_{i},y_{i},t_{i}^{s},t_{i}^{e},t_{i}^{w})\), which requires any robot to move to the cell at location \((x_{i},y_{i})\) and work at that location. Task \(T_{i}\) appears at time-step \(t_{i}^{s}\) and is accomplished by a robot at time-step \(t_{i}^{e}\) (where \(t_{i}^{e}=\infty\) as long as the task has not been finished). The work time \(t_{i}^{w}\) is the time required from a robot to stay at the task location and actually execute the task (e.g., cleaning, delivery, or maintenance). The task set \(\mathcal{T}\) is the disjoint union of the completed tasks \(\mathcal{T}^{c}=\{T_{i}|T_{i}\in\mathcal{T},t_{i}^{e}\
eq\infty\}\) and the unfinished tasks \(\mathcal{T}^{u}=\{T_{i}|T_{i}\in\mathcal{T},t_{i}^{e}=\infty\}\). At any time \(t\), we can define the set of available tasks \(\mathcal{T}^{a}(t)=\{T_{i}|T_{i}\in\mathcal{T}^{u},t_{i}^{s}<t\}\). In this study, the primary objective is to serve the highest number of tasks (max \(|\mathcal{T}^{c}|\)). We consider \(R\) identical holonomic robots starting in randomly assigned free cells. A robot \(r_{i}\in\mathcal{R}\) is described by tuple \(r_{i}=(i,x_{i},y_{i},s_{i},a_{i})\) identified by its unique id \(i\), an associated position in the environment given by its coordinates \((x_{i},y_{i})\) a discrete state \(s_{i}\) indicating the current behavior (whether exploring or exploiting available knowledge,  
Figure 1: **Left: example outcome of Hierarchical Task Assignment and Path Finding (HTAPF) with four robots and four tasks in a \(16\times 16\) grid world, here divided in 4 sub-areas. Robots move to the closest cell with a Manhattan neighborhood, and share their plan with other robots within the communication range. Conflicts are resolved by sequential planning, exploiting the knowledge of others’ plans for task assignment and collision-free path planning. In the image, each robot is identified by its unique color and number, i.e., \(r_{1}\) white, \(r_{2}\) green, \(r_{3}\) blue, \(r_{4}\) yellow. Grey regions are walls. Right: Interaction scheme among the different components of HTAPF. The local knowledge of robot \(r\) stores the world model, the estimated area utilities obtained upon interaction with other robots, and the received plans from other robots. Both the area assignment process and the motion planner exploit and update the local knowledge and interact with each other with local information passing. Information received from other robots about area utilities (i.e., \(U^{r_{0}}(a)\) from robot \(r_{0}\) about area \(a\) and the goal region \(a_{g}\)) and individual motion plans are exploited to update the local knowledge. **  
see below) and an area \(a_{i}\) where the robot is currently deployed. At each time-step, a robot can wait at its current position, move to an adjacent free cell, or work on a task located in the cell it is occupying. We assume limited sensing capabilities: robots can only sense adjacent neighbors, and use their sensing abilities to avoid moving in a cell that is already occupied. Additionally, robots can communicate with each other wirelessly.