# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 7 Discussion of the Scheduling Algorithm  
### Complexity of the Scheduling Algorithm  
In this section, we will discuss the overall complexity of the scheduling algorithm as shown in Algorithm 1. First, we will discuss the complexity of _findfastestpath_, which is called inside Algorithm 1. In _findfastestpath_, suppose \(L\) is the maximum number of iterations of the _while loop_. Then, the value of \(L\) is equal to the total number of edges of all the possible paths from the start node to end node. Let \(node_{e}\) be the end node of a graph where Algorithm 1 is applied and let \(Edges(node_{e})\) be the total number of edges of all possible paths from start node to \(node_{e}\). Hence, \(L=Edges(node_{e})\). For a given node \(node_{n}\) where \(node_{n}\) is any node in the graph except the start node, \(Edges(node_{n})\) is given recursively as shown below.  
\[\text{Edges}(node_{n})\,=\,\left\{\begin{array}{ll}1,&\text{$c$ is a successor of the start node}\\ |S|+\sum\limits_{node_{e}\,\,s}\text{Edges}(node_{s})\,,&\text{otherwise} \end{array}\right. \tag{30}\]  
where \(S\) is a set of the successors of \(node_{n}\).  
To explain Equation (30), let us consider a simpler graph shown in Figure 9. It is easy to see that the total number of edges of all the possible paths from start node to \(node_{A}\) is \(1\) since it is a successor of the start node hence, \(Edges(node_{A})=1\). Similarly, \(Edges(node_{B})=1\) and \(Edges(node_{C})=1\). For \(node_{D}\), it can be reached from \(node_{A}\), \(node_{B}\), and \(node_{C}\). Hence, \(\text{Edges}(node_{D})\) is the summation of \(Edges(node_{A})\), \(Edges(node_{B})\), and \(Edges(node_{C})\) plus the number of edges from \(node_{A}\) to \(node_{D}\), \(node_{B}\) to \(node_{D}\), and \(node_{C}\) to \(node_{D}\). Therefore, \(Edges(node_{D})=6\).  
Inside _findfastestpath_, _checkpathtosuccessor_ is implemented. In _checkpathtosuccessor_, each cube in \(rc\) is checked for conflict. Checking for conflict of one cube is \(O(log_{2}n)\) since it is a standard searching operation in red-black tree where \(n\) is the number of UAVs reserved in the cube. Let \(c^{max}\) be the maximum number of cubes to be checked between two nodes. Then the complexity of _checkpathtosuccessor_ is \(O(c^{max}log_{2}n)\). Since _checkpathtosuccessor_ is called in the _while loop_ of _findfastestpath_, the complexity of _findfastestpath_ is \(O(Lc^{max}log_{2}n)\).  
As shown in Algorithm 1, _findfastestpath_ is called iteratively in a while loop. It is called iteratively until we know that the current path found is the fastest time that the UAV can exit the intersection from the time it arrived at the reservation zone. Suppose \(I^{max}\) is the maximum number of iterations of _findfastestpath_. Thus, the complexity of the _while loop_ in Algorithm 1 is \(O(I^{max}Lc^{max}log_{2}n)\).  
After finding the path, the cubes will be reserved to the UAV as shown in the last line of Algorithm 1. Reserving a cube is an insertion operation in a red-black tree with complexity of \(O(log_{2}n)\). Since \(c^{max}\) is the maximum number of cubes to be checked between two nodes, the total number of cubes to be reserved in the path from start to end node is \(c^{max}e\), where \(e\) is the number of edges in the found path. Thus, the complexity of reserving the cubes is \(O(c^{max}elog_{2}n)\). Therefore, the complexity of Algorithm 1 is \(O(I^{max}Lc^{max}log_{2}n+c^{max}elog_{2}n)\).  
Even though \(L\) is a constant value, its value is the largest compared to the other variables. In our intersection model, the maximum value of \(L\) is 128,101, which is when we find a path for a UAV that will enter the intersection at the second left-most lane, while the maximum value of \(e\) is 13. Thus, the overall complexity of scheduling a UAV is \(O(I^{max}Lc^{max}log_{2}n)\). To make the scheduling faster, we will show how to reduce the complexity of the scheduling algorithm in the next subsection.