# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 6 Scheduling Scheme
### Scheduling a UAV  
When scheduling a UAV, the intersection manager decides the time that the UAV will enter the intersection and the path of the UAV in the intersection. Denote \(t_{e}\) as the earliest time that the UAV can reach the entrance of the intersection, then the UAV can be scheduled to enter the intersection any time from \(t_{e}\) as long as its path in the intersection does not conflict with other UAVs. The paths without conflict depend on the time the UAV will enter  
Figure 8: Summary of the tasks of the intersection manager every \(k\Delta t\). the intersection because the reserved cubes of the other UAVs change over time. Hence, to decide the time that the UAV will enter the intersection, we plan the path of the UAV on different intersection entrance times and choose the path with the fastest intersection exit time. Specifically, we plan the path of the UAV in the intersection given the entrance time to the intersection \(t_{inter}\), where \(t_{inter}^{lb}\leq t_{inter}\leq t_{inter}^{ub}\). \(t_{inter}^{lb}\) is the earliest time that the UAV can enter the intersection and \(t_{inter}^{ub}\) is the latest time that the UAV can enter the intersection such that it is possible to find the fastest path in the intersection. If there is a UAV ahead, then it can enter the intersection only after the UAV ahead has entered the intersection. Otherwise, then it can enter the intersection at the time it will arrive at the entrance of the intersection given that it will not experience delay from the time it sent its request. Thus,  
\[t_{inter}^{lb}=\max(t_{a},\,t_{e}) \tag{22}\]  
where \(t_{a}\) is the reserved departure time of the UAV ahead from the first cube it will occupy in the intersection and \(t_{e}\) is the earliest time that the UAV can reach the entrance of the intersection, assuming that it will not experience delay from the time it sent its request. The pseudocode of the algorithm for scheduling a UAV is in Algorithm 1. In Algorithm 1, we initially set \(t_{inter}\) to \(t_{inter}^{lb}\), set \(t_{inter}^{ub}\) to null and set path \(P\) as an empty set where \(P\) will contain the nodes of the path that the UAV will use. Then, we find a path given that the UAV will enter the intersection at \(t_{inter}\) through the function _findfastestpath_. Details on _findfastestpath_ will be discussed in the next subsection. In the algorithm, we find a path iteratively until \(t_{inter}\) reaches the upper bound \(t_{inter}^{ub}\). The value of \(t_{inter}\) is increased by \(\Delta t\) at each iteration. At each iteration, if a new path \(newP\) is found and the \(newP\)'s exit time is faster than the exit time of current \(P\), set the \(newP\) as \(P\) and assign  
\[t_{inter}^{ub}=t_{exit}^{P}-t_{ml}. \tag{23}\]  
where \(t_{exit}^{P}\) is \(P\)'s time to exit the intersection and \(t_{ml}\) is the travel time in the intersection when the path passes only across the middle layer. After finding the fastest path, we reserve the cubes that the UAV will occupy in \(P\). A UAV is reserved to a cube by inserting an associated node to the red-black tree of the cube.