# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 6 Scheduling Scheme  
Scheduling a UAV means planning for a UAV's path and entrance time in the intersection. There are multiple possible paths that a UAV can take since the intersection is multi-layered. For that reason, the goal is to find a path such that the UAV can exit the intersection the fastest.  
In path finding, a graph represents the environment where the path is searched. A graph consists of a set of nodes and edges that connect them, while a path is a sequence of nodes from the start node to the end node.  
In our scheduling scheme, we find a path in a graph where the nodes are the waypoints of the blocks, and the edges are the movements of the UAV in the intersection. For example, when a UAV is to move left and will enter the left-most lane, the graph where a path is to be searched is shown in Figure 5. The black circles represent the nodes, the blue lines represent the edge from a node to another node in a lower layer, the red lines represent the edge from one node to a node in a higher layer, and the green lines represent the edge from one node to another node in the same layer. The start node is the node at the entrance of the intersection, while the end node is the node at the exit of the intersection. To show the graph more closely, we show its y-z view in Figure 6.  
Figure 4: Possible movements of a UAV in the intersection (**a**) Turn left on the same layer (**b**) Move forward on the same layer (**c**) Turn right on the same layer (**d**) Move down then turn left (**e**) Move down then forward (**f**) Move up then turn left (**g**) Move up then forward.  
Along with path finding, we implement the reservation-based scheduling approach to allow multiple UAVs to be scheduled in the intersection at the same time without collision. In this approach, multiple UAVs can be in the intersection without collision by reserving a space in the intersection to one UAV at a time. Thus, we divide the intersection into cubes to discretize the space in the intersection that will be reserved by the UAVs. Note that in this paper, the cubes are not the same with the blocks and a block can contain multiple cubes.  
To explain how reservation-based scheduling is implemented along with pathfinding, suppose we are finding a path for a UAV, let \(node_{n}\) be the node currently visited and let \(node_{s}\) be the successor node of \(node_{n}\). A successor node of \(node_{n}\) is a node that can be directly visited from \(node_{n}\). Before \(node_{s}\) can be included in the path finding, the cubes that the UAV will pass through when it will travel from \(node_{n}\) to \(node_{s}\) must not be reserved by other UAVs. We will discuss the scheduling scheme in detail in Section 6.3.  
To keep track of which cubes are reserved by which UAVs and at the times they are reserved, we use red-black trees [56] to store the reservations at each cube. Each cube has a red-black tree that contains the reservations on the cube. An example of a red-black tree is shown in Figure 7. One node of the red-black tree represents a reservation of a UAV. A node contains the reserved arrival and departure times of a UAV on that cube with respect to the current simulation time.  
Figure 5: 3D view of graph to be searched for a UAV entering from the left-most entrance lane.  
Figure 6: y-z view of Figure 5.  
If there are multiple UAVs to be scheduled, the UAVs are scheduled in sequence. It is important to note that the sequence of the UAVs has an effect on the UAVs' schedules. For example, we schedule \(\{UAV_{1},\,UAV_{2},\,UAV_{3}\}\) in order. Since \(UAV_{1}\) is scheduled first, the available cubes that \(UAV_{2}\) can reserve depends on the reserved cubes by \(UAV_{1}\). Likewise, the available cubes to \(UAV_{3}\) depends on the reservations of \(UAV_{1}\) and \(UAV_{2}\). Therefore, we implement genetic algorithm to decide the scheduling sequence that will be used. The implementation of genetic algorithm will be discussed in the next subsection.