# Strategies for Scaleable Communication and Coordination in Multi-Agent (UAV) Systems
## 3 Multi-Agent Planning and Control  
Multi-agent systems present two distinct challenges. First, there is a \"control\" problem caused by the exponential growth of the state space in the number of agents. Second, there is a communication problem of sharing all the local states so that the agents arrive at a common view of the global state. The communication problem is addressed in Section 4, so the default assumption here will be that each agent sees the global state space. Large state spaces require longer training times because the training process must sample a sufficiently large subset of the state space \(\mathcal{S}\), sufficiently often, to learn both \(V_{\pi}(s)\) and the optimal policy \(\pi^{*}(s)\) for all \(s\in\mathcal{S}\). An important strategy to shorten the training times is state-space compression. The idea is to map the old state space \(\mathcal{S}\) to a new space \(f:\mathcal{S}\rightarrow\mathcal{S}^{\prime}\) where  
\[|\mathcal{S}^{\prime}|<<|\mathcal{S}| \tag{12}\]  
but \(\pi^{*}(s)\approx\pi^{*}(f(s))\), or equivalently:  
\[V_{\pi}^{*}(s)\approx V_{\pi}^{*}(f(s)). \tag{13}\]  
The value on the left side of (13) is obtained from the optimal policy \(\pi^{*}(s)\) over \(\mathcal{S}\) and the value on the right is optimal over \(\mathcal{S}^{\prime}\). The constraint (13) implies that \(\mathcal{S}^{\prime}\) retains all of the important information in \(\mathcal{S}\), namely, the information that allows the system of robots to behave optimally with respect to \(\mathcal{S}\). The compression rate in (12) usually implies polynomial (as opposed to exponential) growth in the number of agents \(n\), so that:  
\[|\mathcal{S}^{\prime}|=O(p(n))\ \ \text{as}\ \ n\rightarrow\infty, \tag{14}\]  
where \(p(n)\) is some polynomial function of \(n\). If a compression \(f\) satisfying (13) exists, then it suffices to sample \(\mathcal{S}^{\prime}\) instead of \(\mathcal{S}\) (which has fewer states and thus shorter convergence times). A key objective is finding such an \(f\) and understanding the conditions for its existence. Although the communication problem does not appear in (13) and (14), the fact remains that individual agents do not see the global state \(\mathcal{S}\). Let \(\mathcal{N}\) denote the set of agents. Each agent \(i\in\mathcal{N}\) makes a unique reconstruction of the global state \(\mathcal{S}^{\prime}_{i}\) from the local states shared through the communication medium. Ideally, these reconstructions are identical so that \(\mathcal{S}^{\prime}_{i}=\mathcal{S}^{\prime}\) for all \(i\in\mathcal{N}\). However in light of the communication problem, it is better to relax this constraint and allow different reconstructions. Each agent \(i\) then effectively applies a unique compression \(f_{i}:\mathcal{S}\rightarrow\mathcal{S}^{\prime}_{i}\). The local policies \(\pi_{i}(f_{i}(s))\) act on \(\mathcal{S}^{\prime}_{i}\) and collectively define the global policy \(\pi(s)=(\pi_{1}(f_{1}(s)),\pi_{2}(f_{2}(s)),\ldots,\pi_{|\mathcal{N}|}(f_{| \mathcal{N}|}(s))\). The objective then is to find the full suite of compression functions \(\{f_{i}:i\in\mathcal{N}\}\) that achieves (13). The distributed compression approach (above) simplifies the control problem because the global state-space \(\mathcal{S}\) has locally interactive structure. Relative to any given agent, the local states in its vicinity are more significant to its optimal operation than local states that are further away. A \"good\" compression function \(f_{i}\) prioritizes these local states over remote states, but also includes enough remote information to capture lower-order phenomena. One enduring ambiguity in deep RL is the absence of any guarantees the recovered policies are optimal. Neural networks have no known bounds on the accuracy of their approximations, and the training itself relies on stochastic gradient descent, which converges only to a local optimum.