# Reservation-Based 3D Intersection Traffic Control System for Autonomous Unmanned Aerial Vehicles
## 6 Scheduling Scheme
### Scheduling a UAV
Hence, we do not need to maintain a closed list since previously visited nodes can still be visited again. Note that the complexity of our algorithm is worse than A*, since a node can be visited more than once. The complexity will be further discussed in Section 7.1. The similarity of our algorithm with the A* is that among the successor nodes of \(node_{n}\), the next node to be visited is the node with minimum value of \(f(s)\,\) as defined in Equation (25). Now we will explain our path finding approach. First, we add the start node to the open list. While open list is not empty, set \(node_{n}\) as the node from the open list with minimum \(f(n)\,\). For each successor \(node_{s}\) of \(node_{n}\), we check if the path from \(node_{n}\) to \(node_{s}\) does not conflict with other UAVs by calling the function _checkPathtoSuccesser_. It will return true if UAV can go from \(node_{n}\) to \(node_{s}\) without conflict. Otherwise, it will return false. Details on _checkPathtoSuccesser_ will be discussed in the next subsection. If there is no conflict, then the UAV can move from \(node_{n}\) to \(node_{s}\), so we assign values to \(h(s),\,g(s),\,f(s),\) and set \(node_{n}\) as the parent of \(node_{s}\). Then, we add \(node_{s}\) to the open list. The nodes are repeatedly visited in this way until the end node is reached or when the open list is empty, which means no path is found. If the end node is reached, we obtain the path from start node to end node by backtracking the parents of the nodes starting from the end node until start node. The returned value \(P\) is the set of nodes from start node to end node. In summary, the pseudocode of the path finding algorithm is in Algorithm 2. * Checking the path between nodes: _checkPathToSuccessor_ Before \(node_{s}\) can be included in the path finding, we need to check if the path from currently visited \(node_{n}\) to \(node_{s}\) does not conflict with other reservations. This means all of the cubes that the UAV will pass through from \(node_{n}\) to \(node_{s}\) must not be reserved by other UAVs at the time the UAV being scheduled will occupy them. Let \(rc\) be the set of cubes that it will occupy when it travels from \(node_{n}\) to \(node_{s}\), let \(rta\) be the set containing the earliest possible arrival times to each cube in \(rc\) and let \(rtd\) be set containing the latest possible departure times from each cube in \(rc\). How to determine the values of \(rc\), \(rta\), and \(rtd\) will be explained in the next subsection. The times in \(rta\) and \(rtd\) are relative from the time the UAV is at \(node_{n}\). Hence, the values in \(rta\) and \(rtd\) must be adjusted by adding the time the UAV will arrive at \(node_{n}\). The time the UAV will arrive at \(node_{n}\) is equal to the time it will enter the intersection, \(t_{intr}\), plus the time it will spend traveling from the start node until \(node_{n}\). The time it will spend traveling from the start node to \(node_{n}\) depends on the length of the path from start node to \(node_{n}\) and the speed of the UAV in the intersection. Recall that UAVs can travel at any speed within \([s_{min},s_{max}]\). If the UAV moves at \(s_{max}\) in the intersection, then it will arrive and depart from \(node_{n}\) at the earliest time possible while if it moves at \(s_{min}\), then it will arrive and depart from \(node_{n}\) at the latest time possible. To guarantee collision avoidance on any speed that UAV might take between the allowed speed range, we reserve the cube to the UAV from the earliest possible time it will arrive at the cube until the latest possible time it will depart the cube. Thus, we get \(t_{n}^{s_{max}}\), the time the UAV will reach \(node_{n}\) if it will travel at \(s_{max}\) in the intersection and we also get \(t_{n}^{s_{min}}\) the time the UAV will reach \(node_{n}\) if it will travel at \(s_{min}\) in the intersection. The value of \(t_{n}^{s_{max}}\) is added to every value in \(rta\), while is \(t_{n}^{s_{min}}\) added to every value in \(rtd\).