# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 6 Scheduling Scheme
### Scheduling a UAV
```
\(scheduleLIAV\) (UAV ID, UAV\({}^{\prime}\)s size, UAV\({}^{\prime}\)s lane, time the request was sent) \(Get\)\(t_{inter}^{lb}\) \(t_{inter}=t_{inter}^{lb}\)  Set \(P\) as empty set \(t_{inter}^{ub}\) as null while\(t_{inter}^{ub}\) is null or \(t_{inter}<\)\(t_{inter}^{ub}\) \(newP\ \gets findfastestpath\) (\(t_{inter}\), UAV\({}^{\prime}\)s size, UAV\({}^{\prime}\)s lane) if\(P\) is null or \(newP\)'s exit time \(<P\)'s exit time then \(P\gets newP\) \(t_{inter}^{ub}=t_{exit}^{P}-t_{ml}\) endif \(t_{inter}=t_{inter}+\Delta t\) endwhile  reserve the cubes the UAV will occupy in \(P\)
```  
**Algorithm 1** Scheduling a UAV  
To explain the value assigned to \(t_{inter}^{ub}\) in Equation (23), let \(t_{inter,\,i}\) be the value of \(t_{inter}\) on the \(i\)th iteration of _findfastestpath_, while let \(t_{path,\,i}\) and \(t_{exit,\,i}\) be the travel time in the intersection and the exit time from the intersection of the path found in \(i\)th iteration, respectively. Then,  
\[t_{exit,\,i}=t_{inter,\,i}+t_{path,\,i}. \tag{24}\]At \(j\)th iteration where \(j>i\), even though the UAV will enter the intersection at a later time than \(t_{inter,\,i}\), the value of \(t_{exit,\,j}\) will still be smaller than \(t_{exit,\,i}\) when \(t_{inter,\,j}+t_{path,\,j}<t_{exit,\,i}\), which is when \(t_{inter,\,j}<t_{exit,\,i}-t_{path,\,j}\). In other words, assuming we found a faster path at the \(i\)th iteration and we set this path as \(P\) and set \(P\)'s time to exit the intersection as \(t_{exit}^{P}\), then a path found in the later iteration \(j\) is faster than \(t_{exit}^{P}\) only when \(t_{inter,\,j}<t_{exit}^{P}-t_{path,\,j}\). We know that the path that passes only across the middle layer is the path with the fastest travel time in the intersection, hence the smallest possible value of \(t_{path,\,j}\) is \(t_{ml}\). Thus, we only need to find path while \(t_{inter}<t_{exit}^{P}-t_{ml}\). For that reason, we set new value to \(t_{inter}^{ub}\) using Equation (23) every time a new faster path is found. * Finding the fastest path in the intersection: _findfastestpath_ Given UAV's size, UAV's entrance lane, and \(t_{inter}\), the function _findfastestpath_, finds the path that will make the UAV exit the intersection the fastest. To start the path finding, we define the graph where a path will be searched based on the UAV's entrance lane (e.g., Figure 5). Then from the graph, we find a path from the start node to the end node with the fastest travel time in the intersection given that the UAV will enter the intersection at \(t_{inter}\). The path finding is done using modified A* search. A* search is a path finding algorithm that finds the path from the start to the end node with the smallest cost (e.g., shortest time or shortest distance). Suppose \(node_{n}\) is the currently visited node in A* search, the next node to be visited is the successor node, \(node_{s}\), with the smallest cost  
\[f(s)\,=g(s)\,+h(s) \tag{25}\]  
where \(g(s)\) is the length of the path from start node to \(node_{s}\) and \(h(s)\) is the Manhattan distance from \(node_{s}\) to end node. In addition, there is an open list and a closed list in A* search to keep track of the visited nodes. The nodes that are yet to be visited are in the open list, while the nodes that were already visited are in the closed list. The nodes in the closed list will not be visited anymore. In our path finding algorithm, even though there is an edge between \(node_{n}\) and \(node_{s}\), a path can be made from \(node_{n}\) to \(node_{s}\) only when the UAV can travel from \(node_{n}\) to \(node_{s}\) without conflict with other reservations. This depends on the time the UAV will arrive at \(node_{n}\) which depends on \(t_{inter}\) and the previously visited nodes from start node to \(node_{n}\). Also, in our approach, even if \(node_{n}\) was already previously visited, it can still be visited later if the nodes in the path from the start node to \(node_{n}\) are different.