# A Cluster-Based Hierarchical-Approach for the Path Planning of Swarm
## 4 Model of the Proposed System
### Vicsek MAS  
The Vicsek MAS consists of \(n\) autonomous agents moving in the plane with the same absolute velocity [31]. The model updates the heading of every agent with respect to the state of its neighbor. The neighbors of an agent \(I\) (\(1\leq I\leq n\)) at time \(t\) are those which lie within a circle of radius \(r\) (\(r>0\)) centered at the current position of agent \(i\). We represent the neighbors of the agent \(i\) at time \(t\) as \(N_{i}(t)\),  
\[N_{i}(t)=\left\{j\big{|}d_{ij}(t)<r\right\} \tag{7}\]  
whereas \(d_{ij}(t)\) can be found using the Pythagorean theorem  
While, \((x_{i}(t),y_{i}(t))\) are the coordinates of the agent at time \(t\). Agent \(i\) and agent \(j\) are neighbors to each other. Every agent in the system has the same absolute velocity \(v\) (\(v>0\)).  
\[\left\{\begin{array}{l}x_{i}(t+1)=x_{i}(t)+v\cos\theta_{i}(t)\\ y_{i}(t+1)=y_{i}(t)+v\sin\theta_{i}(t)\end{array}\right. \tag{8}\]  
where \(\theta_{i}(t)\) represents the heading angle of agent \(i\) at time \(t\). The MAS updates the heading angle using the following equation,  
\[\theta_{i}(t+1)=\arctan\frac{\sum_{j\in N_{i}(t)}\sin\theta_{j}(t)}{\sum_{j \in N_{i}(t)}\cos\theta_{j}(t)} \tag{9}\]  
Equation (9) is used to detect obstacles by checking their neighbors. If there is a missing node in the neighbor (meaning an obstacle), then it will change the heading angle to avoid collision with the obstacle.  
The Vicsek MAS model is a dynamic system, and we can use elementary graph theory to analyze this model. Keep in mind that the neighbors of each agent do not remain the same. To define the coordination of agents, [PERSON] et al. [22] made use of an undirected graph sequence \(\mathbb{G}_{t}=\{\mathcal{V},\ \mathcal{E}_{t}\}\). Whereas, \(\mathcal{V}=\{1,\ 2,\ \cdots,\ N\}\) is the set that contains all agents, and \(\mathcal{E}_{t}\) is the edge set that changes with time. If any two vertexes of a graph are joined together, that graph would be considered connected.  
We can simplify Equation (9) as,  
\[\tan\theta_{i}(t+1)=\sum_{j\in N_{i}(t)}\frac{\cos\theta_{j}(t)}{\sum_{k\in N _{i}(t)}\cos\theta_{k}(t)}\tan\theta_{i}(t) \tag{10}\]  
We can also simplify Equation (10) by using a matrix,  
\[\tan\theta(t+1)=A(t)\tan\theta(t) \tag{11}\]  
whereas, \(\tan\theta(t)\triangleq(\tan\theta_{1}(t),\ \ldots,\tan\theta_{N}(t))^{\tau}\), \(A(t)\triangleq\big{(}a_{ij}(t)\big{)}\) is the weighted average matrix of the graph \(\mathbb{G}_{t}\):  
\[a_{ij}(t)=\ \begin{cases}\frac{\cos\theta_{j}(t)}{\sum_{k\in N_{i}(t)}\cos \theta_{k}(t)}&if\ (i,\ j)\in\mathcal{E}_{t}\\ 0,&otherwise\end{cases} \tag{12}\]To study the synchronization of the Vicsek MAS, [PERSON] et al. (2018) examined the linearized model of Equation (9), which is:  
\[\theta_{i}(t+1)=\frac{1}{n_{i}(t)}\sum_{j\in N_{i}(t)}\theta_{j}(t) \tag{13}\]  
where, \(n_{i}(t)\) is the number of elements in \(N_{i}(t)\). Similarly, we can replace Equation (11) by,  
\[\tan\theta(t+1)=\widetilde{A}(t)\theta(t) \tag{14}\]  
where, \(\theta(t)\triangleq(\theta_{1}(t),\ \ldots,\theta_{N}(t))^{\tau}\), and the entries of the matrix \(\widetilde{A}(t)\) are,  
\[\widetilde{a}_{ij}(t)=\left\{\begin{array}{ll}\frac{1}{n_{i}(t)},&if\ (i,j)\in\mathcal{E}_{t}\\ 0,&otherwise\end{array}\right. \tag{15}\]