# 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
Spontaneous abandonment is the more probable the lower is the utility of the current area:  
\[\alpha_{i}^{n}=k(1-U^{r}(a_{i}^{n})). \tag{6}\]  
On the other hand, a robot \(r\) residing in area \(a_{i}^{n}\) can be inhibited by another robot \(r_{o}\) belonging to the sub-tree either from the same area (self-inhibition) or from a different area \(a_{i^{\prime}}^{n}\) at the same hierarchical level \(n\) (i.e., \(a_{i}^{n}\) and \(a_{i^{\prime}}^{n}\) share the same parent node, that is, they are sibling nodes). Self-inhibition is used to cope with overcrowding, where several robots share the same region, hence impairing robot motion. It is defined as:  
\[\psi_{i}^{n}=h\cdot U^{r_{o}}(a_{i}^{n})\cdot\mathcal{H}(R(a_{i}^{n})-\theta _{\phi}\mathcal{C}(a_{i}^{n})), \tag{7}\]  
where \(R(a_{i}^{n})\) represents the number of robots in area \(a_{i}\), and \(\mathcal{H}\) is the Heaviside step function, which enables the process only if the population in the area exceeds a fraction \(\theta_{\phi}=3/4\) of its capacity \(\mathcal{C}(a_{i}^{n})\), defined as the number of cells that do not contain an obstacle. Overall, self-inhibition balances recruitment to an area when the population density is too high (also see Reference [11]). Conversely, Cross-inhibition forces a robot \(i\) to abandon a region with low utility in favor of a region \(i^{\prime}\) with higher utility. It is used to focus the assignment to areas of high utility, allowing the robots to abandon their current area (i.e., getting assigned to the parent node) to explore one of the sibling areas. The purpose of this process is to balance poor commitments that might arise from the probabilistic nature of the system and outdated/limited knowledge. Hence, given a robot \(r_{o}\) residing in the sub-tree of area \(a_{i^{\prime}}^{n},i^{\prime}\
eq i\), the probability of cross-inhibition is proportional to the utility \(U^{r_{o}}(a_{i^{\prime}}^{n})\), as defined in the following:  
\[\beta_{i,i^{\prime}}^{n}=h\cdot U^{r_{o}}(a_{i}^{n})\cdot\mathcal{H}(\theta_{ \beta}\mathcal{C}(a_{i}^{n})-R(a_{i^{\prime}}^{n})),\;i\
eq i^{\prime}, \tag{8}\]  
where the Heaviside function \(\mathcal{H}\) enables the process only if the population in area \(i^{\prime}\) does not exceed one fourth of the capacity, i.e., \(\theta_{\beta}=0.25\), again to limit potential overcrowding. Similar to recruitment, also in this case inhibition happens only if \(r_{o}\) belongs to areas at the same hierarchical level or below, otherwise the transition probability is null. Overall Algorithm and Control Parameters  
A pseudo-code of the steps followed by the robot during the area assignment process is provided in Algorithm 1. The robot moves in the hierarchical tree one node at the time based on ascending and descending transition, respectively, selected according to two a-priori fixed probabilities \(P_{a}\) and \(P_{d}\) (i.e., probabilistic selection of the robot state \(s_{i}\) and hence the next transition type, ascending or descending). Next, transitions probabilities are computed according to the currently selected neighboring robot and the considered areas (see Algorithm 1, lines 7 and 9) and are, respectively, associated to the locally computed interactive and spontaneous processes values as in Equation (4) to (8). The assignment process randomly extract a new hierarchical area (line 10) on the basis of computed transition probabilities and propagate this decision up, to all its ancestors in its local quad-tree. We assume the assignment process to be faster than robot motion, so that \(D\) decisions are performed while a robot is moving between two adjacent cells. In this study, we heuristically set \(D\) to be equal to the depth of the quad-tree \(M\). Increasing or decreasing \(D\) can improve or diminish the tree exploration. Last, a new motion plan is made (line 12) only if the assignment process changes the current area after \(D\) steps, hence requiring to determine a new destination (either a chosen task or a randomly determined cell). As originally proposed by [PERSON] et al.