# Strategies for Scaleable Communication and Coordination in Multi-Agent (UAV) Systems
## 4 Multi-Agent Communication and Networking
### Belief Propagation in Multi-Level Clustering  
The previous discussion of MLC focused on the need for reliable communication in multi-robot networks, where safe collision-free operation is of paramount importance. However, the wireless medium itself is subject to fundamental scaling laws that bound the total throughput as the size of the network (i.e., the number of nodes) grows to infinity [36]. Figure 7: Member transfer and cluster-head reassignment. **(a)** A cluster-member drifts away from its cluster-head. **(b)** The cluster elects a new cluster-head closer to the centroid. **(c)** The new cluster-head initiates a transfer which allows the remote member to join the more suitable cluster. Wireless scaling has been studied extensively in the literature [54; 55]. For convenience, let \(n:=|\mathcal{N}|\) denote the number of nodes in the network. The sharpest results so far show the total throughput \(T(n)\) satisfies:  
\[T(n)\leq K(\epsilon)n^{1-\epsilon}, \tag{19}\]  
where \(K(\epsilon)\) is function of \(\epsilon\). Moreover,  
\[\lim_{\epsilon\to 0}K(\epsilon)n^{1-\epsilon}=0. \tag{20}\]  
The implication of (19) and (20) is that the rate per-node goes to zero as the number of nodes becomes large. Therefore a communication policy in which nodes transmit uncompressed data is not scaleable in multi-agent networks. MLC is necessary because it matches the locally interactive structure of the global state to the network capabilities (bounded by (19)). Each agent has a \"belief\", a probabilistic estimate of interest-point locations in the grid. Beliefs play a key role in the POMDP framework; the value function depends on the beliefs over states and not the states themselves. In multi-agent systems, the beliefs of the agent may differ. Each agent is relatively confident about the interest-point locations in its vicinity, and perhaps less so of those in the remote regions; those in the vicinity are observed directly, whereas those further way are relayed through the communication network. Since the global state-space has soft locally interactive structure (Section 3), the robots need not have the same beliefs to collectively maximize the interest-points visited over the operating lifetime. It is this freedom that allows the system to satisfy (19). The MLC tree defines a mechanism for belief sharing that conforms to the scaling laws in (19). The level-\(k\) cluster-heads aggregate the beliefs of their cluster-members into a single belief and send this belief to their level-\(k+1\) cluster-heads. In return they receive beliefs from outside of the sub-tree, and forward them down to their members. Every level of the MLC adds another layer of compression to ensure the total throughput does not exceed (19). To make this more precise, let \(b(i)\) and \(s(i)\) denote the belief and local state of agent \(i\) respectively. Assume this agent is a cluster-head and let \(\textsc{level}(i)\) denote the cluster level. Let \(M(i)\subseteq\mathcal{N}\) denote the members of the cluster where \(\mathcal{N}\) is the set of agents. Let \(c\) denote the compression factor. The compression algorithm satisfies the following recursion:  
\[b(i)= \begin{cases}\frac{1}{c}\sum_{j\in M(i)}b(j),&\textsc{level}(i)>0,\\ s(i),&\textsc{level}(i)=0,\end{cases}  \tag{21}\]  
where the sum \(\sum_{k\in M(j)}b(k)\) denotes the belief aggregation performed by agent \(j\). Belief propagation in general multi-agent networks has also been studied in the literature [56; 57]. One of the main challenges is preventing old beliefs from contaminating new beliefs, which occurs when there are cycles in the network that propagate beliefs indefinitely. Tree-structured networks (like MLC) have no cycles. The successful propagation of beliefs does not in itself guarantee optimal system operation. Agents must still collectively \"sample\" the global state in search of interest-points by visiting all regions sufficiently often. The process of exploration continues until the system learns the interest-point dynamics.