# Strategies for Scaleable Communication and Coordination in Multi-Agent (UAV) Systems
## 4 Multi-Agent Communication and Networking
### Hierarchical Multi-Level Clustering  
Single-level clustering permits agents to only communicate with cluster-members, preventing inter-cluster communication. To allow this capability, level-1 cluster-heads can form level-2 clusters and elect level-2 cluster heads, continuing the process for higher levels until all robots are united under one hierarchical multi-level clustering (MLC) tree, as depicted in Figure 6.  
A completely unique set of challenges emerges in MLC. Strictly speaking, the levels are not independent; processes that occur in lower-level clusters such as evictions, leader elections, cluster merges and splits, also change the membership of higher-level clusters. Regardless of the activity in higher or lower levels, it is generally desirable that all agents remain responsive to the agents in their vicinity and protected from the overhead of the full tree. Two principles aid in that endeavor: first, every cluster-head must belong to a level-1 cluster, and second, every robot must only be the head of one cluster. Figure 5: The consensus problem in cluster formation. (**a**) Some agents that view themselves as members of blue clusters appear to other agents as heads of purple clusters. (**b**) Agents attempting to form purple clusters become orphans (circled in orange). Figure 6: Hierarchical multi-level clustering. (**a**) 3-level hierarchical tree where blue = level 1, green = level 2, and orange = level 3. Every level 2 and level 3 cluster-head belongs to a level 1 cluster. (**b**) Ideally, higher-level clusters are more stable and tolerate drift over longer trajectories. To isolate higher-level clusters from the activity in lower-levels, each level-\(k\) cluster is associated with a token that points to the tokens of its level \(k-1\) cluster-members and the token of its level \(k+1\) cluster-head. Any membership changes to a level-\(k\) cluster can then be executed by token transfers and pointer modifications at levels \(k-1\) and \(k+1\). It is useful to see examples of token behavior in some basic cluster operations. 1. [label=(O0)]
2. _Cluster-Head Reassignment_: Sometimes a designated cluster-head is no longer suitable for the role. This occurs when another member is closer to the centroid of the cluster, or the cluster-head \"despawns\" (i.e., powers-down or self-disables). Prior to the trigger-event, the cluster-head transfers the cluster token (and the associated responsibilities) to the member closest to the centroid. 3. _Member Transfer_: An agent may drift closer to the centroid of another cluster. The \"old\" cluster-head then initiates a transfer to the new cluster by alerting the higher-level head of the sub-tree. Upon approval, the old token deletes its pointers to the departing agent. The new token adds pointers to the joining agent, which does the same in reciprocity, as depicted in Figure 7.
4. _Cluster Split_: Level-\(k\) clusters with sizes that exceed a certain threshold may split in two. The level-\(k+1\) cluster-head creates a new level-\(k\) token and designates the new level-\(k\) cluster-head as an \"idle\" member (an agent in the sub-tree that is not the head of any cluster) closest to the centroid. The new cluster includes all members of the old cluster closest to the new cluster-head. The token pointers are adjusted appropriately. 5. _Cluster Assimilation_: Clusters can also shrink when their members leave or de-spawn. If a level-\(k\) cluster-size falls below a threshold, the level-\(k\) cluster-head initiates an assimilation request, in which the head of the subtree moves the members to the closest level-\(k\) clusters. The token of the old level-\(k\) cluster is then destroyed. 6. _Boss Demotion_: As the system approaches the end of its operating lifetime, agents de-spawn faster than they re-spawn. The MLC tree then shrinks until the head of the tree, (i.e., the boss) has only one member in its cluster. The boss destroys its token to make this member the new boss and eliminate the superfluous extra level.