# Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms
## 3 Hierarchical Task Assignment and Path Finding
### HTAPF: Principles and Methods
#### 3.2.2 Decentralized Area Assignment  
The world model is constantly updated upon receipt of information about new tasks or about the presence of other robots in a certain area. In this way, each robot can compute the utility of each area from its own perspective, which is then used to select a goal area. The decision ultimately corresponds to the assignment of the robot to a node of the hierarchical world model. Here, the selection of a non-leaf node corresponds to the robot deciding to move to and remain in a certain area, while the assignment to a leaf node corresponds to the robot deciding to move to the corresponding area and possibly execute one of the available tasks. To determine the assignment to the nodes of the hierarchical word model, we exploit a decentralized algorithm inspired by the collective decision-making abilities of honeybees [10; 28], which was used in different contexts [25; 32; 33] and also extended for MRTA [11]. Here, we improve over previous studies by extending the algorithm to a hierarchical representation of the world, and by considering the constraints imposed by both the need for collision-free movements and limited communication. At any time, a robot \(r_{i}\) is considered committed to a node in the quad-tree, i.e., an area \(a_{i}=a_{j}^{n}\) in the environment wherein its movements are constrained. Initially, robots start committed to the root node \(a_{i}=a^{0}\) representing the whole environment. Robots committed  
Figure 2: **Left**: Graphical representation of the considered hierarchical model. In this figure, the environment is discretized in a \(8\times 8\) matrix (i.e., \(N=8\)) and the corresponding quad-tree is built upon it, where only certain areas are partitioned, for the sake of brevity. **Center**: The quad-tree has a maximum depth of \(\log_{2}(N)=3\). Each node of the quadtree contains the identifying tuple \((x,y,l)\), with the \(x\) and \(y\) coordinates and size \(l\) of the corresponding area. For instance, a robot residing in area \((4,2,2)\) has the possibility to descend to any of the four corresponding leaf-nodes, such as the cell \((5,3,1)\), exploiting its current knowledge of the sub-tree, or to ascend the quad-tree to area \((4,0,4)\) for wider exploration of the environment. **Right**: probabilistic transitions between possible states, where a robot committed to \(a_{i}^{n}\) can either move up to the parent node (area \(a_{j}^{n-1}\)) when in the ascending state \(s_{a}\), or move down to one of the children nodes (area \(a_{i}^{n+1}\)) when in the descending state \(s_{d}\). Robots first decide whether to switch state \(s_{a}\to s_{d}\) (\(s_{d}\to s_{a}\)) with probability \(P_{d}\) (\(P_{a}\)). Then, transitions can take place that allow a robot to move in the quad-tree, either spontaneous (commitment \(\gamma_{m}^{n+1}\), abandonment \(a_{i}^{n}\)) or interactive (recruitment \(p_{m}^{n+1}\), cross-inhibition \(\beta_{i,r}^{n}\) and self-inhibition \(\psi_{i}^{n}\)). to non-leaf nodes in the quad-tree are not assigned to any specific task and are free to explore the corresponding area performing a random walk [41]. Robots committed to leaf nodes are considered allocated for task execution, whenever tasks become available. At each decision step, a robot can either descend the quad-tree towards leaf nodes or move up the hierarchy towards the root node (see Figure 2). When descending the quad-tree, a robot _exploits_ its current knowledge about the children nodes in the quad-tree to choose the area with higher utility (3) for task execution. When ascending the quad-tree, the robot gets committed to the parent node, hence accessing a larger area to _explore_ for servicing tasks elsewhere. Switching between the ascending state \(s_{a}\) and the descending state \(s_{d}\) is performed according to a probabilistic threshold-based decision, which can be tuned to balance the exploration-exploitation trade-off (see Figure 2, right).