# Multi-UAV Conflict Resolution with Graph Convolutional Reinforcement Learning
## 3 Theoretical Background
### Graph Convolutional Reinforcement Learning  
While deep learning proved effective in capturing patterns of Euclidean data, there are a number of applications where data are represented as graphs [38]. The complexity of graph data has imposed significant challenges on existing deep learning algorithms. A graph can be irregular and dynamic, as it can have a variable number of nodes and the connections between nodes can change over time. Furthermore, existing deep learning algorithms largely assume the data to be independent, which does not hold for graph data. Recently, there was an increasing number of works that extend deep learning approaches to graph data, called Graph Neural Networks (GNNs). Variants include: Graph Attention Networks (GATs) [39], Graph Convolutional Networks (GCNs) [40] and Message Passing Neural Networks (MPNNs) [41]. We refer the reader to [38], for a comprehensive review of GNNs. In the case of MARL, communication is often cited as a key ability for cooperative agents [17; 29]. In such a setting, agents exchange information before taking an action. In this work, we will use Graph Convolutional Reinforcement Learning [17] (dubbed DGN by its authors), which is a GNN algorithm for cooperative agents. In DGN, the multiagent environment is modeled as a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) is the set of nodes and \(\mathcal{E}\) is the set of edges. Each agent is a node and the local observation of the agent are the features of the node. Each node \(i\) has a set of neighbors \(\mathbb{B}_{i}\), where \((i,j)\in\mathcal{E},\forall j\in\mathbb{B}_{i}\). The set of neighbors is defined according to some criteria, depending on the environment and changes over time. In DGN, neighbor nodes can communicate with each other. Such a choice leads to the agents only considering local information when making their decisions. Another option would be to consider all agents in the environment, however, this comes with higher computational complexity. DGN has three modules: an observation encoder, convolutional layer and Q network. The observation of an agent \(i\) at time step \(t\), \(\sigma_{t^{\prime}}\) is encoded into a feature vector \(h_{t^{\prime}}\) by a Multi Layer Perceptron (MLP). The convolutional layer combines the feature vectors in the local region and generates a latent feature vector \(h^{\prime}_{t^{\prime}}\). The receptive field of the agents increase by stacking more convolutional layers on top of each other. An important property of the convolutional layer is that it should be invariant from the order of the input feature vectors. Furthermore, such a layer must be effective in learning how to abstract the relation between agents as to combine the input features. DGN uses multihead dot-product attention [42], which is an implementation of attention which runs the attention mechanism several times in parallel, to compute interactions between agents (we refer the reader to [17; 42] for a detailed overview of the attention mechanism). Let us denote with \(\mathbb{B}_{i+i}\) the set of neighbors \(\mathbb{B}_{i}\) and agent \(i\). The input features of the agent \(i\) are projected into query \(Q\), key \(K\) and value \(V\) representation by every attention head. For an attention head \(m\) the relation for \(i,j\in\mathbb{B}_{+i}\) is as follows:  
\[\alpha^{m}_{ij}=\frac{exp(\tau\cdot W^{m}_{Q}h_{i}\cdot(W^{m}_{K}h_{j})^{T})}{ \sum_{\in\mathbb{B}_{+i}}exp(\tau\cdot W^{m}_{Q}h_{i}\cdot(W^{m}_{K}h_{a})^{T} )))} \tag{4}\]  
where \(\tau\) is a scaling factor and \(W^{m}_{Q}\) and \(W^{m}_{K}\) are the weight matrices of the query and key for attention head \(m\). The representations of the input features are weighted by the relation and summed together, which is done for each head \(m\).