# 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
Specifically, a robot changes its state \(s_{i}\) from ascending (\(s_{a}\)) to descending (\(s_{d}\)) with probability \(P_{d}\) per time-step, while it switches from descending to ascending with probability \(P_{a}\) per time-step. Overall, the probability that a robot at any time is found in the ascending (descending) state is \(\frac{P_{a}}{P_{a}+P_{d}}\) (\(\frac{P_{d}}{P_{a}+P_{d}}\)). In this work, we use equal probabilities \(P_{a}=P_{d}=0.5\) to obtain a fair exploration-exploitation trade-off. In both the descending and ascending states, a robot decides whether or not to change the current area on the basis of its local knowledge. The proposed decentralized algorithm exploits both the world model and the knowledge from other robots to determine if neighboring areas are worth being considered. The idea is that areas with high utility should be preferred over areas of low utility, following a proven decision-making design pattern [10,28]. At the same time, overcrowding should be avoided, hence balancing exploitation among different areas. To this end, robots interact with each other to determine the best possible allocation. Note that, to move towards areas at the same hierarchical level, a transition through the parent node is required. The selection of a destination node in the quad-tree is performed according to four stochastic processes: (i) _commitment_ to an area at a lower hierarchical level, (ii) _recruitment_ by a peer robot committed to an area at a lower hierarchical level, (iii) _abandonment_ of the current area to move up the hierarchy, and (iv) _inhibition_ determined by a peer robot--either committed to the same (self-inhibition) or to a same-level area (cross-inhibition)--leading to a move up in the hierarchy (see Figure 2, right panel). Descending Transitions  
The robot \(r\) located in area \(a_{i}^{n}\) and in state \(s_{d}\) can change node by means of commitment or recruitment (see Figure 2, right). Commitment represents the spontaneous decision of \(r\) to move to one of the four children nodes \(a_{m}^{n+1}\) according to the perceived utility. For each area \(a_{m}^{n+1}\), the transition probability is computed proportionally to its utility as follows:  
\[\gamma_{m}^{n+1}=k\cdot U^{r}(a_{m}^{n+1}), \tag{4}\]where \(k\) is a control parameter for spontaneous processes. Conversely, recruitment allows a robot \(r\) to get recruited by another robot. At any time, a robot \(r_{o}\) is randomly chosen among the robots known by \(r\), and--if it belongs to the sub-tree of a child node \(a_{m}^{n+1}\)--a transition probability is computed according to the utility shared by \(r_{o}\), based on the assumption that \(U^{r_{o}}\) provides a better estimation for area \(a_{m}^{n+1}\) since \(r_{o}\) is located in that region. Moreover, thanks to the coupling with the motion planner, \(U^{r_{o}}\) embeds the motion costs as estimated by \(r_{o}\), which serve as an indication of the perceived ease of motion within that area. Additionally, recruitment provides a means to tune the assignment process to the density of robots in a given area, as the probability of selecting a robot assigned to a certain area is proportional to the robot density of that area. Hence, the recruitment transition probability is computed as follows:  
\[\rho_{m}^{n+1}=h\cdot U^{r_{o}}(a_{m}^{n+1}), \tag{5}\]  
where \(h\) is a control parameter for interactive processes. Note that, at any time, only a single neighboring robot \(r_{o}\) is considered, and recruitment takes place only if it belongs to a sub-tree of the children nodes of \(a_{i}^{n}\). In all other cases, no recruitment is considered. In this way, the overall recruitment rate of robots to a given area is proportional to the population of robots already committed to that area [10]. Ascending Transitions  
When in state \(s_{a}\) and in area \(a_{i}^{n}\), robot \(r\) may decide to move to the parent node \(a_{j}^{n-1}\) through abandonment, self-inhibition or cross-inhibition (see Figure 2, right).