# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 6 Scheduling Scheme
### Scheduling a UAV
\[t_{n}^{s_{max}}=t_{inter}+\frac{g(n)}{s_{max}} \tag{26}\]  
\[t_{n}^{s_{min}}=t_{inter}+\frac{g(n)}{s_{min}} \tag{27}\]After updating the values in \(rta\) and \(rtd\), we will now check the availability of the cubes. For each cube \(k\) in \(rc\), we check \(rc_{k}\)'s red-black tree if there are no other reservations that will conflict from \(rta_{k}\) to \(rtd_{k}\) where \(rta_{k}\) is the earliest possible arrival time to \(rc_{k}\) and \(rtd_{k}\) is the latest possible departure time from \(rc_{k}\). Note that a conflict does not mean that there will be sure collision. However, to make sure there will be no collision on any speed the UAV might take within \([s_{min},s_{max}]\), then there must be no conflict to all of the cubes in \(rc\) for the UAV to be able to travel from \(node_{n}\) to \(node_{s}\). If at least one cube has conflict, then we stop checking for the other cubes in \(rc\). To check for conflict at cube \(rc_{k}\), the red-black tree of \(rc_{k}\) is traversed to check the arrival and departure times of the current reservations at \(rc_{k}\). The current reservations' arrival and departure times must not overlap with \([rta\,\ rtd_{k}\ ]\). To explain this in detail, let \(T\) be the red-black tree of \(rc_{k}\), let \(x\) be a node in \(T\), let \(x_{ta}\) be the arrival time of node \(x\), let \(x_{td}\) be the departure time of node \(x\), let \(x_{l}\) be the left node \(x\), and let \(x_{r}\) be the right node \(x\). We traverse the nodes of \(T\) until there is conflict or until the end of the tree has been reached. First, we set \(x\) to the root of \(T\). If \(rtd_{k}\)and if there will be conflict with other reservations. To determine the cubes and the time the UAV will occupy them, we simulate the movement of the UAV from \(node_{n}\) to \(node_{s}\) every \(\Delta t\) and we get the cubes it will occupy. Recall that UAVs can move at any speed within \([s_{min},\,s_{max}]\). If UAV moves at \(s_{max}\), then it will arrive and depart from the cubes at the earliest time possible. If it moves at \(s_{min}\), then it will arrive and depart at the latest time possible. Thus, we reserve the cubes from the earliest possible arrival time until the latest departure time. Hence, the simulation is done twice. One simulation for the UAV moving at \(s_{max}\) to get the earliest arrival time, and another simulation for the UAV moving at \(s_{min}\) to get the latest departure time. The smoothness of the UAV's movement in the simulation depends on the granularity of \(\Delta t\). We get the change in position of the UAV every \(\Delta t\), thus using smaller \(\Delta t\), results to smoother movement of the UAV in the simulation. Consequently, we cannot capture the exact times on when a UAV arrives and departs at each cube. To deal with the accuracy error in the times the UAV will occupy the cubes, we subtract one \(\Delta t\) from the arrival time to the cube and add one \(\Delta t\) to the departure time from the cube. In addition, to make sure that all cubes that the UAV will pass through are obtained in the simulation when it travels at \(s_{max}\), we assign an upper bound limit to \(\Delta t\) that is  
\[\Delta t\ <\frac{\text{UAV }diameter}{s_{max}}. \tag{28}\]  
We will now explain the implementation of the simulation. Let \(rc\) be the set containing the cubes that the UAV will occupy when it travels from \(node_{n}\) to \(node_{s}\). Let \(rta\) be the set containing the arrival times to each cube in \(rc\) and let \(rtd\) be the set containing the departure times from each cube in \(rc\). Before the start of the simulation, \(rc\), \(rta\), \(rtd\) are initialized as empty sets, then we populate them as we do the simulation. We start the simulation with the UAV's center positioned at \(node_{n}\) and set the simulation time \(t_{s}\) to zero. The UAV will move with distance of \(d_{sim}\) at every \(\Delta t\) where  
\[d_{sim}=\left\{ \begin{array}{l}\Delta t\ s_{max},\ \text{1 st }simulation\\ \Delta t\ s_{min},\ \text{2 nd }simulation\end{array}